Late homework assignments will not be accepted, unless you have a valid
written excuse (medical, etc.). You must do this assignment alone. No
team work or “talking with your friends” will be accepted. No copying from
the Internet. Cheating means zero.
============================================================
SUBMITTING THE HOMEWORK ASSIGNMENT
For this assignment you have to create two files:
1) One file called “answers.pdf” which contains your answers to Questions 1-5.
2) One file called “parser.y” which contains your answer to Question 6.
These two file must be in a directory that you name using your student ID
number. This directory must therefore contain the two files answers.pdf
and parser.y and nothing else.
Once you are done answering the assignment then create an archive or zip
file of the directory with the two files answers.pdf and parser.y in it,
just like you did in homework assignment 1, and upload the archive on
iSpace. Again the archive or zip file must be named using your student ID
number. If you do not remember how to do that then read the instructions
for homework assignment 1 again.
Following this naming convention is very important, as I will use a
computer program to automatically compile, run, and test your parser (on
many different input programs), and print your homework assignment.
Submitting files with the wrong names will result in your assignment not
being processed correctly by my program, which means you will get a zero
and you will have submitted your homework assignment for nothing. I will
not have time to change the program I use just because one or two students
failed to follow the instructions in this homework assignment. It is YOUR
responsibility to ensure that the files you submit are the right files with
the right names.
============================================================
Consider the following context-free grammar for a small programming language:
B -> { L }
L -> D ; L
L -> S ; L
L -> eps
D -> INT ID = E
S -> IF ( E ) B ELSE B
S -> ID = E
E -> E + E
E -> E * E
E -> ( E )
E -> ID
E -> NUM
where {, }, ;, INT, ID, =, IF, (, ), ELSE, +, *, and NUM are tokens, and
eps represents the empty string epsilon. B is the start symbol of the
grammar and represents a block of code, between curly braces. A block of
code is then a list L of definitions and statements, in any order. A
definition D is simply the definition of an integer variable which is
initialized using an arithmetic expression E. A statement S is either an
IF statement (with one block of code for the “then” part and one block of
code for the “else” part) or the assignment of an arithmetic expression E
to a variable. NUM is a token representing a natural number.
1) For each nonterminal in the grammar above, define an attribute called
¡¯time¡¯ which represents the maximum amount of time necessary for a computer
to execute the corresponding code, expressed as a number of clock cycles.
To simplify things, tokens and epsilon do not have such a ¡¯time¡¯ attribute.
For each grammar production in the grammar above, write an attribute
computation rule that computes the value of the ¡¯time¡¯ attribute for the
corresponding nonterminal. Your rules must be based on the following
assumptions:
– reading a number takes one clock cycle;
– reading a variable (using the variable¡¯s value in an expression) takes
one clock cycle;
– writing a variable (using an assignment to the variable¡¯s name)
takes one clock cycle;
– allocating memory for a new integer variable takes one clock cycle;
– doing an addition takes one clock cycle;
– doing a multiplication takes two clock cycles;
– testing whether the value of an expression is true or false and
making a decision based on the result of the test takes a total of
one clock cycle.
Also give a clear explanation in English of each rule, explaining why you
wrote the rule the way you did.
2) Is the ¡¯time¡¯ attribute synthesized or inherited? Explain why.
3) Write the parse tree for the following program:
{int x=y*3;}
then compute the value of the ¡¯time¡¯ attribute for all the nonterminals in
the parse tree.
What is then the maximum running time of that program?
4) How would you modify the attribute computation rules of Question 1 to
compute the minimum running time of a program?
5) The attribute computation rules you wrote in Question 1 always compute a
finite maximum running time for all programs written in our small
programming language.
Would the same be true if you tried to write the same kind of attribute
computation rules for a general-purpose programming language like C? Why
or why not?
What does this mean for the computational power of our small programming
language compared to the computational power of a general-purpose
programming language like C?
Do your answers change if you compare our small programming language with
the database query language SQL (limiting yourself to the data manipulation
part of the original version of SQL, i.e. statements like INSERT, UPDATE,
DELETE, and SELECT, and therefore ignoring later extensions to the language
that allow the programmer to create his own functions)?
What does this tell you about the computational power of SQL?
6) Implement your attribute computation rules from Question 1 using Lex and
YACC (or Flex and Bison).
Here is the file lexer.l that you need for Lex (you are not allowed to
change this file in any way):
========================================
%{
#include
#include
#include “y.tab.h”
void lexical_error(char c){
printf(“lexical error, unknown character: %c\n”, c);
exit(1);
} %}
%%
[{};()=+*] return *yytext; /* token is ASCII code of symbol */
if return IF;
else return ELSE;
int return INT;
[a-zA-Z][a-zA-Z0-9]* return ID;
[0-9]+
[ \t]+
\n
.
========================================
return NUM;
/* ignore white spaces */
/* ignore newlines */
lexical_error(*yytext);
and here is part of the file parser.y that you need for YACC, to implement
your attribute computation rules from Question 1:
========================================
%{
#include
void yyerror(const char *str) {
printf(“error: %s\n”, str);
}
int yywrap() {
return 1;
}
int main() {
return yyparse();
} %}
%token IF ELSE INT ID NUM
%%
========================================
Note: for single-character lexemes (such as ; or +), you can use them
directly as tokens in your YACC grammar by putting them inside single
quotes (such as ¡¯;¡¯ or ¡¯+¡¯), just like you did in the parser you wrote for
homework assignment 3.
Note: in the C action for the grammar production B -> { L }, after
computing $$, add a ¡¯printf(“%d\n”, $$);¡¯ statement to print the result of
your attribute computation rules for each block of code.
Note: the parser generated by YACC (or Bison) must not have any
shift-reduce confilct or any reduce-reduce conflict; you are not allowed to
change the context-free grammar; the + and * operators must have their
usual associativity and precedence.
Here are two examples (with one value printed for each block of code in the
input):
$ ./hw06
{int x=3;if(4+5){y=y*2;int z=0;}else{a=(2+5);};}
8
4
15
$ ./hw06
{if(156){}else{int x=7;}}
0
3
error: syntax error