Subject: Re: context-free?

From: "Rosen, Brian" <[email-masked]>
Date: Thu, 14 Dec 2000 12:55:09 -0500

It was not brought up, or if it was, it was forgotten.

If we had discussed it, I would have tried to make it context free,
by disallowing explicit language tokens as other identifiers, and
I would have gotten arguments from some who think that they must
have complete freedom to define termination.

Given where we are, we have to make it context dependent.

Brian

> -----Original Message-----
> From: Troy Cauble [mailto:[email-masked]]
> Sent: Thursday, December 14, 2000 10:57 AM
> To: [email-masked]
> Subject: Re: context-free?
>
>
> Paul Long wrote:
> >
> > Troy,
> >
> > On what do you base your answer? Is this stated anywhere or
> is this simply your opinion? Context-dependent grammars are
> usually more difficult to parse... correctly. :-)
>
> [TROY]
> It is not stated anywhere.  That's an implementation detail.
> It's the opinion of someone who's written a parser (me).
> Your example below demonstrates the problem.  NAME and other
> relatively freeform value tokens are indistinguishable from
> keyword tokens such as AddToken without positional context.
>
>
> >
> > If you are right, I am concerned that those implementations
> that do not use a simple, most-likely hand-coded, predictive
> parser but instead use a parser generator where the lexer and
> parser are separate, e.g., lex/yacc, risk incorrect parsing
> due to the uncoupling between these two components. The
> reason is that most programming languages are context-free
> (C, C++, and Pascal are context-free; PL/I is not) so most
> implementors presumably have more experience parsing
> context-free grammars, e.g., programming languages, than
> context-dependent grammars, such as our Megaco text encoding.
> Unless implementors take special care to pass the context
> from the parser back to the lexer, e.g., by having yacc
> actions shift between lex states, their products will most
> likely parse
>
>
> [TROY]
> That is a concern for people using lex/yacc.  But they'll probably
> see the problems before they finish, if not before they start.
>
> I did successfully use bison & flex.  I won't tell all my secrets
> but I'll give one hint:  Be careful with that concept of passing
> "context from the parser back to the lexer" as yacc and bison are
> *lookahead* parsers.
>
> I would guess that others have worked around this issue with
> parser generators too.  Even though the grammar is context-dependent,
> for me, parser generators were too useful to do without.
>
> -troy
>
>
> >
> >     A = A { M { L { } } }
> >
> > incorrectly as
> >
> >     AddToken EQUAL AddToken LBRKT ...
> > or
> >     NAME EQUAL NAME LBRKT ...
> >
> > rather than
> >
> >     AddToken EQUAL NAME LBRKT ...
> >
> > This is just a head-up for implementors to make sure that
> your parser will handle the Megaco ABNF as a
> context-_dependent_ grammar and to add test cases like the
> above as a test case to assure correctness.
> >
> > Paul Long
> > ipDialog, Inc.
> >
> > ---------- Original Message ----------------------------------
> > From: Troy Cauble <[email-masked]>
> > Reply-To: Troy Cauble <[email-masked]>
> > Date:         Wed, 13 Dec 2000 19:18:06 -0500
> >
> > >Paul Long wrote:
> > >>
> > >> Does the text encoding use a context-free grammar? This
> cannot be discerned
> > >> from the ABNF. For example, does "A" always represent
> the AddToken and never
> > >> a name, e.g., a digitMapName?
> > >>
> > >> Paul Long
> > >> ipDialog, Inc.
> > >
> > >No.
>