Tip:
Highlight text to annotate it
X
In the last video we looked at how we went from a BNF into making some bison rules, and
on building that bison file we had some shift/reduce conflicts. This video looks at how we can
eliminate those shift reduce conflicts and go on and debug the grammar using bison.
So, we are starting from a point where, in the command prompt, we have just run bison
with three shift/reduce conflicts. Well, the first thing that is actually useful to do
is, if we go to the "Frequently Asked Questions" file for the coursework; question number 7
says "If I've got shift/reduce error in my yacc/bison grammar how to I locate them?".
It says you have to turn on the verbose output for bison, which is the "-v" parameter and
it says it generates a file called ".output", which in the case of a grammar called "pascal-like.y"
would make "pascal-like.output" file, which we can then read, and it points at a binary
operator and dual recursion has been part of the problem. We can see if that is it in
our case. So, what we have to do then is go to bison
with a minus verbose rule on this grammar, we get three conflicts as before, but we make
a file called "pascal-like.output". Opening that file we can see that state 32 caused
one of the errors and state 34 the other. So if we search for state 32, here, that's
the if statement, and we go on a little bit and state 34 which has two of errors is a
binary operator surrounded by expressions, which was not unexpected.
So, here we are in the grammar, we have got an expression operator expression, the suggestion
is in the FAQ file is that we change one of those to be value, which is also one of the
definitions of expression, and save the file. So, if we quickly click on here it shows how
its been re-written to take whatever that thing is and put it on the left hand side
of the operator. It actually is the same language. So, we can re-run the bison and now we have
only got one shift/reduce error, so I expect that is the if statement. We can go back into
"pascal-like.output", we read it from the disk, and go to the top of the file, its still
state 32 which is now this if statement. Now we can go why is if statement in this pascal-like
language causing a shift/reduce error. That's because it is an Algol-like language which
has a dangling else problem, which hopefully you learned about when you did left and right
derivation trees and realised that the dangling else causes a problem in Algol-like languages.
There are many ways to fix it in different languages, but what we'll do is just remove
it in this language, just so we don't have the problem and can move ahead. Having just
gone back to bison, you can see having removed the dangling else, having got rid of the double
recursion on a binary operator, we have on shift/reduce conflicts, we have an unambiguous
language. So, what we now want to do is make this run.
So, we need to now run the bison together with the flex. So, if we run flex on "pascal-like.l"
and then bison, without the "-v" because its OK on there, the other thing we've got to
do is we've got to include the output from flex into bison so they are linked together.
We do this by putting a %% at the end of the file, and in this last section we put "#include
lex.yy.c" carriage-return and save that. We've got to re-run bison again, because we
edited the bison file, that links together the output of flex and bison. We can now build
that with gcc and we can make an output called "parser.exe" and we can build the file it
makes called "pascal-like.tab.c" and we can do "-lfl". We don't want the "-DPRINT" in
the gcc which we did when we were running flex on its own, because we are not debugging
the print we are actually getting the returning for the tokens. Now, its got lots of errors,
which could panic you, but if we go back and look at the errors, we will actually see its
flagged up lots of our tokens which happen to have the same name as reserved words in
the C programming langauge, so we obviously can't compile them with a C compiler. That
is a particular problem with languages which are like C, so we have to disambiguate them.
So, having the names of tokens that are the same name as reserved words in C is a bit
awkward, we can change those. One of the ways is to make them into uppercase words, or to
put something on the end. In this particular case I'm going to put something on the end
of the tokens. So, if I go to "pascal-like.l" and I rename the tokens and instead of begin
I go begin hypen. I put underbar "t", just to stop them being reserved words. Save that.
And when I import these tokens into the bison I have to put the underbar T in them as well.
Although it says in the SPL we don't necessarily need to do this as we use the uppercasing
technique. We have to go through each rule that uses these tokens as a terminal symbol
and put the underbar T on each one of these reserved words begin and if, while, and do.
So we can save that now and we can build it with flex as we changed the flex file. We
can build it with bison as we changed the bison file (and I've made a typo there!) So
i'll just fix: I forgot to put the "T" in. And then we can build with the gcc line. Now
its failing to build again and now its saying "undefined reference to yyerror", but this
is actually another on of the standard things. Question number six: "When I compile my yacc/bison
code I get an error message yyerror not found." This is because we have got to have a main
program, and it says just copy this main program from what we did in the calculator "arith.c".
So we can do that. I can find my file "arith.c" and I can save
that to a file "pascal-like.c", and there we are.
So I can just change my gcc line to include a build of "pascal-like.c" "-lfl", and now
we've built a parser. So, we need to test the parser. We can test
the parser by just running the parser and we can give it input from, and I happen to
have made a little example program of the pascal-like language that I can give it, and
I called it example program - test program. I made a typo.... and now the parser has parsed
that test program, but nothing has printed out. We have no proof that it works. What
we need to do now is turn on the debug mode of bison, or test mode rather, and actually
that is on question number eight: "How do I turn on the test mode to allow me to debug
that". It says I have to use the "-t" argument where we previously used the "-v" argument
to bison and we have to add these few lines to turn on the printing into my main program,
which I just made earlier, so I can go down to my main program, I can paste in those lines
of code and save my main program, and I can re-run it through bison with "-t". I don't
have to run it through flex as I haven't altered the flex file, and now I just have to use/goto
my gcc line. I do have to add "-DYYDEBUG" because I've used another flag in that main
program to turn on the output, and then, if I run it on my test program, I get a whole
load of output, which I can scroll through, which is showing me which token it reads and
which rules its says its found an expression and then an assignment statement, then its
found a statement, and it goes all the way through and its says I've found a program
and end-of-input. That's actually worked. Now that's how I've debugged my program.