Debugging Bison/Yacc Grammars

Inevitably when you write Bison/Yacc grammars you will run into a grammatical errors. In this case the grammar was my LBNF grammar (Fortran.cf, Fortran.y, Fortran.l) for Fortran and I’m running the terminal.for module from the old Galaxy program through my ‘go’ script (current files: debugging.7z). Here’s the terminal output from my script run. Interspersed with the output from my echo statements are the outputs from the various programs run (including Bison/Yacc):

The important part for this post are the lines:

This tells us there are two types of errors occuring shift/reduce and reduce/reduce which prevents Bison/Yacc from creating a parser. There can be other types of errors, such as gramatical errors, which will only be discovered by thorough testing.

Understanding the errors

To understand exactly what shift/reduce and reduce/reduce errors a compiler course which includes the theory of LR parsers would be handy. However, the quick explanation is that as Bison/Yacc tries to find a complete rule in your grammar it shifts (lexical and rule) tokens onto the stack until it finds the last token in the rule then Bison/Yacc reduces (removes) all the tokens on the stack corresponding to that rule and replaces them with a single token of that rule type. Essentially it is building the AST (Abstract Synatx Tree) representation of the program being compiled.

To solve these types of errors we look at the Parser.output file which contains the output of the run of Bison/Yacc. This file contains a number of sections:

• Error list
• Abbreviated grammar
• Terminal (leaf) nodes in the AST
• Non-Terminal (internal) nodes in the AST
• The generated grammar states.

The Error list just lists all the shift/reduce and reduce/reduce errors that need to be fixed before a working parser is generated. The Abbreviated grammar shows the raw grammar without any adornments that go along with the grammar (like your C-code). This abbreviated grammar is usually easier to read once the parser file becomes filled in.

The Terminal (leaf) node list gives a cross reference to the rules in the Abbreviated grammar where that terminal node appears. The first number in each line, in brackets (), is the token ID of the token (the lexer and parser use this number to communicate the token).

The Non-Terminal node list again has a node ID in brackets() and then lists all the grammar rules that contain that node on either the right-hand-side(output) or the left-hand-side(input).

The Generated grammar states are created corresponding to a NFA (Non-deterministic Finite Atomaton) which is like a DFA (Deterministic FA) but will take into account the Bison/Yacc grammar doesn’t always have a terminal token at each location. For instance in the following grammar line when the parser tries to parse a ‘statement’ it has three (in this case) statements that it can follow. In a DFA it needs a terminal-token (e.g. ‘a’,’b’,’c’, … , ‘(‘, ‘)’ etc to make a decision on which rule to follow. What a NFA does is just follows all the possibilities until it finds a terminal token :

The gist of this is that the generated states in the Parser.output file will look very dissimilar to any one of your rules (usually). They will be, instead, a collection of your rules. Here is the generated state 2 from my grammar:

In the numbered lines at the top corresponding to our grammar the period ‘.’ corresponds to the location in all those rules that is the current position of parsing. Thus in lines 8-32 we are in the Simple_stm: part of our grammar waiting to get the first token of a new statement. If we get a T_WRITE token then two rules (15,16) will correspond. If we then go down to the next section which shows what we do when we get various tokens we see that a T_WRITE leads us to state 30 where we will process the next tokens from a write statement (e.g “WRITE(1, 13) (ISCORE(I), I = 1, 8)” ).

Shift/Reduce and Reduce/Reduce errors

So now lets look at the two types of errors shift/reduce and reduce/reduce errors in my program and go through the debugging process.

The shift/reduce error then is when Bison/Yacc can’t decide whether to shift the next token onto the stack (for instance when we are in the middle of a statement) or remove a set of tokens and replace them with a single token (like when a statement has been completely parsed). Here is the top of my Parser.output file:

Error “State 174 conflicts: 1 shift/reduce”

First lets look at the “State 174 conflicts: 1 shift/reduce” error. Going down to “State 174” in this file we find:

The second section were Bison/Yacc show the SHIFTs and REDUCEs it wants to do you can see two lines that define the problem:

The parser wants to both SHIFT and REDUCE at this state when it gets a T_RPAREN or ‘)’. So now we have to go through our grammar (at the top of this state) to determine where we see a period ‘.’ followed directly by a T_RPAREN. There are two places (grammar lines 110 and 133). In line 110 :

This is a good time to go back to our original grammar (Fortran.cf) and look a the code corresponding to these two rules:

You will notice that the Efunk. and Efunkpar. rules are almost identical except the second one has a list of SpecLExp tokens. Going further down the grammar file we notice that the SpecLExp can be either NILL (SpLExpNil.) or an LExp (SpLExpNot.). This essentially means there is two ways to have an empty function call in this grammar so the parser doesn’t know if it should shift a “SpecLExp” token onto the stack or to reduce the LExp8 “(” “)” token sequence into a LExp8 token.

The solution, that I decided upon (there may be many ways to change the grammar to fix this problem) was to eliminate the 110 rule (Ffunk.). So I did that and recompiled and the “State 174” error disappeared (NOTE: The state names may change over compiles).

Error “State 178 conflicts: 3 reduce/reduce”

The solution to reduce/reduce errors is similar. In this case state 178 shows us:

You will note here that the terminals T_MULT, T_DIV, and T_POW are all mentioned on two REDUCE lines each. These are the 3 reduce/reduce errors for this state. Looking at the BNFC grammar file (Fortran.cf) again we see what the problem is:

The chunk at the top of this listing shows the problem (the unary operators ‘+’, ‘-‘ and ‘.NOT.’ are the simple reason that this causes a problem in the lines “LExp? ::= LExp5 {*|/|** } … ” where Bison/Yacc doesn’t know whether to reduce as a Epreop. token or as a LExp7 token. The overarching problem is not the unary operator it is me being lazy about thinking how logical and arithmetic expressions should be expressed in the grammar … instead I just mushed everything together.

What this version of the grammar will do is create another type of error (for instance a coding error where logical expression like “.NOT. 6” is valid. This type of error would have to be detected with tests. For now I will just remove the unary operators and will fix the Logical/Arithmetic grammar error later.

Recompiling we see that removing the unary operator does fix the reduce/reduce error but also flags a number of tokens as unused:

The rest of the error correction process is similar. In fact, looking at the remaining reduce/reduce and shift/reduce errors points to the same chunk of grammar. Therefore it appears my next job is to correct my grammar laziness.

So until I fix my grammar…