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.
AUTHOR
Xin Chen <chenx@hawaii.edu>
Send bug report or comments to the above address.
Version 0.97: 28 March 2009 HYACC(1)