Re: Grammars, Ambiguous, ASN.1

Robin Edgar Hansen wrote:


> > 1. Does anyone know of an extremely reliable electronic copy of the
> > grammar in raw EBNF? I'm typing it in by comparing a copy of
> > X.208 and some yacc source I've unearthed.
>
> A couple of years ago I did the very same. I used X.208 and a book from
> "Technology Appraisals" - can't think of the title now. It was not too
> bad. I used yacc++ (Which compiler compiler are you using?)


I think it was:


@Book{Steedman0,
    author = "Douglas Steedman",
    title = "{A}bstract {S}yntax {N}otation {O}ne ({ASN.1}) - {T}he
        {T}utorial and {R}eference",
    publisher = "Technology Appraisals",
    year = 1990
}


It is fine for understanding X.208.


For further information you should visit the following sites:


http://asn1.elibel.tm.fr/
http://www.mindspring.com/~asn1/left.htm
http://www.oss.com/
http://www-sop.inria.fr/rodeo/personnel/hoschka/asn1.html


Myself (htttp://cristal.inria.fr/~rinderkn/) I wrote a parser for
_complete_ X.208 (yes, including unkown macros:) in a typed functional
language: Objective Caml (http://caml.inria.fr/). I rewrote the
standard grammar into an LL(1) equivalent one (I proved equivalence at
each step of the rewriting since the general equivalence problem is
undecidable). I then wrote straighforward a parser in OCaml (using the
stream features and high-order parsers). The distribution of my
parser-typechecker includes a Yacc version of it, but without the
semantic actions, since I used OCaml for them. The difficulty, if you
try to use it, is that the final grammar is very obscure, and you have
to follow the productions in order to understand what semantics is
intended. But it's worth doing, since my grammar is bullet-proof:)


> > 2. What's the best primer for grammar disambiguation? I can borrow
> > the dragon book (Aho & Ullman) and/or the moderator's lex & yac
> > text very quickly. Should I order something else?
>
> Left-factoring should do most of it. The value part is a bit nasty,
though.


Well, I fear it's worst than just left-factoring. I assume here you
want to parse a context-free grammar of X.208. Then you will find
that following ambiguity:


Type ::= Tag Type | Type Constraint | OtherTypes


this is a typical ambiguity since you can build the two following
derivation trees for the same leaves:




Type
Type
                            /
\
/ \
                  Tag Type
and Type Constraint
                                          /
\ / \
                              Type Constraint
Tag Type


OK. Here you have to make a meta-choice for desambiguating: there is
no automatic way to decide which is the best. I chose the first one,
since semantically a subtype constraint apply to a type, whatever its
tags is.


This is the only ambiguity the grammar contain (I proved that). Now I
see another problem I you really do not want to use OCaml (or SML):
when parsing the subtype grammar I needed (this is maybe due to the
fact I wanted an LL(1) grammar ,though) to return partially evaluated
parsers (ie functions). Of course you can do it in C or C++, but it
should be rather more complex than in a functional language (actually,
the problem was related to the fact taht the token "<" can appear in a
type (SelectionType) and in a Value used as a strict bound of a
subtype constraint). Check my technical report at my homepage at
INRIA.


A last point. About macros: I also used a functional feature in order
to get an extensible parser. This is untractable using only Yacc,
since the LALR(1) automaton is compiled once and you can not extend it
dynamically.




> > 3. What other advice do the readers of this newsgroup have to offer
> > me?
>
> Beware that X.208 is outdated by X.680 (and X.681 etc)


Right!


A last piece of advice: you should subscribe to asn1@oss.com (firsr:
asn1-request@oss.com) where these questions about how to develop an
ASN.1 compiler are quite frequent.


Hope this helps,


--


Christian


-----------------------------------------------------------------------
Christian Rinderknecht Phone +33 (0)1 60 76 44 43
Institut National des Télécommunications Fax +33 (0)1 60 76 47 11
Département Logiciels Réseaux (LOR) WWW
9, Rue Charles Fourier, F-91011 Évry Cedex

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