Re: Parsing if, while, for, etc

[Akim Demaille]

| 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