Del2: ShML Parser

Purpose: The purpose of deliverable #2 is to use lex and yacc to make a C program which can parse the ShML language of Professor Pollett's Fall '01 CS146 classes HW 2 and output appropriate shapes. The point of this deliverable is to get familiar with lex and yacc.

Description: Lex and yacc are tools designed to transform structured input. Any application that looks for patterns in its input, or has an input or command language is a good candidate for lex and yacc. In programs with structure input, the lexer divides the input into meaningful units, the parser discovers the relationship among the units (tokens).

ShML Language: ShML is a language Professor Pollett invented for this homework. Similar to HTML,ShML has three pairs of tags:

<square>

</square>

<circle>

</circle>

<triangle>

</triangle>

The meaning of a pair of tags is to draw that kind of shape in the current enclosing shape. If there is no enclosing shape the shape should be drawn directly on the frame's background.

This program consists of three parts:

1. test.txt: source code for lex part. The purpose of this part is to read ShML file, then identify all theá tokens and return them to yacc part. Tokens are valid tags: <circle>, </circle>, <triangle>, </triangle>, <square>, </square>.
2. test.h: data structures header file.
3. test.y : source code for yacc part. In this part, data structures are intergrated with the grammar rules for translation. The rules are as following:

   start: Triangle start| Circle start | Square start |;

   Triangle: TRIANGLE_START start TRIANGLE_STOP;

   Circle: CIRCLE_START start CIRCLE_STOP;

   Square: SQUARE_START start SQUARE_STOP;

A generalized lists structure is used in the program, so we can get a structure, which contains all the shapes with their neighbors and children shapes. Due to the lack of graphics.h in gcc, this program cannot output shapes in graphics. But we can see that the output matches the input file. So we can say that the lex scaner and yacc parser works correctly.

Lex Code

/*****************************************************************
*test.txt: 	   Source code for the flex part
* Project:         CS 297 Del 1
* Date:		   10/15/2002
* Student:         Yan Yao
******************************************************************/

%{

#include <stdio.h>

#include <string.h>

#include "del2.tab.h"

%}



%%

[ \t]+
\<circle> 	{return CIRCLE_START;} 

\<\/circle>	{return CIRCLE_STOP;} 

\<triangle\>	{return TRIANGLE_START;} 

\<\/triangle\>	{return TRIANGLE_STOP;} 

\<square\>	{return SQUARE_START;} 

\<\/square\>	{return SQUARE_STOP;}



%%

int yywrap(void)

 {
    return 1;
}



int main(int argc, char *argv[])
 
{
   
 yyin = fopen(argv[1], "r");
 
 
    yyparse();
    

}

YACC code

%{

#include <stdio.h>

#include <string.h>

#include <malloc.h>

#include "test.h"

void drawshape(shapes *n);
%}




%union{

struct shapes *shape;
}

%type <shape> construct;
%type <shape> start;
%type <shape> Circle;
%type <shape> Triangle;
%type <shape> Square;


%token 	CIRCLE_START CIRCLE_STOP TRIANGLE_START TRIANGLE_STOP SQUARE_START
SQUARE_STOP



%%
construct: start { $$ = $1;drawshape($$);};


start: Triangle start{$1->next = $2; $$ = $1;} |
	 Circle start{$1->next= $2; $$ = $1;} | 
	Square start {$1->next = $2; $$ = $1;} |
	 { $$= NULL; };


Triangle: TRIANGLE_START start TRIANGLE_STOP	
	{	shapes *temp = (shapes*)malloc(sizeof(shapes));
		temp->shape_type =0; temp->next = NULL;
		temp->list =$2; $$=temp;
	};


Circle: CIRCLE_START start CIRCLE_STOP
	{	shapes *temp = (shapes*)malloc(sizeof(shapes));
		temp->shape_type = 1;
 		temp->next = NULL; temp->list =$2; $$=temp;
	};


Square: SQUARE_START start SQUARE_STOP
	{	shapes *temp = (shapes*)malloc(sizeof(shapes));
		temp->shape_type = 2; temp->next = NULL;
 		temp->list =$2; $$=temp;
	};



%%
yyerror(s)

char *s;

{printf("%s", s);}


void drawshape(shapes *n)
{

   if (n==NULL) return;

   switch(n->shape_type)
   {
      case 0:
         printf("\tTriangle\t");
      break;
      
      case 1:
         printf("\tCircle\t");
      break;
      
      case 2:
         printf("\tSquare\t");
      break;

   }
   
   
   printf("\n");
   drawshape(n->list);
   
   printf("\n");
   switch(n->shape_type)
   {
      case 0:
         printf("\t/Triangle\t");
      break;
      
      case 1:
         printf("\t/Circle\t");
      break;
      
      case 2:
         printf("\t/Square\t");
      break;

   }
   printf("\n");
   drawshape(n->next);
   printf("\n");
}

Header File

/***************************************************************
* test.h:          Data structures header file
* Project:         CS 297 Del 2
* Date:			   10/15/2002
* Student:         Yan Yao
******************************************************************/
#include <stdio.h>
#include <string.h>
#include <malloc.h>


typedef struct shapes{
 int shape_type;
 struct shapes *list;
 struct shapes *next;
} shapes;