Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/#!/StackCompSci/status/266764308946493440
changed formatting, made beginning sound friendlier
Source Link
edit approved Nov 5, 2012 at 1:53
Merbs
edit approved Nov 5, 2012 at 1:53
Merbs
  • 1.2k
  • 1
  • 11
  • 21

InI am having difficulty with one of the Dragon Book there are exercises for section 2.4:

Exercise 2.4.1: Construct recursive-descent parsers, starting within the following grammarsDragon Book:

c) $S \rightarrow 0S1\ |\ 01$

Exercise 2.4.1(c): Construct recursive-descent parsers, starting with the following grammars:

$$S \rightarrow 0S1\ |\ 01$$

ButYet, for a constructing a feasible parser, it is required that for two productions $A \rightarrow \alpha\ |\ \beta$, their FIRST sets are disjoint. But since:

$FIRST(0S1) = \{ 0 \}$ and $FIRST(01) = \{ 0 \}$

$$FIRST(0S1) = \{ 0 \} \hspace{2em}\&\hspace{2em} FIRST(01) = \{ 0 \}$$

this is not the case. How does one proceed here? Just state it is not feasible due to the stated conflict or is there alternative approach, like modfying the grammar?

In the Dragon Book there are exercises for section 2.4:

Exercise 2.4.1: Construct recursive-descent parsers, starting with the following grammars:

c) $S \rightarrow 0S1\ |\ 01$

But for a constructing a feasible parser, it is required that for two productions $A \rightarrow \alpha\ |\ \beta$, their FIRST sets are disjoint. But since:

$FIRST(0S1) = \{ 0 \}$ and $FIRST(01) = \{ 0 \}$

this is not the case. How does one proceed here? Just state it is not feasible due to the stated conflict or is there alternative approach, like modfying the grammar?

I am having difficulty with one of the exercises in the Dragon Book:

Exercise 2.4.1(c): Construct recursive-descent parsers, starting with the following grammars:

$$S \rightarrow 0S1\ |\ 01$$

Yet, for constructing a feasible parser, it is required that for two productions $A \rightarrow \alpha\ |\ \beta$, their FIRST sets are disjoint. But since:

$$FIRST(0S1) = \{ 0 \} \hspace{2em}\&\hspace{2em} FIRST(01) = \{ 0 \}$$

this is not the case. How does one proceed here? Just state it is not feasible due to the stated conflict or is there alternative approach, like modfying the grammar?

Source Link
Mahoni
Mahoni
  • 131
  • 3

Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

In the Dragon Book there are exercises for section 2.4:

Exercise 2.4.1: Construct recursive-descent parsers, starting with the following grammars:

c) $S \rightarrow 0S1\ |\ 01$

But for a constructing a feasible parser, it is required that for two productions $A \rightarrow \alpha\ |\ \beta$, their FIRST sets are disjoint. But since:

$FIRST(0S1) = \{ 0 \}$ and $FIRST(01) = \{ 0 \}$

this is not the case. How does one proceed here? Just state it is not feasible due to the stated conflict or is there alternative approach, like modfying the grammar?