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

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

0 голосов
/ 09 мая 2018

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

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

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))

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

* 1017 Е.Г. *

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

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.

Проблема

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

1052 * Е.Г. * 

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.

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

1 Ответ

0 голосов
/ 10 мая 2018

РЕДАКТИРОВАТЬ Я только сейчас понял, что вы используете 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 '-'
                  ]

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

...