Создание attoparsec парсеров рекурсивных - PullRequest
Новая
       9

Создание attoparsec парсеров рекурсивных

4 голосов
/ 19 июня 2011

Я кодирую синтаксический анализатор attoparsec и использую шаблон, в котором я хочу превратить парсеры в рекурсивные парсеры (рекурсивно комбинируя их с оператором монадного связывания >> =).

Итак, я создалфункция для преобразования анализатора в рекурсивный анализатор следующим образом: 

recursiveParser :: (a -> A.Parser a) -> a -> A.Parser a
recursiveParser parser a = (parser a >>= recursiveParser parser) <|> return a

Что полезно, если у вас есть рекурсивный тип данных, такой как 

data Expression = ConsExpr Expression Expression | EmptyExpr

parseRHS :: Expression -> Parser Expression
parseRHS e = ConsExpr e <$> parseFoo

parseExpression :: Parser Expression
parseExpression = parseLHS >>= recursiveParser parseRHS
  where parseLHS = parseRHS EmptyExpr

Есть ли более идиоматическое решение?Похоже, что recursiveParser должно быть чем-то вроде сгиба ... Я также видел sepBy в документах, но этот метод мне больше подходит для моего приложения.

РЕДАКТИРОВАТЬ: О, на самом деле теперь, когда я думаю об этом, на самом деле должно быть что-то похожее на fix ... Не знаю, как я об этом забыл.

РЕДАКТИРОВАТЬ 2: Ротсор делаетХороший вопрос с его альтернативой для моего примера, но я боюсь, что мой AST на самом деле немного сложнее, чем это.На самом деле это выглядит примерно так (хотя это все еще упрощено) 

data Segment = Choice1 Expression
             | Choice2 Expression
data Expression = ConsExpr Segment Expression 
                | Token String
                | EmptyExpr

, где строка a -> b заключена в скобки справа и c:d в скобках слева, а : связывается более плотно, чем->.

Т.е. a -> b оценивается в 

(ConsExpr (Choice1 (Token "a")) (Token "b"))

, а c:d оценивается в 

(ConsExpr (Choice2 (Token "d")) (Token "c"))

Полагаю, я мог бы использовать foldl дляодин и foldr для другого, но там все еще больше сложности.Обратите внимание, что это немного странно рекурсивно, поэтому "a:b:c -> e:f -> :g:h ->" на самом деле является допустимой строкой, а "-> a" и "b:" - нет.В итоге fix показалось мне проще.Я переименовал рекурсивный метод так: 

fixParser :: (a -> A.Parser a) -> a -> A.Parser a
fixParser parser a = (parser a >>= fixParser parser) <|> pure a

Спасибо.

1 Ответ

4 голосов
/ 20 июня 2011

Почему бы просто не разобрать список и сложить его во что угодно позже?Может быть, я что-то упускаю, но для меня это выглядит более естественным: 

consChain :: [Expression] -> Expression
consChain = foldl ConsExpr EmptyExpr

parseExpression :: Parser Expression
parseExpression = consChain <$> many1 parseFoo

И это тоже короче.

Как видите, consChain теперь не зависит от анализа и может бытьполезно где-то еще.Кроме того, если вы выделяете свертывание результатов, несколько неинтуитивный рекурсивный анализ в этом случае упрощается до many или many1.

Возможно, вы захотите взглянуть и на то, как реализован many.: 

many :: (Alternative f) => f a -> f [a]
many v = many_v
    where many_v = some_v <|> pure []
          some_v = (:) <$> v <*> many_v

Это имеет много общего с вашим recursiveParser:

  • some_v похоже на parser a >>= recursiveParser parser
  • many_v являетсяпохоже на recursiveParser parser

Вы можете спросить, почему я назвал вашу рекурсивную функцию синтаксического анализатора неинтуитивной.Это связано с тем, что этот шаблон позволяет аргументу синтаксического анализатора влиять на поведение при разборе (a -> A.Parser a, помните?), Что может быть полезно, но не очевидно (я пока не вижу варианта использования для этого).Тот факт, что ваш пример не использует эту функцию, делает его излишним.

...