c++ - Bison :轮类减少冲突

Question

我相信我无法理解轮类减少冲突的工作原理。我知道 Bison 可以向前看，所以我不明白为什么我会遇到这个问题。

在我的语言中，列表被定义为 [ ] 之间的一组数字或列表。 例如 [] [1] [1 2] [1 [2] 3] 都是有效列表。

这是导致问题的定义

 value: num 
    | stringValue
    | list          
    ;

list: LEFTBRACE RIGHTBRACE  
    | LEFTBRACE list RIGHTBRACE 
    | num list          
    | RIGHTBRACE            
    ;

冲突是从数开始的，不知道是按列表规则移位，还是按值规则归约。我很困惑，因为它不能检查列表是否跟在数字后面吗？

任何关于我应该如何进行的建议都将不胜感激。

Answer 1

我想我会以不同的方式定义事物，以一种避免问题开始的方式，比如:

value: num
     | stringvalue
     | list
     ;

items:
     | items value
     ;

list: LEFTBRACE items RIGHTBRACE;

编辑:除非消除空列表，否则无法干净地将数字列表与字符串列表分开。出现的问题是您希望允许空列表包含在数字列表或字符串列表中，但是查看空列表本身并不能让解析器决定是哪一个。例如:

[ [][][][][][][][] 1 ]

要弄清楚这是什么类型的列表，解析器必须一直向前看到 1 —— 但是 LALR(N) 解析器只能向前看 N 个符号才能做到这一点决定。 Yacc(和 Byacc、Bison 等)只做 LALR(1)，所以它们只能向前看一个符号。这留下了一些可能性:

1. 完全消除空列表的可能性
2. 让词法分析器将任意数量的连续空列表视为单个标记
3. 使用不限于 LALR(1) 语法的解析器生成器

然而，在 yacc 语法内部，我认为您无能为力——您的语法根本不符合 yacc 的限制。