Re: SGML to YACC

vosse@ruls41.LeidenUniv.nl (Theo Vosse)
Mon, 30 May 1994 07:43:09 GMT

          From comp.compilers

Related articles
SGML to YACC j_mcarthur@BIX.com (1994-05-26)
Re: SGML to YACC vosse@ruls41.LeidenUniv.nl (1994-05-30)
Re: SGML to YACC glyph@netcom.com (1994-05-31)
| List of all articles for this month |

Newsgroups: comp.compilers
From: vosse@ruls41.LeidenUniv.nl (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.