Bison: Shift Reduce Conflict

Question

I find it difficult for me to understand how problems with conflict reduction work. I understand that a bison can look ahead, so I don’t understand why I have a problem.

In my language, a list is defined as a set of numbers or lists between []. For example, [] [1] [1 2] [1 [2] 3] are all valid lists.

Here are the definitions causing the problems

value: num | stringValue | list ; list: LEFTBRACE RIGHTBRACE | LEFTBRACE list RIGHTBRACE | num list | RIGHTBRACE ; 

The conflict comes from a number, he does not know that the weather moves according to the list rule or decreases according to the value rule. I am confused because it cannot check if the list matches the number?

Any instigators of how I should act will be very grateful.

Answer 1

I think that I would define things differently, so as to avoid the problem, to start with something like:

 value: num | stringvalue | list ; items: | items value ; list: LEFTBRACE items RIGHTBRACE; 

Edit: Separating lists of numbers from lists of strings cannot be done cleanly unless you delete empty lists. The emerging problem is that you want to allow the inclusion of an empty list in a list of numbers or a list of strings, but looking at an empty list, it does not allow the parser to decide which one. For instance:

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

To figure out what the list is, the parser will have to look ahead to 1 , but the LALR (N) parser can only display N characters to make this decision. Yacc (and Byacc, Bison, etc.) Only LALR (1), so they can only look forward one character. This leaves several possibilities:

• completely exclude empty lists.
• Ask lexer to process an arbitrary number of consecutive empty lists as a single token
• use a parser generator that is not limited to LALR (1) grammars

Inside the yacc grammar, however, I don’t think you can do much - your grammar just does not fit the yacc limits.

Answer 2

Using the bottom-up analyzer, it is generally recommended that you avoid the correct recursion that you have in the highlighted grammar line below.

 list: LEFTBRACE RIGHTBRACE | LEFTBRACE list RIGHTBRACE **| num list** | RIGHTBRACE 

Instead, have you thought of something like this?

 value:value num | value string | value list | num | string | list list: LEFTBRACE RIGHTBRACE | LEFTBRACE value RIGHTBRACE 

Thus, you do not have the correct recursion, and the logic of nesting the grammar is more simply expressed.