[unix-history] / man6 / eyacc.6

.th EYACC VI 8/28/77
.sh NAME
eyacc \- modified yacc allowing much improved error recovery
.sh SYNOPSIS
.bd eyacc
[
.bd \-v
]
[ grammar ]
.sh DESCRIPTION
.it Eyacc
converts a context-free grammar into a set of
tables for a simple automaton which executes an LR(1) parsing
algorithm.
The grammar may be ambiguous;
specified precedence rules are used to break ambiguities.
.s3
The output is
.it y.tab.c,
which must be compiled by the C compiler
and loaded with any other routines
required.
If the
.bd \-v
flag is given, the file
.it y.output
is prepared, which contains a description of the parsing tables
and a report on
conflicts generated by ambiguities in the grammar.
.s3
.it Eyacc
is a slightly but significantly modified version of
.it yacc
(I).
The most important change is that
.it eyacc
fully enumerates test actions in its parser when an error token
is in the look-ahead set.
This prevents the parser from making undesirable reductions
when an error occurs before the error is detected.
.it Eyacc
also uses a different encoding for the action tables to allow the
parser to run faster.
Because of the change in enumerating look-aheads,
there are more frequently a series of ``test'' states
in the parse tables.
For this reason,
test states are encoded as the arithmetic inverse
of the value of the token to be tested for.
This allows a much tighter inner loop in the parser and
more than compensates for the extra tests required.
(Of course, the same change could be made to the tables of
.it yacc
and it would then run significantly faster than
.it eyacc,
but error recovery of the kind performed using
.it eyacc
would not be possible without the enumerated look-aheads.)
.s3
Minor changes to
.it yacc
in 
.it eyacc
include
the recognition of a form-feed as a white space character,
increased table size so as to handle larger grammars,
and a change of the code for the error action (from 0 to 1)
because of the change in the testing outlined above.
For this reason it is not possible to use the standard
.it yacc
library with
.it eyacc.
This would be pointless in any case,
because a different set of recovery routines is needed.
.s3
A document describing the error recovery method used with
.it eyacc
in the Pascal translator
.it pi
(VI)
is in preparation.
.sh "SEE ALSO"
``LR Parsing'', by A. V. Aho and S. C. Johnson, Computing Surveys, June, 1974.
.s3
``The YACC Compiler-compiler'', internal memorandum.
.s3
``Practical syntactic error recovery'', by Susan L. Graham and Stephen P. Rhodes,
CACM, November 1975.
.s3
pi (VI), yacc (I)
.sh AUTHOR
S. C. Johnson
.s3
.it Eyacc
modifications by Charles Haley and William Joy.
.sh FILES
y.output
.br
y.tab.c
.br
.sh DIAGNOSTICS
The number of reduce-reduce and shift-reduce conflicts
is reported on the standard output;
a more detailed report is
found in the
.it y.output
file.
.sh BUGS
A
.it eyacc
library
should be available.
Commit	Line	Data
cd1b5d54 CH	1	.th EYACC VI 8/28/77
	2	.sh NAME
	3	eyacc \- modified yacc allowing much improved error recovery
	4	.sh SYNOPSIS
	5	.bd eyacc
	6	[
	7	.bd \-v
	8	]
	9	[ grammar ]
	10	.sh DESCRIPTION
	11	.it Eyacc
	12	converts a context-free grammar into a set of
	13	tables for a simple automaton which executes an LR(1) parsing
	14	algorithm.
	15	The grammar may be ambiguous;
	16	specified precedence rules are used to break ambiguities.
	17	.s3
	18	The output is
	19	.it y.tab.c,
	20	which must be compiled by the C compiler
	21	and loaded with any other routines
	22	required.
	23	If the
	24	.bd \-v
	25	flag is given, the file
	26	.it y.output
	27	is prepared, which contains a description of the parsing tables
	28	and a report on
	29	conflicts generated by ambiguities in the grammar.
	30	.s3
	31	.it Eyacc
	32	is a slightly but significantly modified version of
	33	.it yacc
	34	(I).
	35	The most important change is that
	36	.it eyacc
	37	fully enumerates test actions in its parser when an error token
	38	is in the look-ahead set.
	39	This prevents the parser from making undesirable reductions
	40	when an error occurs before the error is detected.
	41	.it Eyacc
	42	also uses a different encoding for the action tables to allow the
	43	parser to run faster.
	44	Because of the change in enumerating look-aheads,
	45	there are more frequently a series of ``test'' states
	46	in the parse tables.
	47	For this reason,
	48	test states are encoded as the arithmetic inverse
	49	of the value of the token to be tested for.
	50	This allows a much tighter inner loop in the parser and
	51	more than compensates for the extra tests required.
	52	(Of course, the same change could be made to the tables of
	53	.it yacc
	54	and it would then run significantly faster than
	55	.it eyacc,
	56	but error recovery of the kind performed using
	57	.it eyacc
	58	would not be possible without the enumerated look-aheads.)
	59	.s3
	60	Minor changes to
	61	.it yacc
	62	in
	63	.it eyacc
	64	include
65	the recognition of a form-feed as a white space character,
66	increased table size so as to handle larger grammars,
67	and a change of the code for the error action (from 0 to 1)
68	because of the change in the testing outlined above.
69	For this reason it is not possible to use the standard
70	.it yacc
71	library with
72	.it eyacc.
73	This would be pointless in any case,
74	because a different set of recovery routines is needed.
75	.s3
76	A document describing the error recovery method used with
77	.it eyacc
78	in the Pascal translator
79	.it pi
80	(VI)
81	is in preparation.
82	.sh "SEE ALSO"
83	``LR Parsing'', by A. V. Aho and S. C. Johnson, Computing Surveys, June, 1974.
84	.s3
85	``The YACC Compiler-compiler'', internal memorandum.
86	.s3
87	``Practical syntactic error recovery'', by Susan L. Graham and Stephen P. Rhodes,
88	CACM, November 1975.
89	.s3
90	pi (VI), yacc (I)
91	.sh AUTHOR
92	S. C. Johnson
93	.s3
94	.it Eyacc
95	modifications by Charles Haley and William Joy.
96	.sh FILES
97	y.output
98	.br
99	y.tab.c
100	.br
101	.sh DIAGNOSTICS
102	The number of reduce-reduce and shift-reduce conflicts
103	is reported on the standard output;
104	a more detailed report is
105	found in the
106	.it y.output
107	file.
108	.sh BUGS
109	A
110	.it eyacc
111	library
112	should be available.