消除移/减少由产生式规则的冲突与相同前缀

这里是简化yaac文件：消除移/减少由产生式规则的冲突与相同前缀

%token CONTEXT_ // the corresponding string is "context" 
%token CONTEXTREF_ //"contextref" 
%token IS_   //"is" 
%token ID_L  //"id_l" 
%token ID_L1  //"id_l1" 
%token LIB_ 

%start design_file 

%% 
design_file :design_unit 
       |design_file design_unit 
       ; 

design_unit :context_cl LIB_ 
       |context_decl 
       ; 

context_cl : /* empty */ { } 
       |context_cl context_ref 
       ; 

context_decl :CONTEXT_ ID_L IS_ ';' 
       ; 

context_ref :CONTEXT_ ID_L1 '.' ID_L ';' 
       ;

有2个移/减少冲突。

CONTEXT_ shift, and go to state 1 

CONTEXT_ [reduce using rule 5 (context_cl)]

第5 context_cl : /* empty */ { }。

一般来说，这并不重要，解析器在大多数情况下运行良好。但在一个奇怪的情况下，对源文件进行像以下：

context id_l is ... 
...

分析器不会移位，但减少，因此使用context_ref :CONTEXT_ ID_L1 '.' ID_L ';'解析context id_l is ...，这会导致语法错误。

所以我必须消除冲突。我想他们是由规则context_decl和context_ref在开始时都有CONTEXT_引起的。

为了验证我的猜测，我只是将context_ref :CONTEXT_ ID_L1 '.' ID_L ';'更改为context_ref :CONTEXTREF_ ID_L1 '.' ID_L ';'。然后，没有冲突，并且没有语法错误。

但是，我不能用这种方法代替context_ref。这是标准。

那么，如何通过其他方式避免这两个冲突呢？或者，是否有解决这种冲突的一般方法？

而且，对于移位/减少冲突，解析器会选择减少而不是移位？因为我认为解析器总是会转移到reduce。

来源

2017-05-09 Yuan Wen

我无法重现你描述的问题。我精确地使用了你指定的语法，并精确地得到了你引用的两种状态下的转换/减少冲突。这样所有的检查。我猜测一个词法分析器可能看起来像什么样，并且在调试模式下使用输入'context id_l is;'来运行它;它认可输入没有错误。由于转换/减少冲突的解决，它不会解析'context_id_l1 ...'。这是你的意思吗？如果是这样，请编辑您的问题，我会尽力回答。否则，请[mcve]，强调“完整”和“可验证”。 – rici

语法错误间歇发生。所以我只想消除转移/减少冲突。@ rici –

的基本模式，这引起这场冲突是：

union : x x_rest 
     | y_list y_rest 
y_list: /* empty */ 
     | y_list y

其中x和y都有开始用相同的符号生产。

值得一提的是，问题就会消失，如果y_list是一个或更多的y S，而不是零个或多个：

y_list: y 
     | y_list y

只要x和y是真正区分。（还有一些其他要求，具体取决于剩余的生产，但基本上可以，如果他们有相同的前缀，他们甚至可以是相同的，只要第一个令牌中的延续不同。）

如果你真的需要y_list是潜在空（或两者x和y是潜在空的），你应该做平常空生产消除，这涉及融通可能的空生产出来的语法：

union : x x_rest 
     | y_rest   /* Corresponds to an empty y_list */ 
     | y_list y_rest 
y_list: y    /* As above, this list cannot be empty */ 
     | y_list y

来源

2017-05-10 03:11:36 rici

我不知道在您的“间歇”语法错误的来源 - 书面你的语法，则不能使用像context id_l1 . id_l输入......作为这一转变将导致它尝试解析context_decl不是context_ref。

但是，尽管如此，您的冲突几乎没有与共同的前缀做的事情 - 它真正从/* empty */来了，最简单的解决方法是重构它删除规则：所以现在

design_unit : context_cl LIB_ 
       | LIB_ 
       | context_decl 
       ; 

context_cl : context_ref 
       | context_cl context_ref 
       ;

context_cl是“1或更多”context_ref而不是“0或更多”，并且我们重复了规则以分别具有0个情况。

来源

2017-05-10 03:11:13

消除移/减少由产生式规则的冲突与相同前缀

回答

相关问题