-4

Remove left recursion from following grammar :

Q.1 

S -> SXY | a
X -> xY | xX
Y -> Yy | epsilon

Q.2

P ->  P H 4 U | p
H -> h
U -> u | u P

I know the rules to remove left recursion, but I am confused. So if someone please post the answer of this grammar, it would be helpful.

Update from comment:

I know this 2 are left recursive grammar : 

S -> SXY | a
P -> P H 4 U | p

And I know how to remove left recursion from those grammars, but what about other grammars?

P -> P ... This is left recursive. 
P -> p ... Is this is also left recursive ?
Prune
  • 76,765
  • 14
  • 60
  • 81
Meena
  • 1
  • "I am confused" is not a problem description. Asking someone to give you the answer is cheating. SO is a place to get *help*: show us how far you got in the conversion, describe where you're stuck, and we'll get you over the hump. – Prune Mar 03 '16 at 00:15
  • I know this 2 are left recursive grammar : S -> SXY | a AND P -> P H 4 U | p And I know how to remove left recursion from that grammars but what about other grammars, Is it left recursive or not ? P -> P -> This is left recursive. P -> p -> Is this is also left recursive ? – Meena Mar 03 '16 at 00:26

1 Answers1

0

First of all, let's get the terminology straight: the four lines in your comment (which I added to the question) are grammar rules, not grammars. Each handles only one expansion; none of them provide a path from the start symbol S to a string of terminal symbols.

A left-recursive rule is one in which the expansion of the LHS, a non-terminal symbol (capital letter), can result in a longer string that begins with the same symbol. Thus, P -> P is not left-recursive, as the rule is meaningless. P -> p is not left-recursive, as it expands P, a non-terminal symbol, to p (lower-case), a terminal symbol.

You are correct that the first two rules are left-recursive.

Does that get you moving? I believe that it answers all of your outstanding specific questions.

Prune
  • 76,765
  • 14
  • 60
  • 81