- Thread starter
- #1

- Apr 14, 2013

- 4,047

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$.

- Thread starter mathmari
- Start date

- Thread starter
- #1

- Apr 14, 2013

- 4,047

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$.

- Admin
- #2

- Mar 5, 2012

- 8,774

Hey yourself!

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$.

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?

- Thread starter
- #3

- Apr 14, 2013

- 4,047

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?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?

- Admin
- #4

- Mar 5, 2012

- 8,774

Yep.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?

- Thread starter
- #5

- Apr 14, 2013

- 4,047

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?

- Admin
- #6

- Mar 5, 2012

- 8,774

Well, I can't find "dilemma" with Google in this context.

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?

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.

- Thread starter
- #7

- Apr 14, 2013

- 4,047

Ok!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.

And something else. The part $$S \to Sa|b$$ contains left recursive production, right?

How can I eliminate it?

- Admin
- #8

- Mar 5, 2012

- 8,774

Well, you can't usually eliminate a recursion.Ok!

And something else. The part $$S \to Sa|b$$ contains left recursive production, right?

How can I eliminate it?

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?

- Thread starter
- #9

- Apr 14, 2013

- 4,047

This production rule creates strings of the form $baa....aa$,so can we rephrase this rule to be right recursive as followed?What kind of strings can your production rule make?

Can you rephrase it to be right recursive?

$$S \to b|bS', S' \to aS'| \varnothing $$

- Admin
- #10

- Mar 5, 2012

- 8,774

Yep!!!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 $$

Note that you can limit yourself to:

$$S \to bS', S' \to aS'| \varnothing $$

- Thread starter
- #11

- Apr 14, 2013

- 4,047

Nice!!! Thanks a lot!!!Yep!!!

Note that you can limit yourself to:

$$S \to bS', S' \to aS'| \varnothing $$