python - 我怎样才能使这个语法明确？

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是 bool 值或算术(除非你强制使用匈牙利命名)​​，所以语法只能告诉“有时”。有时还不够好。

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

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

!a < b

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