Building Parsers with Leopurd

Whether it's from a user, script file, or serial line, input often must be broken into logical parts before it can be processed. Many programmers resort to nested conditions involving string comparisons, but the resulting code can be hard to understand and maintain. Sometimes a brute-force approach is not sufficient, and trusty old yacc is used to generate a "real" parser. The advantage of this approach is that only the grammar must be maintained; the disadvantage is that yacc generates table-driven parsers that are difficult to read and modify manually. In this article, I'll present leopurd, a program that generates a maintainable, table-free parser from an input grammar.

The two types of parsers in widespread use are top-down and bottom-up. All parsers read language tokens from an input stream and examine them against a set of production rules. Each rule has a left side--the target--and a right side describing a valid way to reach the target. More than one production rule can be associated with each target.

A typical bottom-up parser determines which production rule to apply for a given input sequence by implementing rules as lookup tables. When the parser receives the first token, it tags all rules that can begin with that token. As it reads more tokens, it eliminates candidate rules until only one remains. This process involves guesswork and backtracking. The code implementing table-driven, bottom-up parsers is illegible and difficult to modify, and parser speed often is slower than that of top-down parsers. However, plenty of tools generate bottom-up parsers automatically, and such parsers can always be generated for an unambiguous grammar that requires no more than one token look ahead. Bottom-up parsers include those generated by yacc, bison, and similar programs.

Most handcoded parsers are of the top-down variety, and start with the top-level rule in the grammar. They examine input to see if they can complete this rule. If not, other functions are called to parse any candidate rules. As each rule is completed, the corresponding function executes action code associated with the rule and returns control to the caller. Top-down parsers are easier to modify and optimize than table-driven parsers--the parser can often be made both smaller and faster. However, no standardized tools exist for generating top-down parsers, and some grammars cannot be implemented correctly as top-down parsers. (Fortunately, most popular computer languages can be easily parsed this way.)

The leopurd parser combines the best features of both top-down and bottom-up parsers. It builds legible, maintainable, optimizable top-down parsers from standard grammars similar to yacc grammars. Leopurd generates two C source files from an input grammar: yyleo.h, containing definitions and function prototypes; and yyleo.c, containing the parser source code and any user-supplied code.

Leopurd's input grammar describes the syntax of the parser input. The syntax of a language tells you only if a sentence is valid; the sentence's meaning is the realm of semantics. Leopurd supports a subset of the yacc definition language, but it lacks a literal block, associativity, %type and %union statements in the definition section, and C action statements in the rules section. Future versions of leopurd should be fully compatible with yacc.

Leopurd generates C code to implement a top-down recursive descent parser from an input grammar. The entry point to the parser is the function yyparse(). The parsing target for yyparse() is the top-most nonterminal symbol in the grammar. Since there can be only one yyparse(), there can be only one top-level target.

Because error handling varies widely between applications, leopurd generates only the prototype of the error handler, yyerror().

Leopurd also generates prototypes for the functions next() and match(). A call to next() causes the next token to be read from the input stream. A subsequent call to match() evaluates whether the argument matches the token read from input. These functions are highly dependent on the nature of the input and are left up to you to implement.

Two functions are generated for each nonterminal symbol: <name>_parse() and <name>_action(). The <name>_parse functions are generated completely by leopurd and perform the actual parsing of the nonterminal symbol <name>.

The <name>_action() functions are placeholders for the language's semantics. Leopurd generates a function skeleton, to which you add actions to be taken upon successful parsing of the token. Separating syntax and semantics in this way increases portability and maintainability, and simplifies testing and debugging.

An abstract, top-down parser parses a sentence by building a parse tree, in which each node represents a token. After a tree is built, the parser traverses the tree in postorder, executing code associated with each node. If the parser cannot generate a tree, it flags an error and returns.

Recursive-descent parsers generate parse trees implicitly by calling parse functions recursively. Upon a successful parse, the leaf function returns. As each parse function returns, its action code executes.

Parsing starts with the yyparse() function, which gets the first token from the input by calling next(). yyparse() then determines which production rule to use by calling match(). When a match is found, the parser does one of two things: If it expects a terminal token, it gets the next token and checks it by calling match(); if it expects a nonterminal symbol, it calls the symbol's <name>_parse() function. This process continues until an error is encountered, in which case yyerror() is called or the production rule is parsed successfully. Upon success, the last <name>_parse() function calls <name>_action(), which executes code associated with <name>. After <name>_action() returns, the process continues until the whole parse tree is unwound. Finally, any actions associated with yyparse() are executed, and yyparse() returns.

Since functions return in the reverse of the order in which they are called, the <name>_action() code of leaf nodes exe-cutes before code closer to the root. Thus, a production far down in the grammar has precedence over one further up. This is how the grammar's structure determines operator precedence. (Right-recursive rules result in right-association for operations.)

How does the parser determine which production rule to select? How do you determine which tokens to match against? For terminal tokens, the parser just matches against the token itself. For nonterminals, it must know which terminal tokens can legally begin a particular nonterminal. That set of tokens for a nonterminal n is called "first of n" and is written FIRST(n).

For a nullable nonterminal, you must determine which terminal tokens can legally come after the empty nonterminal. That set of tokens is called "follow of n" and written FOLLOW(n). Finding the FIRST() and FOLLOW() sets is an iterative process. Once the sets are defined, leopurd knows which tokens to match in each rule.

The complete C source code for the current version of leopurd is available electronically (see "Availability," page 3). LITE.H contains definitions common to all source files. It defines the symbol LIST, resulting in visible run-time trace on stdout. For leopurd to run quietly, you must undefine LIST. The scanner is found in LITE1.C. LITE2.C contains functions to parse the definition and user sections. The rules section is parsed by functions in LITE3.C. LITE4.C contains functions that calculate FIRST() and FOLLOW() sets and build the parser.

Leopurd itself is constructed around several top-down parsers. The source code also shows ways to implement the next(), match(), and yyerror() functions, as well as a simple scanner, yylex().

The code generator in LITE5.C produces ANSI C output. It is relatively easy to modify to produce code for other languages.

The source code is ANSI C compliant, with the exception of calls to strdup(), a non-ANSI function supported by many compilers. They can be replaced with calls to malloc(), strlen(), and strncpy(). Leo-purd compiles cleanly using Borland C++ and Turbo C under MS-DOS, and on many UNIX platforms.

%token NUMBER
%token '+' MINUS
%token '='
%%

expression: sum '=' |
        difference '='
        ;
sum:    NUMBER '+' NUMBER |
        NUMBER '+' sum |
        EMPTY
        ;
difference:
        NUMBER MINUS NUMBER |
        NUMBER MINUS difference
        ;
%%

#include <stdio.h>
#include <stdlib.h>
static int line_number=0;
/* print an error message */
void yyerror(char *msg_str){
    printf("Error! line %d: %s\n",
line_number,msg_str);
}
int main(){
    int rc;
    while(!(rc=yyparse()));
    exit(rc);
}

 statement:
  while '(' expression ')' statement ;