时间戳

首页 > 解决方案 > 如何使用可选前缀 LL(2) 制作语法？

compiler-construction - 如何使用可选前缀 LL(2) 制作语法？

问题描述

考虑这个语法

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_]* ;

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

标签： compiler-constructiongrammarcontext-free-grammar

解决方案

与仅使用 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_]* ;

该文法除了是 LL(2) 之外，还是 LL(1)。但是，将其扩展以包含更多语言可能会被证明是棘手的。

（如果上面的链接失效，它只是指向一个在线工具，它验证了语法是 LL(1)。）

推荐阅读