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:
-
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>.
-
test.h: data structures header file.
-
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;
|