LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 08-02-2016, 10:54 AM   #1
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Rep: Reputation: 38
Question A Bison problem: should it work as it is?


Hello.

I am beginning to read the book "flex & bison", author John Levine.

This book has all of its programs available online at the address ftp://ftp.iecc.com/pub/file/flexbison.zip .

After I solved my flex installation problem (as described in another thread), the flex related commands worked as shown in the book. For example:

Code:
$ flex fb1-1.l     # file inside above flexbison.zip
$ cc lex.yy.c -lfl 
$ ./a.out
The boy stood on the burning deck
shelling peanuts by the peck
^D
2 12 63
$
A few pages after that example, the first compilation involving Bison comes. It uses the given file fb1-5.y and the makefiles. Our important section of these makefiles is:

Code:
# part of Makefile.ch1
fb1-5: fb1-5.l fb1-5.y
        bison -d fb1-5.y
        flex fb1-5.l
        cc -o $@ fb1-5.tab.c lex.yy.c -lfl
The content of fb1-5.y file is:

Code:
/* simplest version of calculator */

%{
#  include <stdio.h>
%}

/* declare tokens */
%token NUMBER
%token ADD SUB MUL DIV ABS
%token OP CP
%token EOL

%%

calclist: /* nothing */
 | calclist exp EOL { printf("= %d\n> ", $2); }
 | calclist EOL { printf("> "); } /* blank line or a comment */
 ;

exp: factor
 | exp ADD exp { $$ = $1 + $3; }
 | exp SUB factor { $$ = $1 - $3; }
 | exp ABS factor { $$ = $1 | $3; }
 ;

factor: term
 | factor MUL term { $$ = $1 * $3; }
 | factor DIV term { $$ = $1 / $3; }
 ;

term: NUMBER
 | ABS term { $$ = $2 >= 0? $2 : - $2; }
 | OP exp CP { $$ = $2; }
 ;
%%
main()
{
  printf("> "); 
  yyparse();
}

yyerror(char *s)
{
  fprintf(stderr, "error: %s\n", s);
}
It should work, right? As this:

Code:
$ make fb1-5
 ... # some output I do not know without errors
$ # now an example of interaction
$ # with the above program, as shown in the book
$ ./fb1-5
2 + 3 * 4
= 14
2 * 3 + 4
= 10
20 / 4 - 2
= 3
20 - 4 / 2
= 18
The example was simply copied, as I cannot generate the fb1-5 program. In the bison call I have an error:

Code:
$  bison -d fb1-5.y
fb1-5.y: conflicts: 3 of shift/reduce

$ # I have also tried, manually:
$ # -v = verbose
$ # -Wall = warn about everything it can
$ # the output did not change:

$ bison -d -v -Wall
fb1-5.y: conflicts: 3 of shift/reduce
$ #  :(
Can you help me to understand what is wrong and to fix it to continue reading with working examples?

A question that should sufice to solve the problem here is to find an error in the bison file I copied above.

Last edited by dedec0; 08-02-2016 at 12:51 PM.
 
Old 08-02-2016, 12:23 PM   #2
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,590

Rep: Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908
Just guessing, but maybe

Code:
 | exp ADD exp { $$ = $1 + $3; }
Should be
Code:
 | exp ADD factor { $$ = $1 + $3; }
Otherwise, check the bison man page for some options to print out more information.
 
1 members found this post helpful.
Old 08-02-2016, 12:47 PM   #3
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Original Poster
Rep: Reputation: 38
Thank you! That solved it!! I did not belive when I read your suggestion, but I tried it for completeness' sake... and it worked! LOL And, sincerely, it is not among the things I would test myself so fast.

About bison's options, I had read its manpage and tested two of them that could write some more... but did not, for this problem. It could point a line number at least, don't you think?

Code:
bison -d # is to produce a header file
bison -v # verbose
bison -W[category] # to warn about specific kinds of warnings
bison -Wall        # there is an "all of them!" category! :D
bison -rall        # reports (all categories) about the automaton

Last edited by dedec0; 08-02-2016 at 01:50 PM.
 
Old 08-02-2016, 01:16 PM   #4
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,590

Rep: Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908
Quote:
Originally Posted by dedec0 View Post
About bison's options, I had read its manpage and tested two of them that could write some more... but did not, for this problem.
I think --report=all might be the relevant option for problems like this.

Quote:
It could point a line number at least, don't you think?
By the time bison detects the problem, it just knows that the grammar as a whole has ambiguities, it's hard to say which line (if any) the problem corresponds to. Although for this particular case, it could probably be done relatively easily. Your problem was basically the one described in https://en.wikipedia.org/wiki/Ambigu...nd_subtraction (although for addition only). In general, giving nice errors for this is an open research topic, see http://www.cs.cornell.edu/~chinawat/...radisaikul.pdf
 
1 members found this post helpful.
Old 08-02-2016, 01:48 PM   #5
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Original Poster
Rep: Reputation: 38
The report option seemed out of scope to me. But I will add it among thing to try and use in the future, since you pointed it (and now I am editing the other post to include "bison -rall" among those useful things).

For that option, the man page says:

Code:
...
-r, --report=THINGS
              also produce details on the automaton
...
   THINGS is a list of comma separated words that can include:
       `state'
              describe the states
       `itemset'
              complete the core item sets with their closure
       `lookahead'
              explicitly associate lookahead tokens to items
       `solved'
              describe shift/reduce conflicts solving
       `all'  include all the above information
       `none' disable the report
 
Old 08-02-2016, 02:20 PM   #6
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Original Poster
Rep: Reputation: 38
Unhappy

Bison does not fail, but the C file it generated generates a few warnings that I did not expect:

Code:
$ flex fb1-5.l 
$ bison -d -v -rall -Wall fb1-5.y -o fb1-5.tab.c
$ gcc -Wall fb1-5.tab.c lex.yy.c -lfl

fb1-5.tab.c: In function ‘yyparse’:
fb1-5.tab.c:1249: warning: implicit declaration of function ‘yylex’
fb1-5.tab.c:1426: warning: implicit declaration of function ‘yyerror’
fb1-5.l: In function ‘yylex’:
fb1-5.l:28: warning: implicit declaration of function ‘yyerror’
fb1-5.l: At top level:
lex.yy.c:1142: warning: ‘yyunput’ defined but not used # not a problem
lex.yy.c:1183: warning: ‘input’ defined but not used   # not a problem
$

Last edited by dedec0; 08-02-2016 at 02:25 PM.
 
Old 08-02-2016, 02:34 PM   #7
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Original Poster
Rep: Reputation: 38
Edit: first I posted that it was an error. Then I retried it manually and it worked (with the warnings you see above). Almost solved... but now I retried it with the makefile, it fails! I do not understand why:

Code:
$make fb1-5
yacc  fb1-5.y                # why it says yacc? Inside Makefile.ch1 is
                             # written bison
mv -f y.tab.c fb1-5.c
cc    -c -o fb1-5.o fb1-5.c
cc   fb1-5.o   -o fb1-5      # why it does not show -lfl ? It is also
                             #  written in the file
fb1-5.o: In function `yyparse':
fb1-5.c:(.text+0x1df): undefined reference to `yylex'
collect2: ld returned 1 exit status    # which mean it did
                                       # not generate fb1-5 file. Why?
                                       # -lfl ? It is in Makefile.ch1
make: ** [fb1-5] Erro 1
rm fb1-5.o fb1-5.c

Last edited by dedec0; 08-02-2016 at 02:36 PM.
 
Old 08-02-2016, 02:52 PM   #8
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Original Poster
Rep: Reputation: 38
Question

Sorry for so many consecutive posts. I am getting too tired today. Starting from zero, in another folder, I tried a few commands that should work, but it ends with an error:

Code:
$ wget ftp://ftp.iecc.com/pub/file/flexbison.zip
$ unzip flexbison.zip
$ vim fb1-5.y    # change line 28 to " | exp ADD factor { $$ = $1 + $3; } "
$ make fb1-5
cc   fb1-5.o   -o fb1-5
fb1-5.o: In function `yyparse':
fb1-5.c:(.text+0x1df): undefined reference to `yylex'
collect2: ld returned 1 exit status
make: ** [fb1-5] Erro 1
Why it did not execute

Code:
        bison -d fb1-5.y
        flex fb1-5.l
        cc -o $@ fb1-5.tab.c lex.yy.c -lfl
Which are in the Makefile.ch1. Is it quiet?

Last edited by dedec0; 08-02-2016 at 08:29 PM.
 
Old 08-02-2016, 03:14 PM   #9
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,590

Rep: Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908
Quote:
Originally Posted by dedec0 View Post
Why it did not execute

Code:
        bison -d fb1-5.y
        flex fb1-5.l
        cc -o $@ fb1-5.tab.c lex.yy.c -lfl
Which are in the Makefile.ch1? Was it quiet?
make only looks at Makefile (or GNUMakefile if you have GNU Make) by default, try
Code:
make -f Makefile.ch1
 
1 members found this post helpful.
Old 08-02-2016, 07:03 PM   #10
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 9,078
Blog Entries: 4

Rep: Reputation: 3187Reputation: 3187Reputation: 3187Reputation: 3187Reputation: 3187Reputation: 3187Reputation: 3187Reputation: 3187Reputation: 3187Reputation: 3187Reputation: 3187
... and, "tomorrow is another day."

Tonight, I think you're entitled to an apparently well-deserved beer!
 
Old 08-02-2016, 08:46 PM   #11
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Original Poster
Rep: Reputation: 38
@ntubski I thought that Makefile.ch1 (and the other Makefile.* files given in that zip file) was included in the standard Makefile. The Makefile (with this name) does not have the fb1-5 target, it only exists in the Makefile.ch1 file. I never saw this organization for Makefiles, but it seemed to work (or almost, since I got in trouble with it).

What is the magic of things getting compiled, if the Makefile.* were not read? make itself?

@sundialsvcs hehe... thank you. A day to relax with a good drink and some friends will probably be the next friday.
 
Old 08-02-2016, 09:02 PM   #12
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Original Poster
Rep: Reputation: 38
It seemed so simple that I decided to try it right now. To compile it by reading the Makefile.ch* files, there are two ways:

Code:
$ #1. The target All, which runs make with *.ch* files as argument
$ make All
 [output removed]
Code:
$ #2. The wanted target, passing the Makefile.ch* file as argument
$ make -f Makefile.ch1 fb1-5
bison -d fb1-5.y
flex fb1-5.l
gcc -Wall -o fb1-5 fb1-5.tab.c lex.yy.c -lfl
fb1-5.tab.c: In function ‘yyparse’:
fb1-5.tab.c:1249: warning: implicit declaration of function ‘yylex’
fb1-5.tab.c:1426: warning: implicit declaration of function ‘yyerror’
fb1-5.l: In function ‘yylex’:
fb1-5.l:28: warning: implicit declaration of function ‘yyerror’
fb1-5.l: At top level:
lex.yy.c:1142: warning: ‘yyunput’ defined but not used
lex.yy.c:1183: warning: ‘input’ defined but not used

$ # It compiled, no errors. I just wish a way to remove the first two
  # warnings. Do you know how? A header file not yet mentioned or used?

Last edited by dedec0; 08-02-2016 at 10:33 PM.
 
Old 08-03-2016, 08:52 AM   #13
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,590

Rep: Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908Reputation: 1908
Quote:
Originally Posted by dedec0 View Post
What is the magic of things getting compiled, if the Makefile.* were not read? make itself?
Yes, see Catalogue of Built-In Rules

Quote:
Yacc for C programs
n.c is made automatically from n.y by running Yacc with the recipe ‘$(YACC) $(YFLAGS)’.
Lex for C programs
n.c is made automatically from n.l by running Lex. The actual recipe is ‘$(LEX) $(LFLAGS)’.
Quote:
Originally Posted by dedec0 View Post
Code:
$ # It compiled, no errors. I just wish a way to remove the first two
  # warnings. Do you know how? A header file not yet mentioned or used?
According to http://stackoverflow.com/a/27672138/319698, this is a symptom of using an old bison version. Can be worked around by adding
Code:
%{
int yylex();
int yyerror(char *);
%}
 
Old 08-07-2016, 06:35 AM   #14
dedec0
Senior Member
 
Registered: May 2007
Posts: 1,120

Original Poster
Rep: Reputation: 38
Arrow

Quote:
Originally Posted by ntubski View Post
Complex. Many things that work silently under the hood.

Quote:

According to http://stackoverflow.com/a/27672138/319698, this is a symptom of using an old bison version. Can be worked around by adding
Code:
%{
int yylex();
int yyerror(char *);
%}
I found out that this is wrong for some cases. yyerror accepts a variable number of arguments, like printf. So the above fix should be:

Code:
%{
int yylex();
int yyerror( char *, ...);
%}
And to register how the compilation problem ended, I decided to create symbolic links in folder /usr/lib to all 4 files in the subdirectory i386 (libfl.a libfl_pic.a libfl.so libl.a). I did not move the files to avoid problems or exceptions with what apt installed.

Thank you all again, very much (:

Last edited by dedec0; 08-15-2016 at 06:05 AM.
 
Old 08-18-2016, 03:48 AM   #15
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,581
Blog Entries: 11

Rep: Reputation: 3596Reputation: 3596Reputation: 3596Reputation: 3596Reputation: 3596Reputation: 3596Reputation: 3596Reputation: 3596Reputation: 3596Reputation: 3596Reputation: 3596
Hi dedec0!

I'll try to provide some answers for several posts inline here, so I'll organize by post number to keep it all straight... I hope!

Post #1

Quote:
Originally Posted by dedec0 View Post
Hello.

I am beginning to read the book "flex & bison", author John Levine.

This book has all of its programs available online at the address ftp://ftp.iecc.com/pub/file/flexbison.zip .

After I solved my flex installation problem (as described in another thread), the flex related commands worked as shown in the book.
Yea, that is a strange packaging issue, but it is a distro/packaging issue not related to the book.

Glad that you got help making it work.

Quote:
Originally Posted by dedec0 View Post
A few pages after that example, the first compilation involving Bison comes. It uses the given file fb1-5.y and the makefiles. Our important section of these makefiles is:

Code:
# part of Makefile.ch1
fb1-5: fb1-5.l fb1-5.y
        bison -d fb1-5.y
        flex fb1-5.l
        cc -o $@ fb1-5.tab.c lex.yy.c -lfl
The content of fb1-5.y file is:

Code:
/* simplest version of calculator */
...
exp: factor
 | exp ADD exp { $$ = $1 + $3; }
 | exp SUB factor { $$ = $1 - $3; }
 | exp ABS factor { $$ = $1 | $3; }
 ;
It should work, right?
Yes it should work, and it does! There are no errors here!

The Makefile arrangement may be unfamiliar to you but it is not uncommon. It is just the way he has organized it. Work with it and try to understand it - don't try to "fix" it!

Also, Flex and Bison themselves are almost by definition for use by fairly advanced users. There is an explicit assumption that the reader knows how to use the other necessary tools, including make. If you need help with those obviously LQ is a good place to start, but do not interpret things unfamiliar to you as errors in the book.

And the lines...

Code:
exp: factor
 | exp ADD exp { $$ = $1 + $3; }
 | exp SUB factor { $$ = $1 - $3; }
... are correct, that is not an error! That is the grammar!

He is using the grammar to enforce precedence, addition before subtraction, which will become an example later in the chapter (or maybe the next chapter). I stress, this is a common grammar device that does a specific and desireable thing - try to understand it, not fix it!

The shift/reduce message may be visible due to newer Bison version, and/or he is also allowing you to see the bison shift/reduce conflict message that results, and to see that it is mostly harmless... he hasn't pointed it out yet because the reader is not yet equipped to understand it - don't try to get ahead of him!

Do you know what shift/reduce conflicts are? Probably not yet... but look in the index and read ahead and you will find what that means and whether to worry about it at this point.

I think this is one reason the book gets some mostly undeserved bad reviews. He is teaching the very basics of Flex and Bison (the software) but he must also teach them to people who have little or no understanding of the grammar (the problem being solved). He cannot teach the grammar and parsing theory in depth too! But he must introduce enough along the way to make the code useful, without losing focus or overwhelming the reader.

I think he actually does a pretty good job of it, just follow along and let him lead the way!

Quote:
Originally Posted by dedec0 View Post
The example was simply copied, as I cannot generate the fb1-5 program. In the bison call I have an error:

Code:
$  bison -d fb1-5.y
fb1-5.y: conflicts: 3 of shift/reduce

$ # I have also tried, manually:
$ # -v = verbose
$ # -Wall = warn about everything it can
$ # the output did not change:

$ bison -d -v -Wall
fb1-5.y: conflicts: 3 of shift/reduce
$ #  :(
Can you help me to understand what is wrong and to fix it to continue reading with working examples?
There is nothing there to be fixed - yet! It works, the message about grammar conflicts is harmless and educational at this point - ignore it for a few more pages. It will be the subject of a whole chapter later in the book!

It is not a code error. It is not a compiler error. It is a property of this particular grammar. The message is a normal Bison summary of what it found in this grammer.

Bison even has a way for you to tell it to expect a certain number of shift/reduce conflicts, %expect on page 145 - go read that quickly for comfort!

Again, just follow the examples, observe what it spits out, that is how he is teaching you what to expect! Let him lead, you follow...

Post #6

Just use the Makefile... you are looking for an error where there is none, and reinforcing your expectation of problems by forcing it to spit out unnecessary warnings... just use the Makefile...

Posts #7 thru #14

... Just use the (correct) Makefile (as you have discovered).

All the rules for each chapter's examples are in the Makefile.ch{1,2,3...} for each chappter.

Invoke them with the -f Makefile.ch1 option of make, as you have seen above, and you will see something like this (and get a working executable):

Code:
make -f Makefile.ch1 fb1-5
bison -d fb1-5.y
fb1-5.y: conflicts: 3 shift/reduce
flex fb1-5.l
cc -o fb1-5 fb1-5.tab.c lex.yy.c -lfl
So, the score now is Levine 1, Ubuntu packagers penalty, dedec0 1 - and moving the ball down the field!

Continue with Levine and follow - it really is an excellent introduction to Flex and Bison, and the examples work with only a few minor quirks! If you need help getting them going... here we are!

Good luck!

Last edited by astrogeek; 08-21-2016 at 12:07 AM. Reason: typos and fixed oops!
 
  


Reply

Tags
bison


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
problem with installing bison dharm_sk Linux - Software 1 08-07-2014 01:01 AM
Problem with bison 2.4.1 savio84 Programming 1 03-25-2011 07:55 PM
Is there any support for bison-bridge and bison-locations in flex on windows systems? rami alkhateeb Linux - Software 0 12-29-2010 09:10 AM
Problem installing Bison 2.4.1 on Suse 11.1 Takuan Linux - Newbie 1 10-13-2009 10:59 AM
bison, flex and make problem ChimpFace9000 Programming 4 05-19-2002 07:49 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 06:32 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration