1.1 - RECOGNIZING SOME TAGS IN THE HEADER PART

////////////////////////////////  lex1.1a.l   /////////////////////////////////
X	"<?xml "
V	"version="\"[0-9]+\.[0-9]+\"
E	" encoding=\""
I	"ISO-8859-"[1-5]

%%
{X}{V}({E}{I}\")?" ?>"	{ printf("[B1=%s]",yytext); }
.			{ // markedly show all what was unforeseen
			  printf("[%s!!]",yytext);
			}
%%

///////////////////////////////  1.1a.datOK   /////////////////////////////////
<?xml version="1.0" encoding="ISO-8859-1" ?>
<?xml version="3.2" encoding="ISO-8859-5" ?>
<?xml version="99.99" ?>
///////////////////////////////  1.1a.datBAD  /////////////////////////////////
<?xml version="100" ?>
<?xml version="1.0" encoding="iso-8859-1" ?>
<?xml version="1.0" encoding="ISO-8859-1"?>
<?xmlversion="1.0" encoding="ISO-8859-1" ?>

////////////////////////////////  lex1.1b.l   /////////////////////////////////

X	"<?xml-stylesheet "
HPref	"href="\"
TPref	"type=\"text/"
Symbol	[A-Za-z][A-Za-z0-9]*
Path	({Symbol}\/)*{Symbol}

%%
{X}{HPref}{Path}".xsl\" "{TPref}(xsl|css)"\" ?>"   { printf("[B2=%s]",yytext);}
.						   { printf("[%s!!]",yytext); }
%%

///////////////////////////////  1.1b.datOK   /////////////////////////////////
<?xml-stylesheet href="catalog.xsl" type="text/xsl" ?>
<?xml-stylesheet href="truc.xsl" type="text/css" ?>
<?xml-stylesheet href="truc/machin.xsl" type="text/css" ?>
<?xml-stylesheet href="/truc/machin.xsl" type="text/css" ?>

///////////////////////////////  1.1b.datBAD  /////////////////////////////////
<?xml-stylesheet href="catalog.xsl" type="text/xss" ?>
<?xml-stylesheet href="truc/.xsl" type="text/xsl" ?>
<?xml-stylesheet href="/truc//machin.xsl" type="text/css" ?>

////////////////////////////////  lex1.1c.l   /////////////////////////////////
DT		"<!DOCTYPE "
Sys		"SYSTEM"
Symbol		[A-Za-z][A-Za-z0-9]*
Path		({Symbol}\/)*{Symbol}
DtdPath 	{Path}\.dtd
EnclPath	\"{DtdPath}\"

%%
{DT}{Symbol}[ ]{Sys}[ ]{EnclPath}">"		{ printf("[B3=%s]",yytext); }
.						{ printf("[%s!!]",yytext);  }
%%

///////////////////////////////  1.1c.datOK   /////////////////////////////////
<!DOCTYPE catalog SYSTEM "catalog.dtd">
<!DOCTYPE truc SYSTEM "machin.dtd">
<!DOCTYPE truc SYSTEM "machin/bidule.dtd">

///////////////////////////////  1.1c.datBAD  /////////////////////////////////
<!DOCTYPE _catalog SYSTEM "catalog.dtd">
<!DOCTYPE catalog SYSTEM "catalog.ddd">
<!DOCTYPE catalog SYSTEM "catalog/.dtd">
<!DOCTYPE catalog system "catalog.dtd">
1.2 -  RECOGNIZING THE MAIN TAGS IN THE BODY OF AN Xml FILE

a) RECOGNITION ONLY

///////////////////////////////// lex1.2a.l ///////////////////////////////////
OpTag	"<"[^>]+">"
ClTag	"</"[^>]+">"
STag	"<"[^>]+" />"

%%
{STag}		{ printf("[S_TAG=%s]",  yytext); }
{ClTag}		{ printf("[CL_TAG=%s]", yytext); }
{OpTag}		{ printf("[OP_TAG=%s]", yytext); }
%%

///////////////////////////// lex1.2a.dat /////////////////////////////////////
<package>
  <name>user.mod.news</name>
  <refdir value="xxx" />
  <time   value="10" />
  <filelist>
      <dir baseinstalldir="user/testsite/mod/news">
        <file>EditNews?.php</file>
        <dir name="tmpl">
          <file>EditNews?.tpl</file>
        </dir>
      </dir>
  </filelist>
</package>
///////////////////////////////////////////////////////////////////////////////

Remarks
- here we choose not to show all other chars, but just to echo them.
  A more cautious possibility would be to echo spaces and newlines, and to show
  all other chars very markedly (this quickly gets boring, but it's for debug):
[ \n]		ECHO;
.		printf("[%c!]", yytext[0]);
- we assume that in simple tags the "/>"end must be preceded with a space
- using expressions as [^>] makes the specification more general, the analyzer
  won't be tied to accept a restricted char set in the tag body
- the rules have to be specified in some suitable order, due to ambiguities
- we might be tempted to use the [^/] subexpression for defining STag, but this
  would forbid '/' chars inside the tag body. Or to use [^/>] but then the rule
  for the S tag could take an opening tag as a simple tag, and the rule order
  would be even more crucial

b) EXTRACTING THE TAG NAME

///////////////////////////////// lex1.2b.l ///////////////////////////////////
%{
#include <stdlib.h>

// Locate a separator-delimited "field" in the recognized fragment yytext, copy
// it into a dedicated buffer (yytext will be overwritten by next fragment)
char * getFieldFrom( int beg ) {
  int  i = beg, c;
  char * s;
  while( (c=yytext[i]) != '\0' && c!='/' && c != '>' && c != ' ' ) i++;
  if( (s=malloc(i-beg+1))==NULL ) { printf("malloc FAILED !");exit(1);}
  strncpy( s, &yytext[beg], i-beg );
  s[i-beg] = 0;
  return s;
}
%}

OpTag	"<"[^>]+">"
ClTag	"</"[^>]+">"
STag	"<"[^>]+" />"
%%
{STag}			{ printf("[S_TAG name=%s]",  getFieldFrom( 1 ) ); }
{ClTag}			{ printf("[CL_TAG name=%s]", getFieldFrom( 2 ) ); }
{OpTag}			{ printf("[OP_TAG name=%s]", getFieldFrom( 1 ) ); }
%%


c) VARIANT (bonus)

Since lexical analysis may gets tricky, it's a good idea to proceed with very
gradual macro definitions. (Note that, for several notions here, the correct
place to recognize them could be the syntaxic level).

Symb	[^ />\n]+
Path    {Symb}("/"{Symb})*
Pair	{Symb}"="({Symb}|{Path})
Field	{Pair}|{Symb}|{Path}
S1Tag	"<"({Field}" ")*"/>"

%%
{S1Tag}			{ printf("[S1Tag=%s]", yytext); }
%%

/////////////// lex1.2c.dat = variant from lex1.2a.dat ////////////////////////
  <refdir value="xxx/yyy/zzz/" />
  <refdir value="xxx/yyy//zzz/" />



2.1 - TREE GRAMMARS : RECOGNIZING THE STRUCTURE ONLY

In this question, the OP, CL, S tags have no associated names.

2.1a) Entry text presented on a only line

To nevertheless deal with a final \n, it is convenient to define a notion of
Text. The tree structure is encoded with a Block, and it is followed with a \n.

/////////////////////////////  2.1a.dat  //////////////////////////////////////
OP OP S S CL OP S CL S CL

///////////////////////////// gram2.1a.y //////////////////////////////////////
%token	OP  CL  S  '\n'

%%
Text	:	Block  '\n'
		{ printf("<<Text>>"); }
	;
Block	:	OP  List  CL
		{  printf("<<Block>>"); }
        ;
List	:
		{  printf("<<L>>");  }
	|	List   S
		{  printf("<<L+S>>");  }
	|	List   Block
		{  printf("<<L+B>>");  }
	;
%%

/////////////////////////////////// lex2.1a.l /////////////////////////////////
%{
#include "y.tab.c"
%}

%%
OP	{ printf("[OP]"); return OP; }
CL	{ printf("[CL]"); return CL; }
S	{ printf("[S]");  return S;  }
\n	  return '\n';
[ \t]	  ECHO;
.	{
	  printf("[%c!!]",yytext[0]);	// Clearly spot the error
	  return yytext[0];		// Make the syntaxic analyzer to err
	}
%%

2.1b) Entry text is presented on several lines

Here we have to admit a \n after any tag (P, CL or S). A possible grammar is as
follows. The Text notion no longer is useful. The lexical analyzer is the same.

//////////////////////////    2.1b.dat   //////////////////////////////////////
OP
  OP
    S
    S
  CL
  OP
   S
  CL
  S
CL

////////////////////////// gram2.1b.y /////////////////////////////////////////
%token	OP  CL  S  '\n'

%{
#include "lex.yy.c"
%}

%%
Block	:	OP '\n'  List  CL  '\n'
		{  printf("<<Block>>"); }
        ;
List	:
		{  printf("<<L>>");  }
	|	List   S  '\n'
		{  printf("<<L+S>>");  }
	|	List   Block
		{  printf("<<L+B>>");  }
	;
%%

2.2 - TREE GRAMMARS : RECOGNIZING A NAMED TREE

Now the OP, CL and S tags have an associated name. At the lexical level,
getNameFrom() gets this name. This function is nearly the same as Q1.2b's
getFieldFrom(), it just accounts for less delimiters. To pass a name to the
syntaxic level, we define types associated to the (union) yylval variable.
(In view of Q3, we define also an <any> type for the Block and List notions).
The values associated to lexical categories OP, CL, S are given a type.
The action for the Block rule checks the values associated to OP and CL tokens.

///////////////////////////////  2.2.dat //////////////////////////////////////
OP1
  OP2
    S3
    S4
  CL2
  OP5
   S6
  CL5
  S7
CL1

///////////////////////////////  gram2.2.y ////////////////////////////////////

%token	<name>  OP  CL  S
%token  '\n'
%type   <any>  List Block

%union {
  char * name;
  void * any;
}

%%
Block	:	OP '\n'  List  CL  '\n'
		{
		  printf("<<Block:%s,%s>>\n",$1,$4);
		  if( strcmp( $1, $4 ) )
		    { printf("UNMATCHED NAMES!\n"); exit(1); }
		}
        ;
List	:
		{  printf("<<empty L>>");  }
	|	List   S  '\n'
		{  printf("<<S>>\n");  }
	|	List   Block
	;
%%

///////////////////////////////  lex2.2.l /////////////////////////////////////
%{

#include "y.tab.c"

char * getNameFrom( int beg ) {
  int  i = beg, c;
  char *s;
  while( (c=yytext[i]) != '\0' && c != '\n' && c != ' ' && c != '\t' ) i++;
  s = malloc( i-beg+1 );  // one more for \0
  if( s == NULL ) { printf("malloc() FAILED !!"); exit(1); }
  strncpy( s, &yytext[beg], i-beg );
  return s;
}
void lexTrace( ) { printf("[%s]",yytext); }

%}

%%
OP[^ \t\n]+		{ lexTrace( ); yylval.name=getNameFrom(2); return OP; }
CL[^ \t\n]+		{ lexTrace( ); yylval.name=getNameFrom(2); return CL; }
S[^ \t\n]+		{ lexTrace( ); yylval.name=getNameFrom(1); return S;  }
\n	  		  return '\n';
[ \t]	  		  ECHO;
.			{ printf("[%c!!]",yytext[0]); return yytext[0]; }
%%
3.1 - RECOGNIZING A NAMED TREE

- the syntaxic analyzer is nearly as gram2.2.y
. here we just deal with some more cases with respect to newlines, to accept
  a List, and an OP/CL block when defined on a only line.
. note that gram1.2.y already cared to assign types to Block and List,
  in view of the subsequent tree building

- the lexical analyzer derives very simply from lex2.1b.l :
. includes y.tab.c, pass the names via yylval, return the tokens, including \n
. for simplicity, it skips any unforeseen character (note that in an industrial
  context this should be improved)

////////////////////////////// gram3.1.y //////////////////////////////////////
%token	<name>  OP  CL  S
%token  '\n'
%type   <any>  List Block

%union {
  char * name;
  void * any;
}

%%
Block	:	OP '\n'  List  CL  '\n'
		{
		  printf("<<Block:%s,%s>>\n",$1,$4);
		  if( strcmp( $1, $4 ) ) {
		    printf("UNMATCHED NAMES!\n");
		    exit(1);
		  }
		}
	|	OP  List  CL  '\n'
		{
		  printf("<<Block:%s,%s>>\n",$1,$3);
		  if( strcmp( $1, $3 ) ) {
		    printf("UNMATCHED NAMES!\n");
		    exit(1);
		  }
		}
        ;
List	:
		{  printf("<<L>>");  }
	|	List   S  '\n'
		{  printf("<<L.S>>\n");  }
	|	List   S
		{  printf("<<L.S>>");  }
	|	List   Block
		{  printf("<<L.B>>\n");  }
	;
%%
////////////////////////////////// lex3.1.l //////////////////////////////////
%{
#include <stdlib.h>
#include "y.tab.c"
char * getFieldFrom( int beg ) {
  int  i = beg, c;
  char * s;
  while( (c=yytext[i]) != '\0' && c!='/' && c != '>' && c != ' ' ) i++;
  if( (s=malloc(i-beg+1))==NULL ) { printf("malloc FAILED !");exit(1);}
  strncpy( s, &yytext[beg], i-beg );
  s[i-beg] = 0;
  return s;
}
%}

OpTag	"<"[^>]+">"
ClTag	"</"[^>]+">"
STag	"<"[^>]+" />"
%%
{STag}		{  yylval.name = getFieldFrom(1); return S;  }
{ClTag}		{  yylval.name = getFieldFrom(2); return CL; }
{OpTag}		{  yylval.name = getFieldFrom(1); return OP; }
\n	   	   return '\n';
[ \t]		   ECHO;
.		;
%%

////////////////////////////////// 3.1.dat ////////////////////////////////////
<package>
  <name>user.mod.news</name>
  <refdir value="xxx" />
  <time   value="10" />
  <filelist>
      <dir baseinstalldir="user/testsite/mod/news">
        <file>EditNews?.php</file>
        <dir name="tmpl">
          <file>EditNews?.tpl</file>
        </dir>
      </dir>
  </filelist>
</package>
3.2 - BUILDING THE TREE STRUCTURE

- the syntaxic part gram3.2.y derives from gram3.1.y as follows:
. we include the lists.c file to manage Nodes, Lists, Blocks
. a Block variable remembers the root Block, for printing the resulting tree
. other auxiliary pointer variables are defined once for all
. actions for the "Block" rules consists in creating one Block
. actions associated to the List rules respectively: create a new List,
  add a "simple" node to it, or add a "node with a block"
- the lexical analyzer lex3.2.l is identical to lex3.1.l
- in the "prin.c" file, just yyparse() is modified to print the tree

///////////////////////////////   gram3.2.y   /////////////////////////////////

%token	<name>  OP  CL  S
%token  '\n'
%type   <any>   List Block

%union {
  char * name;
  void * any;
}

%{
#include <stdlib.h>

#include "lists.c"

Block  * root, * bptr;
List   * lptr;
Node   * nptr;
int      level = 0;
%}

%%
Block	:	OP '\n'  List  CL  '\n'
		{
		  if( strcmp( $1, $4 ) ) {
		    printf("UNMATCHED NAMES!\n");
		    exit(1);
		  }
		  else {
		    bptr = newBlock( $1, $3, --level );
		    if( level==0 ) { root = bptr; printf("ROOT "); }
		    $$ = bptr;
		  }
		}
	|	OP  List  CL  '\n'
		{
		  printf("<<Block:%s,%s>>\n",$1,$3);
		  if( strcmp( $1, $3 ) ) {
		    printf("UNMATCHED NAMES!\n");
		    exit(1);
		  }
		  else {
		    bptr = newBlock( $1, $2, --level );
		    if( level==0 ) { root = bptr; printf("ROOT "); }
		    $$ = bptr;
		  }
		}
        ;
List	:
		{
		  lptr = newList( );
		  printf("<L%x l=%d>",lptr,level);
		  level++;
		  $$ = lptr;
		}
	|	List   S  '\n'
		{
		  nptr = newSimpleNode($2);
		  appendNodeToList( nptr, $1 );
		  printf("<L%x+S=%s>\n",$1, $2);
		  $$ = $1;  // current list remains the same
		}
	|	List   S
		{
		  nptr = newSimpleNode($2);
		  appendNodeToList( nptr, $1 );
		  printf("<L%x+S=%s>\n",$1, $2);
		  $$ = $1;
		}
	|	List   Block
		{
		  nptr = newNodeWithABlock($2);
		  appendNodeToList( nptr, $1 );
		  printf("<L%x+Block=%s>\n",$1,nptr->bptr->name);
		  $$ = $1;
		}
	;
%%

///////////////////   prin.c : only yywrap() modified  ///////////////////////

#include <stdlib.h>
#include "lex.yy.c"

main() { yyparse(); }
yyerror(char *s) { printf("<%s!!>",s); }
yywrap() {
  printf("\nTREE LISTING :\n");
  blockList( root );
  return 1;
}