Мегапарсек: не удалось разобрать арифметическую строку

Question

Я работаю над небольшим парсером, использующим Мегапарсек, и пытаюсь разобрать арифметику.

-- Arithmetic expressions
data Aexp = N Num 
            | V Var 
            | Mult Aexp Aexp
            | Add Aexp Aexp 
            | Sub Aexp Aexp 
             deriving (Show, Eq, Read)


arithParser :: Parser Aexp
arithParser = V <$> strParser
            <|> N <$> numParser
            <|> Mult <$> arithParser <* tok "*" <*> arithParser
--boolParser :: Parser Bexp


strParser :: Parser Var
strParser = tok "\"" *> some (noneOf ("\n\r\"=[]{},:")) <* tok "\""

numParser :: Parser Num
numParser = (some (oneOf ['0' .. '9']) >>= return . read) <* whitespace

Если я запускаю команду Parse arithParser "5*5" "5*5" это просто возвращает Right (N 5)куда он должен вернуться Mult(N 5) (N 5), Из-за приоритета в arithParser. Но если я изменю порядок, то, похоже, он заходит в бесконечный цикл и вылетает.

Не уверен, что я делаю не так, любая помощь будет оценена.

Answer 1

Парсек пытается левый вариант <|> прежде чем он попробует правильный. Если левая альтернатива будет успешной, она не будет беспокоить правую. Так что в этом случае, когда кормили вход 5*5 Процесс Parsec выглядит следующим образом:

1. Пытаться V <$> strParser, strParser начинается с tok "\"", но входная строка не начинается с '"' так strParser выходит из строя.
2. Пытаться N <$> numParser, numParser успешно разбирает число 5, поэтому Parsec просто возвращает N 5,
3. Готово! Не нужно пробовать третий вариант.

---

Таким образом, мы можем попытаться исправить этот парсер, переместив Mult вариант до верха, завернутый в try так что он может вернуться и попробовать numParser или же strParser если вход оказывается не умножением.

arithParser :: Parser Aexp
arithParser = try (Mult <$> arithParser <* tok "*" <*> arithParser)
            <|> N <$> numParser
            <|> V <$> strParser

У этого парсера есть другая, более тонкая проблема. Давайте пройдемся по ступеням, как указано выше.

1. Пытаться try (Mult <$> arithParser <* tok "*" <*> arithParser), Этот парсер начинается с arithParser так рекурсивно звони arithParser,
2. Пытаться try (Mult <$> arithParser <* tok "*" <*> arithParser), Этот парсер начинается с arithParser так рекурсивно звони arithParser,
3. Пытаться try (Mult <$> arithParser <* tok "*" <*> arithParser), Этот парсер начинается с arithParser так рекурсивно звони arithParser,
4. ...

Это бесконечный цикл. Parsec не может обработать леворекурсивные грамматики. Вы должны спроектировать свой синтаксический анализатор так, чтобы он использовал по крайней мере один токен перед рекурсивным вызовом. Один из распространенных способов сделать это - "сгладить" вашу грамматику:

expr, term :: Parser AExp
expr = do
    n <- term
    rest <- optional $ tok "*" *> expr
    return $ maybe n (Mult n) rest
term = N <$> numParser
    <|> V <$> strParser
    <|> parenthesised expr

parenthesised = between (char '(') (char ')')

Здесь я разделил парсер на один, который разбирает произвольный expr - а term необязательно сопровождается символом умножения и умножением expr - и тот, который анализирует один term s - числа, строки и выражения в скобках. Рекурсивные вызовы expr все в порядке - один внутри expr происходит только после того, как вы проанализировали term (который всегда потребляет вход) и тот, что внутри term происходит только после того, как вы проанализировали открывающую скобку.

Обратите внимание, что expr имеет структуру, подобную списку: она анализирует одну вещь, за которой, возможно, следуют многие вещи. В общем, вы должны думать о парсерах, потребляющих линейный входной поток входных токенов, поэтому неудивительно, что парсеры в форме списка имеют тенденцию быть более эффективными, чем древовидные.

Text.Megaparsec.Expr Модуль содержит функции, которые упаковывают этот шаблон и анализируют выражения с произвольными правилами приоритета и исправления.

expr = makeExprParser term [[InfixR $ tok "*" $> Mult]]

Answer 2

Типы лгут вам: когда вы определяете рекурсивный парсер p вы не можете использовать p сама где хочешь! Вы должны сначала скопировать часть ввода, чтобы гарантировать, что вы делаете успехи. Иначе Хаскелл действительно с радостью войдет в бесконечный цикл.

Как правило, эта проблема решается путем определения различных "ярусов" выражений и предоставления только "более простых" или "более сложных" скобок в лево-рекурсивных позициях (поскольку сопоставление с открытыми скобками заставляет вас пробираться через часть строка ввода).

Например, грамматика для ваших выражений будет преобразована (от самой простой до самой сложной):

<Literal> ::= [0-9]+
<Var>     ::= [a-zA-Z]+
<Base>    ::= '(' <Expr> ')' | <Var> | <Literal>
<Factor>  ::= <Base> | <Base> '*' <Factor>
<Expr>    ::= <Factor> | <Factor> '+' <Expr> | <Factor> '-' <Expr>

Вот где сияет тотальный язык: поскольку типы должны быть абсолютно честными, когда дело доходит до завершения, становится буквально невозможным написать эти плохо ведущие себя рекурсивные парсеры. Проверка типов говорит вам, что вам нужно найти другой способ распознавания терминов вашего языка.

Например, исправление комбинатора fixpoint, которое я использую в своей библиотеке комбинаторов общего синтаксического анализа, не имеет типа (a -> a) -> a а точнее (игнорируя смешные скобки) (□ a → a) → a что точно мешает вам использовать рекурсивный вызов, прежде чем вы добились определенного прогресса. Вы все еще можете написать парсер для Expr, но средство проверки типов здесь, чтобы предупредить вас, когда вы делаете незаконный ход.