Shift/Reduce 在 Java 杯的状态中发现冲突

Question

我正在尝试在 java 杯中编写解析，但我遇到了冲突

start with prog;

prog ::= header;
header ::= t1 t3 t2 | t3 t1 t2 | t2 t3 t1 | t1 t2 t3 | t2 t1 t3 | t3 t2 t1;

t1 ::= TOK1;
t2 ::= TOK2 | TOK2 TOK2 ;
t3 ::= | t3 TOK3;

我遇到了这个错误；

Warning : *** Shift/Reduce conflict found in state #3
  between t3 ::= (*) 
  and     t1 ::= (*) TOK1 
  under symbol TOK1
  Resolved in favor of shifting.

谁能解释一下我错在哪里？

Answer 1

t3 可以为空（它匹配零个或多个 TOK3 标记的序列）。这会产生歧义，因为没有 TOK3 的输入可以匹配多个 header.

的备选方案

尽管所有的可能性都归约到同一个非终结符，但这是模棱两可的，因为每个产生式都有不同的归约动作，而语法无法知道要执行哪个动作。如冲突报告中所述，解析器将移动而不是减少。例如，如果第一个输入是 TOK1，解析器可以假定输入将匹配 t1 t2 t3 或 t1 t3 t2，在这种情况下，TOK3 的序列将稍后出现，或者它可以假设输入是 t3 t1 t2 和一个空的 t3，其中它必须在继续解析之前对一个空的 t3 执行操作。选择移位意味着拒绝输入开头为空t3的可能性。

在这种特殊情况下，默认班次可能不会造成问题。这意味着仅包含 TOK1 和 TOK2 的输入将始终在末尾解析为空 t3，但如果没问题，那么您可以随意忽略警告。

所谓的“可空非终端”通常正是这种形式的移位减少冲突的原因。避免它们通常很有用；与其创建可能为空的列表，更好的解决方案通常是使列表非终结符匹配一个或多个元素，然后通过添加列表不存在的产生式使其成为可选的。换句话说，而不是

header: t3 t1 t2
t3    :  
      | t3 TOK3

使用

header: t3 t1 t2
      |    t1 t2
t3    : TOK3
      | t3 TOK3

该解决方案可能会导致不希望出现的代码重复，但它是解决由于可空非终端引起的移位归约冲突的简单方法。

Shift/Reduce 在 Java 杯的状态中发现冲突

Shift/Reduce conflict found in state in Java Cup

java

grammar

parsing

cup