Re: Grammars, Ambiguous, ASN.1

Geoff Elgey <>
10 Jul 1999 01:25:30 -0400

          From comp.compilers

Related articles
Grammars, Ambiguous, ASN.1 (1999-06-19)
Re: Grammars, Ambiguous, ASN.1 (Dmitri Katchalov) (1999-06-27)
Re: Grammars, Ambiguous, ASN.1 (Rajappa Iyer) (1999-06-27)
Re: Grammars, Ambiguous, ASN.1 (Robin Edgar Hansen) (1999-06-27)
Re: Grammars, Ambiguous, ASN.1 (Christian Rinderknecht) (1999-06-29)
Re: Grammars, Ambiguous, ASN.1 (Christian Rinderknecht) (1999-07-01)
Re: Grammars, Ambiguous, ASN.1 (1999-07-05)
Re: Grammars, Ambiguous, ASN.1 (Geoff Elgey) (1999-07-10)
| List of all articles for this month |

From: Geoff Elgey <>
Newsgroups: comp.compilers
Date: 10 Jul 1999 01:25:30 -0400
Organization: Distributed Systems Technology CRC
References: 99-06-072 99-06-089
Keywords: parse


> Bear in mind that the ASN.1 grammar is ambiguous and cannot be parsed
> completely with LALR(1). It needs lexical tie-ins for disambiguation.

I'm writing an ASN.1 compiler at the moment, actually. The grammar is
horrible - how was it ever designed? I've had to do all sorts of evil
tricks to parse correctly.

> Also, macros are horrendously hard, if not downright impossible, to
> implement with Yacc and friends since macros can change the grammar
> midstream.

This relates to the question I was going to ask - what is the best way
of parsing a user-defined grammar on the fly?

In X.681, a CLASS type may be given its own syntax, as follows:

SyntaxList ::= "{" Productions "}" .
Productions ::= { Production } .
Production ::= "[" Productions "]"
                              | word
                              | ","
                              | PrimitiveFieldName .

where 'word' is an sequence of upperclass letters (except for some
special cases), and a 'PrimitiveFieldName' is an '&' followed by some
identifers and periods.

So the text to be parsed could (syntactically) look like this:

  T1 ::= CLASS {
        &ArgumentType INTEGER,
        &ResultType INTEGER,
            ARGUMENT &ArgumentType
            RESULT DEFINED TO BE &ResultType
        [ ARGUMENT &ArgumentType
            RESULT DEFINED AS &ResultType ]
        [ ARGUMENT &ArgumentType
            RESULT DEFINED BY &ResultType ]
            ARGUMENT &ArgumentType
            RESULT DEFINED &ResultType

I'm wondering - what is the best way to parse such productions? I'm
thinking that a bottom-up parser would be the best option.

Of course, a parser would have to be generated automatically for each
syntax list in the source text, and from within the main parser itself.

Any ideas/suggestions?


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.