The exercises that follow are designed to provide further examples of the concepts covered in this book. Their purpose is to put these concepts to work in practical contexts that will enable you, as a programmer, to better and more- efficiently use algorithms when designing your compiler.
Construct the regular expression that corresponds to the state transition diagram shown in Figure 12.1.
Prove that regular sets are closed under intersection. Present a method for constructing a DFA with an intersection of two regular sets.
Transform the following NFA into an optimal/minimal state DFA.
| 1 | ˆˆ | |
A | A, C | B | D |
B | B | D | C |
C | C | A, C | D |
D | D | A | ˆ’ |
Obtain the canonical collection of sets of LR(1) items for the following grammar:
Construct an LR(1) parsing table for the following grammar:
Construct an LALR(1) parsing table for the following grammar:
Construct an SLR(1) parsing table for the following grammar:
Consider the following code fragment. Generate the three-address -code for it.
if a < b then while c > d do x = x + y else do p = p + q while e <= f
Consider the following code fragment. Generate the three-address code for it.
for (i = 1; i <= 10; i++) if a < b then x = y + z
Consider the following code fragment. Generate the three-address-code for it.
switch a + b { case 1: x = x + 1 case 2: y = y + 2 case 3: z = z + 3 default: c = c -1 }
Write the syntax-directed translations to go along with the LR parser for the following:
Write the syntax-directed translations to go along with the LR parser for the following:
There are syntactic errors in the following constructs. For each of these constructs, find out which of the input's next tokens will be detected as an error by the LR parser.
while a = b do x = y + z
a + b = c
a *+ b + c
Comment on whether the following statements are true or false:
Given a finite automata M ( Q , & pound ; , , q , F ) that accepts L ( M ), the automata M 1 ( Q , , , q , ( Q ˆ’ F )) accepts L ( M ), where L ( M ) is complement of L ( M ). If M is an optimal or minimal state automata, then M 1 is also a minimal state automata.
Every subset of a regular set is also a regular set.
In a top-down backtracking parser, the order in which various alternatives are tried may affect the language accepted by the parser.
An LR parser detects an error when the symbol coming next in the input is not a valid continuation of the prefix of the input seen by the parser.
Grammar ambiguity necessarily implies ambiguity in the language generated by that grammar.
Every name is added to the symbol table during the lexical analysis phase irrespective of the semantic role played by each name.
Given a grammar with no useless symbols, but containing unit productions, if the unit productions are eliminated from the grammar, then it is possible that some of the grammar symbols in the resulting grammar may become useless.
In any nonambiguous grammar without useless symbols, the handle of a given right-sentential form is unique.