如何使用可选前缀 LL(2) 创建语法？

Question

考虑这个语法

start: lvalue ASSIGN expr SEMICOLON | expr SEMICOLON;
expr: OPENPAREN expr CLOSEPAREN | literal | lvalue;
lvalue: ID lvalue_tail ;
lvalue_tail: OPENBRACK expr CLOSEBRACK | ;
ID : [a-zA-Z]+[a-zA-Z0-9_]* ;

所以 lvalue 是 expr，但 expr 可能不是 lvalue。
使用此输入 var[10]，语法将需要 4 个前瞻（ID、openbrack、literal、closebrack）才能确定它应该选择 lvalue expr 还是 expr。
我如何制作这样的语法 LL(2)？
注意：expr这里是简化的，大写字母的符号是终端。

Answer 1

与仅使用 LALR 解析器生成器相比，我不确定通过减少此语法的 LL 前瞻性可以达到什么目的，因为未修改的语法是 LALR(1)。

然而，它可以通过将 expr 分成 lvalue 和我们可能称之为 rvalue 的方式来完成——即，在表达式的左侧不可用的表达式赋值运算符。这可能会产生类似

的东西

start: lvalue start_tail | rvalue SEMICOLON;
start_tail: ASSIGN expr SEMICOLON | SEMICOLON;
expr: lvalue | rvalue;
rvalue: OPENPAREN expr CLOSEPAREN | literal;
lvalue: ID lvalue_tail ;
lvalue_tail: OPENBRACK expr CLOSEBRACK | ;
ID : [a-zA-Z]+[a-zA-Z0-9_]* ;

This grammar is LL(1) 除了是 LL(2)。但是，将其扩展以包含更多语言可能会很棘手。

（如果上面的link rots，它只是指向一个在线工具验证语法是LL（1）。）

如何使用可选前缀 LL(2) 创建语法？

How do I make grammar with optional prefix LL(2)?

compiler-construction

grammar

context-free-grammar