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:

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

YACC file:

%token NUMBER
%left '+' '-'

%%

commands:
	commands command;

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

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

Compiler error:

$ 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?

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."

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

commands:
	commands command;

to

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:
  
  

  [-+*/] 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....)

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:

$ 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)

%% -?[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!

I already fixed that before post #4.

And as I said:

The problem is that there is no good explanation of YACC syntax — not that I could find, at least.

http://ds9a.nl/lex-yacc/cvs/lex-yacc-howto.html

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

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

$ bison *.y
lexyacctut.y: conflicts: 16 shift/reduce

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.

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.

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.

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):

$ ./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

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.

Originally Posted by larryherman 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.

Originally Posted by larryherman 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