Introduction

The information stored in the document type definition, from now on called DTD, must be transferred to the document parser. This is necessary because the DTD and the document are parsed separately. Information about the structure of the document, the element-rules (<&#!element ...>), is translated into LLgen Jacobs rules. Information about the attributes, entities and so on is stored in several files and those files are included in the document parser.

LLgen

LLgen is a parser-generator. Its input is a grammar, that consists of tokens (terminal symbols) and production-rules (non-terminals). A typical LLgen grammar is:

%token b,c;
%start a\(rupars, a;

a :	b c d ;
d :	b c ;

When a terminal or non-terminal on the righthandside is followed by question-mark (`?'), it is marked as optional.

%token b,c;
%start a\(rupars, a;

a :	b c? d ;
d :	b c ;

Element Declarations

To translate the DTD into LLgen-rules is relatively straightforward. For every starttag (and endtag) of an element a terminal symbol is introduced that must precede (follow) that element. When the starttag can be omitted, a question-mark follows the terminal symbol denoting the starttag. However, the omission of the starttag is not simple solved by just adding a question-mark after the starttag, because the starttag can only be omitted when the element is contextual required (see Standard, page 8, def. 4.61). This implies that not every optional starttag can be omitted. For example:

<!element a O - (b?, c)? >
<!element b O - (d) >
<!element c O - (d) >
<!element d O - CDATA >

a : [starttag_b b]? [%if (starttag_b has occurred) [starttag_c? | starttag_c] c] ;
b : starttag_d d endtag_b ;
c : starttag_d d endtag_c ;
d : cdata endtag_d ;

The endtag may be omitted in most cases, but the omission can only be determined during parsing. So all the rules are generated with a required endtag. If the endtag may be omitted and the user does omit the endtag, the parser itself adds the missing endtag during error-recovery and resumes parsing. If the endtag is omitted but it is not allowed, the parser does not insert the missing endtag but instead issues an error-message (see also the chapter on Endtag Omission).

The sequence-group in a content model is translated directly into LLgen-code. Between two content tokens, a separator is generated. This separator handles the parsing of newlines, spaces, tabs, comments, shortrefs etc. between two consecutive tokens. If the content model is mixed content, i.e. the content model contains the keyword PCDATA or ANY, spaces, tabs and newlines are part of PCDATA and not of the separator (see Standard section 7.6, page 24).

<!element a		O O	(b, c) >
<!element b		O O	(#PCDATA, d) >
<!element (c,d)		O O	CDATA >

Generated LLgen-code:

document :	\fIseparator2\fP [starttag_a a] \fIseparator2\fP ;
a :	\fIseparator2\fP [starttag_b b] \fIseparator2\fP [starttag_c c] \fIseparator2\fP [endtag_a] ;
b :	\fIseparator1\fP [pcdata] \fIseparator1\fP [starttag_d d] \fIseparator1\fP [endtag_b] ;
c :	[cdata] [endtag_c] ;
e :	[cdata] [endtag_d] ;

The or-group in the content model is translated directly into LLgen-code, only the order in which the alternatives are generated may differ. If there is an empty alternative i.e. the alternative can be skipped without being filled in, this one is generated first. For example:

<!element a		- - (b|c|d?) >
<!element (b,c,d)	- - CDATA >

Generated code:

document : [starttag_a a] ;
a :	[%if (conflict, choose first alternative) [starttag_d d]? | [starttag_b b]  | [starttag_c c] ] ;
b :	cdata endtag_b ;
c :	cdata endtag_c ;
d :	cdata endtag_d ;

To parse an and-group some extra rules are introduced. This is necessary because this construct is not know in LLgen: it must be simulated. The and-group `a & b' means `a' followed by `b' or `b' followed by `a'. The possible LLgen-rule might be:

and-group :	[ a b ] | [ b a ] ;

and-group :	[ a b c ] | [ a c b ] | [ b a c ] | [ b c a ] | [ c a b ] | [ c b a ] ;

and-group :	[ a and2_3 ] | [ b and1_3 ] | [ c and1_2 ] ;
and1_2 :	[ a b ] | [ b a ] ;
and1_3 :	[ a c ] | [ c a ] ;
and2_3 :	[ b c ] | [ c b ] ;

Inclusions

The production-rule for the inclusion elements are part of the generated grammar. However, a call to invoke the production-rule is not generated in the rule itself where the inclusion may occur, this would produce a great overhead. Take `Q' is a generic identifier or group in a content model and `x' the occurrence indicator, i.e `x' is \fBREP\fP, \fBOPT\fP or \fBPLUS\fP or empty if there is not any. Take ``$R sub 1$'' through ``$R sub n$'' are applicable inclusions, then a token

This approach is rather cumbersome, so we choose another method. In LLgen it is possible to write one's own error recovery routine, i.e. on encountering an error LLgen calls the users error-routine to handle the error. If the error-routine does not take any action, the error recovery of LLgen takes over. We use this feature for inclusions. When an inclusion is encountered, i.e. the starttag of the inclusion does not fit in the production-rule being parsed, our error-routine is automatically called by LLgen. The error-routine checks whether the starttag is the starttag of an applicable inclusion and if so the inclusion is parsed.

To parse the inclusion, we have to indicate in the grammar that the rule for the inclusion is a possible start element in the grammar. Note that the parser for the inclusion must be linked with the corresponding starttag, this is done on the generated file ``incl.i''. The file contains a structure with two fields. For example:

<!element a		- -	(b, c, d)	+(b) >
<!element (b,c,d)	- -	CDATA	>

The generated structure on ``incl.i'':

Inclfunc incl\(rufunc[] = {
	{ starttag_b, f\(ruB },
	{ 0, 0 }
};

After parsing the inclusion the LLgen parser expects the end-of-file token. However, we know at this moment that an end-of-file token is expected so we put it on the inputstream and the inclusion is terminated. The document parser can resume with the rest of the input in the state the parser was before the inclusion occurred. There is no restriction on the number of times the inclusion may appear. The file ``incl.i'' is included in ``incl.c''.

Endtag Omission

The endtag for an element may be omitted for the document element when the permission is yes (`O'). If the permission is yes (`O') for an element the endtag can be omitted when the element is followed either

The above rules make it necessary to transfer information about the content of an element from the DTD parser to the document parser. The information is stored on the file ``taglist.i''. The information about the content consist of the starttags of the content tokens and the keywords CDATA, PCDATA or RCDATA. When the endtags are marked optional in the grammar, a lot of ambiguities arise. To prevent this all the endtags are required. This causes an error if an endtag is omitted and our error-routine (see Inclusions) is called. The error-routine checks if the required token is an endtag. If the wrong token (the one causing the error) is an endtag of an open element, rule 1 is applied and the endtag of the most recent open element is pushed on the inputstream. Otherwise if the wrong token is not a starttag of an element that may appear in the content of the most recent open element and the wrong token is not a SGML character that may appear in the content, rule 2 applies and the endtag is also pushed on the inputstream. In all other cases an error really has occurred and a message is printed.

To get any idea of the generated file see the following example.

<!element a	O O	(b, d, c, #PCDATA) >
<!element b	O O	(c, d) >
<!element c	O O	CDATA >
<!element d	O O	RCDATA >

The generated file ``taglist.i'' :

ttaglist taglist[] = {
	endtag_a, true, { starttag_b, starttag_d, starttag_c, pcdata, 0 },
	endtag_b, true, { starttag_c, starttag_d, 0 },
	endtag_c, true, { cdata, 0 },
	endtag_d, true, { rcdata, 0 },
	0, 0, 0
};

<a>
<b>
<c>
This is element c
<d>
This is element d
<d>
This is element d in element a
<c>
This is element c in element a
This is PCDATA, impossible to determine whether this is
element c or pcdata

<a>
<b>
<c>
This is element c
<d>
This is element d
<&#/b>
<d>
This is element d in element a
<c>
This is element c in element a
<&#/c>
This is PCDATA, it is now possible to determine whether
this is element c or pcdata

Attribute Declarations

The attribute definition list declaration is needed in the document parser to check if the attribute values conform to the declared type and to check whether the starttag has attributes of the given attribute name. For this purpose a list with all the attribute definitions is generated on the file ``att\(rupar.i''. The file ``att\(rupar.ext'' contains the extern declarations. Every attribute definition list is stored in a single structure. The structure has several fields corresponding to the attribute definition.

struct attdef\(rustruct attr<nr> = {
{ name, declared value, name-token-group, default type, default value, current value },
\.....
{ 0, 0, 0, 0, 0, 0 }
};

<!attlist element-one
a		CDATA		#IMPLIED
b		(c|d|e)		"c"	-- no declared value but a name-token group --
c		NAMES		"tinker tailor soldier"
>

The generated list on ``att\(rupar.i'' :

String range1[] = { "c", "d", "e", 0 };
struct attdef\(rustruct attr1[] = {
	{ "a", CDATA,		0,		IMPLIED,		 0,	0 },
	{ "b", ENUMERATE,	range1,	UNDEFINED,	"c",	0 },
	{ "c", NAMES,		0,		UNDEFINED,	"tinker tailor soldier", 0},
	{ 0, 0, 0, 0, 0, 0 }
};

The generated external definition:

extern struct attdef\(rustruct attr1;

<!-- parameter entities -->
<!entity %	extern	PUBLIC "/usr/sylvia/test.i" >
<!entity %	ent		"This is a test" >

<!-- general entities -->
<!entity 	what		STARTTAG	"one" >
<!entity	who		ENDTAG		"one" >
<!entity	extern	PUBLIC "/usr/sylvia/test.i" >

The generated file looks like:

Extern\(ruid	extern0 = { <type> , "/usr/sylvia/test.i", "" };
Entity	dtd\(rugen\(ruentities[] = {
	{ "what", 25, "one", 0 },
	{ "who", 24, "one", 0 },
	{ "extern", 605, 0, &extern0 },
	{ 0, 0, 0, 0 }
};

Extern\(ruid	extern1 = { <type> , "/usr/sylvia/test.i", "" };
Entity	dtd\(rupar\(ruentities[] = {
	{ "extern", 605, 0, &extern1 },
	{ "ent", 604, "This is a test", 0 },
	{ 0, 0, 0, 0 }
};

<!shortref	mapje	"'"	entity\(ru1
				"("	entity\(ru2
				")"	entity\(ru3
>

Generate file ``map.i''

Map	MAPEMPTY = { "EMPTY",
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
0 };
Map	MAPMAPJE = { "MAPJE",
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, entity\(ru1, entity\(ru2, entity\(ru3,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
0 };
P\(ruMap	maps[] = { &MAPEMPTY, &MAPMAPJE, ILL\(ruMAP };

int totalcap = <integer>;
int entcap = <integer>;
int entchcap = <integer>;
int mapcap = <integer>;

<!element a	- - (b, c) +(fig) >
<!element b	- - CDATA >
<!element c	- - (b) -(fig) >
<!element fig	- - EMPTY >
<!attlist a	attr1		CDATA  #REQUIRED >
<!shortref	map1		"'"	"ent" >
<!usemap	map1	a >
<!entity	ent	"This is an entity" >

The generated file ``tags.i'' contains:

int doc\(rustart = starttag_a;

int incl1[] = { starttag_fig, 0 };
int excl1[] = { starttag_fig, 0 };

static Parsertable parserinfo = {
	{ "A", starttag_a, endtag_a, attr1, incl1, 0,     &MAPMAP1, 0 },
	{ "B", starttag_b, endtag_b, 0,     0,     0,     0,        0 },
	{ "C", starttag_c, endtag_c, 0,     0,     excl1, 0,        0 },
	{ "FIG", starttag_fig, endtag_fig, 0, 0, 0, 0, 0 },
	{ ILL\(ruSTRING, ILL\(ruSYMBOL, ILL\(ruSYMBOL, ILL\(ruATTR, ILL\(ruEXCEP, ILL\(ruEXCEP, ILL\(ruMAP, 0, 0 }
};

<a>    -- this is a comment --
<b>

Resolves to:
<a><b>