Part a) Due Monday May 5 23:59 (=11:59 PM) Part b) Due Sunday May 11 23:59 (=11:59 PM)
· Input
· Output
· Examples
Construct a parser for the SRC3 Language described on the official class page in the file. http://www.cs.ucla.edu/classes/spring03/cs132/src3.html.
You must define a BNF grammar for the source language specified and then code it in yacc. Please ensure that your BNF corresponds exactly with the defined source language. It is important that you do not have any shift-reduce or reduce-reduce conflicts in your grammar. Resolve all conflicts either by using the precedence operators provided in yacc or simply rewrite the BNF. (Note: on compiling the yacc code, the compiler issues a summary of the number of conflicts and their possible locations. This can help you to identify and eliminate these ambiguities)
This project ties in with project 1. In project 1 you defined the different tokens and then tried to identify them in the input stream. After identification, the token descriptions were printed on the screen. In this project, you must pass these tokens to yacc. Yacc must accept these tokens and either parse them successfully according to the defined BNF, or issue an error message to stdout. The error message must contain a brief yet sufficient description and location (line#) of the error in the input stream. (Note: Error messages are with respect to user input; user SRC3 code in this case, and not relative to the tokens passed by the lexical analyzer)
The output format for this part is simply one of the following.
· Parse Successful.
· Parse Error: line#
Any questions regarding this should be directed to abhay@cs.ucla.edu or the class discussion board.
At this stage you are able to parse user input. You must add the construction of an Abstract Parse Tree, to the parsing process. This can be done, by writing code for actions to be performed once a production has been used to reduce. This is on similar lines to flex.
Once a production rule has recognized a stream of tokens, its tree building partner constructs a piece of the abstract syntax tree with the instantiated non-terminals and terminals that appear on the right hand side of the production rule.
For this part, you might need to define an appropriate data structure, to store the tree elements.
You can define the tree nodes of the types as described in section 3 onwards of the SRC3 description.
Please adhere to the specification
described here as much as possible since we are mostly running scripts
comparing the outputs. Deviations could result in point loss. Grading will be based
on the input and output from the program executable. Actual code will be
scrutinized only in special circumstances or to establish academic honesty.
The program should assume input from
standard input (which can be redirected by you or a grader to read any
specified file).
The output is standard output.Makefile, etc. The executable name should be parse. README.
Simple text file, no word/html documents please. It should describe
1
Myprogram ;
begin
/*empty body*/
end ;
end Myprogram
2
Myprogram ;
begin
/*main body*/
begin
/*nested block 1*/
end ;
begin
/*nested block 2*/
end ;
end ;
end Myprogram
3
Myprogram ;
/*varaible Declaration list*/
var a,b,c:int;
var d,e,f:real;
/*constant declaration list*/
var g,h,i:5;
var j,k,l:"hello"
/* first Subroutine */
SubroutineA (a,b,c: real; e,f: int; var g,h: real; k,l: int): bool;
begin
/* Empty body of subroutine*/
end ;
end subroutineA
begin
/* Empty main body*/
end ;
end Myprogram
4
Myprogram ;
/*varaible Declaration list*/
var a,b,c:int;
var d,e,f:real;
/*constant declaration list*/
var g,h,i:5;
var j,k,l:"hello"
/* first Subroutine */
SubroutineA (a,b,c: real; e,f: int; var g,h: real; k,l: int): bool;
Begin
var dummy:real
end ;
end subroutineA
begin
end ;
end Myprogram
5
Myprogram ;
/*varaible Declaration list*/
var a,b,c:int;
var d,e,f:real;
/*constant declaration list*/
var g,h,i:5;
var j,k,l:"hello"
/* first Subroutine */
Greater (e,f: int): int;
begin
if e>f then
return e ;
else
return f ;
end if ;
end ;
end Greater
begin
/*main body*/
while 1
do
write "please enter two numbers and we will output the greater of the two" ;
read x ;
read y ;
write Greater(x,y),"is the larger of the ",x," and ",y ;
end while ;
end ;
/* testVarDecls.s */
testVarDecls;
var a : bool;
var i, j, k : int;
var x, y, z : real;
var str : string;
var four : 4;
var mygrades : array[0..4] of int;
var mycreditcardnumbers : array[10, four] of int /*
omit ; here */
begin
end; /* note the semi here */
end testVarDecls
-------------------------------
-------------------------------
/* bigtest.s */
bigtest ;
var s:
"""Time heals all""";
var
levelofdifficulty : -1e8;
var
score : levelofdifficulty; /* what's this? */
var n
: 6 ;
var a
: array [-5..-1, n] of string;
var
b,i:int /* omit ; here */
add
(x,y : int) : int;
begin
return x+y;
end; /* note the semi here */
end
add
times(x, y :int) : int;
begin
var a,i:int /* omit ; here */
a := 0; i := 1;
while (i <= x)
do
a := add(a,
y);
i := i + 1;
end while;
return a;
end; /* note the semi here */
end
times
factorial (a:int) : int;
begin
if (a <> 0) then
return a*factorial(a-1);
else
return (1);
end if;
end; /* note the semi here */
end
factorial
gcd
(u:int; v:int) : int;
begin
if (v = 0) then
return u;
else
return gcd(v, u-u/v*v);
end if;
end; /* note the semi here */
end
gcd
nonsense(a:
array [-5..-1, n] of string): bool ;
begin
read a[-5, 1];
a[-1, 5] := s + " is a
proverb";
read b;
if !(b<5||b-1>6) then
return 0;
end if;
begin
var x : array [3, 0..0]
of real /* omit ; here */
x[0, 0] := score;
x[2, 0] := +8 * -.9 /
(x[1,0]);
end;
end; /* note the semi here */
end
nonsense
odd(a:
int) : bool;
begin
return a % 2;
end; /* note the semi here */
end
odd
begin
write "factorial(4) = ", factorial(4), " (should be
24)";
write "gcd(18, 48) = ", gcd(18, 48), " (should be
6)";
nonsense(a);
if odd(5) then
write "5 is odd";
end if;
end;
/* note the semi here */
end bigtest
-------------------------------
Subroutine inside subroutine
SubInsideSub ;
var a:int ;
var b:real
add
(x,y : int) : int;
begin
var
dummy: 5
/*
subroutine inside a subroutine*/
oracle()
: bool ;
begin
var
result: bool
result
:= 5 ;
return
1 ;
end
;
end
oracle
return x+y;
end; /* note the
semi here */
end
add
begin
/*empty main*/
end ;
end SUbInsideSub