Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border1.nntp.dca1.giganews.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: Alexander Morou Newsgroups: comp.compilers Subject: Re: First vs Predict and LL(*) Date: Fri, 9 Jan 2015 12:47:02 -0600 Organization: Compilers Central Lines: 38 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-01-008@comp.compilers> References: <15-01-003@comp.compilers> <15-01-005@comp.compilers> <15-01-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 1420920199 45979 2001:470:1f07:1126:0:676f:7373:6970 (10 Jan 2015 20:03:19 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 10 Jan 2015 20:03:19 +0000 (UTC) Keywords: parse, LL(1) Posted-Date: 10 Jan 2015 15:03:19 EST 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:1465 > If the source is "uCDPL" then a follow stack would be insufficient > in determining the next valid token, unless you ignored failures > in a rule when an accept state is reached and let the parent > rule figure it out by rewinding. Based on the above, the requirements > could change based on the entire stack, if there were other rules > which introduced other requirements, the parse stack would be a > determining factor on what was next. > > Is the above contrived example simple to calculate the Follow for? I might add, ANTLR 4, in looking after writing the above response, does what I surmised a possible solution would be: For each rule construct a state machine, uisng the tree context that represents your parse as you go, note the state that the parser was in when that tree was being constructed. This provides a traversable structure that gives you a per-rule state to know what elements are valid next. The predict method likely steps through the source input and walks up the tree evaluating the look-ahead as necessary with multiple state machines (or perhaps a single unified state machine.) This would require the states across all rules to use a shared state pool, but that's a simple enough matter. The only complaint I have on this is: ANTLR's source is not human alterable. And it's not terribly performant, though Terrence Parr did mention that was a secondary focus. 32KB worth of data in an altered version of the contrived example yielded 250ms for roughly 32KB of data, increasing the number of iterations increases time requirements linearly (320KB would be 2.5 seconds). Another limit seems to be ANTLR 4 allows direct left recursion but indirect left recursion is strangely not allowed. Likely a rewrite rule in effect. I'd prefer the state machines be expanded into the code so that this logic is laid out and easier for someone to infer the intent by stepping through the code. Someone pipe in if the view of how ANTLR 4 works is incorrect.