1

我正在尝试使用柠檬编写一个简单的解析器，用于类似 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

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

4

1 回答 1

1

问题的核心是您希望enterScope()在启动语句块的大括号之后执行。但是，如果大括号后面跟着两个标记VARand :，那么它开始一个对象字面量，而不是一个块。因此，如果没有两个标记的前瞻，就不可能知道是否执行该enterScope动作，并且柠檬不会产生 LR(2) 语法。从这个意义上说，你是正确的，这个问题是无法解决的。但当然有解决方案。

从任何角度（可读性、复杂性、可验证性）来看，最糟糕的解决方案可能是使用通常的 LR(2)→LR(1) 转换创建一个 LR(1) 语法，这将允许您在执行该enterScope();操作的位置调用该操作很明显，已进入范围。这意味着将减少延迟一个令牌。这反过来意味着expr分成两个不相交的非终结符：expr可以以 a 开头的非终结符VAR和不能以 a 开头的非终结符。对于expr可以以 a 开头的那些VAR，您还需要提供一种机制，该机制基本上允许您将 aVAR和其余部分粘合在一起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）。尽管这使词法分析器复杂化（特别是因为您需要识别在变量名和冒号之间出现空格甚至注释的结构），但它使语法更加简单。通过该更改，没有冲突，因为对象字面量必须以 while 开头，VAR_COLON而 expr 只能以 a 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++ 中的类定义的末尾）使程序员受益。

于 2016-08-01T18:25:58.517 回答