# Left Recursive productions

#### mathmari

##### Well-known member
MHB Site Helper
Hey!

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
Hey!

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!

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
Hey yourself!

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
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
Nice!

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
Nice!

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
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!
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
Ok!
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
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
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
Yep!!!
Note that you can limit yourself to:
$$S \to bS', S' \to aS'| \varnothing$$
Nice!!! Thanks a lot!!!