c - 获得柠檬解析器冲突

Question

我正在尝试使用柠檬为类似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操作，并且 lemon 不会产生 LR(2( 语法。从这个意义上说，你是对的，问题是无法解决的。但当然有解决方案。

从任何角度(可读性、复杂性、可验证性(来看，最糟糕的解决方案可能是使用通常的 LR(2(→LR(1( 变换创建 LR(1( 语法，这将允许您在明确已输入范围时调用enterScope();操作。这意味着将减少延迟一个令牌。这反过来意味着将expr分为两个不相交的非终端：那些可以从VAR开始的expr和那些不能。对于那些可以从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(或其他不相关的标记(开头。

更简单的解决方案是不尝试创建范围继承属性。如果我们综合地进行范围解析，那么问题或多或少会消失：

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(，在块的末尾进行范围界定实际上更方便，甚至作为AST上的解析后漫游。与 C 不同，Javascript 允许在第一次提及后声明局部变量。甚至可以在声明之前使用本地函数。(这与 Python 略有不同，在 Python 中，函数声明是可执行赋值，但范围规则是相似的。

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

还有很多其他的例子。这些范围规则通常通过允许样式选项(例如将成员变量定义放在C++类定义的末尾(使程序员受益，这在 C 语言中是不可能的。