Compilers(Question about Computer Science)

1 Consider the following grammar (describing LISP arithmetic):

X -> ( E ) 

E -> O | O T

O -> + | * | - | /

T -> n | X

X == executable, E == expression, T == term, n == number

terminals == ( ) n + * - / 

Find FIRST, FOLLOW and LR(0) sets for this grammar.

Is the grammar LR(0)? Is it SLR?

2.Give a rightmost derivation of the string (x+a)*x using:

S=> E

E=> E+T | T

T=> T*F | F

F=> i | (E)

The lexical analyzer returns a token i==identifier for variables 'x' and 'a'.

Display the parse tree, the syntax tree, and the expression DAG.

3. The algorithm for DOM in the text is based on data flow analysis, but it is often desirable to find the DOM tree from the control flow graph without t need to do data flow. Describe a possible algorithm based on breadh-first search to find DOM given a control flow graph. (An overview description in Englishis sufficient, you do not need a formal specification or code of an algorithm)