lex – codingcrazy

This is a sample tutorial describes how to check your grammar is in correct order or not and print the DFA states of your grammar using bison and flex in windows environment.

To describe the procedure I’ve got the “simple thermostat controller example” from the “Ivan’s Blog” at “http://ivan215.blogspot.com/2009/04/yacc-yet-another-compiler-compiler.html“.

First we must define our grammar in lex (*.l) and yacc (*.y) files. In this example I named them as “heat.l” and “heat.y” according to the “Ivan’s Blog” because these files are describes a process of heat equipment. (Figure 1)

Figure 1

heat.l

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+ yylval=atoi(yytext); return NUMBER;
heat return TOKHEAT;
on|off yylval=!strcmp(yytext,"on");return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;\n /*ignore end of line*/;
[\t]+ /*ignore whitespace*/;
%%
int yywrap(void)
{
 return 1;
}

heat.y

%{
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
int lineno =1;
void yyerror(char *str);
%}
%start commands
%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE
%%
commands :/*empty*/
|commands command
;
command :heat_switch
|target_set
;
heat_switch :TOKHEAT STATE
{
if($2)
   printf("\tHeat turned on \n");
else
   printf("\tHeat turned off \n");
}
;
target_set :TOKTARGET TOKTEMPERATURE NUMBER
{
   printf("\tTemperature set to %d\n",$3);
}
;
%%
void yyerror(char *str)
{
   fprintf(stderr,"line %d: %s\n",lineno,str);
}
main()
{
   yyparse();
}

Then open a terminal and type the following command only for “heat.y” file only (Figure 2)

>bison –dv heat.y (here the –v parameter for more details type >bison –help)

Figure 2

This will generate following output file (Figure 3)

“heat.output”

Figure 3

When we open the file using a text editor the file includes the following data

Used and unused nonterminals.
Used and unused terminals.
Grammar rules.
And the states of the Finite Automata (DFA).

heat.output

Grammar
rule 1 commands -> /* empty */
rule 2 commands -> commands command
rule 3 command -> heat_switch
rule 4 command -> target_set
rule 5 heat_switch -> TOKHEAT STATE
rule 6 target_set -> TOKTARGET TOKTEMPERATURE NUMBER
Terminals, with rules where they appear
$ (-1)
error (256)
NUMBER (257) 6
TOKHEAT (258) 5
STATE (259) 5
TOKTARGET (260) 6
TOKTEMPERATURE (261) 6
Nonterminals, with rules where they appear
commands (8)
on left: 1 2, on right: 2
command (9)
on left: 3 4, on right: 2
heat_switch (10)
on left: 5, on right: 3
target_set (11)
on left: 6, on right: 4
state 0
$default reduce using rule 1 (commands)
commands go to state 1
state 1
commands -> commands . command (rule 2)
$ go to state 10
TOKHEAT shift, and go to state 2
TOKTARGETshift, and go to state 3
command go to state 4
heat_switch go to state 5
target_set go to state 6
state 2
heat_switch -> TOKHEAT . STATE (rule 5)
STATE shift, and go to state 7
state 3
target_set -> TOKTARGET . TOKTEMPERATURE NUMBER (rule 6)
TOKTEMPERATURE shift, and go to state 8
state 4
commands -> commands command . (rule 2)
$default reduce using rule 2 (commands)
state 5
command -> heat_switch . (rule 3)
$default reduce using rule 3 (command)
state 6
command -> target_set . (rule 4)
$default reduce using rule 4 (command)
state 7
heat_switch -> TOKHEAT STATE . (rule 5)
$default reduce using rule 5 (heat_switch)
state 8
target_set -> TOKTARGET TOKTEMPERATURE . NUMBER (rule 6)
NUMBER shift, and go to state 9
state 9
target_set -> TOKTARGET TOKTEMPERATURE NUMBER . (rule 6)
$default reduce using rule 6 (target_set)
state 10
$ go to state 11
state 11
$default accept

If there is an error it will show the errors in (*.output) file as a below (Figure 4)

Figure 4

This method is briefly described in page 6 of “LEX & YACC TUTORIAL” by Tom Niemann.

Thank you!

Share this: