DEPARTMENT OF COMPUTER SCIENCE

CMPS 401 - Programming Languages

Spring 2007

Assignment #4

Due: April 19, 2007

In this assignment you will demonstrate your understanding of grammars, parsing, productions, and the basis of compilers (pushdown machines).

1.  Design a grammar that can generate correct simple FOR loops in Perl as follows.

• Loops can be nested at arbitrary depths
• Assume that the only statements that will compose the code besides the FOR loops are simple assignment statements of the form X=Y+Z;

Show how your grammar can generate the following code:

       for (i=1, i<5,i++) { for (j=1, j<10, j++) { x=i+j} }

2.  Consider the following grammar:

            S -> ABA            A -> aA            A -> c

            B -> bB            B -> c

• Show a parse tree for the string aacbcac
• Show a derivation for the same string
• Show how a pushdown machine would check this string (explain the steps and show the contents of the stack)

The objectives of this assignment are:

• To familiarize you with grammars and parsing
• To familiarize you with push down machine functions which are the basis for compiler construction