|
resources: lab05 files yacc manpage C language ref GNU Bison Manual Lex-Yacc Howto flex-bison pdf Chapter 5.3 - 5.5 of text |
In this lab you will implement a syntax directed definition (SDD) in yacc that uses synthesized attributes (S-attributes) to control type checking for a simple language. Refer to Chapter 5.3 "Applications of Syntax-Directed Translation" of Dragon for background material. You performed syntax-directed translation in the calculator program that you wrote for lab03. The calculator in lab03 was an SDT that did not involve parsing a programming source for syntax violations. The "semantic actions" of the translator involved computing an expression and displaying a result. For compilers the semantic actions will involve context-sensitive (semantic) issues such as type checking and scope.
Your type checking SDT will be for a simple grammar of assignments and expressions. You will enforce strong typing; i.e., any expression with mixed types is illegal. The type constraint requirements in Phase II will violate strong type to allow some downcasting. This sort of typing is a little more complicated but this lab will point you in the right direction. The type constraints on your language are very simple. You just need to worry about input like this:
int a = 3; // OK
int b = 3.2; // NOT OK
float x = 8.1; // OK
float y = 8; // NOT OK
x = 8.5 + 2; // NOT OK
Things to consider: Yacc produces an LR parser. LR parsers work best
with S-attributed grammars since the tokens of the language are parsed
first (you can easily
trickle token values up). If your grammar is not S-attributed (inherited
attributes),
assigning attribute values does not follow the flow of parsing.
Bison does support inherited attributes but decorating
the parse tree will require 2 steps.
For example:
A -> BC
B -> EG
C -> DF { $1 = $0; } /* D is assigned the value of G's attribute.
* E is also D's left sibling (denoted by $-1)
*/
The parse tree looks show the inheritance between node C and node B:
A
/ \
B C # D grabs G's attribute. E and G are left siblings of D
/ \ / \
E G D F
Even though Bison supports inheritance you should use synthesized
attributes in your parser whenever possible.
Inherited attributes are not only less efficient (requiring two
passes) but will
make your grammar more difficult to debug since node
decoration does not follow the natural flow of bottom-up parsing.
Note that you are not computing the value of the expression in your SDT as you did in calc.y from lab03. In this lab your actions while parsing will be to trickle the data type of the terminal up the tree and spit out an error if a type constraint fails. The sample lab05.y file opens a log file for writing that you can use to spit your semantic errors out to.
Your job is to add type checking SDT to the simple lex/parser that currently implements blocks and expressions. The code to start with is lab05.y and lab05.l Copy these files and the Makefile to your account.
$ cp /fac/home/eddie/public_html/cmps450/lab05_files/* .Read the README file and run the compiler against good.cf (it should parse to an accepting state). Notice that the output from yacc generation includes y.output. This file depicts yacc's CFG based on the BNF rules that are provided in lab05.y. At execution you step through this grammar while parsing. Read y.output. Confirm that the parser generated by yacc matches the grammar that is defined in lab05.y.
Your job is to modify lab05.y and lab05.l to add a declaration type keyword (int or float) before variable statements. Add this syntax to lab05.y for declaration statements:
int i; // add keyword int
float x; // add keyword float
You will then
implement strong type checking constraint to expressions
and assignment statements based on the declaration type keyword.
Follow the Syntax Directed Definition
for type checking is SDD.txt
Trickle the
type up the parse tree via token type (e.g., INTEGER or REAL).
You do not need a %union for type checking since type can be coded as an
integer. For more complicated SDTs you
will need to use the %union option to hold your attributes.
Synthesize the type of number constants up the parse tree. Any expression with mixed type are errors. Your parser should catch three errors in bad.cf. Spit out the line number and type error to a log file (log is opened in the lab05.y file). Then continue parsing. At the end spit out the type error count. Your parser should end up in an accepting state but all three errors should be caught. Note that you will not catch the last type error with the SDT as coded. This type error requires a symbol table lookup. You will do this for Phase II.
If you are careful you only need to add 5 or so lines of code to lab05.l and 5 or so to parse.y. You can use the concepts you learn in this lab to complete your phase II project. A suggestion is to add a new header file lab05.h that contains:
#define ITYPE 1
#define FTYPE 2
Include the header file in all your source files. You will do the same
for your phaseII parser.
Note that in the following bad.cf file you will not be able to
catch the last type error for statement y = 3.5 without a symbol table
lookup. We will take care of such semantic errors in the next lab.
{
int y = 3.6;
float x = 2;
55 + 3.2;
y = 3.5;
}