我怎样才能使这个语法明确无误？

Question

我正在尝试为一种简单的语言编写解析器：

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，这是一种严格的确定性算法，无法处理歧义。

所以我的问题是，我怎样才能使这个语法明确无误？我似乎找不到解决方案。

Answer 1

你不能也不应该。

不要尝试使用语法来进行类型检查。类型是语义的，而不是句法的。词典无法告诉您 ID 是布尔值还是算术（除非您强制使用匈牙利语命名），因此语法只能告诉您 "sometimes"。有时还不够好。

不过没关系。构建语法树后，您可以在语义传递期间轻松进行类型分析。在那之前，表达式就是表达式。

我要做的是摆脱 bool_atom。只需使用一个完整的表达式层次结构，（布尔）表达式在顶部，原子在底部，将 rel_op 放在它自然会去的地方（在 bool_term 中，而不是 bool_atom 中）。但是，这确实以一种方式改变了语法。在现有语法中，表达式

!a < b

表示!(a < b)。这可能是您所期望的，如果是这样，您可以通过一些工作来适应它，但它与我所知道的大多数语言的语义有点不同。在这种情况下，我建议的语法需要使用括号。

我怎样才能使这个语法明确无误？

How can I make this grammar unambiguous?

python

grammar

parsing

ambiguous-grammar

lark-parser