Subject: Re: context-free?

From: Christian Groves <[email-masked]>
Date: Mon, 15 Jan 2001 15:22:56 +1100

G'Day Brian and Paul,

What text do you suggest for the Implementors Guide?

Cheers, Christian

"Rosen, Brian" wrote:
>
> Sure.  What we do at the moment is to put it in the "Implementors Guide"
> When we reissue the RFC, we will put it in there.
>
> Brian
>
> > -----Original Message-----
> > From: Paul Long [mailto:[email-masked]]
> > Sent: Thursday, December 14, 2000 2:11 PM
> > To: Rosen, Brian
> > Subject: RE: context-free?
> >
> >
> > What do you think about my proposal to state this in the
> > spec? I don't think
> > it is at all clear, and I'd be willing to bet that at least a
> > few current
> > implementations would choke on the example I gave.
> >
> > -----Original Message-----
> > From: Media Gateway Control (megaco)
> > [mailto:[email-masked]]On Behalf Of Rosen, Brian
> > Sent: Thursday, December 14, 2000 11:55 AM
> > To: [email-masked]
> > Subject: Re: context-free?
> >
> >
> > 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.
> > >
> >

---

From: Paul Long <[email-masked]>
Date: Mon, 15 Jan 2001 10:41:40 -0600

Christian,

How about adding the following after the single sentence at the beginning of
B.2/RFC3015?

"The syntax SHALL be context-dependent. As a result, there SHALL be no
reserved keywords. For example, "Add" can be the AddToken or a NAME
depending on the context in which it occurs."

Paul

-----Original Message-----
From: Media Gateway Control (megaco)
[mailto:[email-masked]]On Behalf Of Christian
Groves
Sent: Sunday, January 14, 2001 10:23 PM
To: [email-masked]
Subject: Re: context-free?

G'Day Brian and Paul,

Cheers, Christian

---

From: Troy Cauble <[email-masked]>
Date: Mon, 15 Jan 2001 12:00:49 -0500

I find this odd.  Saying "SHALL" seems to imply that we
could say "SHALL NOT" without massively redefining
the ABNF.

How about:

"Note: The protocol is context-dependent.
For example the string "Add" can be the
AddToken or a NAME depending on the context
in which it occurs."

-troy

---

From: Paul Long <[email-masked]>
Date: Mon, 15 Jan 2001 11:10:02 -0600

Christian,

Oh, okay, I see in what form you want suggestions for the IG. Here is my
suggestion for the ABNF context ambiguity.

1.x ABNF is context dependent

Description:     RFC3015 does not indicate whether the ABNF is context
dependent. The concensus is that it is.
Reference:      Subject:      context-free?
Date:         Wed, 13 Dec 2000 17:54:32 -0600
Reply-To: [email-masked]
From: Paul Long <[email-masked]>
Organization: ipDIalog, Inc.
To: [email-masked]
Add to beginning of B.2/RFC3015:
[Begin Correction]
The syntax SHALL be context-dependent. As a result, there SHALL be no
reserved keywords. For example, "Add" can be the AddToken or a NAME
depending on the context in which it occurs.
[End Correction]

Paul Long
ipDialog, Inc.

-----Original Message-----

G'Day Brian and Paul,

Cheers, Christian

---

From: Paul Long <[email-masked]>
Date: Mon, 15 Jan 2001 11:48:33 -0600

Troy,

Okay, so what you are saying is that while it may not be clear at first
glance, the syntax is inherently context-dependent and that to say, "SHALL,"
means that we actually have a choice. Correct? Now that I think about it, I
agree with you--we need clarification, not disambiguation. How about this?

Description:     It is not clear whether the ABNF is context dependent.
Reference:      Subject:      context-free?
Date:         Wed, 13 Dec 2000 17:54:32 -0600
Reply-To: [email-masked]
From: Paul Long <[email-masked]>
Organization: ipDIalog, Inc.
To: [email-masked]
Add to beginning of B.2/RFC3015:
[Begin Correction]
Note - The syntax is context-dependent. For example, "Add" can be the
AddToken or a NAME depending on the context in which it occurs.
[End Correction]

(Minor point, but I believe that, to be precise, the ABNF _syntax_ is
context dependent and not the protocol.)

Paul Long
ipDIalog, Inc.

-----Original Message-----
From: Media Gateway Control (megaco)
[mailto:[email-masked]]On Behalf Of Troy Cauble
Sent: Monday, January 15, 2001 11:01 AM
To: [email-masked]
Subject: Re: context-free?

How about:

-troy

---

From: Christian Groves <[email-masked]>
Date: Tue, 16 Jan 2001 11:05:09 +1100

G'Day Paul,

The correction sounds OK to me. I'll add it to the implementors' guide.

Cheers, Christian