2

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

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

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

4

1 回答 1

2

你不能也不应该。

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

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

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

!a < b

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

于 2020-03-27T21:33:59.173 回答