2

我正在为我设计的一种语言构建一个解析器，其中类型名称以大写字母开头，变量名称以小写字母开头，这样词法分析器就可以区分并提供不同的标记。此外，词法分析器（它是一种 OOP 语言）可以识别字符串“this”并作为单独的标记传递。最后，数据成员只能在 'this' 对象上访问，所以我这样构建了语法：

%token TYPENAME
%token VARNAME
%token THIS

%%

start:
    Expression
    ;

Expression:
    THIS
    | THIS '.' VARNAME
    | Expression '.' TYPENAME
    ;
%%

Expression 的第一条规则允许用户将“this”作为值传递（例如，从方法返回它或传递给方法调用）。第二个是用于访问“this”上的数据。第三条规则用于调用方法，但是我删除了括号和参数，因为它们与问题无关。最初的语法显然比这大得多，但是这是产生相同错误的最小部分（1 Shift/Reduce 冲突） - 我将其隔离到自己的解析器文件中并验证了这一点，因此错误与任何错误无关其他符号。

据我所知，这里给出的语法是明确的，因此不应该产生任何错误。如果您删除三个规则中的任何一个或将第二个规则更改为

Expression '.' VARNAME

没有冲突。无论如何，我可能需要有人明确说明为什么会发生这种冲突以及如何解决它。

4

2 回答 2

4

问题是语法只能向前看。因此，当您看到 aTHIS然后 a时.，您是在第 2 行（Expression: THIS '.' VARNAME）还是第 3 行（Expression: Expression '.' TYPENAME通过根据第 1 行的缩减）。

语法可以简化THIS.为Expression.然后查找 aTYPENAME或将其转换为THIS.并查找 a VARNAME，但它必须决定何时到达..

于 2010-07-30T18:50:36.200 回答
3

我尽量避免使用 y.output，但有时它确实有帮助。我查看了它生成的文件并看到了。

state 1

    2 Expression: THIS.  [$end, '.']
    3           | THIS . '.' VARNAME

    '.'  shift, and go to state 4

    '.'       [reduce using rule 2 (Expression)]
    $default  reduce using rule 2 (Expression)

基本上它是说它看到'。并且可以减少或可以转移。减少有时让我感到不安，因为它们很难被罚款。这种转变是规则 3 并且很明显（但输出没有提到规则 #）。减少它看到的地方是'。在这种情况下是行

| Expression '.' TYPENAME

当它进入 Expression 时，它会查看下一个字母（'.'）并进入。现在它看到了THIS |，所以当它到达该语句的末尾时，它期望 '.' 当它离开或出现错误时。但是它看到了这个'。而它在 this 和 '.' 之间 （因此输出文件中的点）并且它可以减少规则，因此存在路径冲突。我相信您可以使用%glr-parser它来尝试两者，但是您遇到的冲突越多，您获得意外输出或歧义错误的可能性就越大。我过去有模棱两可的错误。处理它们很烦人，尤其是如果您不记得是什么规则导致或影响了它们。建议避免冲突。

在尝试使用野牛之前，我强烈推荐这本书。

我想不出一个“好”的解决方案，但这不会产生冲突

start:
    ExpressionLoop
    ;

ExpressionLoop:
      Expression
    | ExpressionLoop ';' Expression
    ;
Expression:
      rval 
    | rval '.' TYPENAME
    | THIS //trick is moving this AWAY so it doesnt reduce
rval:

    THIS '.' VARNAME

或者，您可以稍后通过向规则添加更多内容来减少它，这样它就不会立即减少，或者在之前或之后添加一个标记以明确采用或失败的路径（请记住，在减少任何路径之前它必须知道）

start:
    ExpressionLoop
    ;

ExpressionLoop:
      Expression
    | ExpressionLoop ';' Expression
    ;
Expression:
      rval 
    | rval '.' TYPENAME
rval:
      THIS '@'
    | THIS '.' VARNAME
%%

-edit- 如果我想做但我不能这样做func param，type varname因为根据词法分析器函数的类型是 Var（即 A-Za-z09_）以及类型。param 和 varname 也是 var，所以这会导致我减少/减少冲突。你不能把它们写成它们的样子，只能写它们的样子。所以写的时候要记住这一点。您必须编写一个标记来区分两者或将其编写为两者之一，但在代码中编写附加逻辑（规则右侧 { } 中的部分）以检查它是否是 funcname 或一个类型并处理这两种情况。

于 2010-07-30T20:42:25.490 回答