Index


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.

EXERCISE 12.1
start example

Construct the regular expression that corresponds to the state transition diagram shown in Figure 12.1.

click to expand
Figure 12.1: State transition diagram.
end example
 
EXERCISE 12.2
start example

Prove that regular sets are closed under intersection. Present a method for constructing a DFA with an intersection of two regular sets.

end example
 
EXERCISE 12.3
start example

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

ˆ’

end example
 
EXERCISE 12.4
start example

Obtain the canonical collection of sets of LR(1) items for the following grammar:

end example
 
EXERCISE 12.5
start example

Construct an LR(1) parsing table for the following grammar:

end example
 
EXERCISE 12.6
start example

Construct an LALR(1) parsing table for the following grammar:

end example
 
EXERCISE 12.7
start example

Construct an SLR(1) parsing table for the following grammar:

end example
 
EXERCISE 12.8
start example

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 
end example
 
EXERCISE 12.9
start example

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 
end example
 
EXERCISE 12.10
start example

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      } 
end example
 
EXERCISE 12.11
start example

Write the syntax-directed translations to go along with the LR parser for the following:

end example
 
EXERCISE 12.12
start example

Write the syntax-directed translations to go along with the LR parser for the following:

end example
 
EXERCISE 12.13
start example

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.

  1. while a = b do x = y + z

  2. a + b = c

  3. a *+ b + c

end example
 
EXERCISE 12.14
start example

Comment on whether the following statements are true or false:

  1. 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.

  2. Every subset of a regular set is also a regular set.

  3. In a top-down backtracking parser, the order in which various alternatives are tried may affect the language accepted by the parser.

  4. 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.

  5. Grammar ambiguity necessarily implies ambiguity in the language generated by that grammar.

  6. Every name is added to the symbol table during the lexical analysis phase irrespective of the semantic role played by each name.

  7. 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.

  8. In any nonambiguous grammar without useless symbols, the handle of a given right-sentential form is unique.

end example
 



Algorithms for Compiler Design
Algorithms for Compiler Design (Electrical and Computer Engineering Series)
ISBN: 1584501006
EAN: 2147483647
Year: 2005
Pages: 108
Authors: O G Kakde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net