Compilers and More

2.1) Consider the context-free grammar  S -> SS + |  SS * | a

a.) S -> SS*
   -> SS + S*
   -> aS + S*
   -> aa + S*
   -> aa + a*

b.) Parse tree of this string
 
c.) The grammar generates a language that accepts all possible arithmetic
  combinations of a but using only + and * and postfix notation

2.2) What language can be generated by the following grammars?

a.) S -> 0 S 1  |  0 1

The grammar generates a language that accepts equal number of zeroes
and ones where the sequence of 0's precedes the 1's

b.) S-> +SS | -SS | a

The grammar generates a language that accepts all possible arithmetic
combination of a using only + and - and prefix notation

c.) S -> S ( S ) S  |  ε

The grammar generates a language that accepts adjacent, nested and
matched pairs of parentheses.

d.)  S -> a S b S  |  b S a S  |  ε

The grammar generates a language that accepts an empty string or all
possible combination of strings containing equal number of a's and b's.

e.) S -> a  |  S + S  |  S S  |  S *  |  ( S )

An ambiguous grammar that generates a language that accepts strings of a.

2.3) 2.2.e is clearly an ambiguous grammar since string S + S *  can be parsed in
    more than one way as shown below.


2.4) Construct unambiguous context-free grammars for each of the following 
        language

a.) Arithmetic expression in postfix notation

expr -> expr expr +
expr -> expr expr -
expr -> digit
digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7  | 8 | 9

b.) Left-associative lists of identifiers separated by commas

expr -> expr, id
expr -> id

c.) Right associative lists of identifiers separated by commas

expr -> id, expr
expr -> id

d.) Arithmetic expressions of integers and identifiers with the four binary
  operators +, - , *, /

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | identifier | (expr)

e.) Add unary plus and minus to the arithmetic operators of (d)

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | identifier | (expr)  | +factor | -factor