patternMinor
Construct non-recursive predictive parser for grammar $S \to Aa \mid b A c \mid Bc \mid bBa, A \to d, B \to d$
Viewed 0 times
midpredictivenonparserbbarecursivegrammarforconstruct
Problem
In the grammar for S production two bodies have same starting symbol
$ S \to Aa \mid b A c \mid Bc \mid bBa $
So i removed the left factoring from those two productions
$ S \to bC$
$ C \to Ac Bc$
Then I calculated first and follow for all of them. Then i constructed parse table, but for the entry on state S when input symbol is d there are two possible productions
$ A \to d$
$ B \to d$
I don't have much knowledge about what to do when there is a conflict in the entry for this table, if I'm completely wrong please help me to find solution
$ S \to Aa \mid b A c \mid Bc \mid bBa $
So i removed the left factoring from those two productions
$ S \to bC$
$ C \to Ac Bc$
Then I calculated first and follow for all of them. Then i constructed parse table, but for the entry on state S when input symbol is d there are two possible productions
$ A \to d$
$ B \to d$
I don't have much knowledge about what to do when there is a conflict in the entry for this table, if I'm completely wrong please help me to find solution
Solution
You're looking at an implicit conflict in your grammar. Given
\begin{align*}
S &\to Aa \mid b A c \mid Bc \mid bBa \\
A &\to d \\
B &\to d,
\end{align*}
we know that a pair of rules $S \to \alpha$ and $S \to \beta$ "conflicts" if ${\rm first}(\alpha) \cap {\rm first}(\beta) \ne \varnothing$, that is, if the set of characters that can be immediately "consumed" by the productions $\alpha$ and $\beta$ intersects.
Intuitively, you can try to visualize what a 1-lookahead recursive-descent parser would do in the state $S$ when it sees a character that can shift to multiple productions. Say you're parsing $S$, and you encounter a symbol $b$; if you're given no other knowledge about the string you are parsing, then it's entirely uncertain whether you should take the $S \to bAc$ path or the $S \to bBa$ path. Therefore, for a grammar to be "well-formed" for a 1-lookahead recursive descent parser, we have to make sure that the grammar contains no such conflicts.
This also generalizes nicely for the case of n-lookahead. We say that two rules $S \to \alpha$ and $S \to \beta$ conflicts in the first $n$ words if ${\rm first}_n (\alpha) \cap {\rm first}_n(\beta) \ne \varnothing$. Intuitively, an n-lookahead parser will be confused if for a particular string of $n$-words, it can shift into multiple productions as well.
Now, besides the obvious conflict between $bAc$ and $bBa$, you should realize that ${\rm first}(Aa) = \{d\} = {\rm first}(Bc)$, so the rules $Aa$ and $Bc$ also conflicts. We can easily resolve this by "inlining" the nonterminals $A$ and $B$ directly and do the same left-factoring trick you did before:
\begin{align}
S &\to da \mid bdc \mid dc \mid bda \\
&\Rightarrow ({\rm left ~ factoring}) \\
S &\to d X \mid bd X \\
X &\to a \mid c
\end{align}
Computing the 1-lookahead predictive table results in
$$
\begin{array}{ccccc}
& a & b & c & d \\
S & & \to bdX && \to dX\\
X & \to a & & \to c
\end{array}
$$
which corresponds to the algorithm
\begin{align*}
S &\to Aa \mid b A c \mid Bc \mid bBa \\
A &\to d \\
B &\to d,
\end{align*}
we know that a pair of rules $S \to \alpha$ and $S \to \beta$ "conflicts" if ${\rm first}(\alpha) \cap {\rm first}(\beta) \ne \varnothing$, that is, if the set of characters that can be immediately "consumed" by the productions $\alpha$ and $\beta$ intersects.
Intuitively, you can try to visualize what a 1-lookahead recursive-descent parser would do in the state $S$ when it sees a character that can shift to multiple productions. Say you're parsing $S$, and you encounter a symbol $b$; if you're given no other knowledge about the string you are parsing, then it's entirely uncertain whether you should take the $S \to bAc$ path or the $S \to bBa$ path. Therefore, for a grammar to be "well-formed" for a 1-lookahead recursive descent parser, we have to make sure that the grammar contains no such conflicts.
This also generalizes nicely for the case of n-lookahead. We say that two rules $S \to \alpha$ and $S \to \beta$ conflicts in the first $n$ words if ${\rm first}_n (\alpha) \cap {\rm first}_n(\beta) \ne \varnothing$. Intuitively, an n-lookahead parser will be confused if for a particular string of $n$-words, it can shift into multiple productions as well.
Now, besides the obvious conflict between $bAc$ and $bBa$, you should realize that ${\rm first}(Aa) = \{d\} = {\rm first}(Bc)$, so the rules $Aa$ and $Bc$ also conflicts. We can easily resolve this by "inlining" the nonterminals $A$ and $B$ directly and do the same left-factoring trick you did before:
\begin{align}
S &\to da \mid bdc \mid dc \mid bda \\
&\Rightarrow ({\rm left ~ factoring}) \\
S &\to d X \mid bd X \\
X &\to a \mid c
\end{align}
Computing the 1-lookahead predictive table results in
$$
\begin{array}{ccccc}
& a & b & c & d \\
S & & \to bdX && \to dX\\
X & \to a & & \to c
\end{array}
$$
which corresponds to the algorithm
function parseS(words):
if next word is b:
// -> bdX
consume b; consume d; parseX(rest)
else if next word is d:
// -> dX
consume d; parseX(rest)
else: error
function parseX(words):
if next word is a: consume a
else if next word is c: consume c
else: errorCode Snippets
function parseS(words):
if next word is b:
// -> bdX
consume b; consume d; parseX(rest)
else if next word is d:
// -> dX
consume d; parseX(rest)
else: error
function parseX(words):
if next word is a: consume a
else if next word is c: consume c
else: errorContext
StackExchange Computer Science Q#65793, answer score: 3
Revisions (0)
No revisions yet.