How to remove shift/reduce conflicts on variable declarations in bison?

Question

I'm working on my compiler design project and i have to remove all ambiguities from this grammar. At first, the following code(.yac) had 27 shift/reduce conflicts with 3 reduce/reduce conflicts. I managed to make them only 15 shift/reduce conflicts and by now i can see that there are only conflicts on variable declarations like BOOLEAN_KW, CHRACTAR_KW, etc. I really need to solve this problem and i know that some Precedence or Priority need to be used here, and i have tested a lot of possibilites, but no success. If someone could have helped me with this output file of bison which shows the conflicts on shift/reduce, i would be greatly thankful. By the way, I guess that these reduce/conflicts are some warnings that bison gives me for acknowledgment purposes, But unfortunately even knowing that doesn't let me run the whole lexer and parser with my main program and i get this error while trying to run the whole code:

    Error : syntax error
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at YYParser$YYStack.stateAt(YYParser.java:315)
    at YYParser.parse(YYParser.java:1568)
    at global.main(global.java:39)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:497)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

And finally, here is my output from the -o output option with --verbose enabled using bison which shows the conflicts in the early section of the code: My code is uploaded here.

Please include the program in the question. The contents of an external link may change in the future, implicitly changing or invalidating the question, and thereby making answers meaningless. (For example, if you fix the bug.) This is a disservice both to people who help you by answering the question, and to potential future readers of the question who will not be able to understand the issue. — rici
You have two problems. The first is your shift/reduce conflicts. The second is your syntax error. Since you don't provide the input file, you should treat the syntax error as a separate issue, and don't ask that question until you make whatever changes you need to make to fix the S/R conflicts. — aghast

rici rici · Accepted Answer · 2017-04-19T16:41:04

The key warning is:

Rules useless in parser due to conflicts

5 declarations: /* empty */

which refers to these productions:

declarations_list: declarations_list declarations
                 | /* empty */

declarations: type_specifiers declarator_list SEMICOLON_KW
            | /* empty */

This says that a declarations_list consists of zero or more declarations. However, a declaration might be empty. So that's clearly ambiguous: how many instances of an empty declarations non-terminals appear in a given declarations_list? It could be any number, since they are all empty.

All of the shift/reduce conflicts derive from this essential ambiguity. When the parser needs a declarations_list, it needs to decide how many empty declarations to parse at the beginning of the list.

By default, it chooses to not insert any declarations, which makes the production:

declarations: /* empty */

useless (as the warning says). Since the production is, in fact, useless, you might as well just delete it, and thereby avoid the ambiguity (and the shift/reduce conflicts).

As Austin Hastings points out in a comment, this has no impact on the behaviour of the parser. The parser has already eliminated the useless production, and that will not change the response to any input. So if some input is generating an unexpected syntax error when you attempt to parse it, that reflects some different problem with your grammar.

How to remove shift/reduce conflicts on variable declarations in bison?

1 Answers