Re: First vs Predict and LL(*)

Alexander Morou <alexander.morou@gmail.com>
Fri, 9 Jan 2015 12:47:02 -0600

          From comp.compilers

Related articles
First vs Predict and LL(*) alexander.morou@gmail.com (2015-01-07)
Re: First vs Predict and LL(*) alexander.morou@gmail.com (2015-01-07)
Re: First vs Predict and LL(*) DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2015-01-07)
First vs Predict and LL(*) slkpg4@gmail.com (SLK Mail) (2015-01-07)
Re: First vs Predict and LL(*) alexander.morou@gmail.com (Alexander Morou) (2015-01-09)
Re: First vs Predict and LL(*) alexander.morou@gmail.com (Alexander Morou) (2015-01-09)
Re: First vs Predict and LL(*) DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2015-01-09)
Re: First vs Predict and LL(*) alexander.morou@gmail.com (Alexander Morou) (2015-01-22)
Re: First vs Predict and LL(*) DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2015-01-22)
Re: First vs Predict and LL(*) alexander.morou@gmail.com (Alexander Morou) (2015-01-23)
| List of all articles for this month |

From: Alexander Morou <alexander.morou@gmail.com>
Newsgroups: comp.compilers
Date: Fri, 9 Jan 2015 12:47:02 -0600
Organization: Compilers Central
References: 15-01-003 15-01-005 15-01-007
Keywords: parse, LL(1)
Posted-Date: 10 Jan 2015 15:03:19 EST

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



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.