Welcome to our community

Be a part of something great, join today!

Left Recursive productions

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Hey! :eek:

Does the following part of a grammar contains left recursive productions?
$$S \to aSb$$

A left recursive production is of the form $I \to IA|B$.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
Hey! :eek:

Does the following part of a grammar contains left recursive productions?
$$S \to aSb$$

A left recursive production is of the form $I \to IA|B$.
Hey yourself! :p

From wiki:
In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s productions (‘alternatives’) either immediately (direct/immediate left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites to r again.

Is S either directly or indirectly the left-most symbol in its production?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Hey yourself! :p

From wiki:
In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s productions (‘alternatives’) either immediately (direct/immediate left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites to r again.

Is S either directly or indirectly the left-most symbol in its production?
Since at the left and at the right side of $S$ is a symbol, $S$ is not the left-most symbol in its production, so the production is not left recursive, is it?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
Since at the left and at the right side of $S$ is a symbol, $S$ is not the left-most symbol in its production, so the production is not left recursive, is it?
Yep.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Nice! :eek:

Could you also tell me if the production $S \to aSa|bSb|c$ has a dilemma?
We have dilemma when $I \to rK$ and $I \to rL$.

The production $S \to aSa|bSb|c$ means that $S \to aSa$, $S \to bSb$, $S \to c$, is this of the form above? At the first two cases there is the same symbol $S$ at the right side of the production. Or does it have to have only the same terminal symbols to have dilemma?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
Nice! :eek:

Could you also tell me if the production $S \to aSa|bSb|c$ has a dilemma?
We have dilemma when $I \to rK$ and $I \to rL$.

The production $S \to aSa|bSb|c$ means that $S \to aSa$, $S \to bSb$, $S \to c$, is this of the form above? At the first two cases there is the same symbol $S$ at the right side of the production. Or does it have to have only the same terminal symbols to have dilemma?
Well, I can't find "dilemma" with Google in this context.
But yeah, it would need to have the same left-most terminal symbol.

Typical reason why we would like to know, is to be able to uniquely decide, based on the next symbol on the input, which rule we should apply.
That makes for an unambiguous language with a one-token-look-ahead.
As a consequence, it's relatively easy to create a parser for it.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Well, I can't find "dilemma" with Google in this context.
But yeah, it would need to have the same left-most terminal symbol.

Typical reason why we would like to know, is to be able to uniquely decide, based on the next symbol on the input, which rule we should apply.
That makes for an unambiguous language with a one-token-look-ahead.
As a consequence, it's relatively easy to create a parser for it.
Ok! :eek:
And something else. The part $$S \to Sa|b$$ contains left recursive production, right?
How can I eliminate it?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
Ok! :eek:
And something else. The part $$S \to Sa|b$$ contains left recursive production, right?
How can I eliminate it?
Well, you can't usually eliminate a recursion.
But you can convert it to a right recursion, which is needed to turn a grammar into a regular grammar (that is easy to recognize by a deterministic state machine).

What kind of strings can your production rule make?
Can you rephrase it to be right recursive?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
What kind of strings can your production rule make?
Can you rephrase it to be right recursive?
This production rule creates strings of the form $baa....aa$,so can we rephrase this rule to be right recursive as followed?
$$S \to b|bS', S' \to aS'| \varnothing $$
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
This production rule creates strings of the form $baa....aa$,so can we rephrase this rule to be right recursive as followed?
$$S \to b|bS', S' \to aS'| \varnothing $$
Yep!!!
Note that you can limit yourself to:
$$S \to bS', S' \to aS'| \varnothing $$
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047