c - 获取柠檬解析器冲突

Question

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

冲突发生在以下语法之间:

{x = 10;}

和

{x:10};

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

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

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

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

从任何角度(可读性、复杂性、可验证性)来看，最糟糕的解决方案可能是使用通常的 LR(2)→LR(1) 转换创建 LR(1) 文法，这将允许您调用 enterScope(); 在明确输入范围时的操作。这意味着延迟减少一个 token 。这反过来意味着将 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(或其他不相关的标记)开头。

一个更简单的解决方案是不尝试创建范围 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 .
...

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

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

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

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