The following is a grammar was abstracted from the adayacc.lr grammar which was made available on the class home page (under ADA-YACC. It is the full grammar for the entire Ada language (and may be confusingly long).
NOTE: This grammar is set up to handle the passing of parameters, which is not what is required in the class for the next phase. I wanted to give those students who are anxious to get going on additional phases the big picture here. Please do not forget to add the lr_debug statements so that you can continue to have this useful information produced to help with the development and understanding of this project.
body : Body bodydecllist Begin stmtlist
bodydecllist : bodydecllist typedecl
|
bodydecllist procdecl
|
lambda
procdecllist : procdecllist procdecl
{mergeprocs();}
|
lambda {nullproc();}
decllist : decllist decl
|
decl
decl : idlist Colonsym type Termsym
{enteridlist();}
procdecl : procdeclhead Begin stmtlist End id_option2 Termsym
{endprocbody();}
|
subprog_spec Termsym
{endnullprocbody();}
procdeclhead : subprog_spec Is decllist procdecllist
{merge_sub_procs();}
subprog_spec : subproc_head identifier formal_opt
{startproc();}
subproc_head : Procedure
{bump_scope();}
formal_opt : formal_part
|
lambda
{nullparamlist();}
formal_part : Lparen param_decl_list Rparen
param_decl_list: param_decl_list Termsym param_decl
{mergeparamlist();}
|
param_decl
param_decl : idlist Colonsym mode_option type
{decl_paramlist();}
mode_option : mode
|
lambda {pushint(0);}
mode : In out_option
{set_in();}
|
Out
{set_out();}
out_option : Out
{set_out();}
|
lambda
{set_notout();}
call_statement : name Termsym
{ makeproccall();}
name : identifier name_suffix_list
name_suffix_list: Lparen expr_list Rparen
|
lambda
{nullarglist();}
expr_list : expr_list Commasym arg
{mergearglist();}
|
arg
arg : expression
{createarglist();}
id_option2 : Identifier { checkname2(); }
|
lambda
This document will not focus on the parameters.
So what do we need to keep track of for procedures?
static int cur_proc_level = 0; <----- this is already therenew constructs are:
/* for nesting level for procedures */ static int cur_proc_label = 0; <----- this is for codegen static SYMTABPTR scope_array[4]; <----- this is the scope-stackWe have the global variable
Of course a better idea would be to add a parameter to the Insert/Lookup call to pass the "Root" of the particular tree you want searched.
struct programtree{
STMTLIST main;
VARLIST vars;
PROCLIST proclist;
struct constlist *const_listptr;
} Prog;
where PROCLIST is declared as
typedef struct prlist {
IDNAME id; /* procedure's name in characters */
ATTRPTR thisproc; /* pointer to proc's name in symtab */
ATTRPTR oldcurrentproc; /* pointer to old current procedure */
STMTLIST procstmts; /* pointer to stmts in body of proc */
struct prlist *procfirst,*proclast,*next; /* proclist */
} PROCDEF, *PROCLIST;
#define proc_alloc() (PROCLIST) (malloc(sizeof(PROCDEF)))
Notice, there are several lists being created here.
Procedures that are declared at the same static nesting level
need to be linked up through the "next". Procedures that are
subordinate to this procedure, i.e. contained in this procedure,
are linked up through the "procfirst" and "proclast" list.
As before, done() will set the fields of Prog
/* -------------------------------------------------------------------------- */
/* ---------------- DONE: PARSING COMPLETED, TIE UP LOSE ENDS -------------- */
/* -------------------------------------------------------------------------- */
/* PRODUCTIONS:
* pgm ::= stmtlist #done
*/
/* SEMANTIC STACK MANIPULATION:
* top ->| stlstentry|
* ------------
* |prlistentry|
* ------------- -----------
* | ? | top -> | ? | (should be empty now)
{set the values of Prog.proclist from Semstack[Semtop-1]
Prog.main = Semstack[Semtop].se.slist.first
Prog.vars = GetVars();
}
Since they involve different kinds of information, I created a union of the structures
/* ---------------------------------------------------------------------- */
/* ---------------- TYPE DEFINITIONS FOR THE SYMBOL TABLE --------------- */
/* ---------------------------------------------------------------------- */
typedef short ENTRYTYPE; /* types of entries in symbol table */
#define varentry 1
#define procentry 2
#define fwdprocentry 3
typedef struct symtabrec *SYMTABPTR; /* needed for forward decl of SYMTABREC*/
typedef struct attrec{
IDNAME id; /* user name */
TYPEKIND typeid; /* pointer to type */
ENTRYTYPE type;
union{
struct {
int level; /* filled in by genoffsets as it */
int offset; /* traverses the VARLIST */
BOOLEAN typename; /* need to distinguish Integer as
special ID */
BOOLEAN initialized; /* lhs of assign or read */
BOOLEAN used; /* rhs or write */
int loopopen; /* for loops */
}ventry;
struct {
int nestinglevel;
int startlabel;
int actrecsize; /* 4 + space for parameters */
SYMTABPTR localtable; /* local vars; formal params */
PLISTPTR plist; /* the list of formal parars */
BOOLEAN bodydeclared;
}pentry;
}aa;
} ATTREC, *ATTRPTR;
/* dynamic memory allocation of attrec node */
#define attr_alloc() (ATTRPTR)(malloc(sizeof(ATTREC)))
For completeness, let's look at the definition of
PLISTPTR, as well as the typedef's that the symbol table entry
will be using.
typedef short PARAMMODE; /* for parameter lists */
#define in 0
#define out 1
#define in_out 2
typedef struct plist { /* parameter list entry */
int level; /* static nesting level */
int offset; /* in activation record */
TYPEKIND typeid; /* include here to make checking */
IDNAME id; /* easier on proc calls */
PARAMMODE mode; /* in; out; in_out */
struct attrec *loc; /* associated var in symtab */
struct plist *next;
int totalsize; /* accumulated size for all fparams */
} PLIST, *PLISTPTR;
/* dynamic storage allocation of plist */
#define plist_alloc() (PLISTPTR)(malloc(sizeof(PLIST)))
typedef struct symtabrec *SYMTABPTR;
typedef struct stmt *STMTLIST;
typedef struct varnode *VARLIST;
struct semstackentry{
SEMSTACKTAG type;
union{
ADDRTREE addr; /* addrentry */
EXPRTREE expr; /* exprentry,bexprentry */
IDNAME id; /* identry */
struct {
int iconst;
TYPEKIND typeid; /* differentiate (b/i) constants by typeid */
} constant;
OPERATION oper; /* operentry */
STMTPTR stmt; /* stmtentry */
struct {
STMTPTR first,last;
}slist; /* stlstentry */
struct {
PARAMPTR first,last;
}plist; /* parmentry */
char *strconst; /* strconentry */
TYPEKIND type; /* typeentry */
struct {
IDLIST first,last;
} ilist; /* idlist */
struct {
PLISTPTR first,last;
}palist; /* procedure parameter list */
struct {
PROCLIST first,last;
ATTRPTR oldcurrentproc; /* used to restore CurrentProc
when procbody is closed */
ATTRPTR stentry; /* used to get to localtable */
int endlabel;
}prlist;
}se;
}Semstack[STACKDEPTH];
int Semtop;
as well as the "tags"
#define plistentry 15 /* list of parameters using se.palist */
#define prlistentry 16 /* list of procedures using se.prlist */
#define subprocentry 17 /* structure for procedure declaration, this
uses the se.prlist fields */
You want to make sure your print_semstack can print out these 3
new types of entries. NOTE, subprocentry and prlistentry will
both use the same structure of prlist.
typedef struct prlist {
IDNAME id; /* procedure's name in characters */
ATTRPTR thisproc; /* pointer to proc's name in symtab */
ATTRPTR oldcurrentproc; /* pointer to old current procedure */
STMTLIST procstmts; /* pointer to stmts in body of proc */
struct prlist *procfirst,*proclast,*next; /* proclist */
} PROCDEF, *PROCLIST;
#define proc_alloc() (PROCLIST) (malloc(sizeof(PROCDEF)))
--
-- This is a test of nested non-recursive parameterless procedure
-- calls with no local variables.
--
package test0 is body
i : integer;
procedure addone is
procedure okay is
begin
i := i + 1;
end;
begin
okay;
end;
begin
i := 0;
writeln("i = ", i, " (should be 0)");
addone;
writeln("i = ", i, " (should be 1)");
addone;
writeln("i = ", i, " (should be 2)");
addone;
writeln("i = ", i, " (should be 3)");
writeln("All done!");
end;
- The global symbol table will contain: i addone
- The level 1 symbol table will contain: okay
- The level 2 symbol table will be NULL.
The sequence of semantic actions is:
nullproc (for addone and any other level 1 procs)
bump_scope (working on level 1 instead of level 0 = globals)
pushid("addone");
nullparamlist
startproc (generate start label etc, set up attrec in level 0 table)
nullproc (for okay and any other level 2 procs)
bump_scope (working on level 2 instead of level 1)
pushid("okay");
nullparamlist
startproc (generate start label etc, set up attrec in level 1 table)
nullproc (which will stay NULL since there is no proc below okay)
merge_sub_procs (the subproc of okay is NULL)
nulllist (start building the statement list for okay)
generate the code for the body of procedure okay
endprocbody (finished with proc okay, close the level 2 scope)
mergeprocs (merge the level 2 procedure into the level 2 list)
merge_sub_procs (merge the level 2 list as sub_procs of level 1)
nulllist (start the body of the level 1 procedure)
pushid("okay");
nullarglist (for the call to procedure okay inside addone)
make_proc_call (for the call to procedure okay inside addone)
endprocbody (finished with proc addone, close the scope at level 1)
mergeprocs (merge the level 1 procecures into a level 1 list)
nulllist (start translating the body of the main program)
pushid("addone");
nullarglist (for the call to proc addone inside main)
make_proc_call (for the call to proc addone inside main)
done (hook up the fields of Prog)
Let's look at the individual semantic actions above:
/* --------------------------------------------------------------------- */
/* -------------------------- NULLPROC -------------------------------- */
/* --------------------------------------------------------------------- */
/* procdecllist ::= lambda # nullproc */
/* SEMANTIC STACK MANIPULATION:
* |prlistentry|<- top ***** changed
* -------------
* top ->| ? | | ? |
* ------------ -------------
*/
{add prlistentry to stack with all its fields set NULL}
/* -----------------------------------------------------------*/
/* BUMP SCOPE */
/* -----------------------------------------------------------*/
/* subproc_head ::= Procedure #bump_scope */
{set scope_array[cur_proc_level] = Root;
cur_proc_level++;
Root = NULL; (to set up a new table)
}
/* -------------------------------------------------------------------- */
/* ----- NULLPARAMLIST: Place null plist node on the semantic stack - */
/* -------------------------------------------------------------------- */
/* SEMANTIC STACK MANIPULATION:
* | ? | >>> | plistentry|<- top
* ------------- -------------
* top->| identry | | identry |
* ------------- -------------
* |prlistentry| |prlistentry|
* */
/* formal_opt ::= lambda #nullparamlist */
{increment Semtop and set type to plistentry
allocate a plist_alloc();
set fields NULL
}
/* -------------------------------------------------------------------- */
/* ----------- STARTPROC: Start procedure --------------------------- */
/* -------------------------------------------------------------------- */
/* PRODUCTIONS:
* subprog_spec ::= subproc_head identifier formal_opt ; # startproc
*/
/* SEMANTIC STACK MANIPULATION:
* |subprocentr| <- top
* -------------
* top ->| plistentry| | plistentry|
* ------------- -------------
* | identry | >>> | identry |
* ------------- -------------
* |prlistentry| |prlistentry|
*/
{save Root in scope_array[cur_proc_level]
Lookup "identry" in the table one level above
(i.e. scope_array[cur_proc_level-1])
---- shouldn't be there.
allocate attr_alloc() and set id,type,nestinglevel,
startlabel,actrecsize(4),
localtable(NULL),first(from Semtop),
bodydeclared(FALSE)
---- unless it's there without a body
set scope_array[c_p_l] to localtable
set scope_array[c_p_l-1] to Root; Reset Root to scope_array[c_p_l]
so that any formal parameters will be insert in new table.
Increment Semtop, proc_alloc() and set id field to Semtop-2.
set remaining fields to NULL
}
/* ----------------------------------------------------------------------- */
/* -------- MERGE_SUB_PROCS : MERGE SUB PROCEDURES ---------------------- */
/* ----------------------------------------------------------------------- */
/* PRODUCTIONS:
* procdeclhead ::= subproc_spec Is decllist procdecllist # merge_sub_procs
*/
/* SEMANTIC STACK MANIPULATION:
* top ->|prlistentry|
* -------------
* |subprocent | >>> |subprocentry| <- top
* ------------- --------------
* |plistentry | | plistentry |
* ------------- --------------
* | identry | | identry |
* ------------- --------------
* |prlistentry| | prlistentry|
*/
{decrement Semtop, set Semtop.first->procfirst to oldtop.first
set Semtop.first->proclast to oldtop.last
}
/* ---------------------------------------------------------------------- */
/* ------- ENDPROCBODY: End procedure decl ---------------------------- */
/* ---------------------------------------------------------------------- */
/* PRODUCTIONS:
* procdecl ::= procdeclhead Begin stmtlist End
id_option2 Termsym # endprocbody */
/* SEMANTIC STACK MANIPULATION:
* top ->|stlstentry |
* -------------
* |subprocent |
* -------------
* |plistentry |
* -------------
* | identry | >>> |subprocentry| <- top
* ------------- -------------
* |prlistentry| |prlistentry |
*/
{set scope_array[c_p_l]=Root and decrement cur_proc_level
remove prior scope symbol table (scope[c_p_l-1]) by re-setting Root
take "identry" and Look up in prior scope table and attr_alloc,
should be there. set its localtable to prior scope symtab
decrement Semtop by 3, set type to subprocentry.
set Semtop.first to Semtop+2.first
Semtop.first->thisproc = attr
Semtop.first->procstmts = Semtop+3.first
}
/* ---------------------------------------------------------------------- */
/* ---------------- MERGEPROCS: MERGE A PROC INTO A PROCLIST ----------- */
/* ---------------------------------------------------------------------- */
/* PRODUCTIONS:
* procdecllist ::= procdecllist procdecl #mergeprocs
*/
/* SEMANTIC STACK MANIPULATION:
* top ->|subprocentry|
* --------------
* |prlistentry | >>> |prlistentry|<- top
* -------------- -------------
* | ? | | ? |
*/
{use local variable PROCLIST newproc; for Semtop.first
if Semtop-1.first is NULL, set Semtop-1.first=newproc
else set Semtop-1.last=newproc
decrement Semtop
}
New Statement Structure for Proc Call
To implement the procedure call, we need a new statement structure:
typedef struct stmt{ /* statement description */
STMTTYPE type;
union {
struct {
EXPRTREE bexpr;
struct stmt *slist;
struct stmt *elsiflist;
struct stmt *elselist;
}ifthen; /* ifthenstmt, elseif & else */
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 - reads/writes */
struct {
IDNAME id;
int startlabel;
PARAMLIST paramlist;
PLISTPTR palist;
}proccall; /* procedure call */
}se;
struct stmt *next; /* next statement in list */
} STMTNODE, *STMTPTR; /* stmtlistnode */
/* dynamic memory allocation of statement list node */
#define stmt_alloc() (STMTLIST)(malloc(sizeof(STMTNODE)))
/* --------------------------------------------------------------------- */
/* ------ NULLARGLIST: Place null plist node on the semantic stack --- */
/* --------------------------------------------------------------------- */
/* SEMANTIC STACK MANIPULATION:
* | ? | >>> |plistentry|<- top
* ------------ ------------
* top->| ? | | ? |
*
*/
/* name_suffix_list ::= lambda # nullarglist */
{ increment Semtop, set type to parmentry
set Semtop.first to NULL
}
/* --------------------------------------------------------------------- */
/* ------ MAKEPROCCALL: Make procedure call node ---------------------- */
/* --------------------------------------------------------------------- */
/* PRODUCTIONS:
* call_statement ::= name # makeproccall *
* NOTE name ::= identifier name_suffix_list happened first *
*/
/* SEMANTIC STACK MANIPULATION:
*
* top ->|plistentry|
* ------------ -----------
* | identry | >>> |stmtentry| <- Semtop
* ------------ -----------
* | ? | | ? |
*/
{allocate a stmt_alloc, set type to proccallstmt
set paramlist to Semtop.plist.first
set id from Semtop-1
search through the scope_array for the
id - if not found then proc doesn't
exist
when found (at whatever scope-level,
set the startlabel from attr
decrement Semtop and set entry to statemententry
}
Concerns for the Forward Reference
There are some additional concerns for the forward referencing of
procedures. We need to build the symbol table entry for the procedure
but keep track that its body has not been declared yet.
/* ---------------------------------------------------------------------- */
/* ------- ENDNULLPROCBODY: End null procedure decl ------------------- */
/* ---------------------------------------------------------------------- */
/* PRODUCTIONS:
* procdecl ::= subprog_spec Termsym # endnullprocbody
*/
/* SEMANTIC STACK MANIPULATION:
*
* -------------
* top -> |subprocent |
* -------------
* |plistentry |
* -------------
* | identry | >>> |subprocentry| <- top
* ------------- -------------
* |prlistentry| |prlistentry|
*/
{set scope_array[c_p_l] = Root and decrement cur_proc_level
recover Root from scope_array[c_p_l]
attr = Lookup "identry" from Semtop-2, should be found -
set localtable to scope_array[c_p_l+1]
decrement Semtop by 2
set type to subprocentry, set Semtop.first = Semtop+2.first
Semtop.first->thisproc = NULL
Semtop.first->procstmts=NULL
})