|
resources: lab08_files dragon ch 5 |
The parser in this lab implements the BNF grammar shown below for simple expressions. The purpose of the lab is to demonstrate intermediate code generation that can be performed during parsing. The parser in the example files generates an Abstract Syntax Tree. You will modify the parser to generate 3-address code (TAC).
Code generation is a syntax directed translation from the source high-level language into a lower-level language (the target language). The target language is closer to assembly/machine code than the source language but not platform dependent yet. The compiler backend takes the intermediate code and translates it into platform dependent machine code. The middle-end of a compiler (if there is one) is often tasked with optimization.
BNF for Lab08 Expression Grammar list: e | list stmt '\n' stmt: expr expr: term | expr - term | expr + term term: fact | term * fact | term / fact fact: id | (expr) | -fact id: a | b | c
(a-b) * -(b+c) / athe parser generates this AST:
divides(times(minus(a,b),negative(plus(b,c))),a)An Abstract Syntax Tree is similar to a parse tree but with only the semantically meaningful symbols contained in the tree. In the case of this Expression Grammar for this lab, the AST contains only operators and operands. Note that the parentheses can be removed because the order of operations is now explicitly controlled by the location of the operators in the tree. The location of the operators is dictated by the rules of the grammar. An inorder (LVR) traversal generates the evaluation order. Should you wish to actually evaluate the expression you could perform a postorder (LRV) traversal and perform an operation each time you hit an operator in a root node.
(a-b) * -(b+c) / a:
/
/ \
* a
/ \
- -
/ \ |
a b +
/ \
b c
AST generation is performed during parsing
as a syntax directed translation. The nodes of the tree are
held in the attribute bucket for the relevant terminal symbols.
Since the tree is constructed in a bottom-up parse
the final tree is displayed
when parsing hits the starting symbol of the grammar.
The attributes are assigned as actions at the end of each production
rule. When this is the case we know
all attributes are synthesized. A grammar of this form
are called an S-attributed grammar. The parse tree is decorated in a postorder
parse thus matches nicely with a bottom-up LR parser.
Generally an AST is dynamically constructed as an actual tree with pointers and nodes. In this lab the AST is displayed as a text string (see lab08.y). The string is generated during parse with the sprintf command. For example, the command below generates the substring for the '+' symbol at the PLUS production rule.
sprintf($$, "plus(%s,%s)", $1, $3);
The example below shows the BNF, the rightmost parse tree and the corresponding AST on this input:
a * -(b+c) / aSince the AST is an abbreviated parse tree it can be generated as synthesized attributes that are trickled up the tree during a postorder traversal of the parse tree. A postorder traversal corresponds to an LR (bottom-up) parse. This correspondence is demonstrated below.
BNF for Lab08 Expression Grammar list: e | list stmt '\n' stmt: expr expr: term | expr - term | expr + term term: fact | term * fact | term / fact fact: id | (expr) | -fact id: a | b | c
Example AST for input:
a * -(b+c) / a
divides(times(a,negative(plus(b,c))),a)
In tree form:
divides
/ \
times a
/ \
a negative
|
plus
/ \
b c
Rightmost Derivation for: a*-(b+c)/a
list -> list stmt '\n'
____
-> list expr
____
-> list term
___________
-> list term / fact
__
-> list term / id
_
-> list term / a
___________
-> list term * fact / a
_____
-> list term * -fact / a
___
-> list term * -(exp) / a
__________
-> list term * -(exp + term) / a
____
-> list term * -(exp + fact) / a
__
-> list term * -(exp + id) / a
_
-> list term * -(exp + c) / a
____
-> list term * -(term + c) / a
____
-> list term * -(fact + c) / a
__
-> list term * -(id + c) / a
_
-> list term * -(b + c) / a
____
-> list fact * -(b + c) / a
__
-> list id * -(b + c) / a
_
-> list a * -(b + c) / a
_
-> e a * -(b + c) / a
Rightmost Derivation Parse tree for:
a*-(b+c)/a
list
/ \
list stmt
| |
e expr
|
term
/ | \
term / fact
/ | \ |
term * fact id
| / \ |
fact - fact a
| / | \
id ( expr )
| / | \
a term + term
| |
fact fact
| |
id id
| |
b c
Modify expr.y so that, instead of an AST,
your code generates a list of
three-address code (TAC) operations in the order in which the operations
should occur. Your operations should use temporary variables to hold
intermediate values. For this input of 5 operations,
(a-b) * -(b+c) / ayour TAC output should look like this:
t1 = a-b
t2 = b+c
t3 = -t2
t4 = t1 * t3
t5 = t4 / a
To facilitate TAC generation you will construct one assignment for
each operation. Thus, each operation will be assigned to
a new 't' variable. You can generate a new t variable by incrementing
a counter and pasting the counter to 't'. For example, the MINUS operation
looks like this with the AST line commented out and replaced with the code
to generate TAC:
expr MINUS term
{
$$ = (char*)malloc(sizeof(char) * 1024);
// sprintf($$, "minus(%s,%s)", $1, $3);
counter++;
printf("t%d = %s - %s\n", counter, $1, $3);
sprintf($$, "t%d", counter);
free ($1);
free ($3);
$1 = NULL;
$3 = NULL;
}
You will need to do something similar for each operation. You will also
need to take out the code in the scanner that spits out the token since,
unlike the output of an AST that occurs at the root,
the syntax directed translation of TAC output will interfere
with any output
of the scanner.