Homework: Grammars and Parsing

Context-free grammars are notated with the following conventions in this homework:

1. Terminals are a lowercase letter or an ε for empty string
2. Nonterminals are an uppercase letter
3. Productions use an arrow, e.g., A → b
4. Starting symbol, by convention the nonterminal of the first production

An LR parsing table lists one state per row. The columns are the terminals in the language (the action table) and the nonterminals of the language (the goto table). Each entry in the action table is shifts a terminal, reduces a nonterminal, accepts the input. or results in an error (empty cell). The goto table takes a nonterminal a transition to a state or is empty, meaning an error.

1. All context-free languages are also regular languages
   • True
   • False
2. All regular languages are also context-free languages
   • True
   • False

3. Is the language specified by this context-free grammar also a regular language? If so, write a regular expression that describes the same language, otherwise write no.

   A → a A c

   A → ε

4. Write a derivation of the string "aacdbb" using the following grammar.

   A → a A b

   A → V

   V → c V

   V → d

5. Use the following parse table for the above grammar to show each step of the LR parsing algorithm for the string "aacdbb$" where $ is the end of input sentinel. The numbers after "reduce" are the production numbers from the previous grammar, starting from 1. Show the sequence of actions and gotos and optionally show the state stack and/or the derivation or syntax tree.

   State	a	b	c	d	$	A	V
   0	shift 2		shift 3	shift 6		goto 1	goto 4
   1					acc
   2	shift 2		shift 3	shift 6		goto 7	goto 4
   3			shift 3	shift 6			goto 5
   4	reduce 2	reduce 2	reduce 2	reduce 2	reduce 2
   5	reduce 3	reduce 3	reduce 3	reduce 3	reduce 3
   6	reduce 4	reduce 4	reduce 4	reduce 4	reduce 4
   7		shift 8
   8	reduce 1	reduce 1	reduce 1	reduce 1	reduce 1
   State	a	b	c	d	$	A	V