Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: Alexander Morou Newsgroups: comp.compilers Subject: Left Recursive Examples for use with LL Parser Generator Date: Sun, 19 Jul 2015 04:20:14 -0500 Organization: Compilers Central Lines: 55 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-07-007@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: miucha.iecc.com 1437340585 40249 2001:470:1f07:1126:0:676f:7373:6970 (19 Jul 2015 21:16:25 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sun, 19 Jul 2015 21:16:25 +0000 (UTC) Keywords: parse, LL(1), question Posted-Date: 19 Jul 2015 17:16:25 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1575 After further evaluating the very early release of Oilexer, I've discovered a few things: 1. Handling Left Recursion in a LL(*) context is possible. 2. Handling Left Recursive Predictions is the hard part 3. Chicken Before Egg type issues are annoying, but there seems to be a finite set of variations to handling them (I think :) On some levels I found early assumptions about the result decisions in predictions were incorrect, but I'm slowly overcoming those. *If I may ask the assistance of others here for some examples of left recursive grammars that would require a prediction, it would be most appreciated. I could use these as a means to investigate the surrounding logic.* In situations where it is easily determined that a rule is 'x', where 'x' is left recursive, it appears that the left recursive mechanics I have in place handle this case without issue; however, in cases where the decision requires a prediction, the system falls apart, too quickly it tries to say which rule it is when left recursion requires much longer look-ahead. Here's an example that is solved easily: A ::= B C 'd' | E C 'f' ; B ::= 'x' 'y' ; E ::= 'x' 'y' ; C ::= 'c' | C 'c' ; In this example (sourced from http://www.cs.man.ac.uk/~pjj/cs212/ho/node19.html), E and B are identical productions, and you can't solve for which it is until you move past the 'x' and 'y' terminals, and past the C production. The prediction for A would look for x, then y, then it is deterministically in the left-recursive production C, parse C and put it on the stack, if you see d then the prediction says parse B within A, if you see f parse E. Both variations will skip parsing C because it's already on the symbol stack from the prediction on A. Here's an example that isn't as easy: A ::=> B | C | D; B ::= A 'b'; D ::= A 'd'; C ::= 'c'; T ::= A 'a' | B | C | D; In the above example, everything goes great until you hit T, which requires knowledge of which variation is valid to parse correctly. Right now it parses C (since A, B, C and D of T reduce to C after 'c') then it checks for 'a', 'b', or 'd', and only does so once. I can easily look at the state machine and introduce a repetition in the prediction to repeat the check until we hit either EOF, or 'a'. I just need more realistic examples to ensure the logic I put in place is sound.