Subject: Re: context-free?

From: Paul Long <[email-masked]>
Date: Thu, 14 Dec 2000 00:42:00 -0500

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

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

    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: Troy Cauble <[email-masked]>
Date: Thu, 14 Dec 2000 10:57:14 -0500

> 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 sep…

[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

---

From: Paul Long <[email-masked]>
Date: Thu, 14 Dec 2000 10:04:49 -0600

(I am fairly new to the list, so my apologies of this has already been
discussed.)

I noticed this in the 1st-interop report:

   "3. There was confusion on case sensitivity.  Consensus is that the
      Megaco language, including tokens, event names, signal names,
      parameter names, enumeration values, etc. are NOT case sensitive.
      Attention was noted that values in quotations may be case
      sensitive, and that SDP is case sensitive in most circumstances."

So does this mean that the Megaco ABNF is incorrect? For example, instead of

   AddToken                   = ("Add"                   / "A")

should it be replaced by the following?

   A                          = ("A" / "a")
   B                          = ("B" / "b")
   C                          = ("C" / "c")
   D                          = ("D" / "d")
   ...
   Z                          = ("Z" / "z")

   AddToken                   = ((A D D) / A)

IOW, are, for example, "Add", "ADD", "aDd", "add", "A", and "a" all
synonyms?

Paul Long
ipDialog, Inc.

---

From: Paul Long <[email-masked]>
Date: Thu, 14 Dec 2000 10:33:08 -0600

Troy,

Thanks for your reply.

Yes, I am aware of the look-ahead problem you mention. I've had to deal with
it in other grammars. The problem is that if the implementor is not careful,
by the time the context is recognized in yacc, the lexer may have already
recognized and classified the next lexeme via look-ahead before the parser
has had a chance to tell the lexer to use different rules for this context.

I think it should be explicitly stated in the spec that this is a
context-dependent grammar and that as a result there are no reserved
keywords. 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 Long
ipDialog, Inc.

-----Original Message-----
From: Media Gateway Control (megaco)
[mailto:[email-masked]]On Behalf Of Troy Cauble
Sent: Thursday, December 14, 2000 9: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]

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

-troy

---

From: "Boyle, Kevin [NCRTP:3Z70:EXCH]" <[email-masked]>
Date: Thu, 14 Dec 2000 13:10:58 -0500

RFC 2234 - Augmented BNF for Syntax Specifications: ABNF, states that ABNF is
case-insensitive.

To quote from section 2.3: Terminal Values:

"Literal text strings are interpreted as a concatenated set of printable
characters.

        NOTE:     ABNF strings are case-insensitive and the character set for
these strings is us-ascii.

   Hence:

        rulename = "abc"

   and:

        rulename = "aBc"

   will match "abc", "Abc", "aBc", "abC", "ABc", "aBC", "AbC" and "ABC".

                To specify a rule which IS case SENSITIVE, specify the
characters individually."

Kevin