Programming Assignment #2: Formal Grammar and Abstract Syntax Tree

Discrete Mathematics and Its Applications

Programming Assignment #2: Formal Grammar and Abstract Syntax Tree

We define a small imperative programming language called miniC (a mini fragment of the C programming language), making use of the following formal language:
```
prog -> stm prog 
      | stm
stm  -> id = exp; 
      | print (exp);
exp  -> exp + exp 
      | exp - exp 
      | exp * exp 
      | exp / exp 
      | id 
      | num 
      | (exp)
```
where id is a string and num is an integer.
A program in miniC is just composed of a list of statements.
The statement may take two forms: assignment and print. The assignment statement id=exp; first evaluates the value of exp and then assigns it to identifier id. The statement print (exp); will print the value of its argument to standard output terminated with a newline.
There are totally 7 forms of expressions, their use and meanings are the same as those in C.
Answer these questions:
(1) Write some sample programs (sentences) derivable from this formal grammar.
(2) Design an abstract syntax tree (AST) for the above formal grammar miniC, in your favoriate programming language.
(3) Rewrite the sample programs in problem (1) to its AST form as defined in problem (2).
(4) Define and implement some interesting operations on the AST defined in problem (2). For instance, design and implement a function numSetOfProg satisfying this interface
```
  set numSetProg (prog p);
```
which computes and returns the set of all numbers of the input program p. For example, we have
```
  numSetProg (x=9; y=8;) = {9, 8}.
```
The following formal language defines a small assembly language called miniPentium (a mini fragment of the Pentium assembly language).
```
prog        -> instruction prog 
             | instruction
instruction -> movl v, id 
             | addl v, id
             | subl v, id
             | mull v, id
             | print v
v           -> id 
             | num
```
where id is a string and num is an integer.
A miniPentium program is just a list of instructions, and each instruction may take 5 variants. Each instruction is written in an ATT-style syntax, and models the corresponding Intel instruction. For instance, the instruction
```
  addl v, id
```
means that
```
  id = id + v;
```
and other instructions takes a similar meaning.
Answer these questions:
(1) Write some sample programs (sentences) derivable from this formal grammar.
(2) Design an abstract syntax tree (AST) for the above formal grammar miniPentium, in your favoriate programming language.
(3) Rewrite the sample programs in problem (1) to its AST form as defined in problem (2).
(4) Define and implement some interesting operations on the AST defined in problem (2). For instance, design and implement a function idSetOfProg satisfying this interface
```
  set idSetProg (prog p);
```
which computes and returns the set of all identifiers of the input program p. For example, we have
```
  idSetProg (movl 8 x movl 9 y) = {x, y}.
```
(5) (Optional, extra credit.) The above definition of miniPentium is not so realistic, for that there are infinite number of variables (ids), whereas the Intel Pentium machine (x86) has only 6 general registers (%eax, %ebx, %ecx, %edx, %esi and %edi). Study how to modify the formal grammare of miniPentium to take account of this. And then re-implement problems from (1) to (4) for the redesigned grammar.