Приоритет оператора и ассоциативность в парсере (Haskell)

Question

Я пытаюсь расширить синтаксический анализатор с рекурсивным спуском, чтобы обрабатывать новые операторы и правильно связывать их. Первоначально было только четыре оператора (+ - / *), и все они имели одинаковый приоритет. Я смотрю на функцию 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 Plus (Питание BinOpApp (LitInt 3) (LitInt 4)) (LitInt 2)) (LitInt 3)

Что эквивалентно этому в инфиксной записи (включая скобки):

((3 ^ 4) + 2) ^ 3

Как бы это исправить?

Answer 1

Я написал статью о разборе выражений, используя приоритет оператора . В приложении к статье имеется синтаксический анализатор операторного приоритета, написанный на ML, который вы можете легко адаптировать к Haskell. Код можно загрузить со страницы выше.

Хотя в Haskell есть много прекрасных библиотек синтаксических комбинаторов, я никогда не видел ни одной, которая была бы (а) достаточно простой для меня, чтобы легко понять, и (б) поддерживала синтаксический анализ операторов с произвольными уровнями приоритета.

Answer 2

Думаю, вам стоит взглянуть на существующую библиотеку синтаксических анализаторов. Например, parsec , чтобы увидеть, как они реализуют приоритет. В частности, таблица операторов