Please assist: if/else condition problem with lex/yacc
Pakt
The following situation has been doing my head in for too long and I
would be grateful if someone could ease my suffering and point out
what I'm doing wrong. My suspicion is that it's embarassingly
obvious, but I'm a lex/yacc newbie and have found little information
on implementing conditional statements (Even after reading Appel's
Modern Compiler Implementation in C)
To illustrate, I have reduced the problem to a _very_ simple
interpreter which accepts only numbers, if/else blocks, "eq"
expressions and print statements. As in:
if (1 eq 1) {
print ("same");
}
else {
print ("different");
}
However, when the above is fed to the below, it prints:
"same"
"different"
Obviously it should only be printing "same", but I don't understand
how/why execution also enters the else block.
My [f]lex file looks like this:
%{
#include <stdio.h>
#include "spl.tab.h"
%}
%%
[-?0-9]+ yylval=atoi(yytext); return NUMBER;
if return TOK_IF;
else return TOK_ELSE;
eq yylval=(int) strdup(yytext);return TOK_EQ;
ne yylval=(int) strdup(yytext);return TOK_NEQ;
print return TOK_PRINT;
\".*\" yylval=(int) strdup(yytext);return STRING;
\( return LPAREN;
\) return RPAREN;
\{ return LBRACE;
\} return RBRACE;
\; return SEMICOLON;
[ \t]+ /* ignore whitespace */;
%%
And the yacc [/bison] file like this:
%{
#include <stdio.h>
#include <string.h>
#define true 1
#define false 0
void yyerror(const char *str)
{
fprintf(stderr,"error: %s\n",str);
}
int yywrap()
{
return 1;
}
main()
{
yyparse();
}
%}
%token NUMBER TOK_IF TOK_ELSE TOK_EQ TOK_PRINT LPAREN RPAREN LBRACE
RBRACE SEMICOLON STRING TOK_NEQ
%%
commands:
| commands command SEMICOLON
;
command:
print |
if_else_block
;
print:
TOK_PRINT LPAREN STRING RPAREN {
printf("%s\n",$3);
}
;
if_else_block:
TOK_IF expression LBRACE commands RBRACE TOK_ELSE LBRACE commands
RBRACE {
if ($2 == true) {
$$=$4;
}
else {
$$=$8;
}
}
;
expression:
NUMBER {$$ = $1;} |
expression TOK_EQ expression {($1==$3)?($$=true):($
$=false);} |
expression TOK_NEQ expression {($1!=$3)?($$=true):($
$=false);} |
LPAREN expression RPAREN {$$=$2;}
;
%%
Sorry for dumping my code on you lot, but I'm really losing hair over
this one.
Thanks heaps for any assistance.
Pakt.
[Your program is doing exactly what you told it to do, which in this
case is to evaluate each statement as it's parsed. Having been
through this too many times to count, my advice is to compile the
program into an AST, then interpret the AST. This makes it easy to
solve your particular problem, since you can interpret only the desired
branch of the if/else, and next week when you want to add loops, the
AST makes that easy, too. I put a little calculator into "flex &
bison" with an AST interpreter, and it works well enough that one
example is to compute square roots by iterative Newton's method. -John]
Kevin Lynx
"
if_else_block:
TOK_IF expression LBRACE commands RBRACE TOK_ELSE LBRACE commands
RBRACE {
if ($2 == true) {
$$=$4;
}
else {
$$=$8;
}
}
;
"
the two "commands" above, but not parse one of them by the
"expression". The simple solution is to set a global flag to indicate
the "expression" result, and when you interpret "command", you can
check the flag to do your special things.
Kevin Lynx
[A flag will work for if/then/else, but I still encourage people to turn
anything they plan to interpret into an AST first. Flags won't help
when you want to add loops. -John]
Chris F Clark
Why do people have such objections to doing the simple correct thing
and keep trying to hack something that just gets them deeper into a
quagmire? (No need to answer, that question is rhetorical.)
John, our moderator is absolutely correct. Building an AST is the
simplest most straight-forward solution to this problem. It will let
you do what you want and you won't try layering hack-upon-hack trying
to kludge toegther something that is a house-of-cards.
You can have some luck getting if-then-elses working with an execute
as you parse strategy. Others, have done it. You can also get it to
work with simple non-recursive subroutines. However, when it comes to
executing loops or subroutines with recursion, you will find the
problem nearly intractable. In those, cases that only simple solution
is to have a saved representation you can execute. An AST qualifies
for that.
Equally important is that for any complete modern parser generator
(i.e. written since about 1990), you will find ways of generating an
AST directly from your parser grammar with some simple annotations.
If you stay with yacc, you can find add-on tools that do the same
thing.
Even if you don't want to use a tool, it is fairly simple to build an
AST by hand. You simply make one class (data structure) for each
non-terminal or token in your grammar, where the members (fields) in
the class correspond to the (interesting) items in the right-hand-
side(s) of the rules that define the non-terminal. In the grammar,
you construct (allocated and fill in) one instance of the class at the
end of each rule (i.e. when the rule reduces) filling in the members
from the items in the rules right-hand-side, and make that newly
created instance your parser result. Something like this:
if_stmt: if LP expr RP then block else block semi;
{ class if_stmt *result = new if_stmt(
$3, // expr
$6, // then block
$8); // else block
$$ = result;
}
Hope this helps,
-Chris
******************************************************************************
Chris Clark email: christoph...@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------
Pakt
reply with sample code. It was helpful - and tempting, to read that I
can do conditions without an AST (thanks Kevin!) but it sounds like
ASTs are the better solution, particularly as I want to tackle loops
next.
I think I'll build the AST by hand as it'll probably be just as fast
as trying to work out how to make a tool do it for me, particularly
with Chris' sample for reference. I'm confident I'll be able to build
the tree with little trauma.
My next question is probably an obvious one, but what do I with the
tree once it's built? How do I traverse it? I guess don't understand
the 'big picture' view of how an AST helps.
I've tried reading what I can online, but I haven't found anything
that's of any real/comprehensible use. In fact there seems to be
ample examples on how to use yacc to build postfix calculators and the
like, but next to nothing on how to do anything more sophisticated,
such as conditions, loops etc. I even found mention by Yacc's author
of hopes (in 1990's) to one day expand the tutorial to cover
conditions and loops. :)
If my original question is as frequently asked as is claimed, does
anyone have any helpful, straightforward links to pass on, or code
snippets? If someone could point me a helpful direction then I'll
hopefully stop pestering you with silly questions.
Thanks again for any assistance,
Pakt.
[Once you have the AST, you interpret expressions by an ordinary
depth-first recursive tree walk. For if/then/else, you interpret the
condition, then depending on its value you interpret either the "then"
subtree or the "else" subtree. It's not very complicated. -John]
Bruce C. Baker
> If my original question is as frequently asked as is claimed, does
> anyone have any helpful, straightforward links to pass on, or code
> snippets? If someone could point me a helpful direction then I'll
> hopefully stop pestering you with silly questions.
>
> Thanks again for any assistance,
Still, despite its 1993 publication date, THE book on the PL
processors: "Programming Language Processors: Compilers and
Interpreters" (Prentice Hall International Series in Computer Science)
(Paperback) ~ David A. Watt ISBN 013720129X.
App. E contains the complete (except for I/O routines) PASCAL source
code for the simple language described in the body of the book, with
particular emphasis on creating and using ASTs. Available used from
both Abebooks and Amazon.
They will have to pry my copy from my cold, stiff fingers .... :-D
George Neuner
<paktsa...@gmail.com> wrote:
>does anyone have any helpful, straightforward links to pass on
Just about any book on compilers or language construction (SICP, EOPL,
etc.) will have a section about intermediate representation (IR) and
will cover ASTs and their use. But if you're specifically looking for
on-line resources:
Niklaus Wirth, "Compiler Construction", 3rd ed.,
http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf
Torben Mogensen, "Basics of Compiler Design",
http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/
P.D. Terry, "Compilers and Compiler Generators",
http://scifac.ru.ac.za/compilers/
"Engineering a Compiler". I'm not sure who to attribute this to,
there is no face page in the PDF. It is *not* Cooper & Torczon which
is available (but not free) as an ebook. It appears to be a fairly
decent intro text.
http://www.esnips.com/doc/6b2edf7d-fc7a-4950-8b84-6a9de5a23858/Engineering-a-compiler
If somebody knows who authored this work, please tell me.
These are all intro to intermediate level compiler texts that should
get you started.
George
[The PDF appears to be a copy of the unedited MSS for Cooper and Torczon, "Engineering
a Compiler", Morgan Kaufman, 2004. I found it by typing the first sentence of Chapter 1
into Google Books. They would doubtless prefer that people buy a legal copy of the
book, which is better than the MSS due to the excellent editors at Morgan Kaufman.
Follow this link and comp.compilers gets the referral fee:
http://net.gurus.org/bk/a/155860698X -John]
George Neuner
<gneu...@comcast.net> wrote:
>"Engineering a Compiler". I'm not sure who to attribute this to,
>there is no face page in the PDF. It is *not* Cooper & Torczon which
>is available (but not free) as an ebook. It appears to be a fairly
>decent intro text.
>http://www.esnips.com/doc/6b2edf7d-fc7a-4950-8b84-6a9de5a23858/Engineering-a-compiler
>If somebody knows who authored this work, please tell me.
>
>[The PDF appears to be a copy of the unedited MSS for Cooper and Torczon, "Engineering
>a Compiler", Morgan Kaufman, 2004. I found it by typing the first sentence of Chapter 1
>into Google Books. They would doubtless prefer that people buy a legal copy of the
>book, which is better than the MSS due to the excellent editors at Morgan Kaufman.
>Follow this link and comp.compilers gets the referral fee:
>http://net.gurus.org/bk/a/155860698X -John]
Obviously I wasn't as thorough as John was.
I have Cooper & Torczon and it did occur to me to look at it, but
there were enough differences in the organization, table of contents,
etc. that I did not think the PDF was the same book. On closer
examination I believe John is correct.
Unfortunately this PDF is available from many sites ... I just picked
the first one Google found to mention.
I have sent a note of apology to Keith Cooper and Linda Torczon. I
also apologize to everyone here for promoting an illicit book.
George
[It may not be illicit -- it's fairly common to send around manuscript
drafts for comment, but I can assure people from experience that a
good editor makes a book much better. Compare the mss of Linkers and
Loaders which you can still find on the web to the published book,
edited by the same group who did Cooper and Torczon, and the
improvements are obvious. -John]
George Neuner
>"Engineering a Compiler". <link removed>
>[The PDF appears to be a copy of the unedited MSS for Cooper and
>Torczon, "Engineering a Compiler", Morgan Kaufman, 2004. ... -John]
I heard back from Keith Cooper ... he was very gracious and confirmed
that this PDF is an early draft which escaped from the editor.
George