Re: Parsing if, while, for, etc

[JB]

Hey, thanks for the detail! Yeppers, I have Modern Compiler Implementation
in C, but unfortunately I understand very little of it. It is written very
poorly in my opinion. I still don't understand why textbook authors can't
write in plain English so people can read and understand their books,
instead of filling their books with unintelligible squiggles and marks that
mean nothing. Why? Why not a book that people can actually read with clear,
plain English text and clear diagrammes? Beats me.

Why is GNU awk a good example? What is awk?

Yes, intermediate representation is something I'm struggling with, but I am
also struggling with how to build if, while, for etc. What are those bits
beginning with '@'?

(Notice Outlook Express thinks the above '@' is an email address or a link,
it is highlighted in blue with an underline in my editor window here. How
stupid can you get? Ha ha ha!)

OK, what I am trying to ask is, how is it done? I see in your example you're
using standard C++ and you build a list. This was one of my suspicions, but
I am very nearly lost.

Example:

WHILE_LOOP:    WHILE expr DO
                                   stmt_list
                              END WHILE
                                ;                            { /* C code of
some sort */ }

In the part where the C code goes, if I was writing an interpreter and
wanted to execute this straight away, could I just write:

{
    while ($2) {
        $4;
    }
}

.... or am I missing something? What would $4 contain in this case? Would I
need to pass it into a function I write myself to extract the individual
statements, if any? Hmm...

What about:

FUNC:            FUNCTION func_name LPARAN param_list RPARAN
                        stmt_list
                        RETURN_STMT
                        END FUNCTION
                        ;
                                            { /* some C code here */ }

What would I do here?

... and when I ran across

CALL_FUNC:            id ASSIGN_OP CALL func_name PARAM_LIST
                                    ;
                                    { /* ??? */ }

... the O'Reilly book says a kind of "play-back" function can be written.
But the damn book doesn't give any examples of what the author means.


Can you shed any light on this for me? I have tried reading the bison input
file for gcc, but it is too advanced for me to break up into pieces and
learn from. I looked for the functions the file referred to when it
recognised something, but couldn't find them anywhere.

Thanks for your help and for a long and detailed reply to my first request
for help! I have pasted it onto my desktop for study. :-)

Here's to you Akim!!!

--
James


----- Original Message -----
From: "Akim Demaille" <address@hidden>
To: "James Buchanan" <address@hidden>
Cc: <address@hidden>
Sent: Thursday, December 07, 2000 9:12 PM
Subject: Re: Parsing if, while, for, etc


>
> | Hello Bison users,
>
> Hi!
>
> | I am wondering what other people do when needing to
> | parse loops and conditionals. Let's suppose we are generating
> | pseudo assembler as a kind of intermediate representation, and
> | come across something like this in a source file:
> |
> | while x = True and y = False and z > 10 do
> |         ... statements ...
> | end while
> |
> | ... statements that come after while loop ...
> |
> | Would I generate a label, say endwhileX (where X is the x-th while
> | loop seen in the source code) and perhaps build a linked list of all
> | the while conditions, say while_conditions_X->cond,
> | while_conditions_X->next, etc and walk through them one by one
> | testing them for truth, and if so go through the while loop code, but
> | if none of the conditions are true, would I generate say a jump to
> | the endwhileX label? Say (since they are all supposed to be true to
> | continue in the while loop code above):
> |
> | move register1, cond1
> | jumpzero endwhileX
> | move register1, cond2
> | jumpzero endwhileX
> | move register1, cond3
> | jumpzero endwhileX
> | alltrueX:
> |         .... code to execute in while loop ....
> |         .... fall through to endwhileX when done ....
> | endwhileX:
> |         .... code to execute after while loop ....
> |
> | Can someone tell me, if they have ever written a grammar involving
> | conditionals and loops, what you do when you need to generate
> | code for them or what you do when you execute statements
> | straight away as in an interpreted script?
>
> I must confess I'm a bit confused by your question.  You seem to say
> you have problems with Bison, but it seems to me it has nothing to do
> with Bison, but rather with intermediate representation, and effective
> translation of high level structures into low level languages.
>
> | Thanks for any pointers/tips/examples you can possibly give me!
>
> I'm in love with ``Modern Implementation of Compilers in {C, ML,
> Java}''.  This book has a good coverage of all these details.
>
>         http://www.CS.Princeton.EDU/~appel/
>
> To partly answer your question, here is what I'm using in some
> project:
>
> exp:
>   NIL
>    { $$ = new NilExp (@$) }
> | LPAREN exps.2 RPAREN
>    { $$ = new SeqExp (@$, *$2); }
> /* This translation into an empty SeqExp is given in the corrections
>    of the book on the web pages.  DOn't use NilExp, which is very
>    different. */
> | LPAREN RPAREN
>    { $$ = new SeqExp (@$, *new std::list<Exp*>) }
> | LPAREN error RPAREN
>    { $$ = new SeqExp (@$, *new std::list<Exp*>) }
> | lvalue ASSIGN exp
>    { $$ = new AssignExp (@$, *$1, *$3) }
> | IF exp THEN exp
>    { $$ = new IfExp (@$, *$2, *$4) }
> | IF exp THEN exp ELSE exp
>    { $$ = new IfExp (@$, *$2, *$4, *$6) }
> | WHILE exp DO exp
>    { $$ = new WhileExp (@$, *$2, *$4) }
> | FOR ID ASSIGN exp TO exp DO exp
>    {
>      $$ = new ForExp (@$,
>       *new VarDec (@3, *$2, 0, *$4),
>       *$6, *$8);
>    }
> | BREAK
>    { $$ = new BreakExp (@$); }
> /* LET can enclose syntactically several expressions, nevertheless,
>    from the semantical point of view, there should be just one: a
>    SeqExp. */
> | LET decs IN exps END
>    { $$ = new LetExp (@$, *$2, *new SeqExp (@4, *$4)); }
> | LET decs IN error END
>    { $$ = new LetExp (@$, *$2, *new NilExp (@$)); }
> ;
>
> and then, else where, the abstract syntax tree is converted into a
> lower level form.
>
>     virtual void visit (const WhileExp& e)
>     {
>       const type::Type *test_type, *body_type;
>       translate::Exp *test_exp, *body_exp;
>
>       // Type checking the test.
>       e.test_get().accept (*this);
>       test_type = _type;
>       test_exp = _exp;
>
>       if (!check_types_equal (e.test_get ().position_get (),
>       "condition", *test_type,
>       "expected", type::Int::instance ()))
> return;
>
>       // We need a label to the end of the loop, in case a break would
>       // be used.  Keep a copy of the previous label, for nested loops.
>       temp::Label *saved_loop_end_label = _loop_end_label;
>       temp::Label *this_loop_end_label = new temp::Label;
>       _loop_end_label = this_loop_end_label;
>       e.body_get().accept (*this);
>       body_type = _type;
>       body_exp = _exp;
>       _loop_end_label = saved_loop_end_label;
>
>       // A WHILE has type VOID.  And therefore the type of the body
>       // must be VOID.
>       if (!check_types_equal (e.position_get (),
>       "body", *body_type,
>       "expected", type::Void::instance ()))
> return;
>
>       _type = &type::Void::instance ();
>       _exp = translate::whileExp (*test_exp, *body_exp,
*this_loop_end_label);
>     }
>
> with
>
>   inline Exp *
>   whileExp (Exp &test, Exp &body, temp::Label &ldone)
>   {
>     temp::Label *ltest = new temp::Label;
>     temp::Label *lbody = new temp::Label;
>
>     Seq *seq = new Seq;
>     seq
>       ->push_back (*new Label (*ltest))
>       ->push_back (*new Cjump (Cjump::ne, *new Const (0), test.unEx (),
>        *new Name (*lbody), *new Name (ldone)))
>       ->push_back (*new Label (*lbody))
>       ->push_back (body.unNx ())
>       ->push_back (*new Jump (*new Name (*ltest)))
>       ->push_back (*new Label (ldone));
>
>     return new Nx (*seq);
>   }
>
> This is an implementation of the Tiger compiler described in the books
> aforementioned.
>
>
>
> BTW, there are plenty of free packages you could explore to take some
> inspiration.  GNU awk comes to my mind.
>
>         Akim
>
> _______________________________________________
> Help-bison mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/help-bison
>