Java Reference
In-Depth Information
32. Define the quasi-identical states of an LR(1) parsing machine to be
those states whose kernel productions are identical. Such states are
distinguished only by the lookahead symbols associated with their pro-
ductions. Given the LR(1) machine built for Exercise 31, complete the
following:
(a) List the quasi-identical states of the LR(1) machine.
(b) Merge each set of quasi-identical states toobtainanLALR(1)machine.
33. Starting with the CFSM built in Exercise 4, compute the LALR(1) looka-
head information. Compare the resulting LALR(1) machine with the
machine obtained in Exercise 32.
34. Which of the grammars in Exercise 10 are LR(1)? Justify your answers.
35. Consider a grammar G and its LALR(1) construction. Suppose that a
shift
reduce conflict occurs in G 's LALR(1) construction. Prove that G 's
LR(1) construction also contains a shift
/
/
reduce conflict.
36. Describe an algorithm that computes LALR(1) and then splits states as
needed in an attempt to address conflicts. Take note of the issue raised
in Exercise 35.
37. Using a grammar for the C programming language, try to extend the
syntax to allow nested function definitions. For example, you might
allow function definitions to occur inside any compound statement.
Report on any di
culties you encounter and discuss possible solutions.
Justify the particular solution you adopt.
38. Using a grammar for the C programming language, try to extend the
syntax so that a compound statement can appear to compute a value. In
other words, allow a compound statement to appear wherever a simple
constant or identifier could appear. Semantically, the value of a com-
pound statement could be the value associated with its last statement.
Report on any di
culties you encounter and discuss possible solutions.
Justify the particular solution you adopt.
39. In Figure 6.3, Marker 2 pushes a state on the parse stack. In the bottom-
up parse shown in Figures 6.6 and 6.7, stack cells show both the state
and the input symbol causing the state's shift onto the stack. Explain
why the input symbol's presence in the stack cell is superfluous.
 
Search WWH ::




Custom Search