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

Groups > comp.compilers > #1460 > unrolled thread

First vs Predict and LL(*)

Back to article view | Back to comp.compilers

Contents

  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

#1460 — First vs Predict and LL(*)

I took about a three year hiatus (multiple sets of consecutive months without
working on it) from a language-centric project and I'm having the fun of
acclimating myself to my own work.

Up front: I'm self taught, so certain language concepts might be beyond my
current level of understanding, so *please* don't assume I know something
simple.

In my process of regaining my legs in the project, I re-read some common
articles, and noticed: I don't see the point of differentiating First vs
Predict sets.

The type of project I'm writing is a LL(*) parser builder , which aims to scan
ahead and yield a state which denotes which path is the most logical path to
follow next.

To accomplish this, my basic approach is to track the source of a given symbol
referenced by a state within a rule's deterministic state machine.

This can lead to situations where a given rule has tens to hundreds of
possible sources, especially if the nesting goes 20+ deep (expression
precedence defined through left-recursive rules, versus defining operator
precedence sugar in the grammar definition language.)

So far I'm to the point where I've collapsed common routes into a single view,
so if '(' is available through two possible parse paths, but both are the same
outgoing target at the current look ahead, it considers them the same.

An example:
A ::= B | C; //::= defines rules
B ::= D | E;
D ::= '(' P ')';
E ::= '(' Q ')';
C ::= @'O'*; //'@' means case insensitive.
P := [0-9A-Fa-f]+; //:= defines tokens
Q := [:Ll:]+; //:Xx: means unicode character classes as defined by .NET's
standard sets.

'A' would contain '(' within its first set, but it would be observed through
'B' and only 'B', so it would be valid to parse 'B' always when '(' is
encountered at the start of 'A'.  B's definition would have to look ahead
further, for the sake of simplicity, token-level ambiguities are resolved by
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.

(Next step will involve collecting all states which observe a given symbol and
looking ahead further, then further, and so on, until a decision is possible.
I might find this is computationally implausible.  Left-recursive rules will
be handled through loops that parse alternate paths until the rule itself can
be pushed to the stack, once this is done, it can safely re-parse alternate
paths until there are no more symbol reductions.  This is what I do by hand in
the Grammar Definition Language's parser.)

The main question: what's the functional intent behind the First vs. Follow
sets, and the goal of the project I'm writing is a recursive descent parser,
from what's described above, is my classification of LL(*) accurate?

[toc] | [next] | [standalone]

#1461

On Wednesday, January 7, 2015 7:48:02 AM UTC-6, alexand...@gmail.com wrote:
> ...The main question: what's the functional intent behind the First vs. Follow
> sets, and the goal of the project I'm writing is a recursive descent parser,
> from what's described above, is my classification of LL(*) accurate?

To Clarify: what's the functional difference between First and PREDICT sets.

Tying early in the AM is a bad idea sometimes.

[toc] | [prev] | [next] | [standalone]

#1462

alexander.morou@gmail.com schrieb:

> In my process of regaining my legs in the project, I re-read some common
> articles, and noticed: I don't see the point of differentiating First vs
> Predict sets.
>
> The type of project I'm writing is a LL(*) parser builder , which aims to scan
> ahead and yield a state which denotes which path is the most logical path to
> follow next.

Here some mostly practical considerations:

"Traditional" parsers distinguish between an lexer/tokenizer and the
parser. The lexer accepts characters and outputs terminal tokens, which
then are interpreted by the parser. That's the way to go in e.g.
programming languages, where the language construction should prevent
any unwanted/unexpected misinterpretation. Remember that grammars and
regular expressions are fine for telling a machine how to interpret
input, but not for humans *preparing* that input. LL(1) is perfect for
communication between humans and machines, higher degrees make things
more complicated for both; machines then have to use stacks or parallel
processing, while humans may be annoyed by unexpected syntax errors.

Merging both, into an "scannerless parser", opens a can of worms, at
least when the input is prepared by humans and should be readable
(parseable) also by other people. One of the most annoying "features" of
a scannerless parser IMO is the handling of token separators. You can
find out easily, how complicated the grammar for some well known
programming language will become, as soon as whithespace handling is
moved out of the lexer.

But of course there exist use cases for scannerless parsers, in detail
for languages other than programming languages.

> To accomplish this, my basic approach is to track the source of a given symbol
> referenced by a state within a rule's deterministic state machine.
>
> This can lead to situations where a given rule has tens to hundreds of
> possible sources, especially if the nesting goes 20+ deep (expression
> precedence defined through left-recursive rules, versus defining operator
> precedence sugar in the grammar definition language.)

Right, precedence rules are a weak point in formal grammars. Here the
human factor suggests (to me) some formal annotation, in favor of deeply
nested rules, for the implementation of operator precedence, grouping etc.


> So far I'm to the point where I've collapsed common routes into a single view,
> so if '(' is available through two possible parse paths, but both are the same
> outgoing target at the current look ahead, it considers them the same.
>
> An example:
> A ::= B | C; //::= defines rules
> B ::= D | E;
> D ::= '(' P ')';
> E ::= '(' Q ')';
> C ::= @'O'*; //'@' means case insensitive.
> P := [0-9A-Fa-f]+; //:= defines tokens
> Q := [:Ll:]+; //:Xx: means unicode character classes as defined by .NET's
> standard sets.
>
> 'A' would contain '(' within its first set, but it would be observed through
> 'B' and only 'B', so it would be valid to parse 'B' always when '(' is
> encountered at the start of 'A'.  B's definition would have to look ahead
> further, for the sake of simplicity, token-level ambiguities are resolved by
> 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?

In LL(1) the rules D and E could be reduced into
   DE ::= '(' (P|Q) ')';
what I'd understand better. I prefer to use EBNF as much as possible, in
order to reduce the number of rules in an LL grammar. Also PEG
parsers/grammars are easier to understand to me, when it comes to the
clarification of ambiguities; a PEG parser will use the first
interpretation, found in the grammar, so that it's easier to find out
how to make the parser consider some alternative interpretation.

> (Next step will involve collecting all states which observe a given symbol and
> looking ahead further, then further, and so on, until a decision is possible.
> I might find this is computationally implausible.  Left-recursive rules will
> be handled through loops that parse alternate paths until the rule itself can
> be pushed to the stack, once this is done, it can safely re-parse alternate
> paths until there are no more symbol reductions.  This is what I do by hand in
> the Grammar Definition Language's parser.)

IMO left recursion should be resolved by EBNF notation or, if not easily
possible, an LR parser should be used instead of an LL parser.

> The main question: what's the functional intent behind the First vs. Follow
> sets,

Follow sets are useful in the implementation/emulation of left
recursion, when the first token in a rule can be empty (epsilon). Then
both the First set of the first (optional) and following token are
acceptable for that non-terminal. Once the RD parser enters that
subroutine, when will it return from there?

The decision is easy as long as the First and Follow sets are disjoint
(LL(1)), then the loop over tokens in the First set is left when a
different token is found, which consequently must be a member of the
First set of the next token.

When both sets overlap (LL(1) First/First conflict), descending
immediately into the same subroutine will yield an endless loop. That's
why I add a rule to my LL parsers, that every call *must* consume at
least one terminal token, before descending and (possibly) recursing. In
the simplest implementation the parser remembers the current position in
the input stream, after consuming its first (assumed) terminal, then
tries to parse the first (optional) token/alternative. In case of an
error it returns to the input position and tries the next alternative.
This model can be optimized by using an stack or queue of tokens, in
order to eliminate repeated lexing of the offending terminals.

Other models can be used as well, but they may lead easily to LR
parsers, which have little or no use for recursive descent at all. E.g.
LALR parsers use the First sets (SLR also the Follow sets) in order to
abbreviate the search for the applicable production, i.e. to reduce the
size of their LR token stack.

> and the goal of the project I'm writing is a recursive descent parser,
> from what's described above, is my classification of LL(*) accurate?

I don't see your classification of LL(*) :-(

I'd say that an LL(k) parser definitely knows how to proceed after
inspection of at most k terminals, but I may be wrong here - number of
terminals or tokens?

DoDi

[toc] | [prev] | [next] | [standalone]

#1464

On Wednesday, January 7, 2015 7:41:39 PM UTC-6, Hans-Peter Diettrich wrote:
> alexander.morou@gmail.com schrieb:
> Merging both, into an "scannerless parser", opens a can of worms, at
> least when the input is prepared by humans and should be readable
> (parseable) also by other people. One of the most annoying "features" of
> a scannerless parser IMO is the handling of token separators. You can
> find out easily, how complicated the grammar for some well known
> programming language will become, as soon as whithespace handling is
> moved out of the lexer.

> But of course there exist use cases for scannerless parsers, in detail
> for languages other than programming languages.

Apologies, the focus wasn't to yield a scanner-less parser.  To my
understanding, the functional intent behind First, Follow, Predict is
to provide a contextual basis from which the parser can denote issues
with the source in the event that an unexpected token appears on the
look-ahead stack.

By LL(*) I'm referring to situations where tokens are parsed by a
lexer and the rules are parsed by a parser.  The Star aspect comes
into play when you have two rules, say 'Field' and 'Method', both
productions refer to an optional 'Attributes' which starts with a
required '['.

The "First set" of each rule would be identical which would likely
mean that LL(1) would be out at this point.  The issue comes into
play when you consider that Attributes can contain 'x' many actual
tokens.

In evaluating all avenues for a given production, you'll note the
requirement for '[' all begin in 'Attributes'.  The solution in this
instance is to have 'Attributes' be parsed in the rule that can
accept either a 'Field' or a 'Method' and have that pushed onto
the look-ahead stack as the next symbol for consumption.

I think, if done properly, this would remove the need to back-track
or memoize the structure of the 'Attributes' reference, since you've
decidedly figured out that it's always correct to have it there.

> > To accomplish this, my basic approach is to track the source of a given symbol
> > referenced by a state within a rule's deterministic state machine.
> >
> > This can lead to situations where a given rule has tens to hundreds of
> > possible sources, especially if the nesting goes 20+ deep (expression
> > precedence defined through left-recursive rules, versus defining operator
> > precedence sugar in the grammar definition language.)
>
> Right, precedence rules are a weak point in formal grammars. Here the
> human factor suggests (to me) some formal annotation, in favor of deeply
> nested rules, for the implementation of operator precedence, grouping etc.

I actually prefer the recursive approach.  It's unambiguous and doesn't
require any special call-outs.  Situations where Left Recursion are
detected, in theory can be solveable by the symbol approach mentioned
above: when a left-recursive case is encountered, replace the standard
parse method with a loop in which:
1. Failure only truly occurs if zero matches occur.
2. Using the symbol of the rule predict the most logical avenue.
  a. If multiple avenues, look ahead further.
  b. If zero avenues during look-ahead, and no matches have yet
been found, report an error; otherwise, exit gracefully.

This is also, of course, assuming my understanding of LL(k) and/or
LL(1) parsers is accurate, it would mean it's somewhat of a
pseudomorph of LR and LL-styled parsers due to the reduction and
placement of the rule on the stack.

If what I'm describing is something else entirely, someone please
note as such.

> > So far I'm to the point where I've collapsed common routes into a single view,
> > so if '(' is available through two possible parse paths, but both are the same
> > outgoing target at the current look ahead, it considers them the same.
> >
> > An example:
> > A ::= B | C; //::= defines rules
> > B ::= D | E;
> > D ::= '(' P ')';
> > E ::= '(' Q ')';
> > C ::= @'O'*; //'@' means case insensitive.
> > P := [0-9A-Fa-f]+; //:= defines tokens
> > Q := [:Ll:]+; //:Xx: means unicode character classes as defined by .NET's
> > standard sets.
> >
> > 'A' would contain '(' within its first set, but it would be observed through
> > 'B' and only 'B', so it would be valid to parse 'B' always when '(' is
> > encountered at the start of 'A'.  B's definition would have to look ahead
> > further, for the sake of simplicity, token-level ambiguities are resolved by
> > 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?

If I build a decision tree, in which all avenues point to 'x',
you would know, not only that 'x' is next, but what productions
require it.  If 'x' is a rule, then you know, at the very least,
to parse that rule. Though I'm sure there's some technical aspect I
am not fully aware of yet as I'm still writing the thing and I started
in 2008...

> In LL(1) the rules D and E could be reduced into
>    DE ::= '(' (P|Q) ')';
> what I'd understand better. I prefer to use EBNF as much as possible, in
> order to reduce the number of rules in an LL grammar. Also PEG
> parsers/grammars are easier to understand to me, when it comes to the
> clarification of ambiguities; a PEG parser will use the first
> interpretation, found in the grammar, so that it's easier to find out
> how to make the parser consider some alternative interpretation.

This ties into not adhering to a LL(1) compiler, LL(k) for a particular
k tokens wouldn't apply if the common rule required 'n' tokens and 'n'
is only determinable at the runtime of the parser.


> When both sets overlap (LL(1) First/First conflict), descending
> immediately into the same subroutine will yield an endless loop. That's
> why I add a rule to my LL parsers, that every call *must* consume at
> least one terminal token, before descending and (possibly) recursing. In
> the simplest implementation the parser remembers the current position in
> the input stream, after consuming its first (assumed) terminal, then
> tries to parse the first (optional) token/alternative. In case of an
> error it returns to the input position and tries the next alternative.
> This model can be optimized by using an stack or queue of tokens, in
> order to eliminate repeated lexing of the offending terminals.

Initially I posted 'difference between first and follow', but a later
message, that you likely didn't see, clarified: 'The difference between
'first and PREDICT'.  SLK Mail already clarified this point, but for the
sake of the topic project at hand: I'll be using a follow stack (which
it turns out ANTLR 3 uses one to do this same thing) which will contain
what is next relative to the rules currently in play.


> > and the goal of the project I'm writing is a recursive descent parser,
> > from what's described above, is my classification of LL(*) accurate?
>
> I don't see your classification of LL(*) :-(
>
> I'd say that an LL(k) parser definitely knows how to proceed after
> inspection of at most k terminals, but I may be wrong here - number of
> terminals or tokens?

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

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?

Let's use a contrived example:
S ::= A 'C'? 'X'? 'P'+ 'L';
A ::= B 'C' 'D'? 'P'?;
B ::= 'u' ('C'? 'O')?;

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?

[toc] | [prev] | [next] | [standalone]

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

[toc] | [prev] | [next] | [standalone]

#1466

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

[toc] | [prev] | [next] | [standalone]

#1463

The main question: what's the functional intent behind the First vs. Follow
sets, and the goal of the project I'm writing is a recursive descent
parser,
 from what's described above, is my classification of LL(*) accurate?


FIRST is the set of starting terminals derivable from a nonterminal.
FOLLOW is the same iff the nonterminal goes to null, so the FIRST that
follows the nonterminal. PREDICT is the combination of FIRST and FOLLOW.

PREDICT is used to predict which production to use based on the lookahead
terminal.

See http://slkpg.t15.org/llkparse.html for way more detail than you
probably want.

[toc] | [prev] | [next] | [standalone]

#1496

After much more effort, I've finally got what I think is an effective
predictor, but will be able to know more once I can emit the code.  I
didn't want to get ahead of myself because it's one thing to predict
that ten paths all use 'attributes' so parse attributes and reduce
those tokens, but another to resolve 'Dangling Else' style ambiguities.

From the prediction mechanism above, I can effectively know all paths
that lead into a rule, even if it's nested 39 levels deep, but it runs
me into my next dilemma: the dangling else.

So far I have an effective strategy for detecting them, though someone
please pipe in and tell me if I'm short sighted on my approach:
For Every Rule 'x', gather every edge node 'e' within its automation
which contains outgoing transitions.  Then compare these outgoing
transitions with the transitions of the state 's' which is just after
the state 'c' which called rule 'x' .  If there is a symbolic collision
between the two, you have a dangling else ambiguity, naturally it's not
enough to consider just that initial state 's' because it could also be
an edge state and the rule which called its parent would need
considered as well.

This brings me to my next point: what if the point of ambiguity leads
to a situation where the calling rule's tie for that symbol is a
requirement for the parse, but the edge state is optional?  Granted you
have already noted a slight ambiguity, and with most languages, the
dangling else is known to be attached to the innermost rule.  In the
mentioned situation that won't work, if you include it in the innermost
rule's context, you would fail to parse the calling rule's states that
follow.

I've included here a situation that mimics this, which was discovered
in detecting this ambiguity.  The example is an excerpt from a language
which is a derivative of C#:

    #Root        "MemberName";
    #GrammarName "TestGrammar";

    MemberName                                ::=
        (Type:TypePart; '.')?
        Identifier:Name;                        ;


    /* ---------------------------------------- *\
    |* B.2.2 Types                              *|
    \* ---------------------------------------- */
    TypeArgumentList ::=
        '<' Type:Arguments; (',' Type:Arguments;)* '>';

    Type                                     ::=>
        ReferenceType                           ;

    ReferenceType                            ::=>
        NonArrayType                            |
        ArrayType                               ;


    NonArrayType                             ::=>
        StructType                              |
        ClassType                               ;

    ArrayType                                 ::=
        NonArrayType:ElementType;
            RankSpecifier:DimensionInfo;+       ;

    ClassType                                ::=>
        TypeName                                ;

    TypeName                                 ::=>
        NamespaceOrTypeName                     ;

    NamespaceOrTypeName                       ::=
        (
            QualifiedAliasMember:AliasPart;     |
            SimpleName:Names;
        ) ('.' SimpleName:Names;)*              ;


    QualifiedAliasMember                      ::=
        Identifier:AliasName; "::"
        SimpleName:Name;                        ;

    SimpleName                                ::=
        Identifier:Name;
        TypeArgumentList:TypeParameters;?       ;

    StructType                               ::=>
        IntegralDataTypes                       |
        EnumBaseTypes                           |
        NullableType                            ;

    NullableType                              ::=
        Type:NonNullableType; '?'               ;

    RankSpecifier                             ::=
        '[' ',':Rank;* ']';

    Identifier$                                :=
        IdentifierOrKeyword                     |
        '@' IdentifierOrKeyword                 ;

    UnicodeEscapeSequence                      :=
        "\\u" HexChar{4}                        ;

    IdentifierStartCharacter                   :=
        LetterCharacter                         |
        '_'                                     |
        UnicodeEscapeSequence                   ;

    IdentifierOrKeyword                        :=
        IdentifierStartCharacter
        IdentifierPartCharacter*                ;

    IdentifierPartCharacter                    :=
        IdentifierPartCharacterNoEscape         |
        UnicodeEscapeSequence                   ;

    IdentifierPartCharacterNoEscape            :=
        LetterCharacter                         |
        CombiningCharacter                      |
        DecimalDigitCharacter                   |
        ConnectingCharacter                     |
        CombiningCharacter                      |
        FormattingCharacter                     ;

    LetterCharacter                            :=
        [:Lu::Ll::Lt::Lm::Lo::Nl:]              ;

    CombiningCharacter                         :=
        [:Mn::Mc:]                              ;

    DecimalDigitCharacter                      :=
        [:Nd:]                                  ;

    ConnectingCharacter                        :=
        [:Pc:]                                  ;

    FormattingCharacter                        :=
        [:Cf:]                                  ;

    HexChar                                    :=
        [0-9A-Fa-f]                             ;

    StaticTokens                               :=
        '.':Period;                             |
        "::":AliasSeparator;                    |
        '[':LeftSquareBracket;                  |
        ']':RightSquareBracket;                 |
        '<':TypeParameterStart;                 |
        '>':TypeParameterEnd;                   |
        '?':Nullable;                           |
        ',':ArrayRankSpecifier;                 ;

    IntegralDataTypes>Identifier               :=
                      "bool":Boolean;           |
                      "char":Char;              |
                   "decimal":Decimal;           |
                    "double":Double;            |
                     "float":Float;             |
                    "object":Object;            |
                    "string":String;            ;

    EnumBaseTypes>Identifier                   :=
                      "byte":Byte;              |
                       "int":Int32;             |
                      "long":Int64;             |
                      "uint":UInt32;            |
                     "ulong":UInt64;            |
                    "ushort":UInt16;            |
                     "sbyte":SByte;             |
                     "short":Int16;             ;

Since it wasn't obvious to me at first, I've included the ambiguity
context here:
{ Rule = {NamespaceOrTypeName ::= (QualifiedAliasMember:AliasPart; |
        SimpleName:Names;) ('.' SimpleName:Names;)*;},
 Edge = {StateValue: 1231},
 EdgeNode = {Rule Sub-Node for NamespaceOrTypeName at 1231},
 StartingPath = {
   MemberName::Type::ReferenceType::NonArrayType::ClassType::
     TypeName::[NamespaceOrTypeName]},
 TyingPath = {[MemberName(1193)]} }

{ and } denote enclosing scope of members following '='.
Node Paths refer to Rules by name, sub-states of rules
by Name(StateNumber).

Basically the MemberName's '.' following the Type and then the
Identifier would tie on the NamespaceOrTypeName's repetition
over ('.' SimpleName)*

The question I have is: given the context of what could be ambiguous,
couldn't you apply a similar prediction for determining which forward
rule to parse to the tail end of the equation?
The exception being, you couldn't simply consider the inner-most rule's
edges, you'd have to consider it a valid edge, if and only if the
parent rule's context is satisfied.  The initial state that represented
the terminal edge would be valid, but you'd advance and note where
a valid edge should have been, only to accept once the follow context
is satisfied...?

Any insight on this is helpful.  Grammar allows simple token inserts
of '.' | "::" to be directly in the rules, the definition of simple
tokens in a fixed alternation pattern below is understood and
rewritten.

Left recursion of Direct, Indirect, and Hidden allowed in parser
grammar.  Though I'm thinking what I allow is the cause of my
headaches.

On Fri, Jan 9, 2015 at 12:47 PM, Alexander Morou
<alexander.morou@gmail.com> wrote:
>
> > 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.

[toc] | [prev] | [next] | [standalone]

#1497

Alexander Morou schrieb:

> This brings me to my next point: what if the point of ambiguity leads
> to a situation where the calling rule's tie for that symbol is a
> requirement for the parse, but the edge state is optional?

I'd consider that an language error. As you already found out yourself,
your language is not easy to parse, so that I'd expect that will be
equally hard to write valid sentences, which then also are parsed in the
*intended* way.

DoDi

[toc] | [prev] | [next] | [standalone]

#1498

On Thursday, January 22, 2015 at 10:14:19 PM UTC-6,
    Hans-Peter Diettrich wrote:
> Alexander Morou schrieb:
>
> > This brings me to my next point: what if the point of ambiguity
> > leads to a situation where the calling rule's tie for that symbol
> > is a requirement for the parse, but the edge state is optional?
>
> I'd consider that an language error. As you already found out
> yourself, your language is not easy to parse, so that I'd expect
> that will be equally hard to write valid sentences, which then also
> are parsed in the *intended* way.

So a typical reaction to such an ambiguity would be to simplify the
grammar?

I originally followed the C# specification for the language to
construct the basic flow of the document.  In writing the code
to isolate ambiguities, I found a few I did not know about.

On such was the description of Object/Collection Initializers:
when the set between the curly braces ({ and }) is empty, it yielded
an ambiguity because both transitions yielded the same token sets.

Fixing that (allowing one path to be empty, the other not) it found
that there was another ambiguity between array initialization
and the same object initializer when the set is empty.

Those 'different rule same input stream' acceptance are a type of
ambiguity I'm not interested in allowing.  I'm not sure what you'd
classify this kind of overlap.


I think once I've constructed the means to work around the 'required
dangling ambiguity' (the predictive method mentioned earlier) I'll
need to flesh out the parser in full before I can say that the
automations properly represent the language.  There's a known ambiguity
within the base C# language that it's not detecting, which either
means:

    1. The algorithm predicting follow deadlock is incorrect
    2. The algorithm predicting the transition paths is
       incorrect, either because:
          a. I'm over agressively reducing the transition paths
             when a point of commonality is found that leads to
             parse the same sub-rule.
          b. I'm way off target in how to do this :-|
          c. Both a and b. :-(
    3. I made an error in translating the grammar into the my
       self-created grammar description language.
    4. Other changes to the grammar that deviated from the root
       resolved the ambiguity by providing further context.
       This is the least likely candidtate.
    5. I'm over simplifying the problem and the complex parse
       path necessary to isolate the ambiguity isn't attainable
       because all paths aren't considered.  This goes with 2.b.

Would there be any advantage to allowing the parser generator
to be able to resolve these types of 'required dangling ambiguities'?

While I agree that you could view the construction of such an ambiguity
to be a language description error, the means to which such a thing
would be resolved would ultimately be up to either: a
rewrite/simplification of the grammar, or allowing the tool to specify a
consistent means to resolving the issue itself.  Assuming a valid path
is decidable.  Though I wonder if the effort of doing this is worth
it...?

Insight more than welcome.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web