Re: SGML to YACC (Theo Vosse)
Mon, 30 May 1994 07:43:09 GMT

          From comp.compilers

Related articles
SGML to YACC (1994-05-26)
Re: SGML to YACC (1994-05-30)
Re: SGML to YACC (1994-05-31)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Theo Vosse)
Keywords: parse, yacc
Organization: Leiden University, The Netherlands
References: 94-05-113
Date: Mon, 30 May 1994 07:43:09 GMT

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

Post a followup to this message

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