Phase5 : Control Structures - Spring 2008 - CS 524 - Part 2 Loops
26March08 Lecture / Semantic Hints

Description of Code Generation Needs
Phase 5
Due: 14April08 as Group

Don't forget that completing the Control Structures (Phase 5), earns you a C on the project phase of this course. I will have implement Boolean Variables and Boolean Expressions available as on of the additional Phases you can select to earn a higher score, along with implementing Phase7a: Recursive procedures with local and global variables or Phase7b: Recursive procedures with parameters

As in Part 1 of the Hints for Control Structures, covering the If-Then-Elsif-Else-End, I suggested you take it in pieces.


The material in Section 8.4.5 is somewhat related, but it is more on the ForLoop.

Once you have the if-then-elsif-else-end if running, you should try the loop structure. I have combined the Semantic Processing (extensive) with the Code Generation suggestion in this one handout, since so much of the processing is in the creation of the Statement Structure and a great deal of similar code generation has been accomplished with the If-Then structures from Phase 5: Control Structures - Part 1.

Consider the sample:

loopit: while bexpr1 loop
              bunch of statements (i.e. a stmtlist)
              exit when bexpr2;         (exit the "current loop" depending
                                         on bexpr2 being true/false)
              statements
              exit loopit;              (just get out of the loop loopit)
              statements
              exit;                     (exit the "current loop")
              statements
              exit loopit when bexpr3;  (exit "loopit" depending on bexpr3)
              statements
              end loop;                 (or      end loop loopit;     )
Loops can be nested and can optionally have labeled names. You must be able to keep track of named loops - using the symbol table. So there will be a new kind of entry in the symbol table where we keep information about loop labels when they are encountered:
typedef struct attrec{
       IDNAME id;                /* user name */
       int level;                /* variable to hold procedure level */
       int offset;               /* Current variable's offset in memory */
       TYPEKIND typeid;          /* variables are declared with a type */
       int typename;             /* distinguish "integer" from user name */
       int initialized;
       int used;
       int loopopen;             /* for loops, keeping track of scope */
} ATTREC, *ATTRPTR;
"initialized" is set true (1) when the loop name ("loopit" above) is first encountered.
"used" is set true when the loop name appears in an exit statement
"loopopen" is set true at the beginning of the loop {insertloopname();} and is set false when the "end loop" is encountered {closeloop();}. You use this field when parsing an "exit somename" {makexit();} to make sure there is a loop named "somename" and that its scope is currently open.

You can keep track of the loop's scope number (the value of loop_depth, below) in the symbol table.

     The grammar rules that accomplish this can be:

loopstmt      :     id_colon_opt iter_opt basic_loop id_opt
                       {makeloop();}
id_colon_opt  :     identifier Colonsym {insertloopname();}
              |     lambda {nullname();}

iter_opt      :     While booleanexpr
              |     lambda {nullexpr();}

basic_loop    :     loop_head stmtlist End Loop {closeloop();}

loop_head     :     Loop {openloop();}

id_opt        :     identifier {checkname();}
              |     lambda

exitstmt      :     Exit name_opt when_opt {makeexit();}

when_opt      :     When booleanexpr
              |     lambda {nullexpr();}

name_opt      :     identifier
              |     lambda { nullname();}

Don't forget to keep your lrdebug entries going. I am hoping you have seen how useful this mechanism is for tracking the translation of our project.
We have two new types of statements to handle now - the Loop Statement and the Exit Statement. This will be reflected in semform.h as new STMTTYPE
typedef enum { /* --- statements and statement lists --- */
        AssignStmt,
        StdProcCall,   /* read or write */
        IfThenStmt,
        LoopStmt,
        ExitStmt
} STMTTYPE;

With the following summary of all our statement types through Phase 5, Control Structures.
typedef struct stmt{ /* statement description */
     STMTTYPE type;
     union {
          struct {
               EXPRTREE bexpr;
               struct stmt *slist;
               struct stmt *elsiflist;
               struct stmt *elselist;
          }ifthen;               /* ifthenstmt */
          struct {
               ATTRPTR id;
               EXPRTREE bexpr;
               struct stmt *slist;
          }loop;                 /* loopstmt */
          struct {
               ATTRPTR id;
               EXPRTREE bexpr;
          }exit;                 /* exitstmt */
          struct {
               ADDRTREE lhs;
               EXPRTREE rhs;
          }assign;               /* assignstmt */
          struct {
               PROCEDURETYPE type;
               PARAMLIST params;
          }procall;              /* stdproccall */
     }se;
     struct stmt *next;     /* next statement in list */
} STMTNODE, *STMTLIST, *STMTPTR; /* stmtlistnode */
/* dynamic memory allocation of statement list node */
#define stmt_alloc() (STMTLIST)(malloc(sizeof(STMTNODE)))

Here's an idea of what the semantic actions accomplish:

The scoping (nesting) of the loops is kept track of by a global variable, initialized to 0 in sem.h

/* for loops and keeping track of their nesting */
static int loop_depth = 0;

And incremented and decremented in {openloop();} and {closeloop();}

Here's an idea of what the semantic actions accomplish:


/* --------------------------------------------------------------------- */
/* -------- OPENLOOP: INCREASE LOOP NAME SCOPE  ------------------------ */
/* --------------------------------------------------------------------- */
openloop() { loop_depth++; }

/* --------------------------------------------------------------------- */
/* -------- CLOSELOOP: MARK LOOP NAME SCOPE CLOSED --------------------- */
/* --------------------------------------------------------------------- */
/* PRODUCTIONS:
 *   closeloop ::= Loop stmts End Loop : #closeloop
 *
 *    semtop -> | slist |
 *              ---------
 *              | bexpr |
 *              ---------
 *              | name  |     expr may be nullexpr; name may be nullname
 *    
 */

/* ------------------------------------------------------------------- */
/* -------- INSERTLOOPNAME:  INSERT LOOP ID INTO SYMTAB -------------- */
/* ------------------------------------------------------------------- */
/* PRODUCTIONS:
 *   id_colon_option ::= Id : #insertloopname
 */
/* SEMANTIC STACK MANIPULATION:
 *      top ->| identry |   >>>   |  attrec |<- top
 *            -----------         -----------
 *            |    ?    |         |    ?    |
 */

and

/* --------------------------------------------------------------------- */
/* ------ NULLNAME:  Push a null identifier onto semantic stack  ------- */
/* --------------------------------------------------------------------- */
/* SEMANTIC STACK MANIPULATION:
 *            |         |         |  attrec  |<- top
 *            -----------         ------------
 *      top ->|    ?    |         |     ?    |
 *
 */
Are used to get a labeled loop or null-labeled loop name onto the Semstack.

The grammar will have caused a bexprentry to be on the semantic stack if the grammar rule when_opt : When booleanexpr was reduced otherwise there will be

/* --------------------------------------------------------------------- */
/* -------------- NULLEXPR: CREATE A NULL EXPR ------------------------- */
/* --------------------------------------------------------------------- */
/* PRODUCTIONS:
 *   iter_opt ::= lambda #nullexpr
 *   whenoption ::= lambda #nullexpr
 */

If the user has included a "loop name" as an optional id after the end loop, you check it:

/* -------------------------------------------------------------------------- */
/* ------------- CHECKNAME:  CHECK LOOP NAME WITH ONE ON STACK -------------- */
/* -------------------------------------------------------------------------- */
/* PRODUCTIONS:
 *   id_opt ::= Id #checkname
 */
/* SEMANTIC STACK MANIPULATION:
 *      top ->| identry  |   >>>   | stmtlist |<- top
 *            ------------         ------------
 *            | stmtlist |         |null/bexpr|
 *            ------------         ------------
 *            |null/bexpr|         | identry  |
 *            ------------         ------------
 *            | identry  |         |    ?     |
 *
 *   POP 1 - once you verified that the optional name on the end loop is
 *           the valid Open Loop
 *   NOTE:  the picture is not very clear here!
 */

The finishing touches come from:
/* -------------------------------------------------------------------------- */
/* ------- MAKELOOP :  MAKE A LOOP NODE - use assign as model --------------- */
/* -------------------------------------------------------------------------- */
/* PRODUCTIONS:
 *   loopstmt ::= id_colon_opt iter_opt basic_loop id_opt #makeloop
 */
/* SEMANTIC STACK MANIPULATION:
 *      top ->|stlstentry|
 *            ------------
 *            |bexprentry|
 *            ------------
 *            |  identry |   >>>  |stmtentry|<- top
 *            ------------        -----------
 *            |    ?     |        |    ?    |
 *
 *   make the statement entry and POP 2
 */

Then the various ways to exit the loop are handled by these semantic actions.
/* -------------------------------------------------------------------------- */
/* ------- MAKEEXIT :  MAKE AN EXIT NODE - use assign as model -------------- */
/* -------------------------------------------------------------------------- */
/* PRODUCTIONS:
 *   exitstmt ::= exit Id booleanexpr #makeexit
 */
/* SEMANTIC STACK MANIPULATION:
 *      top ->|bexprentry|
 *            ------------
 *            |  identry |   >>>  |stmtentry|<- top
 *            ------------        -----------
 *            |    ?     |        |    ?    |
 */                                             bexprentry may be null;
                                                identry may be null.

Since we have only the equality test this semester, the following comment is not really applicable. but for those who wish to proceed with boolean expressions - this is applicable, so i'll leave the remark.

bexprentry may be a null expression depending on whether the loop is a while bexpr1 loop structure or a simple loop structure.
- identry may be a nullname depending on whether the loop had a label

Return to class page