Debian Codegraph @

extern/btyacc/README

raw
1 BTYACC -- backtracking yacc
2 ===========================
3
4 BTYACC was created by Chris Dodd using ideas from many
5 places and lots of code from the Berkeley Yacc
6 distribution, which is a public domain yacc clone put
7 together by the good folks at Berkeley. This code is
8 distributed with NO WARRANTEE and is public domain.
9 It is certain to contain bugs, which you should
10 report to: [email protected].
11
12 Vadim Maslov of Siber Systems <[email protected]>
13 considerably modified BTYACC to make it suitable
14 for production environment.
15
16 Several people have suggested bug fixes that
17 were incorporated into BtYacc.
18
19 See the README.BYACC files for more about
20 Berkeley Yacc and other sources of info.
21
22 http://www.siber.com/btyacc/ is the current home of BtYacc.
23 It is provided courtesy of Siber Systems http://www.siber.com/.
24
25
26 Version 3.0 changes
27 -------------------
28 by Vadim Maslov
29
30 Changes mostly occurred in btyaccpa.ske file that
31 contains the parsing shift/reduce/backtrack algorithm.
32
33 Version 3.0 innovations focus on:
34 - text position computation and propagation,
35 - industrial-strength error processing and recovery.
36
37
38 ** Added mechanism for computing and propagating
39 text position of tokens and non-terminals.
40
41 Compilers often need to build AST trees such that every node
42 in a tree can relate to the parsed program source it came from.
43 The following applications are very likely to need this:
44 - debuggers that show actual source of the debugged program,
45 - source-to-source translators that want
46 unchanged parts of the tree to generate the unchanged code.
47
48 The new YYPOSN mechanism added in this version of BtYacc
49 helps you in automating the text position computation
50 and in assigning the computed text positions to the AST.
51 This mechanism is successfully used in commercial
52 parsers and source-to-source translators.
53
54 In standard Yaccs every token and every non-terminal
55 has an YYSTYPE semantic value attached to it.
56 In this new version every token and every non-terminal
57 also has an YYPOSN text position attached to it.
58 YYPOSN is a user-defined type that can be anything and
59 that has a meaning of text position attached to
60 token or non-terminal.
61
62 In addition to semantic value stack BtYacc now maintains
63 text position stack. Behavior of the text position stack
64 is similar to the behavior of the semantic value stack.
65
66 If using text position mechanism,
67 you need to define the following:
68
69 YYPOSN Preprocessor variable that contains C/C++ type of
70 the text position attached to
71 every token and non-terminal.
72
73 yyposn Global variable of type YYPOSN.
74 The lexer must assign text position of
75 the returned token to yyposn, just like it assigns
76 semantic value of the returned token to yylval.
77
78 YYREDUCEPOSNFUNC
79 Preprocessor variable that points to unction that
80 is called after the grammar rule reduction
81 to reduce text positions located on the stack.
82
83 This function is called by BtYacc to reduce text
84 positions. The function is called immediately after
85 the regular rule reduction occurs.
86
87 The function has the following prototype:
88 void ReducePosn(YYPOSN &ret,
89 YYPOSN *terms,
90 YYSTYPE *term_vals,
91 int term_no,
92 int stk_pos,
93 int yychar,
94 YYPOSN &yyposn,
95 UserType extra);
96
97 The function arguments are:
98 - ret
99 Reference to the text position returned by
100 the rule. The function must write the computed
101 text position returned by the rule to ret.
102 This is analogue of the $$ semantic value.
103
104 - term_posns
105 Array of the right-hand side rule components
106 YYPOSN text positions. These are analogues of
107 $1, $2, ..., $N in the text position world.
108
109 - term_vals
110 Array of the right-hand side (RHS) rule components
111 YYSTYPE values. These are the $1,...,$N themselves.
112
113 - term_no
114 Number of the components in RHS of the reduced rule.
115 Equal to size of arrays term_posns and term_vals.
116 Also equal to N in $1,...,$N in the reduced rule.
117
118 - stk_pos
119 YYSTYPE/YYPOSN stack position before the reduction.
120
121 - yychar
122 Lookahead token that immediately follows
123 the reduced RHS components.
124
125 - yyposn
126 YYPOSN of the token that immediately follows
127 the reduced RHS components.
128
129 - extra
130 User-defined extra argument passed to ReducePosn.
131
132 Typically this function extracts text positions from
133 the right-hand side rule components and either
134 assigns them to the returned $$ structure/tree or
135 if no $$ value is returned, puts them into
136 the ret text position from where
137 it will be picked up by the later reduced rules.
138
139 YYREDUCEPOSNFUNCARG
140 Extra user-defined argument passed to
141 the ReducePosn function. This argument can use
142 any variables defined in btyaccpa.ske.
143
144
145 ** Added code to btyaccpa.ske that automatically cleans up
146 semantic semantic values and text positions of tokens
147 and non-terminals that are discarded and deleted as
148 a result of error processing.
149
150 In the previous versions the discarded token and non-terminal
151 semantic values were not cleaned that caused quite severe
152 leaks. The only way to fix it was to add garbage collection
153 to YYSTYPE class.
154
155 Now BtYacc skeleton calls delete functions for semantic
156 values and positions of the discarded tokens and
157 non-terminals.
158
159 You need to define the following functions that BtYacc
160 calls when it needs to delete semantic value or text position.
161
162 YYDELETEVAL
163 User-defined function that is called by BtYacc
164 to delete semantic value of the token or non-terminal.
165
166 The user-defined function must have the prototype:
167 void DeleteYYval(YYSTYPE v, int type);
168 v is semantic value to delete,
169 type is one of the following:
170 0 discarding token
171 1 discarding state
172 2 cleaning up stack when aborting
173
174 YYDELETEPOSN
175 User-defined function that is called by BtYacc
176 to delete text position of the token or non-terminal.
177
178 The user-defined function must have the prototype:
179 void DeleteYYposn(YYPOSN p, int type);
180 v is semantic value to delete,
181 type is one of the following:
182 0 discarding token
183 1 discarding state
184 2 cleaning up stack when aborting
185
186
187 ** User can define "detailed" syntax error processing
188 function that reports an *exact* position of
189 the token that caused the error.
190
191 If you define preprocessor variable YYERROR_DETAILED in
192 your grammar then you need define the following
193 error processing function:
194
195 void yyerror_detailed(char *text,
196 int errt,
197 YYSTYPE &errt_value,
198 YYPOSN &errt_posn);
199
200 It receives the following arguments:
201 text Error message.
202 errt Code of the token that caused the error.
203 errt_value Value of the token that caused the error.
204 errt_posn Text position of token that caused error.
205
206
207 ** Dropped compatibility with C.
208
209 Compatibility with C became increasingly difficult
210 to maintain as new features were added to btyaccpa.ske.
211 So we dropped it. If anybody wants to make the new version
212 compatible with C, we would gladly accept the changes.
213
214 Meanwhile we expect that you use C++ to write grammar
215 actions and everything else in grammar files.
216 Since C is (in a sense) subset of C++, your C-based
217 grammar may work if you use C++ compiler to compile it.
218
219 Version 3.0 bugs fixed
220 ----------------------
221
222 Matthias Meixner <[email protected]> fixed a bug:
223 BtYacc does not correctly handle typenames, if one typename
224 is a prefix of another one and if this type is used after
225 the longer one. In this case BTYacc produces invalid code.
226
227
228 Version 2.1 changes
229 -------------------
230 by Vadim Maslov
231
232 ** Added preprocessor statements to BtYacc that are similar
233 in function and behavior to C/C++ preprocessor statements.
234
235 These statements are used to:
236
237 - Introduce modularity into a grammar by breaking it
238 into several *.y files and assembling different
239 grammars from the *.y modules using %include and %ifdef.
240
241 - Have several versions of the same grammar
242 by using %ifdef and $endif.
243
244 - To include automatically generated grammar fragment.
245 For instance, we use %include to include
246 automatically generated list of tokens.
247
248 Preprocessor statements are:
249
250 %define <var-name>
251 Define preprocessor variable named <var-name>.
252
253 %ifdef <var-name>
254 If preprocessor variable named <var-name>
255 is defined by %define, then process the text from
256 this %ifdef to the closing %endif.
257
258 %endif
259 Closing bracket for %ifdef preprocessor statement.
260 Only one nesting level of %ifdef-%endif is allowed.
261
262 %include <file-name>
263 Process contents of the file named <file-name>.
264 If <file-name> is a relative name, it is looked up
265 in a directory in which btyacc was started.
266 Only one nesting level of %include is allowed.
267
268
269 Version 2.0 changes
270 -------------------
271 by Vadim Maslov
272
273
274 ** Changed 16-bit short numbers to 32-bit int numbers in
275 grammar tables, so that huge grammar tables (tables that
276 are larger than 32768 elements) resulting from huge
277 grammars (Cobol grammar, for instance) can work correctly.
278 You need to have 32-bit integer to index table bigger than
279 32768 elements, 16-bit integer is not enough.
280
281 The original BtYacc just generated non-working tables
282 larger than 32768 elements without even notifying about
283 the table overflow.
284
285
286 ** Make error recovery work correctly when error happens
287 while processing nested conflicts. Original BtYacc could
288 infinitely cycle in certain situations that involved error
289 recovery while in nested conflict.
290
291 More detailed explanation: when we have nested conflicts
292 (conflict that happens while trial-processing another
293 conflict), it leads btyacc into NP-complete searching of
294 conflict tree. The ultimate goal is YYVALID operator that
295 selects a particular branch of that tree as a valid one.
296
297 If no YYVALID is found on the tree, then error recovery
298 takes over. The problem with this is that error recovery
299 is started in the same state context that exists on the
300 last surveyed branch of the conflict tree. Sometimes this
301 last branch may be of zero length and it results in
302 recovering to exactly the same state as existed before
303 entering the conflict. BtYacc cycles then.
304
305 We solved this problem by memorizing the longest path in
306 the conflict tree while browsing it. If we ever get into
307 error recovery, we restore state that existed on the
308 longest path. Effectively we say: if we have an error,
309 let us move forward as far as we possibly could while we
310 were browsing the conflict tree.
311
312
313 ** Introduce YYVALID_NESTED operation in addition to
314 simply YYVALID. When we have a nested conflict (conflict
315 while processing in trial mode for another conflict), we
316 want to relate YYVALID to a particular level of conflict
317 being in trial.
318
319 Since we mostly anticipate only 2-level nested conflicts
320 YYVALID_NESTED tells the parser to satisfy only the
321 internal conflict. Therefore, in 1-level conflict
322 situation YYVALID_NESTED acts like a regular YYVALID, but
323 in 2-level conflict it is a no-op and the other YYVALID
324 for outer conflict will be searched for.
325
326
327 ** Improved handling of situation where /tmp directory is
328 missing. Original btyacc just died quietly when /tmp
329 directory was missing. We added code that states the
330 problem explicitly. While on UNIX /tmp directory is always
331 present, it may be missing on WIN32 systems, therefore
332 diagnosing this situation is important.
333
334
335 Version 1.0 changes: BackTracking
336 =================================
337 by Chris Dodd
338
339 BTYACC is a modified version of yacc that supports
340 automatic backtracking and semantic disambiguation to
341 parse ambiguous grammars, as well as syntactic sugar for
342 inherited attributes (which tend to introduce conflicts).
343 Whenever a btyacc generated parser runs into a
344 shift-reduce or reduce-reduce error in the parse table, it
345 remembers the current parse point (yacc stack and input
346 stream state), and goes into trial parse mode. It then
347 continues parsing, ignoring most rule actions. If it runs
348 into an error (either through the parse table or through
349 an action calling YYERROR), it backtracks to the most
350 recent conflict point and tries a different alternative.
351 If it finds a successful parse (reaches the end of the
352 input or an action calls YYVALID), it backtracks to the
353 point where it first entered trial parse mode, and
354 continues with a full parse (executing all actions),
355 following the path of the successful trial.
356
357 Actions in btyacc come in two flavors -- {}-actions, which
358 are only executed when not in trial mode, and []-actions
359 which are executed regardless of mode. There are also
360 inherited attributes, which look like arguments (they are
361 enclosed in "()") and act like []-actions.
362
363 What this buys you:
364
365 * No more lexer feedback hack. In yacc grammars for C, a
366 standard hack, know as the "lexer feedback hack" is used
367 to find typedef names. The lexer uses semantic
368 information to decide if any given identifier is a
369 typedef-name or not and returns a special token. With
370 btyacc, you no longer need to do this; the lexer should
371 just always return an identifier. The btyacc grammar then
372 needs a rule of the form:
373
374 typename: ID [ if (!IsTypeName(LookupId($1))) YYERROR; ]
375
376 While the hack works adequately well for parsing C, it
377 becomes a nightmare when you try to parse something like
378 C++, where treating an ID as a typedef becomes heavily
379 dependent on context.
380
381 * Easy disambiguation via simple ordering. Btyacc runs
382 its trials via the rule "try shifting first, then try
383 reducing by the order that the conflicting rules appear in
384 the input file". This means you can deal with semantic a
385 disambiguation rule like:
386 [1] If it looks like a declaration it is, otherwise
387 [2] If it looks like an expression it is, otherwise
388 [3] it is a syntax error
389 [Ellis&Stroustrup, Annotated C++ Reference Manual, p93]
390
391 To deal with this, you need only put all the rules for
392 declarations before the rules for expressions in the
393 grammar file.
394
395 * No extra cost if you do not use it. Backtracking is
396 only triggered when the parse hits a shift/reduce or
397 reduce/reduce conflict in the table. If you have no
398 conflicts in your grammar, there is no extra cost, other
399 than some extra code which will never be invoked.
400
401 * C++ and ANSI C compatible parsers. The parsers produced
402 by btyacc can be compiled with C++ correctly. If you
403 "#define" YYSTYPE to be some C++ type with constructor and
404 destructor, everything will work fine. My favorite is
405 "#define YYSTYPE SmartPointer", where SmartPointer is a
406 smart pointer type that does garbage collection on the
407 pointed to objects.
408
409 BTYACC was originally written to make it easy to write a
410 C++ parser (my goal was to be able to use the grammar out
411 of the back of the ARM with as few modifications as
412 possible). Anyone who has ever looked at Jim Roskind
413 public domain C++ yacc grammar, or the yacc-based grammar
414 used in g++ knows how difficult this is. BTYACC is very
415 useful for parsing any ambiguous grammar, particularly
416 ones that come from trying to merge two (or more) complete
417 grammars.
418
419 Limitations of the backtracking: Currently, the generated
420 parser does NO pruning of alternate parsing paths. To
421 avoid an exponential explosion of possible paths (and
422 parsing time), you need to manually tell the parser when
423 it can throw away saved paths using YYVALID. In practice,
424 this turns out to be fairly easy to do. A C++ parser (for
425 example) can just put a [YYVALID;] after every complete
426 declaration and statement rule, corresponding to pruning
427 the backtracking state after seeing a ';' or '}' -- there
428 will never be a situation in which it is useful to
429 backtrack past either of these.
430
431 Inherited attributes in btyacc:
432
433 Inherited attributes look a lot like function arguments to
434 non-terminals, which is what they end up being in a
435 recursive descent parser, but NOT how they are implemented
436 in btyacc. Basically they are just syntactic sugar for
437 embedded semantic actions and $0, $-1, ... in normal yacc.
438 btyacc gives you two big advantages besides just the
439 syntax:
440 1. it does type checking on the inherited attributes,
441 so you do not have to specify $<type>0 and makes sure
442 you give the correct number of arguments (inherited
443 attributes) to every use of a non-terminal.
444 2. It "collapses" identical actions from that are produced
445 from inherited attributes. This eliminates many
446 potential reduce-reduce conflicts arising from
447 the inherited attributes.
448
449 You use inherited attributes by declaring the types of the
450 attributes in the preamble with a type declaration and
451 declaring names of the attributes on the lhs of the yacc
452 rule. You can of course have more than one rule with the
453 same lhs, and you can even give them different names in
454 each, but the type and number must be the same.
455
456 Here is a small example:
457 /* lhs takes 2 inherited attributes */
458 %type <t1> lhs(<t1>, <t2>)
459 stuff(<t1>, <t2>)
460 %%
461 lhs($i1, $i2) : { $$ = $i1 }
462 | lhs($i1, $i2) stuff($1,$i2) { $$ = $2; }
463
464 This is roughly equivalent to the following yacc code:
465 lhs :
466 { $$ = $<t1>-1; }
467 | lhs [ $<t1>$ = $-1; ] [ $<t2>$ = $<t2>0; ] stuff
468 { $$ = $4; }
469 ;
470
471 See the file "test/t2.y" for a longer and more complete
472 example. At the current time, the start symbol cannot
473 have any arguments.
474
475 Variant parsers:
476
477 Btyacc supports the -S flag to use a different parser
478 skeleton, changing the way that the parser is called and
479 used. The skeleton "push.skel" is included to produce a
480 "passive" parser that you feed tokens to (rather than
481 having the parser call a separate yylex routine). With
482 push.skel, yyparse is defined as follows:
483
484 int yyparse(int token, YYSTYPE yylval)
485
486 You should call yyparse repeatedly with successive tokens
487 of input. It returns 0 if more input is needed, 1 for a
488 successful parse, and -1 for an unrecoverable parse error.
489
490
491 Miscellaneous Features in ver. 1.0
492 ----------------------------------
493 by Chris Dodd
494
495 The -r option has been implemented. The -r option tells
496 Yacc to put the read-only tables in y.tab.c and the code and
497 variables in y.code.c. Keith Bostic asked for this option so
498 that :yyfix could be eliminated.
499
500 The -l and -t options have been implemented. The -l
501 option tells Yacc not to include #line directives in the code
502 it produces. The -t option causes debugging code to be
503 included in the compiled parser.
504
505 The code for error recovery has been changed to
506 implement the same algorithm as AT&T Yacc. There will still
507 be differences in the way error recovery works because AT&T
508 Yacc uses more default reductions than Berkeley Yacc.
509
510 The environment variable TMPDIR determines the directory
511 where temporary files will be created. If TMPDIR is defined,
512 temporary files will be created in the directory whose
513 pathname is the value of TMPDIR. By default, temporary files
514 are created in /tmp.
515
516 The keywords are now case-insensitive. For example,
517 %nonassoc, %NONASSOC, %NonAssoc, and %nOnAsSoC are
518 all equivalent.
519
520 Commas and semicolons that are not part of C code are
521 treated as commentary.
522
523 Line-end comments, as in BCPL, are permitted. Line-end
524 comments begin with // and end at the next end-of-line.
525 Line-end comments are permitted in C code; they are converted
526 to C comments on output.
527
528 The form of y.output files has been changed to look more
529 like those produced by AT&T Yacc.
530
531 A new kind of declaration has been added.
532 The form of the declaration is
533
534 %ident string
535
536 where string is a sequence of characters beginning with a
537 double quote and ending with either a double quote or the
538 next end-of-line, whichever comes first. The declaration
539 will cause a #ident directive to be written near the start
540 of the output file.
541
542 If a parser has been compiled with debugging code, that
543 code can be enabled by setting an environment variable.
544 If the environment variable YYDEBUG is set to 0, debugging
545 output is suppressed. If it is set to 1, debugging output
546 is written to standard output.
547
548
549 Building BtYacc
550 ---------------
551 by Chris Dodd and Vadim Maslov
552
553 We used GCC and GNU make to compile BtYacc both on UNIX and
554 WIN32 paltforms. You are welcome to try different
555 combinations of makes and compilers. Most likely it will
556 work, but it may require Makefile changes.
557
558 There is no config script.
559 Just type "make" and it should compile.
560
561 AWK. If you want to change file btyaccpa.ske (backtracking
562 parser skeleton), you will need awk to compile it into
563 skeleton.c file. We used GNU AWK (gawk) version 3.0.
564
565 It is known that using older versions of gawk
566 may create problems in compilation, because older awks
567 have problems with backslashes at the end of a line.
568
569 For MSDOS, there a "makefile.dos" that should do the trick.
570 Note: makefile.dos was not tested for a long time.
571
572 The result of compilation should be a single executable called
573 "btyacc" which you can install anywhere you like;
574 it does not require any other files in the distribution to run.
575
576
577 Legal Stuff
578 -----------
579 by Chris Dodd and Vadim Maslov
580
581 In English: BtYacc is freeware. BtYacc is distributed with
582 no warranty whatsoever. The author and any other contributors
583 take no responsibility for any and all consequences of its use.
584
585 In Legalese: LIMITATION OF LIABILITY. NEITHER SIBER SYSTEMS
586 NOR ANY OF ITS LICENSORS NOR ANY BTYACC CONTRIBUTOR SHALL BE
587 LIABLE FOR ANY INDIRECT, INCIDENTAL, SPECIAL OR CONSEQUENTIAL
588 DAMAGES, OR DAMAGES FOR LOSS OF PROFITS, REVENUE, DATA OR
589 DATA USE, CAUSED BY BTYACC AND INCURRED BY CUSTOMER OR ANY
590 THIRD PARTY, WHETHER IN AN ACTION IN CONTRACT OR TORT, EVEN
591 IF SIBER SYSTEMS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
592 DAMAGES.