Until 1975, writing a compiler was a very time-consuming process. In 1975 papers were published on lex and yacc. These utilities greatly simplify compiler writing.
Lex generates C code for a lexical analyzer, or scanner. It uses patterns that match strings in the input and converts the strings to tokens. Tokens are numerical representations of strings, and simplify processing. This is in the figure below. As lex finds identifiers in the input stream, it enters them in a symbol table. The symbol table may also contain other information such as data type (integer or real) and location of the variable in memory. All subsequent references to identifiers refer to the appropriate symbol table index.
Yacc generates C code for a syntax analyzer, or parser. Yacc uses grammar rules that allow it to analyze tokens from lex and create a syntax tree. A syntax tree imposes a hierarchical structure on tokens. For example, operator precedence and associativity are apparent in the syntax tree. The next step, code generation, does a depth-first walk of the syntax tree to generate code. Some compilers produce machine code, while others, as shown above, output assembly.
The figure above illustrates the file naming conventions used by lex and yacc. We'll assume our goal is to write a BASIC compiler. First, we need to specify all pattern matching rules for lex ( bas.l ) and grammar rules for yacc ( bas.y ). Commands to create our compiler, bas.exe , are listed below:
yacc �d bas.y # create y.tab.h, y.tab.c lex bas.l # create lex.yy.c cc lex.yy.c y.tab.c �obas.exe # compile/link
Yacc reads the grammar descriptions in bas.y and generates a parser, function yyparse , in file y.tab.c . Included in file bas.y are token declarations. The �d option causes yacc to generate definitions for tokens and place them in file y.tab.h . Lex reads the pattern descriptions in bas.l , includes file y.tab.h , and generates a lexical analyzer, function yylex , in file lex.yy.c . Finally, the lexer and parser are compiled and linked together to form the executable, bas.exe . From main , we call yyparse to run the compiler. Function yyparse automatically calls yylex to obtain each token.
The first phase in a compiler reads the input source and converts strings in the source to tokens. Using regular expressions, we can specify patterns to lex that allow it to scan and match strings in the input. Each pattern in lex has an associated action. Typically an action returns a token, representing the matched string, for subsequent use by the parser. To begin with, however, we will simply print the matched string rather than return a token value. We may scan for identifiers using the regular expression:
letter(letter|digit)*
This pattern matches a string of characters that begins with a single letter, and is followed by zero or more letters or digits. This example nicely illustrates operations allowed in regular expressions:
Any regular expression expressions may be expressed as a finite state automaton (FSA). We can represent an FSA using states, and transitions between states. There is one start state, and one or more final or accepting states.
Any FSA may be expressed as a computer program. For example, our 3-state machine is easily programmed:
start: goto state0 state0: read c if c = letter goto state1 goto state0 state1: read c if c = letter goto state1 if c = digit goto state1 goto state2 state2: accept string
This is the technique used by lex. Regular expressions are translated by lex to a computer program that mimics an FSA. Using the next input character, and current state, the next state is easily determined by indexing into a computer-generated state table.
Grammars for yacc are described using a variant of Backus Naur Form (BNF). This technique was pioneered by John Backus and Peter Naur, and used to describe ALGOL60. A BNF grammar can be used to express context-free languages. Most constructs in modern programming languages can be represented in BNF. For example, the grammar for an expression that multiplies and adds numbers is
1 E -> E + E 2 E -> E * E 3 E -> id
Three productions have been specified. Terms that appear on the left-hand side (lhs) of a production, such as E (expression) are nonterminals. Terms such as id (identifier) are terminals (tokens returned by lex) and only appear on the right-hand side (rhs) of a production. This grammar specifies that an expression may be the sum of two expressions, the product of two expressions, or an identifier.
At each step we expanded a term, replacing the lhs of a production with the corresponding rhs. The numbers on the right indicate which rule applied. To parse an expression, we actually need to do the reverse operation. Instead of starting with a single nonterminal (start symbol) and generating an expression from a grammar, we need to reduce an expression to a single nonterminal. This is known as bottom-up or shift-reduce parsing, and uses a stack for storing terms. Here is the same derivation, but in reverse order:
/* calculator #1 */
%{
#include "y.tab.h"
%}
%%
[a-z] {
yylval = *yytext - 'a';
return VARIABLE;
}
[0-9]+ {
yylval = atoi(yytext);
return INTEGER;
}
[-+()=/*\n] { return *yytext; }
[ \t] ; /* skip whitespace */
. yyerror("Unknown character");
%%
int yywrap(void) {
return 1;
}
%{
int sym[26];
%}
%token INTEGER VARIABLE
%left '+' '-'
%left '*' '/'
%%
program:
program statement '\n'
| /* NULL */
;
statement:
expression { printf("%d\n", $1); }
| VARIABLE '=' expression { sym[$1] = $3; }
;
expression:
INTEGER
| VARIABLE { $$ = sym[$1]; }
| expression '+' expression { $$ = $1 + $3; }
| expression '-' expression { $$ = $1 - $3; }
| expression '*' expression { $$ = $1 * $3; }
| expression '/' expression { $$ = $1 / $3; }
| '(' expression ')' { $$ = $2; }
;
%%
int yyerror(char *s) {
fprintf(stderr, "%s\n", s);
}
int main(void) {
yyparse();
}