DOC

# Homework

By Edith Stone,2014-10-06 21:47
19 views 0
Homework

4.4

lexp?number | (op lexp-seq)

op?+|-|*

lexp-seq?lexp-seq, lexp | lexp Solution:

Function lexp: integer;

var temp: integer;

var op_kind: integer;

Begin

Case token of

(: match(();

Case token of

+: match(‘+);

op_ kind = PLUS;

-: match(‘-);

op_ kind = MINUS;

*: match(‘*);

op_ kind = MULTIPLICATION;

End case;

temp = lexp_seq(op_kind);

match());

return temp;

End case;

End lexp;

4.9 Consider the following grammar:

lexp?atom | list

atom ?number | identifier

list?(lexp-seq)

lexp-seq?lexp, lexp-seq | lexp 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 (a,(b,(2)),(c)).

[Solution]

a.

lexp?atom|list

atom ?number|identifier

list?(lexp-seq)

lexp-seq?lexp lexp-seq’

lexp-seq’?, lexp-seq|ε

b.

First(lexp)={number, identifier, ( )

First(atom)={number, identifier}

First(list)={( )

First(lexp-seq)={ number, identifier, ( )

First(lexp-seq’)={, , ε}

Follow(lexp)={, \$, } }

Follow(atom)= {, \$, } }

Follow(list)= {, \$, } }

Follow(lexp-seq)={\$, } }

Follow(lexp-seq’)={\$,} }

c. According to the defination of LL(1) grammar (Page 155), the resulting grammar is LL(1) as

each table entry has at most one production as shown in (d).

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

M[N,T] number identifer ( ) , \$

lexp?atom lexp?atom lexp?list Lexp

atom ?atom ? Atom

number identifier

list? List

(lexp-seq)

lexp-seq?lexp-seq?lexp-seq? Lexp-seq

lexp lexp-seq’ lexp lexp-seq’ lexp lexp-seq’

lexp-seq’lexp-seq’?, lexp-seq’?Lexp-seq’

?ε lexp-seq ε e. The actions of the parser given the string (a,(b,(2)),(c))

Parsing stack Input string Action

lexp-seq?lexp lexp-seq’ \$ lexp-seq (a,(b,(2)),(c))\$

lexp?list \$ lexp-seq’ lexp (a,(b,(2)),(c))\$

list?(lexp-seq) \$ lexp-seq’ list (a,(b,(2)),(c))\$ \$ lexp-seq’ ) lexp-seq ( (a,(b,(2)),(c))\$ match

lexp-seq?lexp lexp-seq’ \$ lexp-seq’ ) lexp-seq a,(b,(2)),(c))\$

lexp?atom \$ lexp-seq’ ) lexp-seq’ lexp a,(b,(2)),(c))\$

atom ?identifier \$ lexp-seq’ ) lexp-seq’ atom a,(b,(2)),(c))\$ \$ lexp-seq’ ) lexp-seq’ identifier a,(b,(2)),(c))\$ match

lexp-seq’?, lexp-seq \$ lexp-seq’ ) lexp-seq’ ,(b,(2)),(c))\$ \$ lexp-seq’ ) lexp-seq , ,(b,(2)),(c))\$ match

lexp-seq?lexp lexp-seq’ \$ lexp-seq’ ) lexp-seq (b,(2)),(c))\$

lexp?list \$ lexp-seq’ ) lexp-seq’ lexp (b,(2)),(c))\$

list?(lexp-seq) \$ lexp-seq’ ) lexp-seq’ list (b,(2)),(c))\$ \$ lexp-seq’ ) lexp-seq’)lexp-seq( (b,(2)),(c))\$ match

lexp-seq?lexp lexp-seq’ \$ lexp-seq’ ) lexp-seq’)lexp-seq b,(2)),(c))\$

lexp?atom \$ lexp-seq’ ) lexp-seq’)lexp-seq’lexp b,(2)),(c))\$

atom ?identifier \$ lexp-seq’ ) lexp-seq’)lexp-seq’atom b,(2)),(c))\$

\$ lexp-seq’ ) lexp-seq’)lexp-seq’identifier b,(2)),(c))\$ match

lexp-seq’?, lexp-seq \$ lexp-seq’ ) lexp-seq’)lexp-seq’ ,(2)),(c))\$

match \$ lexp-seq’ ) lexp-seq’)lexp-seq, ,(2)),(c))\$

lexp-seq?lexp lexp-seq’ \$ lexp-seq’ ) lexp-seq’)lexp-seq (2)),(c))\$

lexp?list \$ lexp-seq’ ) lexp-seq’)lexp-seq’lexp (2)),(c))\$

list?(lexp-seq) \$ lexp-seq’ ) lexp-seq’)lexp-seq’list (2)),(c))\$

match \$ lexp-seq’ ) lexp-seq’)lexp-seq’)lexp-seq( (2)),(c))\$

lexp-seq?lexp lexp-seq’ \$ lexp-seq’ ) lexp-seq’)lexp-seq’)lexp-seq 2)),(c))\$

lexp?atom \$ lexp-seq’ ) lexp-seq’)lexp-seq’)lexp-seq’lexp 2)),(c))\$

atom ?number \$ lexp-seq’ ) lexp-seq’)lexp-seq’)lexp-seq’atom 2)),(c))\$

match \$ lexp-seq’ ) lexp-seq’)lexp-seq’)lexp-seq’number 2)),(c))\$

lexp-seq’?ε \$ lexp-seq’ ) lexp-seq’)lexp-seq’)lexp-seq’ )),(c))\$

match \$ lexp-seq’ ) lexp-seq’)lexp-seq’) )),(c))\$

lexp-seq’?ε \$ lexp-seq’ ) lexp-seq’)lexp-seq’ ),(c))\$

match \$ lexp-seq’ ) lexp-seq’) ),(c))\$

lexp-seq’?, lexp-seq \$ lexp-seq’ ) lexp-seq’ ,(c))\$

match \$ lexp-seq’ ) lexp-seq, ,(c))\$

lexp-seq?lexp lexp-seq’ \$ lexp-seq’ ) lexp-seq (c))\$

lexp?list \$ lexp-seq’ ) lexp-seq’lexp (c))\$

list?(lexp-seq) \$ lexp-seq’ ) lexp-seq’list (c))\$

match \$ lexp-seq’ ) lexp-seq’)lexp-seq( (c))\$

lexp-seq?lexp lexp-seq’ \$ lexp-seq’ ) lexp-seq’)lexp-seq c))\$

lexp?atom \$ lexp-seq’ ) lexp-seq’)lexp-seq’lexp c))\$

atom ?identifier \$ lexp-seq’ ) lexp-seq’)lexp-seq’atom c))\$

match \$ lexp-seq’ ) lexp-seq’)lexp-seq’identifier c))\$

lexp-seq’?ε \$ lexp-seq’ ) lexp-seq’)lexp-seq’ ))\$

match \$ lexp-seq’ ) lexp-seq’) ))\$

lexp-seq’?ε \$ lexp-seq’ ) lexp-seq’ )\$

match \$ lexp-seq’ ) )\$

lexp-seq’?ε \$ lexp-seq’ \$

accept \$ \$

The Exercises of The Chapter Five

5.2 Consider the following grammar:

E?(L) | a

L?L,E|E

a. Construct the DFA of LR(1) items for this grammar.

b. Construct the general LR(1) parsing table.

c. Construct the DFA of LALR(1) items for this grammar.

d. Construct the LALR(1) parsing table. e. Describe any difference that might occur between the actions of a general LR(1) parser and an

LALR(1) parser.

[Solution]

Augment the grammar by adding the production: E’?E

a.

State 0: [E’?.E,\$] State 1: [E’?E.,\$]

[E?.(L),\$]

[E?.a,\$]

State 2: [E?(.L),\$] State 3: [E?a.,\$]

[L?.L,E , )]

[L?.E , )]

[L?.L,E , , ] State 4: [E?(L.),\$]

[L?.E , ,] [L?L.,E , )]

[E?.(L),)] [L?L.,E , , ]

[E?.a,)]

[E?.(L), ,] State 5: [L?E. , )]

[E?.a, ,] [L?E. , ,]

State 6: [E?(.L),)] State 7: [E?a.,)]

[E?(.L), ,] [E?a., ,]

[L?.L,E , )]

[L?.E , )] State 8: [E?(L).,\$]

[L?.L,E , , ]

[L?.E , ,] State 9: [L?L,.E , )]

[E?.(L),)] [E?.(L),)]

[E?.a,)] [E?.a,)]

[E?.(L), ,] [L?L,.E , ,]

[E?.a, ,] [E?.(L), ,]

[E?.a, ,]

State 10: [E?(L.),)] State 11: [L?L,E. , )]

[E?(L.), ,] [L?L,E. , ,]

[L?L.,E , )]

[L?L.,E , , ] State 12: [E?(L).,)]

[E?(L)., ,]

E

S0 S1

a (

S2 S3 L E

S5

( a S4 )

a S8

S6 S7 ( , ( L a

E , S10 S9

) E

S11 S12

b. r1: E?(L) r2: E? a r3: L?L,E r4: L?E

State Input Goto

( a ) , \$ L E 0 S2 S3 1 1 Accept 2 S6 S7 4 5 3 r2 4 S8 S9 5 r4 r4 6 S6 S7 10 5 7 r2 r2 8 r1 9 S6 S7 11 10 S12 S9 11 r3 r3 12 r1 r1

c.

State 0: [E’?.E,\$] State 1: [E’?E.,\$]

[E?.(L),\$]

[E?.a,\$]

State 2/6: [E?(.L),\$/)/,] State 3/7: [E?a.,\$/)/,]

[L?.L,E , )]

[L?.E , )]

[L?.L,E , , ] State 4/10: [E?(L.),\$/)/,]

[L?.E , ,] [L?L.,E , )]

[E?.(L),)] [L?L.,E , , ]

[E?.a,)]

[E?.(L), ,] State 5: [L?E. , )]

[E?.a, ,] [L?E. , ,]

State 8/12:[E?(L).,\$/)/,]

State 9: [L?L,.E , )] State 11: [L?L,E. , )]

[E?.(L),)] [L?L,E. , ,]

[E?.a,)]

[L?L,.E , ,]

[E?.(L), ,]

[E?.a, ,]

E S0 S1 a (

S2/6 S3/7

L E ( a S5 S4/10 a )

S8/12

,

S9

E

S11

d. r1: E?(L) r2: E? a r3: L?L,E r4: L?E

State Input Goto

( a ) , \$ L E 0 S2/6 S3/7 1 1 Accept 2/6 S2/6 S3/7 4/10 5 3/7 r2 r2 r2 4/10 S8/12 S9 5 r4 r4 8/12 r1 r1 r1 9 S2/6 S3/7 11 10 S8/12 S9 11 r3 r3

e. The consequence of using LALR(1) parsing over general LR(1) parsing is that , in the presence

of errors, some spurious reducation may be made before error is declared. (Page 225)

5.12 Show that the following grammar is LR(1) but not LALR(1):

A?c

B?c

[Solution]

r1: S?aAd r2: S?bBd r3: S?aBe r4: S?bAe r5: A?c r6: B?c

There is no conflicts in the following general LR(1) parsing:

state Input Goto

a b c d e \$ S A B 0 S2 S3 1 1 Accept 2 S6 4 5 3 S11 10 9 4 S7 5 S8 6 r5 R6 7 r1 8 r3 9 S12 10 S13 11 r6 r5 12 r2 13 r4

While there is a reduce-reduce conflict in the LALR(1) parsing table:

state Input Goto

a b c d e \$ S A B 0 S2 S3 1 1 Accept 2 S6/11 4 5 3 S6/11 10 9 4 S7 5 S8 6/11 r5/r6 r6/r5 7 r1 8 r3 9 S12 10 S13 12 r2 13 r4

Report this document

For any questions or suggestions please email
cust-service@docsford.com