Exercise 1: For each of the following grammars, devise predictive parsers and show the parsing tables. You may left-factor and/of eliminate left-recursion from your grammars first.

a) S     0 5 1 1 0 1 with string 000111.
b) S     + 551 * SSla with string + * aaa.
!c) S    S (S) S\e with string (()()).
!d) S   -> S + S\S S\(S)\S * \ a with string (a + a) * a.
!e) S   (L)/a and L-> L, 515 with string ((a,a),a,(a)).
!! f) S   -» a5 65 |&5 a5|e with string aabbab.

Exercise 2: Compute FIRST and FOLLOW for the given grammar.

Consider the context-free grammar:

5 → SS + \SS *\ a

and the string aa + a*.

a) Give a leftmost derivation for the string.
b) Give a rightmost derivation for the string.
c) Give a parse tree for the string.
! d) is the grammar ambiguous or unambiguous? Justify your answer.
! e) Describe the language generated by this grammar.

Exercise 3:

Show the right most derivation for both sentential forms and underline the handles in each form.

For the grammar 5 -> 0 5 1 1 0 1, indicate the handle in each of the following right-sentential forms:

a) 000111.

b) 00511.

Exercise 4:

Show the rightmost derivation for both sentential forms (a), (c), and (c) and underline the handles in each form.

Repeat Exercise 3 for the grammar S ->> 5 5 + | 5 5 * | a and the following right-sentential forms:

a) SSS + a*+.
b) SS + a*a+.
c) aaa * a + +.

Exercise 5: Give bottom-up parses for the following input strings and grammars:

a) The input 000111 according to the grammar of Exercise 3.
b) The input aaa * a + + according to the grammar of Exercise 4.

Exercise 6. Consider the following grammar:

E → E + T
    |  T
T → T F
    | F

F → F*
   | a
   | b

Construct the SLR parsing table for this grammar. This will require you to compute the Follow sets for the nonterminals E, T, and F, as well as the item sets.

Programming Assignment

To our previous FSS language we add while, begin, and print expressions, resulting in somewhat simple Scheme (SSS) programs. While expressions support iteration, and begin expressions support compound expressions comprising a sequence of one or more expressions.

Prog  → expr+

expr  → DOUBLE

         |  BOOLEAN

         | ID

         | '(' RATOR expr* ')'

         |  '("def ID expr')'

         | '(' 'if expr1, expr2, expr3 ')'

         | '(' 'print' expr ')'

         | '('while' expr₁, expr₂')'

         | '(' 'begin' expr+ ')' 

BOOLEAN    → 'true' | 'false'

RATOR         → ARITHMETIC | RELATIONAL | LOGICAL

ARITHMETIC → '+'|'-'|'*'|'/'

RELATIONAL → '='|'>'|'<'

LOGICAL      → '&'|'|'|'!'

A while expression evaluates its test expression espri. If awn evaluates to true, the body exp₂ is evaluated and then the process is repeated; if expri evaluates to false, the most recent value of exp.: gets returned (or 0 if expr₂: was never evaluated). Thus a while expression behaves like the while expression found in C or Java.

A begin expression evaluates its expressions left to right and returns the value of its rightmost expression. The expressions preceding the rightmost expression are generally performed for their side-effect which, in our current language, is either assignment or print.

A print expression evaluates its operand expression and prints its value and also returns this value.