4 Don't do this (counterexample.c):
6 // This is the fastest way to get the tail node from the gl_list API.
8 list_get_end (gl_list_t list)
10 gl_list_node_t sentinel = gl_list_add_last (list, NULL);
11 gl_list_node_t res = gl_list_previous_node (list, sentinel);
12 gl_list_remove_node (list, sentinel);
16 *** Ambiguous rewriting
17 If the user is stupid enough to have equal rules, then the derivations are
20 Reduce/reduce conflict on tokens $end, "+", "⊕":
24 First derivation exp ::=[ exp "+" exp • ]
26 Second derivation exp ::=[ exp "+" exp • ]
28 Do we care about this? In color, we use twice the same color here, but we
29 could try to use the same color for the same rule.
32 Show the counterexamples. This is going to be really hard and/or painful.
33 Unless we play it dumb (little structure).
36 - How about not evaluating incomplete lines when the text is not finished
43 - Should i18n be part of the Lexer? Currently it's a static method of
46 - is there a migration path that would allow to use TokenKinds in
49 - define the tokens as an enum too.
51 - promote YYEOF rather than EOF.
54 - is there a way to attach yysymbol_name to the enum itself? As we did
57 - It would be better to have TokenKind as return value. Can we use
58 reflection to support both output types?
61 https://git.savannah.gnu.org/gitweb/?p=gettext.git;a=blob;f=gettext-runtime/intl/plural.y;h=a712255af4f2f739c93336d4ff6556d932a426a5;hb=HEAD
63 should be updated to not use YYERRCODE. Returning an undef token is good
68 Stop hard-coding "Calc". Adjust local.at (look for FIXME).
70 ** A dev warning for b4_
71 Maybe we should check for m4_ and b4_ leaking out of the m4 processing, as
72 Autoconf does. It would have caught overquotation issues.
75 I feel it's ugly to use the GNU style to declare functions in the doc. It
76 generates tons of white space in the page, and may contribute to bad page
83 The YYUNDEFTOK could be assigned a semantic value so that yyerror could be
84 used to report invalid lexemes.
87 Consider deprecating impure push parsers. They add a lot of complexity, for
88 a bad feature. On the other hand, that would make it much harder to sit
89 push parsers on top of pull parser. Which is currently not relevant, since
90 push parsers are measurably slower.
92 ** %define parse.error formatted
93 How about pushing bistromathics' yyreport_syntax_error as another standard
94 way to generate the error message, and leave to the user the task of
95 providing the message formats? Currently in bistro, it reads:
98 error_format_string (int argc)
102 default: /* Avoid compiler warnings. */
103 case 0: return _("%@: syntax error");
104 case 1: return _("%@: syntax error: unexpected %u");
105 // TRANSLATORS: '%@' is a location in a file, '%u' is an
106 // "unexpected token", and '%0e', '%1e'... are expected tokens
109 // For instance on the expression "1 + * 2", you'd get
111 // 1.5: syntax error: expected - or ( or number or function or variable before *
112 case 2: return _("%@: syntax error: expected %0e before %u");
113 case 3: return _("%@: syntax error: expected %0e or %1e before %u");
114 case 4: return _("%@: syntax error: expected %0e or %1e or %2e before %u");
115 case 5: return _("%@: syntax error: expected %0e or %1e or %2e or %3e before %u");
116 case 6: return _("%@: syntax error: expected %0e or %1e or %2e or %3e or %4e before %u");
117 case 7: return _("%@: syntax error: expected %0e or %1e or %2e or %3e or %4e or %5e before %u");
118 case 8: return _("%@: syntax error: expected %0e or %1e or %2e or %3e or %4e or %5e or %6e before %u");
122 The message would have to be generated in a string, and pushed to yyerror.
123 Which will be a pain in the neck in yacc.c.
125 If we want to do that, we should think very carefully about the syntax of
128 ** yyclearin does not invoke the lookahead token's %destructor
129 https://lists.gnu.org/r/bug-bison/2018-02/msg00000.html
132 > Modifying yyclearin so that it calls yydestruct seems like the simplest
133 > solution to this issue, but it is conceivable that such a change would
134 > break programs which already perform some kind of workaround in order to
135 > destruct the lookahead symbol. So it might be necessary to use some kind of
136 > compatibility %define, or to create a new replacement macro with a
137 > different name such as yydiscardin.
139 > At a minimum, the fact that yyclearin does not invoke the %destructor
140 > should be highlighted in the documentation, since it is not at all obvious.
144 Les catégories d'avertissements incluent :
145 conflicts-sr conflits S/R (activé par défaut)
146 conflicts-rr conflits R/R (activé par défaut)
147 dangling-alias l'alias chaîne n'est pas attaché à un symbole
148 deprecated construction obsolète
149 empty-rule règle vide sans %empty
150 midrule-values valeurs de règle intermédiaire non définies ou inutilisées
151 precedence priorité et associativité inutiles
152 yacc incompatibilités avec POSIX Yacc
153 other tous les autres avertissements (activé par défaut)
154 all tous les avertissements sauf « dangling-alias » et « yacc »
155 no-CATEGORY désactiver les avertissements dans CATEGORIE
156 none désactiver tous les avertissements
157 error[=CATEGORY] traiter les avertissements comme des erreurs
159 Line -1 and -3 should mention CATEGORIE, not CATEGORY.
163 Get rid of scaffolding in glr.c.
165 ** Unit rules / Injection rules (Akim Demaille)
166 Maybe we could expand unit rules (or "injections", see
167 https://homepages.cwi.nl/~daybuild/daily-books/syntax/2-sdf/sdf.html), i.e.,
176 exp: exp '+' exp | exp '&' exp;
178 when there are no actions. This can significantly speed up some grammars.
179 I can't find the papers. In particular the book 'LR parsing: Theory and
180 Practice' is impossible to find, but according to 'Parsing Techniques: a
181 Practical Guide', it includes information about this issue. Does anybody
184 ** clean up (Akim Demaille)
185 Do not work on these items now, as I (Akim) have branches with a lot of
186 changes in this area (hitting several files), and no desire to have to fix
187 conflicts. Addressing these items will happen after my branches have been
191 Introduce a goto struct, and use it in place of from_state/to_state.
192 Rename states1 as path, length as pathlen.
193 Introduce inline functions for things such as nullable[*rp - ntokens]
194 where we need to map from symbol number to nterm number.
196 There are probably a significant part of the relations management that
197 should be migrated on top of a bitsetv.
200 It should probably take a "state*" instead of two arguments.
203 The "automaton" and "set" categories are not so useful. We should probably
204 introduce lr(0) and lalr, just the way we have ielr categories. The
205 "closure" function is too verbose, it should probably have its own category.
207 "set" can still be used for summariring the important sets. That would make
208 tests easy to maintain.
211 Rename these guys as "diagnostics.*" (or "diagnose.*"), since that's the
212 name they have in gcc, clang, etc. Likewise for the complain_* series of
216 states/nstates, rules/nrules, ..., ritem/nritems
219 * Better error messages
220 The users are not provided with enough tools to forge their error messages.
221 See for instance "Is there an option to change the message produced by
222 YYERROR_VERBOSE?" by Simon Sobisch, on bison-help.
225 https://www.cs.tufts.edu/~nr/cs257/archive/clinton-jefferey/lr-error-messages.pdf
226 https://research.swtch.com/yyerror
227 http://gallium.inria.fr/~fpottier/publis/fpottier-reachability-cc2016.pdf
230 Fix data/skeletons/yacc.c so that it defines YYPTRDIFF_T properly for modern
231 and older C++ compilers. Currently the code defaults to defining it to
232 'long' for non-GCC compilers, but it should use the proper C++ magic to
233 define it to the same type as the C ptrdiff_t type.
236 Several features are not available in all the backends.
238 - lac: D, Java (easy)
239 - push parsers: glr.c, glr.cc, lalr1.cc (not very difficult)
240 - token constructors: Java, C, D (a bit difficult)
241 - glr: D, Java (super difficult)
244 ** Autotest has quotation issues
245 tests/input.at:1730:AT_SETUP([%define errors])
249 $ ./tests/testsuite -l | grep errors | sed q
250 38: input.at:1730 errors
253 ** Get rid of YYPRINT and b4_toknum
254 Besides yytoknum is wrong when api.token.raw is defined.
256 ** Better design for diagnostics
257 The current implementation of diagnostics is ad hoc, it grew organically.
258 It works as a series of calls to several functions, with dependency of the
259 latter calls on the former. For instance:
261 complain (&sym->location,
262 sym->content->status == needed ? complaint : Wother,
263 _("symbol %s is used, but is not defined as a token"
264 " and has no rules; did you mean %s?"),
265 quote_n (0, sym->tag),
266 quote_n (1, best->tag));
267 if (feature_flag & feature_caret)
268 location_caret_suggestion (sym->location, best->tag, stderr);
270 We should rewrite this in a more FP way:
272 1. build a rich structure that denotes the (complete) diagnostic.
273 "Complete" in the sense that it also contains the suggestions, the list
274 of possible matches, etc.
276 2. send this to the pretty-printing routine. The diagnostic structure
277 should be sufficient so that we can generate all the 'format' of
278 diagnostics, including the fixits.
280 If properly done, this diagnostic module can be detached from Bison and be
281 put in gnulib. It could be used, for instance, for errors caught by
284 There's certainly already something alike in GCC. At least that's the
285 impression I get from reading the "-fdiagnostics-format=FORMAT" part of this
288 https://gcc.gnu.org/onlinedocs/gcc/Diagnostic-Message-Formatting-Options.html
290 ** Graphviz display code thoughts
291 The code for the --graph option is over two files: print_graph, and
292 graphviz. This is because Bison used to also produce VCG graphs, but since
293 this is no longer true, maybe we could consider these files for fusion.
295 An other consideration worth noting is that print_graph.c (correct me if I
296 am wrong) should contain generic functions, whereas graphviz.c and other
297 potential files should contain just the specific code for that output
298 format. It will probably prove difficult to tell if the implementation is
299 actually generic whilst only having support for a single format, but it
300 would be nice to keep stuff a bit tidier: right now, the construction of the
301 bitset used to show reductions is in the graphviz-specific code, and on the
302 opposite side we have some use of \l, which is graphviz-specific, in what
303 should be generic code.
305 Little effort seems to have been given to factoring these files and their
306 rint{,-xml} counterpart. We would very much like to re-use the pretty format
307 of states from .output for the graphs, etc.
309 Since graphviz dies on medium-to-big grammars, maybe consider an other tool?
312 Check it too when checking the different kinds of parsers. And be
313 sure to check that the initial-action is performed once per parsing.
316 b4_shared_declarations is no longer what it is. Make it
317 b4_parser_declaration for instance.
319 ** yychar in lalr1.cc
320 There is a large difference bw maint and master on the handling of
321 yychar (which was removed in lalr1.cc). See what needs to be
325 /* User semantic actions sometimes alter yychar, and that requires
326 that yytoken be updated with the new translation. We take the
327 approach of translating immediately before every use of yytoken.
328 One alternative is translating here after every semantic action,
329 but that translation would be missed if the semantic action
330 invokes YYABORT, YYACCEPT, or YYERROR immediately after altering
331 yychar. In the case of YYABORT or YYACCEPT, an incorrect
332 destructor might then be invoked immediately. In the case of
333 YYERROR, subsequent parser actions might lead to an incorrect
334 destructor call or verbose syntax error message before the
335 lookahead is translated. */
337 /* Make sure we have latest lookahead translation. See comments at
338 user semantic actions for why this is necessary. */
339 yytoken = yytranslate_ (yychar);
342 ** Get rid of fake #lines [Bison: ...]
343 Possibly as simple as checking whether the column number is nonnegative.
345 I have seen messages like the following from GCC.
347 <built-in>:0: fatal error: opening dependency file .deps/libltdl/argz.Tpo: No such file or directory
350 ** Discuss about %printer/%destroy in the case of C++.
351 It would be very nice to provide the symbol classes with an operator<<
352 and a destructor. Unfortunately the syntax we have chosen for
353 %destroy and %printer make them hard to reuse. For instance, the user
354 is invited to write something like
356 %printer { debug_stream() << $$; } <my_type>;
358 which is hard to reuse elsewhere since it wants to use
359 "debug_stream()" to find the stream to use. The same applies to
360 %destroy: we told the user she could use the members of the Parser
361 class in the printers/destructors, which is not good for an operator<<
362 since it is no longer bound to a particular parser, it's just a
366 ** Rewrite glr.cc in C++ (Valentin Tolmer)
367 As a matter of fact, it would be very interesting to see how much we can
368 share between lalr1.cc and glr.cc. Most of the skeletons should be common.
369 It would be a very nice source of inspiration for the other languages.
371 Valentin Tolmer is working on this.
374 The code in yyerrlab reads:
378 /* Return failure if at end of input. */
383 There are only two yychar that can be <= YYEOF: YYEMPTY and YYEOF.
384 But I can't produce the situation where yychar is YYEMPTY here, is it
385 really possible? The test suite does not exercise this case.
387 This shows that it would be interesting to manage to install skeleton
388 coverage analysis to the test suite.
390 * From lalr1.cc to yacc.c
392 Merging the three stacks in lalr1.cc simplified the code, prompted for
393 other improvements and also made it faster (probably because memory
394 management is performed once instead of three times). I suggest that
395 we do the same in yacc.c.
397 (Some time later): it's also very nice to have three stacks: it's more dense
398 as we don't lose bits to padding. For instance the typical stack for states
399 will use 8 bits, while it is likely to consume 32 bits in a struct.
401 We need trustworthy benchmarks for Bison, for all our backends. Akim has a
402 few things scattered around; we need to put them in the repo, and make them
408 Some statistics about the grammar and the parser would be useful,
409 especially when asking the user to send some information about the
410 grammars she is working on. We should probably also include some
411 information about the variables (I'm not sure for instance we even
412 specify what LR variant was used).
415 How would Paul like to display the conflicted actions? In particular,
416 what when two reductions are possible on a given lookahead token, but one is
417 part of $default. Should we make the two reductions explicit, or just
418 keep $default? See the following point.
420 ** Disabled Reductions
421 See 'tests/conflicts.at (Defaulted Conflicted Reduction)', and decide
425 Extend with error productions. The hard part will probably be finding
426 the right rule so that a single state does not exhibit too many yet
427 undocumented ''features''. Maybe an empty action ought to be
428 presented too. Shall we try to make a single grammar with all these
429 features, or should we have several very small grammars?
433 Well, only if there is really some demand for it.
436 https://github.com/scfc/bison-php/blob/master/data/lalr1.php
439 https://lists.gnu.org/r/bison-patches/2013-09/msg00000.html and following
441 ** Multiple start symbols
442 Would be very useful when parsing closely related languages. The idea is to
443 declare several start symbols, for instance
450 and to generate parse(), parse_stmt() and parse_expr(). Technically, the
451 above grammar would be transformed into
454 %token YY_START_STMT YY_START_EXPR
456 yy_start: YY_START_STMT stmt | YY_START_EXPR expr
458 so that there are no new conflicts in the grammar (as would undoubtedly
459 happen with yy_start: stmt | expr). Then adjust the skeletons so that this
460 initial token (YY_START_STMT, YY_START_EXPR) be shifted first in the
461 corresponding parse function.
464 This is a popular demand. We already made many changes in the parser that
465 should make this reasonably easy to implement.
467 Bruce Mardle <marblypup@yahoo.co.uk>
468 https://lists.gnu.org/archive/html/bison-patches/2015-09/msg00000.html
470 However, there are many other things to do before having such a feature,
471 because I don't want a % equivalent to #include (which we all learned to
472 hate). I want something that builds "modules" of grammars, and assembles
473 them together, paying attention to keep separate bits separated, in pseudo
477 There is demand for push parsers in Java and C++. And GLR I guess.
479 ** Generate code instead of tables
480 This is certainly quite a lot of work. See
481 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4539.
484 We should find a means to provide an access to values deep in the
485 stack. For instance, instead of
487 baz: qux { $$ = $<foo>-1 + $<bar>0 + $1; }
489 we should be able to have:
491 foo($foo) bar($bar) baz($bar): qux($qux) { $baz = $foo + $bar + $qux; }
493 Or something like this.
496 It should be possible to have %if/%else/%endif. The implementation is
497 not clear: should it be lexical or syntactic. Vadim Maslow thinks it
498 must be in the scanner: we must not parse what is in a switched off
499 part of %if. Akim Demaille thinks it should be in the parser, so as
500 to avoid falling into another CPP mistake.
502 (Later): I'm sure there's actually good case for this. People who need that
503 feature can use m4/cpp on top of Bison. I don't think it is worth the
504 trouble in Bison itself.
507 There are couple of available extensions of Bison targeting some XML
508 output. Some day we should consider including them. One issue is
509 that they seem to be quite orthogonal to the parsing technique, and
510 seem to depend mostly on the possibility to have some code triggered
511 for each reduction. As a matter of fact, such hooks could also be
512 used to generate the yydebug traces. Some generic scheme probably
515 XML output for GNU Bison and gcc
516 http://www.cs.may.ie/~jpower/Research/bisonXML/
518 XML output for GNU Bison
519 http://yaxx.sourceforge.net/
521 * Coding system independence
524 Currently Bison assumes 8-bit bytes (i.e. that UCHAR_MAX is
525 255). It also assumes that the 8-bit character encoding is
526 the same for the invocation of 'bison' as it is for the
527 invocation of 'cc', but this is not necessarily true when
528 people run bison on an ASCII host and then use cc on an EBCDIC
529 host. I don't think these topics are worth our time
530 addressing (unless we find a gung-ho volunteer for EBCDIC or
531 PDP-10 ports :-) but they should probably be documented
534 More importantly, Bison does not currently allow NUL bytes in
535 tokens, either via escapes (e.g., "x\0y") or via a NUL byte in
536 the source code. This should get fixed.
541 Must we keep %token-table?
546 It is unfortunate that there is a total order for precedence. It
547 makes it impossible to have modular precedence information. We should
548 move to partial orders (sounds like series/parallel orders to me).
550 This is a prerequisite for modules.
552 * Pre and post actions.
553 From: Florian Krohm <florian@edamail.fishkill.ibm.com>
554 Subject: YYACT_EPILOGUE
555 To: bug-bison@gnu.org
556 X-Sent: 1 week, 4 days, 14 hours, 38 minutes, 11 seconds ago
558 The other day I had the need for explicitly building the parse tree. I
559 used %locations for that and defined YYLLOC_DEFAULT to call a function
560 that returns the tree node for the production. Easy. But I also needed
561 to assign the S-attribute to the tree node. That cannot be done in
562 YYLLOC_DEFAULT, because it is invoked before the action is executed.
563 The way I solved this was to define a macro YYACT_EPILOGUE that would
564 be invoked after the action. For reasons of symmetry I also added
565 YYACT_PROLOGUE. Although I had no use for that I can envision how it
566 might come in handy for debugging purposes.
567 All is needed is to add
570 YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen, yyloc, (yylsp - yylen));
572 YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen);
575 at the proper place to bison.simple. Ditto for YYACT_PROLOGUE.
577 I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
578 to bison. If you're interested, I'll work on a patch.
581 Equip the parser with a means to create the (visual) parse tree.
592 Copyright (C) 2001-2004, 2006, 2008-2015, 2018-2020 Free Software
595 This file is part of Bison, the GNU Compiler Compiler.
597 Permission is granted to copy, distribute and/or modify this document
598 under the terms of the GNU Free Documentation License, Version 1.3 or
599 any later version published by the Free Software Foundation; with no
600 Invariant Sections, with no Front-Cover Texts, and with no Back-Cover
601 Texts. A copy of the license is included in the "GNU Free
602 Documentation License" file as part of this distribution.