获取柠檬解析器冲突

Question

我正在尝试使用 lemon 为类似 javascript 的语言编写一个简单的解析器。我无法解决冲突错误，我怀疑这是一个无法解决的问题。

语法冲突：

{x = 10;}

和

{x:10};

第一个是包含赋值语句的语句块，第二个是定义对象的表达式语句。

解析它们的语法会导致冲突。最小代码如下：

rMod ::= rStmt.

rStmt ::= rStmtList RCURLY. {leaveScope();}
rStmtList ::= rStmtList rStmt.
rStmtList ::= LCURLY. {enterScope();}

rStmt ::= rExpr SEMI.

rExpr ::= rObj.
rObj ::= LCURLY rObjItemList RCURLY.
rObjItemList ::= rObjItemList COMMA rObjItem.
rObjItemList ::= rObjItem.
rObjItem ::= ID COLON rExpr.

rExpr ::= ID.
rExpr ::= NUM.

输出文件显示如下：

State 4:
  (3) rStmtList ::= LCURLY *
      rObj ::= LCURLY * rObjItemList RCURLY
      rObjItemList ::= * rObjItemList COMMA rObjItem
      rObjItemList ::= * rObjItem
      rObjItem ::= * ID COLON rExpr

                        ID shift        8      
                        ID reduce       3       ** Parsing conflict **
              rObjItemList shift        6      
                  rObjItem shift-reduce 8      rObjItemList ::= rObjItem
                 {default} reduce       3      rStmtList ::= LCURLY

如有任何关于我如何解决此问题的建议，我们将不胜感激。谢谢

Answer 1

问题的核心是你想在启动语句块的大括号之后执行enterScope()。但是，如果大括号后跟两个标记 VAR 和 :，那么它开始一个对象文字，而不是一个块。因此，如果没有两个令牌先行，就不可能知道是否执行 enterScope 操作，并且柠檬不会产生 LR(2) 语法。就此而言，您认为问题无法解决是正确的。但当然有解决办法。

从任何角度（可读性、复杂性、可验证性）来看，最糟糕的解决方案可能是使用通常的 LR(2)→LR(1) 转换创建 LR(1) 文法，这将允许您调用 enterScope(); 在明确输入范围时的操作。这意味着延迟减少一个令牌。这反过来意味着将 expr 分成两个不相交的非终结符：那些 expr 可以以 VAR 开头，而那些不能。对于那些可以以 VAR 开头的 expr，您还需要提供一种机制，该机制基本上允许您将 VAR 和 expr 的其余部分粘合在一起；在表达式的情况下，这特别难看（但仍然可能）。目标是能够写：

block(A)       ::= blockPrefix(B) RCURLY .                 { closeScope(); A = B;} 
blockPrefix(A) ::= lcurlyOpen exprNotStartingVAR(E) .      { A = E; }
blockPrefix(A) ::= lcurlyVAR(V) restOfExprStartingVar(R) . { A = makeExpr(V, R); }
blockPrefix(A) ::= blockPrefix(B) SEMI expr(E) .           { A = appendExpr(B, E); }
lcurlyOpen     ::= LCURLY .                                { openScope(); }
lcurlyVAR(A)   ::= LCURLY VAR(V) .                         { openScope(); A = V; }

另一种方法也很丑陋，但在这种特殊情况下可能不那么丑陋，它是将后跟冒号的变量名识别为单个词法标记 (VAR_COLON)。尽管这会使词法分析器变得复杂（特别是因为您需要识别变量名和冒号之间出现空格甚至注释的结构），但它使语法更加简单。有了这个变化，就没有冲突了，因为对象文字必须以 VAR_COLON 开头，而 expr 只能以 VAR （或其他不相关的标记）开头。

一个更简单的解决方案是不要尝试创建 scope inherited attribute。如果我们综合进行范围解析，那么问题或多或少会消失：

stmt       ::= expr SEMI | block .
stmtList   ::= stmt .
stmtList   ::= stmtList stmt .
block(A)   ::= LCURLY stmtList(B) RCURLY . { A = applyScope(newScope(), B); }
objLiteral ::= LCURLY itemList RCURLY .
objLiteral ::= LCURLY RCURLY .
itemList   ::= item .
itemList   ::= itemList COMMA item .
item       ::= VAR COLON expr .
expr       ::= VAR .
expr       ::= objLiteral .
...

该语法没有冲突，但它可能会从根本上改变您处理范围的方式，因为它需要在块完成后对变量名进行范围限定，而不是在解析过程中内联进行。

然而，我认为对于大多数语言（包括 Javascript）来说，在块的末尾进行范围界定实际上更方便，甚至作为 post-parse walk在 AST 之上。 Javascript 与 C 不同，它允许局部变量在首次提及后声明。局部函数甚至可以在声明之前使用。（这与 Python 略有不同，其中函数声明是可执行赋值，但作用域规则相似。）

作为另一个例子，C++ 允许 class 成员在 class 声明内的任何位置声明，即使该成员已经在另一个 class 成员函数中被提及。

还有很多其他的例子。这些作用域规则通常通过允许风格选项（例如在 C++ 中将成员变量定义放在 class 定义的末尾）而使程序员受益，这在 C 中是不可能的。

获取柠檬解析器冲突

Getting lemon parser conflict

c

parsing

lemon