Как я могу сделать эту грамматику однозначной? - PullRequest
Новая
       85

Как я могу сделать эту грамматику однозначной?

2 голосов
/ 27 марта 2020

Я пытаюсь написать парсер для простого языка: 

parser = Lark("""
    ?start: arithmetic_expr | boolean_expr

    // relational operation
    ?rel_op : arithmetic_expr ("<" | ">" | "==" | "!=") arithmetic_expr 

    // boolean expression
    ?boolean_expr: bool_term
            | boolean_expr "or" bool_term
    ?bool_term: bool_atom
                | bool_term "and" bool_atom
    ?bool_atom: "true"
                | "false"
                | "!" bool_atom
                | rel_op
                | ID
                | "(" boolean_expr ")"

    // arithmetic expression
    ?arithmetic_expr: product
        | arithmetic_expr "+" product
        | arithmetic_expr "-" product
    ?product: atom
        | product "*" atom
        | product "/" atom
    ?atom: NUMBER
            | "-" atom
            | ID
            | "(" arithmetic_expr ")"


    %import common.CNAME -> ID
    %import common.NUMBER

    """, parser='lalr', start='start')

Когда я его запускаю, я получаю следующую ошибку: 

lark.exceptions.GrammarError: Reduce/Reduce collision in Terminal('RPAR') between the following rules: 
                - <bool_atom : ID>
                - <atom : ID>

Я понимаю, что это Это происходит потому, что если мы представим, что анализатор был построен без ошибки, а затем записали parser.parse('foo'), то и arithmetic_expr, и boolean_expr были бы "правильными" производными. Кроме того, как вы можете видеть, я использую LALR, который является строго детерминированным c алгоритмом и не может обрабатывать неоднозначности.

Итак, мой вопрос, как я могу сделать эту грамматику однозначной? Я не могу найти решение.

1 Ответ

2 голосов
/ 28 марта 2020

Вы не можете и не должны.

Не пытайтесь использовать грамматику для проверки типов. Типы semanti c, а не syntacti c. Лексикон не может сказать вам, является ли ID логическим или арифметическим c (если вы не используете венгерское именование), поэтому грамматика может сказать только «иногда». И иногда не достаточно хорош.

Но это не имеет значения. Вы можете легко выполнить анализ типов во время проходов semanti c после построения дерева синтаксиса. До тех пор выражение является выражением.

Что бы я сделал, это избавился бы от bool_atom. Просто используйте полную иерархию выражений с (логическим) выражением вверху и атомом внизу, поместив rel_op там, где он, естественно, будет go (в bool_term вместо bool_atom). Однако это меняет грамматику одним способом. В существующей грамматике выражение 

!a < b

означает !(a < b). Это может быть то, что вы ожидали, и если это так, вы можете выполнить это с небольшим количеством работы, но это немного отличается от семантики большинства языков, которые я знаю. В этом случае моя предложенная грамматика потребует использования скобок.

...