Man Linux: Main Page and Category List

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)