EXERCISES

1. Check which of the following are LL(1):

   (a) S –> A | B
        A –> aA | a    	 
        B –> bB | b
    (b) S –> AB   	    
        A –> Ba
        B –> Cb | c	
        C –> c  
    (c) S –> aAaB | bAbB
        A –> S | cb
        B –> cB | a
   

2. Have you wondered why we did not discuss LL(k), k > 1 parsers, say LL(2) parsers? Try to form a parsing function M() for LL(2) parser.
3. Try to convert the following grammar to a regular expression:

   S –> aA	  B –> bC
   A –> aA	  C –> cB
   A –> aB	  C –> c
   

4. Show that the following grammar is not LL(1):

   V –> S#	  
   S –> aAa | empty
   A –> abS | c
   

5. Give the rules by which you can distinguish the following types of grammars: Regular, LL(1) with and without empty rules, context-sensitive, LR(0) and SLR(1).
6. Check if the following grammar is SLR(1) or not:

   S –> E#	
   E –> T		
   E –> E;T
   T –> empty
   T –> Ta
   

7. What is the difference between the terms “viable prefix” and “valid prefix”?
8. Suppose for a language there are two distinct grammars. While parsing sentences in that language by parsers based on the two grammars, will the definition of a handle be the same or will it be different in the two cases?
9. Why is the following grammar not an SLR(1)?

   S –> E#     E –> bEa | aEb | ba
   

10. State true/false: In a grammar being handled by YACC, Terminal symbols are recognized by yylex() and Non-Terminals by yyparse().
11. Two values may in general be returned by yylex() to yyparse(), one is the return value of the function itself, and another, if present, is returned via —————————.
12. YACC uses certain disambiguating rules while generating a parser for an ambiguous grammar. In a typical procedural language, in

    if <cond1> then if <cond2> then S1 else S2
    

    the else part is associated with second if. YACC ensures such a parsing by using the rule: (select most appropriate answer)

    1. in case of Shift/Reduce conflict, give precedence to shift;
    2. in case of Reduce/Reduce conflict, use the rule which is earlier in the grammar specification;
    3. use operator precedence and associativity;
    4. none of the above.
13. Develop a grammar in yacc syntax for the following “flow-chart” language F1 and implement a parser using yacc.

    program : ‘read’ var+ ‘;’ basicblock+
    basicblock : label ‘:’ assignment* jump
    assignment : var ‘=’ expr
    jump : ‘goto’ label | ‘if’ expr ‘goto’ label ‘else’ label | ‘return’ expr
    expr : constant | op expr expr
    label : identifier | number
    

    What should be the target language to actually draw the flow-charts?
14. Develop a grammar in yacc syntax for the following “Parentheses Language”:

    S –> L
    L –> L P
    L –> P
    P –> ( P )
    P –> ( )
    

    Refer to this grammar as G_p. Input your grammar to yacc and obtain the LR(0) machine, after removing conflicts if any.
15. We plan to develop a Boolean expression calculator (BEC) for manipulating Boolean expressions. It is expected to handle Boolean expressions in “Sum-of-Products” form. The basic grammar is:

    A –> V = E
    E –> V | T | A
    E –> E + E
    E –> E * E
    E –> E ∧ E
    E –> ( E )
    E –> ! E
    E –> E ? T
    

    Here ‘+’ denotes Boolean OR, ‘*’ AND, ‘∧’ EXOR, and ‘!’ negate. T is a min-term expressed as a decimal number. Develop complete BEC grammar input for yacc, including assignment of a Boolean expression value to a variable. Test it on yacc for ambiguities and other problems. Refer to this grammar as G_b.