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