Suppose we have the following context-free grammar which accepts a list of varia

Question

Suppose we have the following context-free grammar which accepts a list of variable

initializations.
Goal ::= single | Goal single
single ::= VAR "=" exp ";"
exp ::= VAR | INT | exp + exp

Here each V AR terminal can be matched to an arbitrary variable name (e.g., a, b, c), and
each INT terminal can be matched to an arbitrary integer value (e.g., 5, 25).

1. Add translation schemes to evaluate the number of variables being initialized and the
number of variables used to initialize other variables.

2. Add translation schemes to evaluate the value of each variable being initialized and
report errors if a variable is used before being initialized. You can assume a global
symbol table exists which can be used to store the value of each variable. You can
invoke add var(name,val) to insert a (VAR,INT) pair to the symbol table and can
invoke lookup var(name) to obtain the value of a varible name; a special value UNDEF
is returned if the variable name does not exist in the global symbol table.

3. Modify your translation scheme for (2) to count the index of each variable being initialized;
that is, for each variable being initialized, remember how many other variables
have already been initialized before it, so that we can use an unique integer to identify
each variable initialization; that is, the interface of add var becomes add var(index,
name, val) in order to insert a new variable to the global symbol table.

Explanation / Answer

Solution:

1.        

Attributes for Goal: vardef and varuser both synthesized.

Attributes for single: vardef and varuser both synthesized.

Attributes for exp: varuser synthesized.

Goal::= single{

Goal.vardef = single.vardef;

Goal.vardef = single.varuser;

        }|Goal1 single {

Goal.vardef = Goal1.vardef + single.vardef;

Goal.varuser = Goal1.varuser +single1.varuser;

                }

single :: VAR “=” exp “;”{

                                           single.vardef =1;

       single.varuser = exp.varuser;

     }

exp:: = VAR{exp.varuser =1;}|INT{exp.varuser = 0;}| exp1 + exp2 {

            exp.varuser = exp1.varuser + exp2.varuser;}

2.

Attributes for Goal: none;

Attributes for single: none;

Attributes for exp: val;

Goal:: = single | Goal single

single::=VAR “=exp”;” {add_var(VAR name,exp.val);}

            if(exp.val =UNDEF)error(‘variable undefined’);}

            |INT {exp.val = INT.val;}

            |exp1+exp2 {exp.val = exp1.val1 + exp2.val;}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.