时间戳

首页 > 解决方案 > 在 Java Cup 中的状态中发现 Shift/Reduce 冲突

java - 在 Java Cup 中的状态中发现 Shift/Reduce 冲突

问题描述

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

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.

有人可以解释我在哪里做错了吗？

标签： javaparsinggrammarcup

解决方案

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

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

在这种特殊情况下，默认班次可能不会引起问题。这意味着仅由TOK1and组成的输入最后TOK2总是会被解析为空t3，但如果没问题，那么您可以随意忽略警告。

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

header: t3 t1 t2
t3    :  
      | t3 TOK3

采用

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

该解决方案可能会导致不需要的代码重复，但它是解决可空非终结符导致的移位减少冲突的一种简单方法。

推荐阅读