Re: Grammars, Ambiguous, ASN.1

Geoff Elgey <elgey@dstc.qut.edu.au>
10 Jul 1999 01:25:30 -0400

          From comp.compilers

Related articles
Grammars, Ambiguous, ASN.1 sge@acm.org (1999-06-19)
Re: Grammars, Ambiguous, ASN.1 dmitrik@my-deja.com (Dmitri Katchalov) (1999-06-27)
Re: Grammars, Ambiguous, ASN.1 rsi@lucent.com (Rajappa Iyer) (1999-06-27)
Re: Grammars, Ambiguous, ASN.1 robin.hansen@irisa.fr (Robin Edgar Hansen) (1999-06-27)
Re: Grammars, Ambiguous, ASN.1 Christian.Rinderknecht@int-evry.fr (Christian Rinderknecht) (1999-06-29)
Re: Grammars, Ambiguous, ASN.1 Christian.Rinderknecht@int-evry.fr (Christian Rinderknecht) (1999-07-01)
Re: Grammars, Ambiguous, ASN.1 sge@acm.org (1999-07-05)
Re: Grammars, Ambiguous, ASN.1 elgey@dstc.qut.edu.au (Geoff Elgey) (1999-07-10)
| List of all articles for this month |

From: Geoff Elgey <elgey@dstc.qut.edu.au>
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

G'day,


> 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,
    } WITH SYNTAX {
            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?


Cheers,
Geoff


Post a followup to this message

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