Приоритет оператора и ассоциативность в синтаксическом анализаторе (Haskell)

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

Как я зафиксировал бы это?

6
задан C. A. McCann 25 September 2012 в 15:46
поделиться

2 ответа

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

5
ответ дан 9 December 2019 в 22:33
поделиться

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

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

6
ответ дан 9 December 2019 в 22:33
поделиться
Другие вопросы по тегам:

Похожие вопросы: