| 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 | |