Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1465

Re: First vs Predict and LL(*)

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

First vs Predict and LL(*) alexander.morou@gmail.com - 2015-01-07 02:09 -0800
  Re: First vs Predict and LL(*) alexander.morou@gmail.com - 2015-01-07 08:37 -0800
  Re: First vs Predict and LL(*) Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2015-01-07 23:04 +0100
    Re: First vs Predict and LL(*) Alexander Morou <alexander.morou@gmail.com> - 2015-01-09 00:37 -0600
      Re: First vs Predict and LL(*) Alexander Morou <alexander.morou@gmail.com> - 2015-01-09 12:47 -0600
      Re: First vs Predict and LL(*) Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2015-01-09 23:35 +0100
  First vs Predict and LL(*) "SLK Mail" <slkpg4@gmail.com> - 2015-01-07 20:40 -0800
  Re: First vs Predict and LL(*) Alexander Morou <alexander.morou@gmail.com> - 2015-01-22 01:07 -0600
    Re: First vs Predict and LL(*) Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2015-01-22 21:46 +0100
    Re: First vs Predict and LL(*) Alexander Morou <alexander.morou@gmail.com> - 2015-01-23 01:16 -0600

csiph-web