Compiler-As-2

Question 1

Given the set of tokens (pay attention to the underline "_ ") and the following CFG grammar:

and answer the following questions. Show the detail of each step.

1. Use the grammar to do left-most and right-most derivation on the input "" and draw the parse tree. (12 pt)

Left-most derivation:

Right-most derivation:

Left-Most Derivation

E

σ

_

P

（

E

）

A

I

=

I

id

lit

r

Right-Most Derivation

E

σ

_

P

（

E

）

A

I

=

I

id

lit

r

2. Eliminate the left recursions. (6 pt)

There is only one production rule that has left recursion, which is . We can eliminate it by introducing a new non-terminal symbol and rewrite the grammar as follows:

Eliminate the left recursions：

Due to ; Therefore,

can be simplified as follows:


Rewrite the grammar as follows:

3. Base on the grammar without left recursions from Q2, left factorize the grammar. (6 pt)

There are several productions that have common prefixes:

We can left factorize the grammar as follows:

And it can be simplified as follows:

Rewrite the grammar as follows:

4. Base on the grammar from Q3, find the set and the set. (10 pt)

First set

For all terminals:
For
For
For
For
For
For
Final First set:

Follow set:
is the start symbol,
For
For
For
For
For
For

These are terminal symbols. So, Follow() is only influenced by the productions involving .

Final Follow set:

5. Base on the grammar from Q3, construct the parsing table. (6 pt)

parsing table

6. Base on the original grammar construct the DFA from the set of items (18 pt)

Construct the corresponding augmented grammar

Construct the items:

E

σ

r

I0

I1

I2

I3

For nothing can be done

For

For

E

σ

r

Unsupported markdown: list

x

I0

I1

I2

I3

I4

I5

For

For

E

σ

r

Unsupported markdown: list

x

P

A

I

id

lit

E

σ

r

I0

I1

I2

I3

I4

I5

I6

I7

I8

I9

I10

I{11}

For

For nothing can be done

For

For nothing can be done
For nothing can be done
For nothing can be done

E

σ

r

Unsupported markdown: list

x

P

A

I

id

lit

E

σ

r

（

^

=

I0

I1

I2

I3

I4

I5

I6

I7

I8

I9

I{10}

I{11}

I{12}

I{13}

I{14}

For

For

For

E

σ

r

Unsupported markdown: list

x

P

A

I

id

lit

E

σ

r

（

^

=

E

σ

r

A

I

id

lit

I

id

lit

I0

I1

I2

I3

I4

I5

I6

I7

I8

I9

I{10}

I{11}

I{12}

I{13}

I{14}

I{15}

I{16}

I{17}

For

For nothing can be done
For nothing can be done

E

σ

r

Unsupported markdown: list

x

P

A

I

id

lit

E

σ

r

（

^

=

E

σ

r

A

I

id

lit

I

id

lit

）

I0

I1

I2

I3

I4

I5

I6

I7

I8

I9

I{10}

I{11}

I{12}

I{13}

I{14}

I{15}

I{16}

I{17}

I{18}

For

E

σ

r

Unsupported markdown: list

x

P

A

I

id

lit

E

σ

r

（

^

=

E

σ

r

A

I

id

lit

I

id

lit

）

x

I0

I1

I2

I3

I4

I5

I6

I7

I8

I9

I{10}

I{11}

I{12}

I{13}

I{14}

I{15}

I{16}

I{17}

I{18}

I{19}

For

E

σ

r

Unsupported markdown: list

x

P

A

I

id

lit

E

σ

r

（

^

=

E

σ

r

A

I

id

lit

I

id

lit

）

x

E

σ

r

I0

I1

I2

I3

I4

I5

I6

I7

I8

I9

I{10}

I{11}

I{12}

I{13}

I{14}

I{15}

I{16}

I{17}

I{18}

I{19}

I{20}

For nothing can be done

Here is the list of sets of items.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

7. Convert the DFA from Q6 to an parsing table. (15 pt)

parsing table
0
1
2
3
4
5 11
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8. Use the parsing table to parse "". Show the configuration and the output for each step. (10 pt)

Stack Input Output

Question 2

Given the following grammar:

9. Show that the grammar is ambiguous. (6 pt)

The grammar is ambiguous if there is a sentence in from which it is possible to construct multiple parse trees (using any type of derivation).

For example the sentence can be derived in two different ways:

Left-Most Derivation-1

E

E

Unsupported markdown: list

E

E

Unsupported markdown: list

E

id

id

id

Left-Most Derivation-2

E

E

Unsupported markdown: list

E

id

E

Unsupported markdown: list

E

id

id

Obviously, the sentence can be derived in two different ways, which means the grammar is ambiguous.

10. Find a sentence in the language such that the sentence is ambiguous but left-most derivation and right-most derivation can produce a same parse tree. You need to prove your answer. (9 pt)

For example the sentence can be derived in two different ways:

Left-Most Derivation:

  6. x

Right-Most Derivation:

Left-Most Derivation

E

E

Unsupported markdown: list

E

E

Unsupported markdown: list

E

id

id

id

Right-Most Derivation

E

E

Unsupported markdown: list

E

E

Unsupported markdown: list

E

id

id

id

Table Of Contents
Compiler-As-2
Question 1
1. Use the grammar to do left-most and right-most derivation on the input "" and draw the parse tree. (12 pt)
2. Eliminate the left recursions. (6 pt)
3. Base on the grammar without left recursions from Q2, left factorize the grammar. (6 pt)
4. Base on the grammar from Q3, find the set and the set. (10 pt)
First set
For all terminals:
For
For
For
For
For
For
Final First set:
Follow set:
is the start symbol,
For
For
For
For
For
For
Final Follow set:
5. Base on the grammar from Q3, construct the parsing table. (6 pt)
6. Base on the original grammar construct the DFA from the set of items (18 pt)
7. Convert the DFA from Q6 to an parsing table. (15 pt)
8. Use the parsing table to parse "". Show the configuration and the output for each step. (10 pt)
Question 2
Given the following grammar:
9. Show that the grammar is ambiguous. (6 pt)
10. Find a sentence in the language such that the sentence is ambiguous but left-most derivation and right-most derivation can produce a same parse tree. You need to prove your answer. (9 pt)