4 - Computer Science and Engineering



CSCE ___25 Compiler Construction

Name ____________________________

SID _____________________

Homework # 1, chapter 4

Wednesday, February 19, 2003

4.1

Write pseudocode for term and factor corresponding to the pseudocode for exp in Section 4.1.2 (page 150) that constructs a syntax tree for simple arithmetic expressions.

4.3

Given the grammar

statement → assign-stmt | call-stmt | other

assign-stmt → identifier := exp

call-stmt → identifier ( exp-list )

write pseudocode to parse this grammar by recursive-descent.

4.5b

Show the actions of an LL(1) parser that uses Table 4.4 (page 163) to recognize the following arithmetic expression: 3*(4–5+6)

4.10

Consider the following grammar of simplified C declarations:

declaration → type var-list

type → int | float

var-list → identifier, var-list | identifier

a. Left factor this grammar.

b. Construct First and Follow sets for the nonterminals of the resulting grammar.

c. Show that the resulting grammar is LL(1).

d. Construct the LL(1) parsing table for the resulting grammar.

e. Show the actions of the corresponding LL(1) parser, given the input string

int x, y, z.

4.15

Define the operator [pic] on two sets of token strings S1 and S2 as follows:

S1 [pic] S2 = { First(xy) | x [pic] S1, y [pic] S2 }

a. Show that, for any two nonterminals A and B, First(AB) = First(A) [pic] First(B).

b. Show that the two conditions of the theorem on page 178 can be replaced by the single condition: if A → α and A → β, then (First(α) [pic] Follow(A)) ∩ (First(β) [pic] Follow(A)) is empty.

4.21

Given the grammar A → a A a | є,

a. Show that this grammar is not LL(1).

b. An attempt to write a recursive-descent parser for this grammar is represented by the following pseudocode.

procedure A ;

begin

if token = a then

getToken ;

A ;

if token = a then getToken;

else error ;

else if token $ then error ;

end A ;

Show that this procedure will not work correctly.

c. A backtracking recursive-descent parser for this language can be written but requires the use of an unGetToken procedure that takes a token as a parameter and returns that token to the front of the stream of input tokens. It also requires that the procedure A be written as a Boolean function that returns success or failure, so that when A calls itself, it can test for success before consuming another token, and so that, if the A → a A a choice fails, the code can go on to try the A → є alternative. Rewrite the pseudocode of part (b) according to this recipe, and trace its operation on the string aaaa$.

4.25

The panic mode error recovery for the simple arithmetic expression grammar, as described in Section 4.5.1, still suffers from some drawbacks. One is that the while-loops that test for operators should continue to operate under certain circumstances. For instance, the expression (2) (3) is missing its operator in between the factors, but the error handler consumes the second factor without restarting the parse. Rewrite the pseudocode to improve its behavior in this case.

4.27

Rewrite the LL(1) parsing algorithm of Figure 4.2 (page 155) to implement full panic mode error recovery, and trace its behavior on the input (2+-3)*4-+5

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download