Разбор выражений внутри арифметических выражений

Question

Я хотел бы разобрать арифметические выражения.

Вот мой текущий парсер:

data AExpr
    = ExprAsAExpr Expr
    | IntConst Integer
    | Neg AExpr
    | ABinary ABinOp AExpr AExpr
    deriving (Show, Eq)

aExpr :: Parser AExpr
aExpr = makeExprParser aTerm aOperators

aTerm :: Parser AExpr
aTerm
    =   parens aExpr
    <|> IntConst <$> integerParser

aOperators :: [[Operator Parser AExpr]]
aOperators =
    [ [Prefix (Neg <$ symbol "-") ]
    , [ InfixL (ABinary Multiply <$ symbol "*")
      , InfixL (ABinary Divide   <$ symbol "/") ]
    , [ InfixL (ABinary Add      <$ symbol "+")
      , InfixL (ABinary Subtract <$ symbol "-") ]
    ]

Используя это, я могу правильно разобрать это:

1 + 2

Генерация AST, как это.

(ABinary Add (IntConst 1) (IntConst 2))

Еще одна вещь, которую я могу разобрать, это общие выражения. Это могут быть такие вещи, как переменные, вызовы методов, троичные и т. Д.

Например

Идентификаторы:

varName

Это создает:

(Identifier (Name "varName"))

Вызов метода:

methodCall()

Это создает:

(MethodCall (Name "methodCall") (BlockExpr []))

Вот пример для разбора общих выражений.

expressionParser :: Parser Expr
expressionParser
    =   methodCallParser
    <|> identifierParser

Это прекрасно работает, но я также хотел бы проанализировать арифметические выражения в этом.

expressionParser :: Parser Expr
expressionParser
    =   newClassInstanceParser
    <|> methodCallParser
    <|> AExprAsExpr <$> aExpr
    <|> identifierParser

Это означает использование expressionParser Теперь я могу анализировать все различные выражения, включая арифметические выражения. Если это арифметическое выражение, оно помещается в AExprAsExpr,

проблема

Я хотел бы разобрать арифметические выражения, содержащие другие выражения.

Например

x + y

Для этого моей первоначальной мыслью было изменить арифметический синтаксический анализатор, чтобы он также анализировал выражения.

data AExpr
    = ExprAsAExpr Expr
    | IntConst Integer
    | Neg AExpr
    | ABinary ABinOp AExpr AExpr
    deriving (Show, Eq)

aExpr :: Parser AExpr
aExpr = makeExprParser aTerm aOperators

aTerm :: Parser AExpr
aTerm
    =   parens aExpr
    <|> IntConst <$> integerParser
    <|> ExprAsAExpr <$> expressionParser

aOperators :: [[Operator Parser AExpr]]
aOperators =
    [ [Prefix (Neg <$ symbol "-") ]
    , [ InfixL (ABinary Multiply <$ symbol "*")
      , InfixL (ABinary Divide   <$ symbol "/") ]
    , [ InfixL (ABinary Add      <$ symbol "+")
      , InfixL (ABinary Subtract <$ symbol "-") ]
    ]

Проблема в том, что существует рекурсивный цикл aTerm вызывает парсер выражений, парсер выражений вызывает aExpr, Это приводит к бесконечному циклу. Существует также проблема, что все identifiers теперь будет завернут в AExprAsExpr,

Каков правильный метод парсинга выражений внутри арифметических выражений?

Answer 1

РЕДАКТИРОВАТЬ Я только сейчас понял, что вы используете makeExpressionParser и мой ответ не относится к этому. В любом случае, может быть, этот ответ все еще полезен?

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

expr ::= addExpr
addExpr ::= mulExpr '+' addExpr
          | mulExpr '-' addExpr
          | mulExpr
mulExpr ::= term '*' mulExpr
          | term '/' mulExpr
          | term
term ::= '(' expr ')'
       | number

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

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

1 - 2 - 3 - 4

будет проанализирован как

1 - (2 - (3 - 4))

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

subExpr = foldl1 (-) <$> many1 mulExpr

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

addExpr = chainl1 mulExpr oper
    where
    oper = choice [ (+) <$ symbol '+'
                  , (-) <$ symbol '-'
                  ]

Я люблю писать парсеры в Хаскеле. Удачи!