parsing - Bison Shift/Reduce 简单语法冲突

Question

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

%token TYPENAME
%token VARNAME
%token THIS

%%

start:
    Expression
    ;

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

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

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

Expression '.' VARNAME

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

Answer 1

问题是语法只能向前看。因此，当您看到 THIS 然后是 . 时，您是在第 2 行(Expression: THIS '.' VARNAME)还是第 3 行(表达式:表达式 '.' TYPENAME，根据第 1 行进行约简。

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