Welcome, gentle reader.

If you have been programming for any length of time in a Unix environment, you will have encountered the mystical programs Lex & YACC, or as they are known to GNU/Linux users worldwide, Flex & Bison, where Flex is a Lex implementation by Vern Paxson and Bison the GNU version of YACC. We will call these programs Lex and YACC throughout - the newer versions are upwardly compatible, so you can use Flex and Bison when trying our examples.

These programs are massively useful, but as with your C compiler, their manpage does not explain the language they understand, nor how to use them. YACC is really amazing when used in combination with Lex, however, the Bison manpage does not describe how to integrate Lex generated code with your Bison program.

When properly used, these programs allow you to parse complex languages with ease. This is a great boon when you want to read a configuration file, or want to write a compiler for any language you (or anyone else) might have invented.

With a little help, which this document will hopefully provide, you will find that you will never write a parser again by hand - Lex & YACC are the tools to do this.

The program Lex generates a so called `Lexer'. This is a function that takes a stream of characters as its input, and whenever it sees a group of characters that match a key, takes a certain action. A very simple example:

%{
#include <stdio.h>
%}

%%
stop	printf("Stop command received\n");
start	printf("Start command received\n");
%%

The first section, in between the %{ and %} pair is included directly in the output program. We need this, because we use printf later on, which is defined in stdio.h.

Sections are separated using '%%', so the first line of the second section starts with the 'stop' key. Whenever the 'stop' key is encountered in the input, the rest of the line (a printf() call) is executed.

Besides 'stop', we've also defined 'start', which otherwise does mostly the same.

We terminate the code section with '%%' again.

To compile Example 1, do this:

lex example1.l
cc lex.yy.c -o example1 -ll

	Note
	NOTE: If you are using flex, instead of lex, you may have to change '-ll' to '-lfl' in the compilation scripts. RedHat 6.x and SuSE need this, even when you invoke 'flex' as 'lex'!

This will generate the file 'example1'. If you run it, it waits for you to type some input. Whenever you type something that is not matched by any of the defined keys (ie, 'stop' and 'start') it's output again. If you enter 'stop' it will output 'Stop command received';

Terminate with a EOF (^D).

You may wonder how the program runs, as we didn't define a main() function. This function is defined for you in libl (liblex) which we compiled in with the -ll command.

%{
#include <stdio.h>
%}

%%
[0123456789]+		printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]*	printf("WORD\n");
%%

$ ./example2
foo
WORD

bar
WORD

123
NUMBER

bar123
WORD

123bar
NUMBER
WORD

logging {
	category lame-servers { null; };
	category cname { null; };
};

zone "." {
        type hint;
        file "/etc/bind/db.root";
};

%{
#include <stdio.h>
%}

%%
[a-zA-Z][a-zA-Z0-9]*    printf("WORD ");
[a-zA-Z0-9\/.-]+        printf("FILENAME ");
\"                      printf("QUOTE ");
\{                      printf("OBRACE ");
\}                      printf("EBRACE ");
;                       printf("SEMICOLON ");
\n                      printf("\n");
[ \t]+                  /* ignore whitespace */;
%%

WORD OBRACE 
WORD FILENAME OBRACE WORD SEMICOLON EBRACE SEMICOLON 
WORD WORD OBRACE WORD SEMICOLON EBRACE SEMICOLON 
EBRACE SEMICOLON 

WORD QUOTE FILENAME QUOTE OBRACE 
WORD WORD SEMICOLON 
WORD QUOTE FILENAME QUOTE SEMICOLON 
EBRACE SEMICOLON 

YACC can parse input streams consisting of tokens with certain values. This clearly describes the relation YACC has with Lex, YACC has no idea what 'input streams' are, it needs preprocessed tokens. While you can write your own Tokenizer, we will leave that entirely up to Lex.

A note on grammars and parsers. When YACC saw the light of day, the tool was used to parse input files for compilers: programs. Programs written in a programming language for computers are typically *not* ambiguous - they have just one meaning. As such, YACC does not cope with ambiguity and will complain about shift/reduce or reduce/reduce conflicts. More about ambiguity and YACC "problems" can be found in 'Conflicts' chapter.

4.1.  A simple thermostat controller

Let's say we have a thermostat that we want to control using a simple language. A session with the thermostat may look like this:

heat on
	Heater on!
heat off
	Heater off!
target temperature 22
	New temperature set!

The tokens we need to recognize are: heat, on/off (STATE), target, temperature, NUMBER.

The Lex tokenizer (Example 4) is:

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  return NUMBER;
heat                    return TOKHEAT;
on|off                  return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

We note two important changes. First, we include the file 'y.tab.h', and secondly, we no longer print stuff, we return names of tokens. This change is because we are now feeding it all to YACC, which isn't interested in what we output to the screen. Y.tab.h has definitions for these tokens.

But where does y.tab.h come from? It is generated by YACC from the Grammar File we are about to create. As our language is very basic, so is the grammar:

commands: /* empty */
        | commands command
        ;

command:
        heat_switch
        |
        target_set
        ;

heat_switch:
        TOKHEAT STATE
        {
         	printf("\tHeat turned on or off\n");
        }
        ;

target_set:
        TOKTARGET TOKTEMPERATURE NUMBER
        {
         	printf("\tTemperature set\n");
        }
        ;

The first part is what I call the 'root'. It tells us that we have 'commands', and that these commands consist of individual 'command' parts. As you can see this rule is very recursive, because it again contains the word 'commands'. What this means is that the program is now capable of reducing a series of commands one by one. Read the chapter 'How do Lex and YACC work internally' for important details on recursion.

The second rule defines what a command is. We support only two kinds of commands, the 'heat_switch' and the 'target_set'. This is what the |-symbol signifies - 'a command consists of either a heat_switch or a target_set'.

A heat_switch consists of the HEAT token, which is simply the word 'heat', followed by a state (which we defined in the Lex file as 'on' or 'off').

Somewhat more complicated is the target_set, which consists of the TARGET token (the word 'target'), the TEMPERATURE token (the word 'temperature') and a number.

4.1.1.  A complete YACC file

The previous section only showed the grammar part of the YACC file, but there is more. This is the header that we omitted:

%{
#include <stdio.h>
#include <string.h>
 
void yyerror(const char *str)
{
 	fprintf(stderr,"error: %s\n",str);
}
 
int yywrap()
{
 	return 1;
} 
  
main()
{
  	yyparse();
} 

%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

The yyerror() function is called by YACC if it finds an error. We simply output the message passed, but there are smarter things to do. See the 'Further reading' section at the end.

The function yywrap() can be used to continue reading from another file. It is called at EOF and you can than open another file, and return 0. Or you can return 1, indicating that this is truly the end. For more about this, see the 'How do Lex and YACC work internally' chapter.

Then there is the main() function, that does nothing but set everything in motion.

The last line simply defines the tokens we will be using. These are output using y.tab.h if YACC is invoked with the '-d' option.

4.1.2.  Compiling & running the thermostat controller

lex example4.l
yacc -d example4.y
cc lex.yy.c y.tab.c -o example4 

A few things have changed. We now also invoke YACC to compile our grammar, which creates y.tab.c and y.tab.h. We then call Lex as usual. When compiling, we remove the -ll flag: we now have our own main() function and don't need the one provided by libl.

	Note
	NOTE: if you get an error about your compiler not being able to find 'yylval', add this to example4.l, just beneath #include <y.tab.h>: extern YYSTYPE yylval; This is explained in the 'How Lex and YACC work internally' section.

A sample session:

$ ./example4 
heat on
	Heat turned on or off
heat off
	Heat turned on or off
target temperature 10
	Temperature set
target humidity 20
error: parse error
$

This is not quite what we set out to achieve, but in the interest of keeping the learning curve manageable, not all cool stuff can be presented at once.

%{
#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 */;
%%

target_set: 
	TOKTARGET TOKTEMPERATURE NUMBER
	{
         	printf("\tTemperature set to %d\n",$3);
	}
        ;

heat_switch:
        TOKHEAT STATE
        {
         	if($2)
         	        printf("\tHeat turned on\n");
	 	else
                        printf("\tHeat turned off\n");
        }
        ;

4.3.  Parsing a configuration file

Let's repeat part of the configuration file we mentioned earlier:

zone "." {
        type hint;
        file "/etc/bind/db.root";
};

Remember that we already wrote a Lexer for this file. Now all we need to do is write the YACC grammar, and modify the Lexer so it returns values in a format YACC can understand.

In the lexer from Example 6 we see:

%{
#include <stdio.h>
#include "y.tab.h"
%}

%%

zone			return ZONETOK;
file			return FILETOK;
[a-zA-Z][a-zA-Z0-9]*    yylval=strdup(yytext); return WORD;
[a-zA-Z0-9\/.-]+        yylval=strdup(yytext); return FILENAME;
\"                      return QUOTE;
\{                      return OBRACE;
\}                      return EBRACE;
;                       return SEMICOLON;
\n                      /* ignore EOL */;
[ \t]+                  /* ignore whitespace */;
%%

If you look carefully, you can see that yylval has changed! We no longer expect it to be an integer, but in fact assume that it is a char *. In the interest of keeping things simple, we invoke strdup and waste a lot of memory. Please note that this may not be a problem in many areas where you only need to parse a file once, and then exit.

We want to store character strings because we are now mostly dealing with names: file names and zone names. In a later chapter we will explain how to deal with multiple types of data.

In order to tell YACC about the new type of yylval, we add this line to the header of our YACC grammar:

#define YYSTYPE char *

The grammar itself is again more complicated. We chop it in parts to make it easier to digest.

commands:
	|	 
	commands command SEMICOLON
	;


command:
	zone_set 
	;

zone_set:
	ZONETOK quotedname zonecontent
	{
		printf("Complete zone for '%s' found\n",$2);
	}
	;

This is the intro, including the aforementioned recursive 'root'. Please note that we specify that commands are terminated (and separated) by ;'s. We define one kind of command, the 'zone_set'. It consists of the ZONE token (the word 'zone'), followed by a quoted name and the 'zonecontent'. This zonecontent starts out simple enough:

zonecontent:
	OBRACE zonestatements EBRACE 

It needs to start with an OBRACE, a {. Then follow the zonestatements, followed by an EBRACE, }.

quotedname:
        QUOTE FILENAME QUOTE
        {
         	$$=$2;
        }

This section defines what a 'quotedname' is: a FILENAME between QUOTEs. Then it says something special: the value of a quotedname token is the value of the FILENAME. This means that the quotedname has as its value the filename without quotes.

This is what the magic '$$=$2;' command does. It says: my value is the value of my second part. When the quotedname is now referenced in other rules, and you access its value with the $-construct, you see the value that we set here with $$=$2.

	Note
	NOTE: this grammar chokes on filenames without either a '.' or a '/' in them.

zonestatements:
	|
	zonestatements zonestatement SEMICOLON
	;

zonestatement:
	statements
	|
	FILETOK quotedname 
	{
		printf("A zonefile name '%s' was encountered\n", $2);
	}
	;

This is a generic statement that catches all kinds of statements within the 'zone' block. We again see the recursiveness.

block: 
	OBRACE zonestatements EBRACE SEMICOLON
	;

statements:
	| statements statement
	;

statement: WORD | block | quotedname

This defines a block, and 'statements' which may be found within.

When executed, the output is like this:

$ ./example6
zone "." {
        type hint;
        file "/etc/bind/db.root";
        type hint;
};
A zonefile name '/etc/bind/db.root' was encountered
Complete zone for '.' found

Although Lex and YACC predate C++, it is possible to generate a C++ parser. While Flex includes an option to generate a C++ lexer, we won't be using that, as YACC doesn't know how to deal with it directly.

My preferred way to make a C++ parser is to have Lex generate a plain C file, and to let YACC generate C++ code. When you then link your application, you may run into some problems because the C++ code by default won't be able to find C functions, unless you've told it that those functions are extern "C".

To do so, make a C header in YACC like this:

extern "C"
{
 	int yyparse(void);
 	int yylex(void);  
 	int yywrap()
 	{
 	 	return 1;
        }

}

If you want to declare or change yydebug, you must now do it like this:

extern int yydebug;

main()
{
	yydebug=1;
	yyparse();
}

This is because C++'s One Definition Rule, which disallows multiple definitions of yydebug.

You may also find that you need to repeat the #define of YYSTYPE in your Lex file, because of C++'s stricter type checking.

To compile, do something like this:

lex bindconfig2.l
yacc --verbose --debug -d bindconfig2.y -o bindconfig2.cc
cc -c lex.yy.c -o lex.yy.o
c++ lex.yy.o bindconfig2.cc -o bindconfig2 

Because of the -o statement, y.tab.h is now called bindconfig2.cc.h, so take that into account.

To summarize: don't bother to compile your Lexer in C++, keep it in C. Make your Parser in C++ and explain your compiler that some functions are C functions with extern "C" statements.

In the YACC file, you write your own main() function, which calls yyparse() at one point. The function yyparse() is created for you by YACC, and ends up in y.tab.c.

yyparse() reads a stream of token/value pairs from yylex(), which needs to be supplied. You can code this function yourself, or have Lex do it for you. In our examples, we've chosen to leave this task to Lex.

The yylex() as written by Lex reads characters from a FILE * file pointer called yyin. If you do not set yyin, it defaults to standard input. It outputs to yyout, which if unset defaults to stdout. You can also modify yyin in the yywrap() function which is called at the end of a file. It allows you to open another file, and continue parsing.

If this is the case, have it return 0. If you want to end parsing at this file, let it return 1.

Each call to yylex() returns an integer value which represents a token type. This tells YACC what kind of token it has read. The token may optionally have a value, which should be placed in the variable yylval.

By default yylval is of type int, but you can override that from the YACC file by re#defining YYSTYPE.

The Lexer needs to be able to access yylval. In order to do so, it must be declared in the scope of the lexer as an extern variable. The original YACC neglects to do this for you, so you should add the following to your lexter, just beneath #include <y.tab.h>:

extern YYSTYPE yylval;

Bison, which most people are using these days, does this for you automatically.

[0-9]+          yylval=atoi(yytext); return NUMBER;
[ \n]+          /* eat whitespace */;
-               return MINUS;
\*              return MULT; 
\+              return PLUS;
...

	exp: 	NUMBER 
		|
		exp PLUS exp
		|
		exp MINUS exp
		|
		exp MULT exp

[0-9]+          yylval=atoi(yytext); return NUMBER;
[ \n]+          /* eat whitespace */;
.               return (int) yytext[0];

	exp: 	NUMBER 
		|
		exp '+' exp
		|
		exp '-' exp
		|
		exp '*' exp

commands: /* empty */
	|
	commands command

commands: /* empty */
	|
	command commands

commands: /* empty */
	|
	command SEMICOLON commands

commands: /* empty */
	|
	commands command SEMICOLON

heater mainbuiling
	Selected 'mainbuilding' heater
target temperature 23
	'mainbuilding' heater target temperature now 23

%token TOKHEATER TOKHEAT TOKTARGET TOKTEMPERATURE

%union 
{
        int number;
        char *string;
}

%token <number> STATE
%token <number> NUMBER
%token <string> WORD

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

heater_select:
        TOKHEATER WORD
	{
	 	printf("\tSelected heater '%s'\n",$2);
        	heater=$2;
	}
        ;

target_set:
        TOKTARGET TOKTEMPERATURE NUMBER
        {
	 	printf("\tHeater '%s' temperature set to %d\n",heater,$3);
  	}
	;

Especially when learning, it is important to have debugging facilities. Luckily, YACC can give a lot of feedback. This feedback comes at the cost of some overhead, so you need to supply some switches to enable it.

When compiling your grammar, add --debug and --verbose to the YACC commandline. In your grammar C heading, add the following:

int yydebug=1;

This will generate the file 'y.output' which explains the state machine that was created.

When you now run the generated binary, it will output a *lot* of what is happening. This includes what state the state machine currently has, and what tokens are being read.

Peter Jinks wrote a page on debugging which contains some common errors and how to solve them.

state 0

    ZONETOK     , and go to state 1

    $default    reduce using rule 1 (commands)

    commands    go to state 29
    command     go to state 2
    zone_set    go to state 3

state 1

    zone_set  ->  ZONETOK . quotedname zonecontent   (rule 4)

    QUOTE       , and go to state 4

    quotedname  go to state 5

delete heater all
delete heater number1

	delete_heaters:
		TOKDELETE TOKHEATER mode
		{
			deleteheaters($3);
		}
	
	mode:	WORD

	delete_a_heater:
		TOKDELETE TOKHEATER WORD
		{
			delete($3);
		}

GNU YACC (Bison) comes with a very nice info-file (.info) which documents the YACC syntax very well. It mentions Lex only once, but otherwise it's very good. You can read .info files with Emacs or with the very nice tool 'pinfo'. It is also available on the GNU site: BISON Manual.

Flex comes with a good manpage which is very useful if you already have a rough understanding of what Flex does. The Flex Manual is also available online.

After this introduction to Lex and YACC, you may find that you need more information. I haven't read any of these books yet, but they sound good:

Thomas Niemann wrote a document discussing how to write compilers and calculators with Lex & YACC. You can find it here.

The moderated usenet newsgroup comp.compilers can also be very useful but please keep in mind that the people there are not a dedicated parser helpdesk! Before posting, read their interesting page and especially the FAQ.

Lex - A Lexical Analyzer Generator by M. E. Lesk and E. Schmidt is one of the original reference papers. It can be found here.

Yacc: Yet Another Compiler-Compiler by Stephen C. Johnson is one of the original reference papers for YACC. It can be found here. It contains useful hints on style.