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

Groups > comp.compilers > #1466

Re: First vs Predict and LL(*)

Show key headers only | View raw

Alexander Morou schrieb:
> On Wednesday, January 7, 2015 7:41:39 PM UTC-6, Hans-Peter Diettrich wrote:


>>> longest prevails, or first come first serve.  So if you want [A-F] to be
>>> parsed in a 'Q' token, you'd have to specify it first, unless other letters
>>> are parsed that make 'Q' parse a longer sub-string.
>> Here I feel a need for some annotation, that tells the (human) generator
>> of a sentence how to go ahead, in order to reach the intended goal. I
>> think that you found the same need already, too?
>
> Could you perhaps give me a run-down of what the annotation would
> clarify?

It should make clear to the *user*, what's the intent behind and usage
of unclear syntax.


> I think the confusion here is that I didn't specify what my
> understanding was, so here goes: k in an LL(k) parser refers to the
> number of TOKENS of look-ahead necessary to deterministically predict
> what's next and parse the appropriate rule from that decision.

ACK

>  In situations where 'k' is unbound because the same rule is referenced
> on multiple avenues, and that rule uses repetitions, you yield an
> unbound 'k' requirement.  This would also occur when two rules are
> equivalent, in that they utilize the same set of tokens, which may or
> may not use repetitions.  The second case is much much trickier, from
> what I can gather.  The computational time necessary to find them is
> *fairly* high.

I wouldn't consider LL(*) as a valid LL grammar, because it looks
impossible to write an parser generator for such a grammar. In such
cases an LR parser were more efficient and economic WRT stack size.

> The other question that seems to puzzle me is what do you do in
> situations where the current rule is in an acceptable state,
> it has possible further tokens, but what do you do when what is
> valid next is also valid in the calling rule?

That's known as e.g. "dangling else", and such ambiguities IMO also are
invalid in LL grammars, or must be solved by additional rules.

IMO the requirement for a low and bounded k, and for an unambiguous
grammar, helps in constructing languages that are both easy to write and
easy to parse.

DoDi

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