NAME
btyacc — an LALR(1) parser generator with support for backtracking
SYNOPSIS
btyacc [-b prefix] [-d] [-DNAME ...] [-E] [-l] [-r] [-S x.ske]
[-t] [-v] filename.y
Description
btyacc is a modified version of byacc (Berkeley YACC), which in turn is
a public domain version of the original AT&T YACC parser generator.
btyacc reads the grammar specification in the file filename.y and
generates an LR(1) parser for it. The parser consists of a set of
LALR(1) parsing tables and a driver routine written in the C
programming language. btyacc normally writes the parse tables and the
driver routine to the file prefix.tab.c, where prefix defaults to ‘y’.
For a detailed description of the format of a grammar specification,
and an excellent tutorial on how to use YACC-like tools, see the info
manual for GNU bison. btyacc-specific extensions are explained below.
Note: The parser skeleton supplied by btyacc’s upstream author only
compiles as C++. Use the skeleton /usr/doc/btyacc/examples/btyacc-c.ske
to generate a parser that compiles both as C and C++. (Unfortunately,
this alternative skeleton does not currently check malloc() return
values.)
Options
-b prefix Change the prefix prepended to the output file names to the
string denoted by prefix. The default prefix is the
character ‘y’.
-d Create a header file called prefix.tab.h along with
prefix.tab.c, containing the symbol definitions and a
declaration for YYSTYPE and yylval.
-DNAME Define the btyacc preprocessor variable NAME, for use with
%ifdef NAME directives in the grammar file.
-E Print the preprocessed grammar to standard output.
-l Do not insert #line directives into the generated parser
code.
-r Write the parser code and the associated tables to different
files. Whereas the tables can be found in prefix.tab.c
as before, the code now gets written to prefix.code.c.
-S x.ske Select a different parser skeleton. The default skeleton is
hardwired into the program, but a copy can be found in the
file btyaccpa.ske.
-t Cause debugging code to be compiled into the generated
parser.
-v Write a human-readable description of the generated parser to
y.output. It includes parser states, actions for a look-ahead
token and information about any conflicts.
BTYACC extensions
Backtracking support
Whenever a btyacc generated parser runs into a shift-reduce or reduce-
reduce error in the parse table, it remembers the current parse point
(stack and input stream state), and goes into trial parse mode. It then
continues parsing, ignoring most rule actions. If it runs into an error
(either through the parse table or through an action calling YYERROR),
it backtracks to the most recent conflict point and tries a different
alternative. If it finds a successful path (reaches the end of the
input or an action calls YYVALID), it backtracks to the point where it
first entered trial parse mode, and continues with a full parse
(executing all actions), following the path of the successful trial.
Actions in btyacc come in two flavors: {} actions, which are only
executed when not in trial mode, and [] actions, which are executed
regardless of mode.
Example: In YACC grammars for C, a standard hack known as the "lexer
feedback hack" is used to find typedef names. The lexer uses semantic
information to decide if any given identifier is a typedef name or not
and returns a special token. With btyacc, you no longer need to do
this; the lexer should just always return an identifier. The btyacc
grammar then needs a rule of the form:
typename: ID [ if (!IsTypeName(LookupId($1))) YYERROR; ]
However, note that adding backtracking rules slows down the parser. In
practice, you should try to restrict the number of conflicts in the
grammar to what is absolutely necessary. Consider using the "lexer
feedback hack" if it is a clean solution, and reserve backtracking for
a few special cases.
btyacc runs its trials using the rule "try shifting first, then try
reducing in the order that the conflicting rules appear in the input
file". This means you can implement semantic disambiguation rules like,
for example: (1) If it looks like a declaration it is, otherwise (2) If
it looks like an expression it is, otherwise (3) it is a syntax error
[Ellis & Stroustrup, Annotated C++ Reference Manual, p93]. To achieve
this, put all the rules for declarations before the rules for
expressions in the grammar file.
Backtracking is only triggered when the parse hits a shift/reduce or
reduce/reduce conflict in the table. If you have no conflicts in your
grammar, there is no extra cost, other than some extra code which will
never be invoked.
Currently, the generated parser performs no pruning of alternate
parsing paths. To avoid an exponential explosion of possible paths (and
parsing time), you need to manually tell the parser when it can throw
away saved paths using the YYVALID statement. In practice, this
turns out to be fairly easy to do. For example, a C++ parser can just
contain [YYVALID;] after every complete declaration and statement rule,
resulting in the backtracking state being pruned after seeing a ‘;’ or
‘}’ - there will never be a situation in which it is useful to
backtrack past either of these.
Improved token position handling
Compilers often need to build ASTs (abstract syntax trees) such that
every node in a tree can relate to the parsed program source it came
from. The YYPOSN mechanism supported by btyacc helps you in
automating the text position computation and in assigning the computed
text positions to the AST nodes.
In standard YACCs every token and every non-terminal has an YYSTYPE
semantic value attached to it. With btyacc, every token and every non-
terminal also has an YYPOSN text position attached to it. YYPOSN is a
user-defined type.
btyacc maintains a stack of text position values in the same way that
it maintains a stack of semantic values. To make use of the text
position feature, you need to #define the following:
YYPOSN Preprocessor symbol for the C/C++ type of the text position
attached to every token and non-terminal.
yyposn Global variable of type YYPOSN. The lexer must assign the
text position of the returned token to yyposn, just like it
assigns the semantic value of the returned token to yylval.
YYREDUCEPOSNFUNC
Preprocessor symbol for a function that is called immediately
after the regular grammar rule reduction has been performed,
to reduce text positions located on the stack.
Typically, this function extracts text positions from the
right-hand side rule components and either assigns them to
the returned $$ structure/tree or, if no $$ value is
returned, puts them into the ret text position where it will
be picked up by other rules later. Its prototype is:
void ReducePosn(
YYPOSN& ret,
YYPOSN* term_posns,
YYSTYPE* term_vals,
int term_no,
int stk_pos,
int yychar,
YYPOSN& yyposn,
UserType extra);
ret Reference to the text position returned by the rule.
You must overwrite this with the computed text
position that the rule yields, analogous to the $$
semantic value.
term_posns
Array of the right-hand side rule components’ YYPOSN
text positions, analogous to $1, $2, ..., $N for the
semantic values.
term_vals Array of the right-hand side rule components’ YYSTYPE
values. These are the $1, ..., $N themselves.
term_no Number of components in the right hand side of the
reduced rule, i.e. the size of the term_posns and
term_vals arrays. Also equal to N in $1, ..., $N.
stk_pos YYSTYPE/YYPOSN stack position before
the reduction.
yychar Lookahead token that immediately follows the reduced
right hand side components.
yyposn YYPOSN of the token that immediately follows the
reduced right hand side components.
extra User-defined extra argument passed to ReducePosn.
YYREDUCEPOSNFUNCARG
Extra argument passed to the ReducePosn function. This
argument can be any variable defined in btyaccpa.ske.
Token deallocation during error recovery
For most YACC-like parser generators, the action of the generated
parser upon encountering a parse error is to throw away semantic values
and input tokens until a rule containing the special non-terminal error
can be matched. Discarding of tokens is simply performed by overwriting
variables and array entries of type YYSTYPE with new values.
Unfortunately, this approach leads to a memory leak if YYSTYPE is a
pointer type. btyacc allows you to supply functions for cleaning up the
semantic and text position values, by #defineing the following symbols
in the preamble of your grammar file:
YYDELETEVAL
Preprocessor symbol for a function to call before the
semantic value of a token or non-terminal is discarded.
YYDELETEPOSN
Preprocessor symbol for a function to call before the text
position of a token or non-terminal is discarded.
Both functions are called with two arguments. The first argument of
type YYSTYPE or YYPOSN is the value that will be discarded. The second
argument is of type int and is one of three values:
0 discarding input token
1 discarding state on stack
2 cleaning up stack when aborting
Detailed syntax error reporting
If you #define the preprocessor variable YYERROR_DETAILED in your
grammar file, you must also define the following error processing
function:
void yyerror_detailed(
char* text,
int errt,
YYSTYPE&
errt_value,
YYPOSN& errt_posn);
text error message
errt code of the token that caused the error
errt_value
value of the token that caused the error
errt_posn text position of token that caused error
Preprocessor directives
btyacc supports defining symbols and acting on them with conditional
directives inside grammar files, not unlike the C preprocessor.
%define NAME
Define the preprocessor symbol NAME. Equivalent to the
command line switch -DNAME.
%ifdef NAME
If preprocessor variable NAME is defined, process the text
from this %ifdef to the closing %endif, otherwise skip it.
%endif Closing directive for %ifdef. %ifdefs cannot be nested.
%include FILENAME
Process contents of the file named FILENAME. Only one nesting
level of %include is allowed.
%ident STRING
Insert an ‘#ident STRING’ directive into the output file.
STRING must be a string constant enclosed in "".
Inherited attributes
Inherited attributes are undocumented. (See the README and the btyacc
source code for a little information.) If you work out how they work,
contact me at <atterer@debian.org>!
Bugs
The worst-case complexity of parsing is exponential for any grammar
which allows backtracking to take place. In other words, a btyacc-
generated parser constitutes a denial-of-service bug if used in
applications where an attacker is able to supply specially crafted data
as input to the parser. (For all "regular" input data, the potentially
exponential complexity is not normally an issue.)
bison’s %expect directive is not supported.
There is no %else and %ifndef. %ifdefs and %includes cannot be nested.
Authors
Robert Corbett <robert.corbett@eng.sun.com> / <corbett@berkeley.edu>
was one of the original authors of Berkeley byacc. Chris Dodd
<chrisd@reservoir.com> had the brilliant idea of adding backtracking
capabilities, and is responsible for the initial backtracking changes.
Vadim Maslov <vadik@siber.com> further improved the code.
This documenation was written by Richard Atterer <atterer@debian.org>
for the Debian GNU/Linux distribution, but is donated to the public
domain and may thus be used freely for any purpose.
Files
/usr/doc/btyacc/examples/btyaccpa.ske
/usr/doc/btyacc/examples/btyacc-c.ske
/usr/doc/btyacc/README
See also
bison(1) (or ‘info bison’), byacc(1), yacc(1), antlr(1)
btyacc(1)