代码之家 › 专栏 › 技术社区 › Flavius

lalr(1)函数参数的空列表

lemon lalr grammar parsing

Flavius · 技术社区 · 16 年前

我有一个简单的lalr(1)语法,但我遇到了一个问题。

start ::= spec.
spec ::= MOD STRING top_stmt.
spec ::= top_stmt.
top_stmt ::= stmt.
top_stmt ::= conditional.
stmt ::= expr.
stmt ::= assignment.
conditional ::= IF stmt_list.
expr ::= retval.
expr ::= NOT retval.
retval ::= access.
retval ::= invoke.
access ::= ns_identifier OBJECT_OPERATOR property_chain.
access ::= ns_identifier.
ns_identifier ::= identifier.
ns_identifier ::= ns_identifier NS_SEPARATOR identifier.
ns_identifier ::=.
property_chain ::= property_chain OBJECT_OPERATOR identifier.
property_chain ::= identifier.
identifier ::= VARIABLE.
identifier ::= STRING.
assignment ::= access ASSIGN expr. [ASSIGN]
stmt_list ::= stmt.
stmt_list ::= stmt_list COMMA stmt. [COMMA]
invoke ::= access LPAREN empty_stmt_list RPAREN.
empty_stmt_list ::=.
empty_stmt_list ::= stmt.
empty_stmt_list ::= empty_stmt_list COMMA stmt. [COMMA]

点标记规则的结尾,方括号之间的端子具有指定的关联性:指定为右关联,逗号为左关联。

但是 lemon 说它不能减少“empty_stmt_list::=”规则,因为它没有连接到开始符号。我敢打赌是:-)

“invoke”还有一个解析冲突,当空的语句列表确实是一个empy语句列表时,它不能决定rparen和comma。

我试图实现的是能够解析没有(void)参数的函数调用。

其他一切都按预期进行。

谢谢

编辑 :我已经编辑了我的原始文章并发布了整个精简语法。

2 回复 | 直到 13 年前

Matthew Slattery 16 年前

你的第一个问题是我认为这一点不符合你的要求:

invoke ::= access LPAREN empty_stmt_list RPAREN.
empty_stmt_list ::=.
empty_stmt_list ::= stmt.
empty_stmt_list ::= empty_stmt_list COMMA stmt. [COMMA]

这个 invoke 生产将匹配 access LPAREN COMMA stmt RPAREN ,我认为这是不可取的(这就是lparen/comma冲突的来源)。

你可以这样做来解决这个问题,这样可以利用你现有的 stmt_list 规则:

invoke ::= access LPAREN maybe_empty_stmt_list RPAREN.
maybe_empty_stmt_list ::= .
maybe_empty_stmt_list ::= stmt_list.

仍然报告有冲突(但现在只有1个)并且仍然抱怨 maybe_empty_stmt_list ::=. 不能减少。所以,在xxx.out文件中查看它是什么:

State 2:
...
     (16) ns_identifier ::= *
...
     (25) maybe_empty_stmt_list ::= *
...
                        RPAREN reduce 25  ** Parsing conflict **
....
                     {default} reduce 16

…看来问题出在 ns_identifier ::=. 规则。回顾相关作品,不难发现 ns_identifier 可以简化为 小精灵 (通过 NS U标识符 -gt; access -gt; retval -gt; expr -gt; stmt -gt; 小精灵 )

这就解释了冲突;事实上 ns_标识符:=。 在这种情况下,规则更受欢迎,因为它出现在语法的前面(请参阅 documentation 解释为什么它抱怨 可能是空的。 规则永远不能减少。

artificialidiot 16 年前

您可以尝试为lparen/comma添加优先规则,并检查它是否影响其他地方的语义。