野牛:转移减少冲突

Question

我相信我无法理解轮班减少冲突的工作方式.我知道野牛可以向前看,所以我不明白我为什么会遇到这个问题.

在我的语言中,List被定义为[]之间的一组数字或列表.例如[] [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的限制.