Chapter 4, Problem 18E

Explanation of Solution

a.

Context-free grammar for “case” or “switch” statements:

• The context-free grammar (CFG) generates the context-free language (CFL).
• Production rules of CFG are simple replacement.
• Parsing is a method of finding a tree which has a given yield.
• Rules can also be applied in reverse to check whether a string is grammatically correct according to the grammar.

In the following grammar, the input is error-free if and only if $\text{S}\text{.dup = }\varnothing$:

$\begin{array}{c}\text{S }\to \text{ switch }\left(\text{ expr }\right)\left\{\text{ arm\_list }\right\}⊳\text{ S}\text{.dup := arm\_list}\text{.dups}\\ \text{arm\_list }\to \text{ case\_list stmt more\_arms}\\ ⊳\text{ arm\_list}\text{.out := case\_list}\text{.out }\cup \text{ more\_arms}\text{.out}\\ ⊳\text{ arm\_list}\text{.dups := case\_list}\text{.dups }\cup \text{ more\_arms}\text{.dups}\\ \cup \left(\text{case\_list}\text{.out }\cap \text{ more\_arms}\text{.out}\right)\end{array}$

$\begin{array}{c}\text{case\_list }\to \text{ case expr : more\_cases}\\ ⊳\text{ case\_list}\text{.out := }\left\{\text{expr}\text{.val}\right\}\cup \text{ more\_cases}\text{.out}\\ ⊳\text{ case\_list}\text{.dups := more\_cases}\text{.dups }\cup \\ \left(\left\{\text{expr}\text{.val}\right\}\cap \text{ more\_cases}\text{.out}\right)\end{array}$

$\begin{array}{c}\text{more\_cases }\to \text{ case\_list}\\ ⊳\text{ more\_cases}\text{.out := case\_list}\text{.out }⊳\text{ more\_cases}\text{.dups := case\_list}\text{.dups}\\ \text{more\_cases }\to \in \\ ⊳\text{ more\_cases}\text{.out := }\varnothing ⊳\text{ more\_arms}\text{.dups := }\varnothing \end{array}$

$\begin{array}{c}\text{more\_arms }\to \text{ arm\_list}\\ ⊳\text{ more\_arms}\text{.out := more\_list}\text{.out }⊳\text{ more\_arms}\text{.dups := arm\_list}\text{.dups}\\ \text{more\_arms }\to \in \\ ⊳\text{ more\_arms}\text{.out := }\varnothing ⊳\text{ more\_arms}\text{.dups := }\varnothing \end{array}$

Explanation of Solution

b.

Replacing the semantic functions with action routines:

• Action routines are a semantic function that the user instructs the compiler to execute at a specific part in the parse.
• An ad hoc translation scheme which is inserted with parsing takes the form of a set of action routine.
• Many parser generators allow the user to identify action routines.

Assumes exponents in the input are all positive integers. The grammar is as follows:

$\begin{array}{c}\text{S }\to \text{ switch }\left(\text{expr}\right)\text{{arm\_list} {S}\text{.dups := arm\_list}\text{.dups}}\\ \text{arm\_list }\to \text{ case\_list stmt more\_arms}\\ \text{ {arm\_list}\text{.out := case\_list}\text{.out }\cup \text{ more\_arms}\text{.out;}\\ \text{arms\_list}\text{.dups := case\_list}\text{.dups }\cup \text{ more\_arms}\text{.dups}\\ \cup \left(\text{case\_list}\text{.out }\cap \text{ more\_arms}\text{.out}\right)\text{} }\end{array}$

$\begin{array}{c}\text{case\_list }\to \text{ case expr : more\_cases }\\ \text{{ case\_list}\text{.out := }\left\{\text{expr}\text{.val}\right\}\cup \text{more\_cases}\text{.out }\\ \text{}\text{(}\left\{\text{exp}\text{.val}\right\}\cap \text{ more\_cases}\text{.out) }\end{array}$

$\begin{array}{c}\text{more\_cases }\to \text{ case\_list}\\ \text{ {more\_cases}.\text{out := case\_list}.\text{out; more\_cases}\text{.dups := case\_list}\text{.dups} }\\ \to \in \left\{\text{more\_cases}\text{.out := }\varnothing ;\text{ more\_cases}\text{.dups := }\varnothing \right\}\end{array}$

$\begin{array}{c}\text{more\_arms }\to \text{ arm\_list}\\ \text{ {more\_arm}.\text{out := arm\_list}.\text{out; more\_arms}\text{.dups := arm\_list}\text{.dups} }\\ \to \in \left\{\text{more\_arms}\text{.out := }\varnothing ;\text{ more\_arms}\text{.dups := }\varnothing \right\}\end{array}$