Compiler Construction – SMD163

Homework assignment 3

1. Consider the following grammar (which incidentally describes the syntax for a simple
   language of regular expression):
   
      t   →   t t
      t   →   t | t
      t   →   t *
      t   →   c
   
   where the symbol c stands for a token representing individual characters. The diagram
   below has been drawn to show the structure of a shift-reduce parser for this grammar:
   
   
   
   Using your knowledge of the way that shift-reduce parsers work, complete this diagram
   by:
   
   
   • Labelling each transition with an appropriate terminal or nonterminal symbol.
     
     
   • Labelling each state in which a reduction might take place with the
     appropriate production from the grammar.
     
     
   • Indicating where you expect shift/reduce conflicts to occur.
   
   [If you can, try to do this without constructing the sets of items that you would expect to
   find in each state!]
   
   
2. Write an unambiguous grammar for the language defined in part 1, that makes it absolutely
   clear what parse-tree should correspond to a string like x|z*y.
   
   Note that there are no prescribed precedences in the specification above! You can choose
   any disambiguating rules that you want, as long as the grammar is unambiguous and
   defines the same language as in part 1. Be careful, though, to explain how you claim your
   rules work on some simple examples.
   
   
3. Consider the simple regular expression (ac)*(ab)*. One way of formulating the language
   generated by this expression as a context-free grammar is
   
      S       →   AC AB
      AB    →   AB  a b
      AB    →  
      AC    →   AC  a c
      AC    →  
   
   Unfortunately, this grammar is not LALR(1); that is, the grammar gives rise to shift/reduce
   conflicts when fed to a LALR(1) parser generator like Jacc. Provide three slight
   reformulations of the grammar, especially regarding the encoding of repetition, and
   indicate whether any of these alternatives result in a grammar that is easier to parse using
   LALR(1) techniques.
   
   Tip: treat the AB and AC nonterminals separately!