LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
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 03-14-2010, 07:10 PM   #1
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Rep: Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713
Lex/YACC Question


I am reading about Lex and YACC and this is my first self-writtem example. It is supposed to solve a mathematical problem on every line.

But it doesn't compile! What do you think is wrong?

Lex file:

Code:
%%
-?[0-9]+ yylval = atio(yytext); return NUMBER;
[-+*/] yylval = *yytext; return OPERATOR;
%%
YACC file:

Code:
%token NUMBER
%left '+' '-'

%%

commands:
	commands command;

command:
	expression '\n' {
		printf("%d", $1);
	};

expression:
	NUMBER
	| expression '+' expression {
		$$ = $1 + $3;
	}
	| expression '-' expression {
		$$ = $1 - $3;
	}
Compiler error:

Code:
$ bison *.y
lexyacctut.y: warning: 4 nonterminals useless in grammar
lexyacctut.y: warning: 6 rules useless in grammar
lexyacctut.y:6.1-8: fatal error: start symbol commands does not derive any sentence
What's wrong with my code?
 
Click here to see the post LQ members have rated as the most helpful post in this thread.
Old 03-14-2010, 11:01 PM   #2
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,401

Rep: Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119
Uhh... go figure it out.

It's not really fair for you to look at this tool for a couple days and then say, "fix my problem for me."
 
0 members found this post helpful.
Old 03-14-2010, 11:07 PM   #3
larryherman
LQ Newbie
 
Registered: Sep 2003
Distribution: RHEL, SUSE, SLED
Posts: 12

Rep: Reputation: 2
Start symbol doesn't have a base (nonrecursive) case

Hi,

The reason for your bison errors is that your start symbol "commands" doesn't have a base (nonrecursive) case. Change your start symbol production from

Code:
commands:
	commands command;
to

Code:
commands:
        | commands command;
The empty case means that "commands" will match nothing, or commands followed by a command.

I haven't used flex/bison for a little while (meaning I could be making some mistakes here) but I believe I noticed some other problems as well:
  • I think you need to return \n from your scanner when \n is seen, otherwise the newline won't be available where your grammar rule "expression" is looking for it.
  • Your operator rule in your lex file is returning OPERATOR, but OPERATOR isn't used in your YACC file. I think you want the following instead:

    Code:
    [-+*/] yylval = *yytext; return yylval;
    Because you're looking for '+' and '-' in your grammar you need to return them.
  • I'm assuming you have a main function defined somewhere, that just calls yyparse()

If you can't get things to work based on that post again and I'll try to reply.

(Note to sundialsvcs- I've never posted here before, so maybe I should just stop while I'm ahead, but if you don't want to reply to the OP's question, why just not reply, instead of replying telling him he has no business asking it? Everything's easy to figure out once you've done it before....)

Last edited by larryherman; 03-14-2010 at 11:08 PM. Reason: fixed typo....
 
2 members found this post helpful.
Old 03-15-2010, 06:55 AM   #4
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713
Still nothing. The problem is that there is no good explanation of YACC syntax — not that I could find, at least.

Here is the error:

Code:
$ gcc *.c -o lexyacctut
lexyacctut.y: In function ‘yyparse’:
lexyacctut.y:11: warning: incompatible implicit declaration of built-in function ‘printf’
lexyacctut.l: In function ‘yylex’:
lexyacctut.l:2: error: ‘yylval’ undeclared (first use in this function)
lexyacctut.l:2: error: (Each undeclared identifier is reported only once
lexyacctut.l:2: error: for each function it appears in.)
lexyacctut.l:2: error: ‘NUMBER’ undeclared (first use in this function)
Attached Files
File Type: txt lexyacctut.l.txt (93 Bytes, 7 views)
File Type: txt lexyacctut.y.txt (239 Bytes, 7 views)

Last edited by MTK358; 03-15-2010 at 06:56 AM.
 
Old 03-15-2010, 07:12 AM   #5
devnull10
Member
 
Registered: Jan 2010
Location: Lancashire
Distribution: Slackware Stable
Posts: 547

Rep: Reputation: 115Reputation: 115
Quote:
%%
-?[0-9]+ yylval = atio(yytext); return NUMBER;
[-+*/] yylval = *yytext; return OPERATOR;
%%
do you not mean atoi?!

People here won't do you homework for you - if you have a specific problem then feel free to ask however just a "I can't do this, can you?" question isn't likely to yield the results you hope!
 
Old 03-15-2010, 07:14 AM   #6
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713
I already fixed that before post #4.

And as I said:

Quote:
The problem is that there is no good explanation of YACC syntax — not that I could find, at least.
 
Old 03-15-2010, 07:21 AM   #7
devnull10
Member
 
Registered: Jan 2010
Location: Lancashire
Distribution: Slackware Stable
Posts: 547

Rep: Reputation: 115Reputation: 115
http://ds9a.nl/lex-yacc/cvs/lex-yacc-howto.html
 
1 members found this post helpful.
Old 03-15-2010, 08:28 AM   #8
grail
Guru
 
Registered: Sep 2009
Location: Perth
Distribution: Manjaro
Posts: 7,564

Rep: Reputation: 1939Reputation: 1939Reputation: 1939Reputation: 1939Reputation: 1939Reputation: 1939Reputation: 1939Reputation: 1939Reputation: 1939Reputation: 1939Reputation: 1939
So it seems the question is not how to fix the issue but what better to search for, have you tried
perhaps Flex and Bison, yielding:

http://dinosaur.compilertools.net/

Amongst many others
 
1 members found this post helpful.
Old 03-15-2010, 11:34 AM   #9
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713
I'll keep reading some more, but anyway this is what I cam up with so far and it produces this error:

Code:
$ bison *.y
lexyacctut.y: conflicts: 16 shift/reduce
Attached Files
File Type: txt lexyacctut.l.txt (290 Bytes, 4 views)
File Type: txt lexyacctut.y.txt (640 Bytes, 7 views)
 
Old 03-15-2010, 05:18 PM   #10
devnull10
Member
 
Registered: Jan 2010
Location: Lancashire
Distribution: Slackware Stable
Posts: 547

Rep: Reputation: 115Reputation: 115
Use the -d switch to yacc to generate an output file (y.output if I remember correctly) which may help with your shift reduce errors. s/r errors are caused where there is ambiguity within a grammar and is usually a result of not defining recursive sections of the grammar correctly.
 
1 members found this post helpful.
Old 03-15-2010, 06:21 PM   #11
larryherman
LQ Newbie
 
Registered: Sep 2003
Distribution: RHEL, SUSE, SLED
Posts: 12

Rep: Reputation: 2
If you're going to be doing a lot of work with lex/yacc(bison), I liked the O'Reilly lex/yacc book quite a bit when I used to use it more often in the past. You might consider it. The online bison manual is at http://www.gnu.org/software/bison/manual/; it's fairly detailed. Take a look at Sections 5.3 and 5.4 regarding precedence.

The reason for your shift/reduce conflict is that your grammar is ambiguous (about as ambiguous as possible). That can be fixed, but what it means is that, when faced with an expression like 20 - 10 - 2, the parser wouldn't be able to determine whether it meant 20 - (10 - 2), or (20 - 10) - 2. Presumably you want the latter.

There are two ways to fix the problem here (in particular for shift/reduce conflicts involving operator precedence):
  1. You can refactor the grammar.

    Instead of an ambiguous grammar like (just using grammar notation here, with E for expression):

    E -> E + E | E - E | E * E | E / E | (E) | number

    you could construct productions such that the higher-precedence operators have to be done first; without going through all the explanation the result would look like (where T and P are new nonterminals):

    E -> E + T | E - T | T
    T -> T * P | T / P | P
    P -> (E) | number
  2. You can use flex/bison's operator precedence rules.

    For operators, you can add the operator precedence declarations %left and %right (described in one of the sections of the bison manual I referred to). For your grammar you probably want:

    %left OPADD OPSUBTRACT
    %left OPMULTIPLY OPDIVIDE

    Put these lines before the productions section of your grammar.

    Note that the order of the %left/%right lines specify the operators' precedence, and %left/%right specify associativity.

Changing the grammar always works (if you write it correctly). The operator precedence declaratrions work just for conflicts involving operators.

I got your example to work right for me using both approaches, although I had to add a few includes/definitions. Give it a shot.

Lastly, it's not wrong but it's not necessary to introduce a nonterminal for each single terminal symbol (in particular, those that are only one character). You can just return the characters '(', ')', '+', '-', '*', '-' from your lexer and use those characters in your grammar, as you had in the original version for the newline character (instead of the nonterminal NEWLINE). My opinion is it makes things easier to read.

Good luck.
 
3 members found this post helpful.
Old 03-15-2010, 07:06 PM   #12
theNbomr
LQ 5k Club
 
Registered: Aug 2005
Distribution: OpenSuse, Fedora, Redhat, Debian
Posts: 5,395
Blog Entries: 2

Rep: Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903Reputation: 903
larryherman has given some very good advice. I have used A Compact Guide to Lex and Yacc as a reference and tutorial in the past. The O'Reilly book is a bit of a standard for Lex & Yacc. Since the Yacc syntax is one application that uses the more general Backus Naur Format (BNF), you may find some useful online resources by searching for that.
--- rod.
 
Old 03-15-2010, 07:10 PM   #13
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713
Cool Success!

What is associativity?

Anyway, I wrote a working example of a calculator that supports variables, even though it gives a shift/reduce conflict.

Here is a sample session (what I typed is normal, the calculator's output is in bold):

Code:
$ ./a.out
3 + 4
7
1 + 2 * 3
7
(1 + 2) * 3
9
a = 6 * 2
a = 12
a + 2
14
b = 42
b = 42
c = a + b
c = 54
c
54
Attached Files
File Type: txt lexyacctut.y.txt (676 Bytes, 22 views)
File Type: txt lexyacctut.l.txt (298 Bytes, 89 views)

Last edited by MTK358; 03-15-2010 at 07:23 PM.
 
Old 03-15-2010, 07:31 PM   #14
larryherman
LQ Newbie
 
Registered: Sep 2003
Distribution: RHEL, SUSE, SLED
Posts: 12

Rep: Reputation: 2
I think you may have changed your example after running it, because the grammar now has rules like "expression expression '-'" and won't produce the results you showed above. Your prior version worked for me with the two %left lines that I gave added, plus a few includes fixed. (Of course you added variables after that.)

Section 3.7.3 of the Bison manual I referred to defines associativity: "The associativity of an operator op determines how repeated uses of the operator nest: whether ‘x op y op z’ is parsed by grouping x with y first or by grouping y with z first." Associativity is a property of an operator, just like precedence. Consider an expression like 20 - 10 - 2. Since subtraction in conventional arithmetic (and most, but not all programming languages) is a left-associative operator, this means (20 - 10) - 2, rather than 20 - (10 - 2). Note these would produce different results. Some operators are right-associative, for example in some languages that have an exponentiation operator (usually using a symbol like ** or ^), an expression like 2 ** 3 ** 4 means 2 ** (3 ** 4), which is a much larger number than (2 ** 3) ** 4. Assignment operators are right-associative (in programming languages in which they're associative at all).

Wikipedia has an article on associativity at http://en.wikipedia.org/wiki/Associativity, which has a link to one on operator associativity in programming languages as well.

Last edited by larryherman; 03-15-2010 at 07:32 PM. Reason: fixed typo
 
1 members found this post helpful.
Old 03-15-2010, 07:46 PM   #15
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Original Poster
Rep: Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713Reputation: 713
Quote:
Originally Posted by larryherman View Post
I think you may have changed your example after running it, because the grammar now has rules like "expression expression '-'" and won't produce the results you showed above. Your prior version worked for me with the two %left lines that I gave added, plus a few includes fixed. (Of course you added variables after that.)
Sorry about that, the program that yielded my example session used the same lex file, but a different yacc file called "infix.y". A have attached it to this post.

Quote:
Originally Posted by larryherman View Post
Section 3.7.3 of the Bison manual I referred to defines associativity: "The associativity of an operator op determines how repeated uses of the operator nest: whether ‘x op y op z’ is parsed by grouping x with y first or by grouping y with z first." Associativity is a property of an operator, just like precedence. Consider an expression like 20 - 10 - 2. Since subtraction in conventional arithmetic (and most, but not all programming languages) is a left-associative operator, this means (20 - 10) - 2, rather than 20 - (10 - 2). Note these would produce different results. Some operators are right-associative, for example in some languages that have an exponentiation operator (usually using a symbol like ** or ^), an expression like 2 ** 3 ** 4 means 2 ** (3 ** 4), which is a much larger number than (2 ** 3) ** 4. Assignment operators are right-associative (in programming languages in which they're associative at all).

Wikipedia has an article on associativity at http://en.wikipedia.org/wiki/Associativity, which has a link to one on operator associativity in programming languages as well.
I guess that makes some sense.

EDIT: If you compile this program and use a terminal with a white background, you might not see the output because it's hard-coded to print in bold white using ANSI escape codes.

Just replace the instances of \e[1;37m with \e[1;30m for bold black output.

EDIT2:

I am waiting for tomorrow already, I will then try to add constructs like:

if test
do stuff
else if test
do stuff
else
do stuff
endif

and

while test
do stuff
loop

and

do
do stuff
loop while test
Attached Files
File Type: txt infix.y.txt (763 Bytes, 5 views)

Last edited by MTK358; 03-15-2010 at 08:05 PM.
 
  


Reply


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
lex and yacc in RHEL4 birds Linux - Software 1 06-03-2009 02:56 AM
LEX and YACC with C gr33ndata Programming 4 11-18-2007 05:12 PM
Lex and Yacc on Federo 2.0 vivekian Fedora 6 05-20-2006 09:09 AM
Lex and Yacc on Mandrake 9.2.2 Anuradha Linux - Software 0 07-02-2005 03:32 AM
Lex & YACC coolfrog Programming 3 09-25-2004 07:00 AM


All times are GMT -5. The time now is 12:55 AM.

Main Menu
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
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration