Я пытаюсь расширить синтаксический анализатор с рекурсивным спуском, чтобы обработать новые операторы и заставить их связаться правильно. Первоначально было только четыре оператора (+ - / *), и у них всех был тот же приоритет. Функция, на которую я смотрю, является функцией parseExpRec:
parseExpRec :: Exp -> [Token] -> (Exp, [Token])
parseExpRec e [] = (e, [])
parseExpRec e1 (op : ts) =
let (e2, ts') = parsePrimExp ts in
case op of
T_Power -> parseExpRec (BinOpApp Power e1 e2) ts'
T_Plus -> parseExpRec (BinOpApp Plus e1 e2) ts'
T_Minus -> parseExpRec (BinOpApp Minus e1 e2) ts'
T_Times -> parseExpRec (BinOpApp Times e1 e2) ts'
T_Divide -> parseExpRec (BinOpApp Divide e1 e2) ts'
T_GreaterThan -> parseExpRec (BinOpApp GreaterThan e1 e2) ts'
T_LessThan -> parseExpRec (BinOpApp LessThan e1 e2) ts'
T_GreaterOrEqual -> parseExpRec (BinOpApp GreaterOrEqual e1 e2) ts'
T_LessOrEqual -> parseExpRec (BinOpApp LessOrEqual e1 e2) ts'
T_EqualTo -> parseExpRec (BinOpApp EqualTo e1 e2) ts'
_ -> (e1, op : ts)
Все строки сопоставления с образцом кроме T_Plus, T_Minus, T_Times и T_Divide были добавлены мной (и тем самым имейте связанные маркеры и расширения типа данных Exp). Однако ни один из них, кажется, не связывается правильно. Например, строка "3^4 + 2^3" оценивает к:
Питание BinOpApp (BinOpApp плюс (питание BinOpApp (LitInt 3) (LitInt 4)) (LitInt 2)) (LitInt 3)
Который эквивалентен этому в инфиксной нотации (с включенными скобками):
((3^4) +2) ^3
Как я зафиксировал бы это?
Я думаю, вам стоит взглянуть на существующую библиотеку комбинаторов синтаксического анализатора. Например, parsec , чтобы увидеть, как они реализуют приоритет. В частности, таблица операторов
Я написал статью о непарсинге выражений с использованием предшествования операторов . В приложении к статье есть парсер с операторным предшествованием, написанный на ML, который вы можете легко адаптировать к Haskell. Код можно загрузить со страницы выше.
Хотя в Haskell есть много прекрасных библиотек комбинаторов синтаксического анализа, я никогда не видел ни одной, которая была бы (а) достаточно простой, чтобы я мог легко понять ее, и (б) поддерживала синтаксический разбор с произвольными уровнями предшествования операторов.