I'm reading about context free grammar and i recognized how to eliminate the left recursion but i did not find out what is the problem with left recursion?? can any one explain
Thanks in advance
The left recursion brings in infinite looping during the implementation. Therefore, it has to be eliminated.
Dear Ahmed
Refer Kenneth C. Louden, Compiler Construction and Practice book. it is having a very good explanation. As far i understood,it means when we are receiving token and if grammar is left recursive we have no idea when to stop. A well known example
A--> A alpha | beta
Consider we are reading a stream of token beta alpha alpha..........
How many alpha we want to process, we do not know current token we are pointing is beta, and we can lookahead to some extend in parsing algorithm. to avoid that situation we try to remove left recursion.
Kindly correct me if i am wrong
Dear Ahmed
the problem with left recursion, from a computational linguistics point of view, is that it leads to infinite recursion, as mentioned in other posts. And, sadly, linguists do tend to write an awful lot of such rules, as the example below shows (a very naive DCG grammar for English relative clauses). If you 'consult' this grammar with swi-prolog, all will apparently run smooth because swi-prolog can deal with such recursive rules appropriately. If you submit the following goal "s([the,man,that,he,knows,sleeps],[]).", you'll get "true" as an answer. But, if you ask swi-prolog to search for more results (";"), then you'll get an "Out of local stack" error because of the left-recursion.
The general strategy is "transform your left-recursive rules into right-recursive ones". It means you must tweak your grammar to eliminate such left-recursive rules and transform them into right-recursive ones, with the help of an intermediate non-terminal (cf. for eg. http://web.cs.wpi.edu/~kal/PLT/PLT4.1.2.html).
From an algorithmic point of view, different approaches have been published, in order to deal with such left-recursive rules (as said earlier, this is how linguists spontaneously write formal grammars). If you're looking for algorithms, you can have a look at Bob Moore's paper http://research.microsoft.com/pubs/68869/naacl2k-proc-rev.pdf.
s --> np, vp.
np --> det, n.
np --> np, relc.%this is a left-recursive rule
relc --> pror, pro, vt.
vp --> vi.
vp --> vt, np.
det --> [the].
n --> [man].
pro --> [he].
pror --> [that].
vt --> [knows].
vi --> [sleeps].
- Badges
- Science topic
- Similar topics
- Social Psychology
- Attitude