P : Program D : Declaration C : Command E : Expression T : TypeStructure F : Field L : LefthandSide N : Numeral I : Identifier P ::= D ; C D ::= D1 ; D2 | var I | proc I : C end C ::= C1 ; C2 | L = E | if E : C1 else C2 end | print L | call I E ::= N | ( E1 + E2 ) | L | new T T ::= array [ N ] | struct F end F ::= I | F1 , F2 L ::= I | L [ E ] | L . I N ::= strings of digits I ::= strings of letters, not including the keywords used aboveThat is, a programmer can define and call procedures, and also allocate arrays and struct objects in the heap, but we do not allow procedures in objects (which would make writing an interpreter significantly harder).
Your interpreter should take a program written in that syntax, and return the values of the expressions being printed during execution of that program (you may assume that only integers are printed).
As a first step, you should write a parser for the language; you will probably want to do that by modifying the one given for the previous assignment.
You may want to consult Assignment 3 for a discussion of the storage layout, cf. Section 2.2 of David Schmidt's Lecture notes.
As an example program, consider the following
var s; var y; var a; var sf; var ao;
proc p : print y; if y: y = 9
else y = (y+1); call p end
end;
s = new struct f, g end;
a = new array[3];
s.f = new array[4];
a[1] = new struct f, h end;
sf = s.f; sf[2] = 7; print s.f[2];
s.f[1] = 5; print sf[1];
ao = a[1]; ao.f = 8; print a[1].f;
a[1].f = 6; print ao.f;
print s.f[1]; y = 0; call p; print y
Given the above program as input,
your interpreter should return the list
7,5,8,6,5,0,1,9Your program should never terminate with an uncaught exception, but should give informative error message in case of syntactic or semantic errors. In comments within your program, you should have a brief discussion of what constitutes a semantic error. As in Assignment 3, you may decide not to enforce data-typing laws, and for instance allow a variable to be bound first to an array and next to a struct object.
For extra credit, you should write your interpreter such that when run on a program that prints infinitely often, it terminates with a result from which an arbitrary number of those prints can be extracted. (But your interpreter cannot be expected to terminate when run on a program that neither prints output nor terminates.) To accomplish that, you may take inspiration from the lecture slides on Lazy Evaluation. For example, given the program
var y; proc p : print y; y = (y+1); call p end; y = 2; call pyour interpreter, when asked for the first 6 outputs, should return the list
2,3,4,5,6,7,