Re: SGML to YACC

> <!ELEMENT foo - - (a, b*, c) +(d | e) >
> Means that the tags/tokens <d> and <e> can occur anywhere. My first pass
> ...
> The problem I am having is the grammar grows almost exponentially when
> exceptions are fully implemented. Or am I missing some simple construct?


Although I'm not a great expert on SGML, I'll try something...


Actually, what you have here is a simple regular expression, so there is
nothing context dependent really. If you express it in terms of a DFA
(Deterministic Finite State Automaton), you get the following:


state 0: a->1, d->0, e->0
state 1: b->1, c->2, d->1, e->1
state 2: d->2, e->2, or accept on end of input


So, since every DFA can be easily transformed into a CFG, you get:


S0: a S1 | d S0 | e S0 ;
S1: b S1 | c S2 | d S1 | e S1 ;
S2: d S2 | e S2 | /* empty */ ;


Very YACC-ish...


Theo Vosse
----------
Unit for Experimental Psychology
University of Leiden
The Netherlands
--

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