HYACC(1)                                                              HYACC(1)



NAME
       hyacc  - LR(0)/LALR(1)/LR(1)/LR(k) parser generator. Similar utility as
       yacc and bison.

SYNOPSIS
       hyacc -?
       hyacc -h
       hyacc --help
       hyacc -V
       hyacc --version
       hyacc [-bcCdDghKlmnoOPQRStvV]
             [-b file-name-prefix] [--file-prefix==file-name-prefix]
             [-c] [--no-compiler]
             [-C] [--keep-unit-production-with-action]
             [-d] [--defines]
             [-Di] (i = 0~15)
             [-g] [--graphviz]
             [-h] [--help]
             [-K] [--lrk]
             [-l] [--no-lines]
             [-m] [--man-page]
             [-o output-file-name] [--output-file==output-file-name]
             [-Oi] (i = 0~3)
             [-P] [--lane-tracing-pgm]
             [-Q] [--lane-tracing-ltt]
             [-R] [--lalr1]
             [-S] [--lr0]
             [-t] [--debug]
             [-v] [--verbose]
             [-V] [--version]


DESCRIPTION
       Hyacc is a program similar to yacc(1) and bison (LALR(1) parser genera-
       tors),  but which accepts all LR(1) grammars and thus are more powerful
       than yacc(1) and bison.  It is backward compatible with input files  of
       yacc(1)  and bison.  Hyacc also contains LR(0) algorithm, LALR(1) algo-
       rithm (based on lane-tracing) and a partially working  LR(k)  algorithm
       (also based on lane-tracing).

       Input  files  should better follow the yacc convention of ending in .y,
       but don't have to. By default, the output file is y.tab.c. When you use
       -d  you  also  get  y.tab.h, and when you use -v you also get y.output,
       same as yacc. The user can use the -b or -o  switches  to  specify  the
       output file names.

       Hyacc supports both traditional single letter options and mnemonic long
       option names. Long option names are indicated with  --  instead  of  -.
       When  a  long  option  takes an argument, like file-prefix, connect the
       option name and the argument with ==.


   OPTIONS
       Command line options are decribed below.

       Most options may be give in one of two forms: either a dash followed by
       a single letter, or two dashes followed by a long option name.


       -b fileprefix
       --file-prefix==fileprefix
              Specify  a  prefix  to use for all hyacc output file names.  The
              names are chosen as if the input file were named fileprefix.c.


       -c
              Use this switch  to  not  generate  parser  files  (y.tab.c  and
              y.tab.h).  This is useful when the user only wants to use the -v
              and -D switches to parse the grammar and check the y.output file
              about the grammar's information.

              -c generally is used with -v, -D and -C.


       -C
              For the unit production removal optimization (when -O2 or -O3 is
              used), if a unit production rule has semantic action, when it is
              removed  the  semantic  action won't be preserved, so the output
              compiler will miss some code.

              To solve this problem, by default HYACC adds a placeholder  non-
              terminal to unit production rules with actions, so they won't be
              removed. E.g., from
              program : expression              {printf("answer = %d\n", $1);}
                      ;
              to
              program : expression $PlaceHolder {printf("answer = %d\n", $1);}
                      ;
              $PlaceHolder : /* empty */
                           ;

              If the -C switch is used, this default action will not be taken.
              This  is  used when the user wants to just parse the grammar and
              does not care about generating a useful compiler.  Specifically,
              -C is used together with switch -c.


       -d
       --define
              Write  an extra output file containing macro definitions for the
              token type names defined in the grammar.

              The file is named y.tab.h.

              This output file is essential if you wish to put the  definition
              of  yylex  in  a separate source file, because yylex needs to be
              able to refer to token type codes and the variable yylaval.   In
              such  case  y.tab.h  should be included into the file containing
              yylex.


       -D
              Change the print option to  debug  file  y.output.  A  user  who
              checks  the debug file should assume certain degree of knowledge
              to the LR(1) compiler theory and optimization algorithms.

              If the -v options is used, a debug file y.output will be  gener-
              ated  when  hyacc parses the grammar file. Use of -D switch will
              automatically turn on the -v switch, and will allow  to  specify
              what kind of information to be included into y.output.

              By default, use -v will output the information about the states,
              plus a short statistics summary of the number of  the  grammar's
              terminals,  nonterminals,  grammar  rules  and states.  like the
              y.output file of yacc.

              -D should be followed by a parameter from 0 ~ 14:

              -D0
              Include all the information available.

              -D1
              Include the grammar.

              -D2
              Include the parsing table.

              -D3
              Include the process of generating  the  parsing  machine,  basi-
              cally, the number of states and the current state in each cycle.

              -D4
              This is useful only if  at  the  time  of  compilation,  in  y.h
              USE_CONFIG_QUEUE_FOR_GET_CLOSURE  is  set  to 0.  This then will
              include the information of combining compatible  configurations:
              the  number  of configurations before and after the combination.
              -D4 can be used together with -D3.

              -D5
              Include the information of the multi-rooted  tree(s)  built  for
              the optimization of removing unit productions.

              -D6
              Include  the  information  in  the optimization of removing unit
              productions. Specifically, the new states created and the origi-
              nal states from which the new states are combined from.

              -D7
              Include  the  information  of  the step 4 in the optimization of
              removing unit productions. Specifically, this shows  the  states
              reachable from state 0.

              -D8
              Show  the  entire parsing table after removing unit productions,
              including those states that will be removed.

              -D9
              Show a list of configurations and  the  theads  of  the  strings
              after the scanning symbol.

              -D10
              Include information of the symbol hash table.

              -D11
              Include  the  information  of shift/shift conflicts if any. This
              happens when the input grammar is not LR(1)  or  ambiguous,  and
              the optimization of removing unit production is used. The occur-
              rence of shift/shift conflicts means the optimization of  remov-
              ing  unit  productions  (-O2  and -O3) cannot be applied to this
              grammar.

              -D12
              NOT to include the default information about states when the  -v
              option  is used. Use -D12 to show only the short statistics sum-
              mary, and not the states list.

              -D13
              Include the statistics of configurations  for  each  state,  and
              also dump the state hash table.

              -D14
              Include  the  information  of  actual/pseudo  states.  An actual
              state number is the row number of that state in the parsing  ta-
              ble.  After the step of unit production removal, some states are
              removed but their rows still remain in the parsing  table,  thus
              the  state's  pseudo  state  number  (counted  by ignoring those
              removed states/rows) will be different.

              -D15
              Shows the originator and transitor list of  each  configuration,
              as  well  as the parent state list of each state.  This is rele-
              vant when lane-tracing is used.



       -g
       --graphviz
              Generate a graphviz input file for the parsing machine.



       -h
       --help Print a usage summary of hyacc.


       -K
       --lrk  Apply the LR(k) algorithm. The LR(k)  algorithm  is  called  the
              edge-pushing  algorithm, which is based on lane-tracing, using a
              lane-tracing table based method to split states. In other words,
              this  is  extension  of  the  option -Q (--lane-tracing-ltt) for
              LR(k) where k > 1. So far this works for  those  LR(K)  grammars
              where  lanes  involved  in lane-tracing upon increasing k do not
              contain cycle.



       -l
       --nolines
              Don't put any #line preprocessor commands in  the  parser  file.
              Ordinarily hyacc puts them in the parser file so that the C com-
              piler and debuggers will associate errors with your source file,
              the  grammar  file. This options causes them to associate errors
              with the parser file, treating it as an independent source  file
              in its own right.


       -m
       --man-page
              Show  man  page.  Same as "man hyacc". This is used when the man
              page file exists in the same directory as the hyacc  executable.
              So if installation moves this man page file to another location,
              you must use "man hyacc".


       -o outfile
       --output-file==outfile
              Specify the name outfile for the parser file.

              The other output files' names are constructed  from  outfile  as
              described under the v and d switches.


       -O
              Specify  the  kind  of optimization used to parse the yacc input
              file.

              Basically, three optimizations are used: 1)  Combine  compatible
              states based on weak compatibility.  2) Remove unit productions.
              3) Remove repeated states after optimization 2).

              The -O switch should be followed by a parameter from 0 to 3:

              -O0
              No optimization is used.

              -O1
              Optimization 1) is used.

              -O2
              Optimizations 1) and 2) are used.

              -O3
              Optimizations 1), 2) and 3) are used.

              By default, when -O switch is not specified, the optimization 1)
              of  combining  compatible  states is used.  So "hyacc file.y" is
              equivalent to "hyacc file.y -O1" or "hyacc -O1 file.y".


       -P
       --lane-tracing-pgm
              Use LR(1) based on the lane-tracing algorithm. The  lane-tracing
              algorithm  first  obtains  the  LR(0)  parsing machine, then use
              lane-tracing to obtain  the  contexts  for  those  states  where
              shift/reduce  or reduce/reduce conflicts exist. If conflicts are
              not resolved for some  states,  then  the  involved  states  are
              splitted using the practical general method.


       -Q
       --lane-tracing-ltt
              Use  LR(1) based on the lane-tracing algorithm. The lane-tracing
              algorithm first obtains the  LR(0)  parsing  machine,  then  use
              lane-tracing  to  obtain  the  contexts  for  those states where
              shift/reduce or reduce/reduce conflicts exist. If conflicts  are
              not  resolved  for  some  states,  then  the involved states are
              splitted using a lane-tracing table based method.


       -R
       --lalr1
              Use LALR(1) algorithm based on lane-tracing phase 1.


       -S
       --lr0  Use LR(0) algorithm.


       -t
       --debug
              In the parser files, define the macro YYDEBUG to 1 if it is  not
              already  defined, so that the debugging facilities are compiled.
              When the generated compiler parses an input yacc file, the parse
              process  will  be  recorded  in  an  output  file y.parse, which
              includes all the shift/reduce actions, associated  state  number
              and  lookahead, as well as the content of state stack and symbol
              stack.


       -v
       --verbose
              Write an extra output file containing  verbose  descriptions  of
              the  parser  states  and what is done for each type of lookahead
              token in that state.

              This file also describes all the conflicts, both those  resolved
              by operator precedence and the unresolved ones.

              The file's name is y.output.


       -V
       --version
              Print the version number of hyacc and exit.



   EXAMPLES
       Assume the input grammar file is arith.y.


       The user wants y.tab.c only:
              hyacc arith.y


       The user wants y.tab.c and y.tab.h:
              hyacc -d arith.y


       The  user  wants  the  generated compiler create y.parse when parsing a
       program:
              hyacc -dt arith.y
              or
              hyacc arith.y -d -t


       The user wants y.ta.b, y.tab.h, and create a y.output file when parsing
       the grammar:
              hyacc -dv arith.y


       The  user  wants,  y.tab.c,  y.tab.h,  y.output and wants to include no
       other information than the short statistics summary in y.output:
              hyacc -dD12 arith.y


       Here -D12 will suppress the states list.


       The user wants y.tab.c and y.tab.h, use optimization 1) only, and wants
       a default y.output:
              hyacc -d -O1 -v arith.y
              or
              hyacc -dO1v arith.y


       The user wants to parse the grammar and check y.output for information,
       and doesn't need a compiler. While use all the optimizations, he  wants
       to keep those unit productions with semantic actions:
              hyacc -cCv arith.y


DIAGNOSITICS
       Self explanatory.


AUTHORS
       Xin Chen <chenx@hawaii.edu>
       Perry Smith <pedzsan@gmail.com> (new features in hyacc 0.98)
       Send bug report or comments to the above addresses.




                          Version 0.98: 1 January 2017                 HYACC(1)