Miniyacc

A Lightweight Yacc for C

This single-file program implements a useful subset of POSIX yacc. It lets you describe a language with an unambiguous LALR(1) grammar and compiles it into a fast C parser for that language. Because it is so simple, you can use it to learn about parser generation. You can also use it to quickly bootstrap a yacc for another language. Finally, because it is standalone and under MIT/X license, you can integrate it very easily in your programs.

• Get a working version of yacc.c.
  Compilation is as simple as cc yacc.c -o yacc.
• Read the MIT/X license.
• You can browse the source.
  Or check it out at git://c9x.me/miniyacc.git.

Example

Here is a complete minimal example to get started. You can compile it using yacc xmpl.y && cc y.tab.c. Then use the input "2*(3+4*3+1)" to test it, for example.

%{
	#include <stdio.h>
	int yylex(void);
%}
%token INT
%left '+'
%left '*'
%%
prog: expr          { printf("-> %d\n", $1); } ;
expr: INT
    | '(' expr ')'  { $$ = $2; }
    | expr '+' expr { $$ = $1 + $3; }
    | expr '*' expr { $$ = $1 * $3; } ;
%%
int yylex() {    /* crude lexer */
	int c = getchar();
	if (c >= '0' && c <= '9') {
		yylval = c-'0';
		return INT;
	}
	return c == EOF ? 0 : c;
}
int main() { return yyparse(); }

Features

• Short and hacker-friendly C89 implementation.
• Mostly POSIX (-b, -d, and -v are supported).
• Standalone (the skeleton code is in the source).
• Generated tables are as efficient as GNU bison's.
• Reasonably fast implementation (<1s for 500+ grammar rules).
• Supports #line directives.

The two main features lacking to make it fully POSIX compliant are error recovery and mid-action rules (although these can be emulated by adding a few extra non-terminals with an empty production). Negative references into the parsing stack are also unsupported.

Hacker's Guide

Yacc is a complex program, to understand it one must first understand the basics of shift-reduce parsers and get a high level idea of how LR state generation goes. I cannot cover these topics here because I know I will make a poor job at it. The Dragon Book has excellent coverage for them and the first edition (which is more than enough) can be found for a couple of dollars on Amazon (I bought one there and I'm extremely happy with it). If you contact me in person, I can provide additional documentation. In the sequel I will assume that you are a bit familiar with the terminology.

My implementation is divided into four parts, the first one deals with straightforward inference of properties on the grammar (is a non-terminal nullable, what is its FIRST set); the second part implements the primitve operations GOTO and CLOSURE on sets of LALR(1) items together with the state generation; the third part figures out the final parsing tables and compresses them; finally the last part and also the simplest deals with all the .y parsing and the .c/.h printing.

With loose discipline, I prefixed most functions of the first three parts with respectively, g, i and tbl. Also, the order in which I listed the parts is the order in which you will find them in the source. This gives you a basic way to navigate the code. What follows is a high level description of every important function and type.

E -> E . O E
O -> . A
A -> . '+'
A -> . '-'

A Yacc program is expected to generate two main tables: the goto table and the action table. In practice, one needs to generate a few more. Here is a description of all the tables generated by the yacc.c program.

1. yytrns POSIX requires that 'c' for every c is a valid token, we use this table to map tokens given by yylex to a smaller range (this makes the tables more compact).
2. yyr1 maps a rule number to the arity (number of elements in the rhs) of this rule.
3. yyr2 maps a rule number to the lhs symbol of this rule.
4. yyadef maps a state to the default reduce for this state, or -1 if the state cannot reduce.
5. yygdef maps a non-terminal to its most frequent GOTO destination. (Remember that the gotos are indexed [nonterm][state].)
6. yyadsp maps states to displacements for actions.
7. yygdsp maps non-terminals to displacements for gotos.
8. yyact contains actions and gotos, this is the most important table together with the next one.
9. yychk is the checking table for yyact.

The scheme used to store tables in a space-efficient manner uses what we call a row displacement table. The idea is described very well in Robert Tarjan's paper Storing a sparse table, it is also described in section 3.9 of the Dragon Book. I will try to sum it up in a few words. Assume we want to store efficiently a table A with many zeroes inside, we also would like that the access in the compacted table is in constant time. To do this, we linearize the table A into a simple array and overlap the different rows of A to make sure very few zeroes are left. Each original row of A will be assigned a displacement into the linear array. The following figure shows an example of this packing process on a sample table, the r{n} number is the displacement of the original row n. Stars in the A table represent non-zero entries.

The above figure does not show the table T that stores all the non-zero entries, instead it shows the checking table C. Using the displacements r{n}, it is easy to construct T. The table C is used for retrieval of data: to get the entry A[n][m] (if n and m are 1-indexed) we use the algorithm below.

x := r{n} + m
if (x <= 0) || (x > size of C) || (C[x] != (n-1)*5 + m-1) then
    return 0
else
    return T[x]
fi

Notice how the C table holds the cell number of the corresponding entry stored in the A table. It is also sufficient to make C store only the row number of the entry stored in A, this makes the numbers stored in C smaller and can help save a few bytes. This is what we do for the goto table: the checking table yychk stores only non-terminal numbers for validation. You can see how they are checked in code0, the skeleton code for C files generation.

The case of the action table is a bit trickier. One can easily observe that many rows in an action table are often identical, so we would like to assign these rows the same displacement. This is possible but what is stored in the checking table needs to be changed. Indeed, the whole point of the checking table is that no two entries of A can be validated at the same location in T. One way to make this compression possible is to store the column number in the checking table instead of the row number. This way, two same rows can be assigned the same displacement and will both be correctly validated by the checking table. This explains why the yychk table checks action entries based on token number (and not on state number).

We can now discuss the way to find the displacements r{n} used above. There is a fairly straightforward greedy algorithm that works well for that (it is explained in Tarjan's paper why). We simply sort the rows by decreasing number of non-zero entries and greedily assign the first-fit displacements for all the rows. This explains why there are qsort calls in the actgen function. You can check that the displacements for A above were generated with this technique. This is all nice and simple, but when we play the trick explained in the previous paragraph we have to be a bit careful. The risk is that a naive implementation of the algorithm described here could assign the same displacement to the two following rows.

Colmns   1 2 3 4 5 6 7 8 9
-------+-------------------+
       ...
Row n  | 0 0 3 0 4 0 0 0 6 |
       ...
Row m  | 0 0 3 0 0 0 0 0 6 |

Row m is "included" in row n, a naive implementation could give them the same displacement, but then, when querying the entry [m][5], one would get 4 as an answer (becasue the checking table would validate the column 5 for row n) and not 0! This is a potential source of nasty bugs. The lesson is that rows must be assigned the same displacement if and only if they are exactly the same. The loop in actgen makes sure it is the case by relying on the fact that entries are supplied in decreasing number of non-zero entries. This is probably the trickiest part of table generation (and it is also a performance hog), I would be happy to take your suggestions about that.

I want to conclude these remarks on table generation/compression by saying that if this remains opaque for you, the best we to understand it is to use a very small grammar (infix addition and multiplication for example), run it through yacc.c with the -v option and decypher the code generated using the y.output file, a pen, and some paper. You might even discover a bug that way!