Copyright © 2006 Gradiance Corporation.

Bottom-Up Parsing

---

---

shift-reduce parsing, viable prefixes.

---

1.

Consider the grammar: S → aSa | bSb | aa | bb A shift-reduce parser works by identifying the handle of each right-sentential form and replacing it by the head of the corresponding production. In this question, we indicate the handle of a right-sentential form by surrounding it by square brackets [...]. Which of the following shows a right-sentential form of the above grammar with the handle properly marked?

a)	abab[aababa]
b)	ababaS[ababa]
c)	ababbS[bbaba]
d)	abab[bSb]baba

2.	Perform a shift-reduce parse of the input aaa+a*+ according to the grammar: S → SS+ | SS* | a Show the stack and remaining input at each stage, using the form ($stack, input$). Then, identify the pair that is NOT a stage of the shift-reduce parse.

a)	($SS, a+a*+$)
b)	($a, aa+a*+$)
c)	($SS+, $)
d)	($SSa*, +$)

3.	Perform a shift-reduce parse of the input aa+aa*+ according to the grammar: S → SS+ | SS* | a Show the stack and remaining input at each stage, using the form ($stack, input$). Then, identify the pair that is NOT a stage of the shift-reduce parse.

a)	($Sa, +aa*+$)
b)	($Sa+, aa*+$)
c)	($SS, +aa*+$)
d)	($Sa, a*+$)

4.	Consider the augmented grammar: S' → S S → aSb | ab Describe the set of viable prefixes for this grammar. Then, identify one of the viable prefixes from the following list:

a)

aaabb

b)

aa

c)

aSbbb

d)

aaaSbb

5.

Consider the grammar: S → aSb | ab A shift-reduce parser works by identifying the handle of each right-sentential form and replacing it by the head of the corresponding production. In this question, we indicate the handle of a right-sentential form by surrounding it by square brackets [...]. Which of the following shows a right-sentential form of the above grammar with the handle properly marked?

a)	[aaaaab]bbbb
b)	aaaa[abbbbb]
c)	aaaaa[S]bbbbb
d)	aaaa[aSb]bbbb