Перевод производства грамматики в Parsec

Я пытаюсь преобразовать следующую грамматическую продукцию

callExpr:
    primaryExpr
  | callExpr primaryExpr

к выражению Parsec в Haskell.

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

e = primaryExp
while(true) {
    e2 = primaryExp
    if(e2 failed) break;
    e = CallExpr(e, e2)
}

и моя попытка перевести это на Haskell:

callExpr :: IParser Expr
callExpr = do
    e <- primaryExpr
    return $ callExpr' e
  where
    callExpr' e = do
        e2m <- optionMaybe primaryExpr
        e' <- maybe e (\e2 -> callExpr' (CallExpr e e2)) e2m
        return e'

где primaryExpr имеет тип IParser Expr, а IParser определяется как

type IParser a = ParsecT String () (State SourcePos) a

Однако это дает мне следующую ошибку типа:

Couldn't match type `ParsecT String () (State SourcePos) t0'
              with `Expr'
Expected type: ParsecT String () (State SourcePos) Expr
  Actual type: ParsecT
                 String
                 ()
                 (State SourcePos)
                 (ParsecT String () (State SourcePos) t0)
In a stmt of a 'do' block: return $ callExpr' e
In the expression:
  do { e <- primaryExpr;
       return $ callExpr' e }
In an equation for `callExpr':
    callExpr
      = do { e <- primaryExpr;
             return $ callExpr' e }
      where
          callExpr' e
            = do { e2m <- optionMaybe primaryExpr;
                   .... }

Как исправить ошибку этого типа?


parsing functional-programming haskell parsec left-recursion
person Mathias Vorreiter Pedersen    schedule 25.03.2015    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Используйте chainl1. chainl1 p op анализирует одну или несколько p, разделенных op, левоассоциативным способом. op возвращает бинарную функцию, которая используется для объединения результатов p с обеих сторон в один результат.

Поскольку в вашей грамматике нет разделителя, вы можете использовать chainl1 с op, который просто возвращает функцию объединения:

callExpr :: IParser Expr
callExpr = chainl1 primaryExpr (return CallExpr)

Что касается вашей реализации callExpr, я могу заметить две ошибки.

Во-первых, вы используете return $ callExpr' e, но callExpr' e уже является монадическим значением, так что просто callExpr' e будет правильным.

Во-вторых, в maybe e (\e2 -> callExpr' (CallExpr e e2)) e2m значение по умолчанию e должно быть монадическим (иначе как бы мы могли связать его с e'?), поэтому оно должно быть return e.

person András Kovács    schedule 25.03.2015
comment
Не могли бы вы объяснить, зачем нужен этот комбинатор? Чем это лучше, чем использовать many, а затем сворачивать результат? Я все еще пытаюсь изучить основы синтаксического анализа. - person dfeuer; 25.03.2015
comment
Это, вероятно, несколько быстрее, но я думаю, что это в основном соглашение и сообщение о намерениях. Я думаю, что комбинаторы синтаксических анализаторов должны в целом максимально напоминать чистую нотацию CFG и должны свести к минимуму количество манипуляций с AST постфактум. Читатели нашего кода должны иметь возможность четко видеть грамматику и не быть чрезмерно обремененными операционными деталями. Левая рекурсия — это тот момент, когда мы должны отклониться от абстрактной записи, поэтому мы пытаемся инкапсулировать ее в chainl. - person András Kovács; 25.03.2015