[unix-history] / .ref-BSD-2 / man / eyacc.u

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