TODO

   1 * Soon
   2 ** YY_LOCATION_PRINT
   3 This is an internal detail.  But it's very handy, we should make it public.
   4 It already has leaked in the documentation by accident.
   5
   6 ** glr
   7 There is no test with "Parse on stack %ld rejected by rule %d" in it.
   8
   9 ** %merge
  10 Tests with typed %merge: 716 717 718 740 741 742 746 747 748
  11
  12 716: Duplicate representation of merged trees: glr.c FAILED (glr-regression.at:517)
  13 740: Leaked semantic values if user action cuts parse: glr.c FAILED (glr-regression.at:1230)
  14 746: Incorrect lookahead during nondeterministic GLR: glr.c FAILED (glr-regression.at:1610)
  15
  16 Document typed merges.
  17
  18 ** yyrline etc.
  19 Clarify that rule numbers in the skeletons are 1-based.
  20
  21 ** Macros in C++
  22 There are many macros that should obey api.prefix: YY_CPLUSPLUS, YY_MOVE,
  23 etc.
  24
  25 ** YYDEBUG etc. in C++
  26 Discourage the use of YYDEBUG in C++ (see thread with Jot).  Stop supporting
  27 #define YYSTYPE by the user.
  28
  29 Add value_type as a synonym for semantic_type.
  30
  31 ** yyerrok in Java
  32 And add tests in calc.at, to prepare work for D.
  33
  34 ** YYERROR and yynerrs
  35 We are missing some cases.  Write a test case, and check all the skeletons.
  36
  37 ** Cex
  38 *** Improve gnulib
  39 Don't do this (counterexample.c):
  40
  41 // This is the fastest way to get the tail node from the gl_list API.
  42 gl_list_node_t
  43 list_get_end (gl_list_t list)
  44 {
  45   gl_list_node_t sentinel = gl_list_add_last (list, NULL);
  46   gl_list_node_t res = gl_list_previous_node (list, sentinel);
  47   gl_list_remove_node (list, sentinel);
  48   return res;
  49 }
  50
  51 *** Ambiguous rewriting
  52 If the user is stupid enough to have equal rules, then the derivations are
  53 harder to read:
  54
  55     Reduce/reduce conflict on tokens $end, "+", "⊕":
  56         2 exp: exp "+" exp .
  57         3 exp: exp "+" exp .
  58       Example                  exp "+" exp •
  59       First derivation         exp ::=[ exp "+" exp • ]
  60       Example                  exp "+" exp •
  61       Second derivation        exp ::=[ exp "+" exp • ]
  62
  63 Do we care about this?  In color, we use twice the same color here, but we
  64 could try to use the same color for the same rule.
  65
  66 *** XML reports
  67 Show the counterexamples.  This is going to be really hard and/or painful.
  68 Unless we play it dumb (little structure).
  69
  70 ** Bistromathic
  71 - How about not evaluating incomplete lines when the text is not finished
  72   (as shells do).
  73
  74 ** Questions
  75 *** Java
  76 - Should i18n be part of the Lexer?  Currently it's a static method of
  77   Lexer.
  78
  79 - is there a migration path that would allow to use TokenKinds in
  80   yylex?
  81
  82 - define the tokens as an enum too.
  83
  84 - promote YYEOF rather than EOF.
  85
  86 ** YYerror
  87 https://git.savannah.gnu.org/gitweb/?p=gettext.git;a=blob;f=gettext-runtime/intl/plural.y;h=a712255af4f2f739c93336d4ff6556d932a426a5;hb=HEAD
  88
  89 should be updated to not use YYERRCODE.  Returning an undef token is good
  90 enough.
  91
  92 ** Java
  93 *** calc.at
  94 Stop hard-coding "Calc".  Adjust local.at (look for FIXME).
  95
  96 ** A dev warning for b4_
  97 Maybe we should check for m4_ and b4_ leaking out of the m4 processing, as
  98 Autoconf does.  It would have caught over-quotation issues.
  99
 100 ** doc
 101 I feel it's ugly to use the GNU style to declare functions in the doc.  It
 102 generates tons of white space in the page, and may contribute to bad page
 103 breaks.
 104
 105 ** consistency
 106 token vs terminal.
 107
 108 ** api.token.raw
 109 The YYUNDEFTOK could be assigned a semantic value so that yyerror could be
 110 used to report invalid lexemes.
 111
 112 ** push parsers
 113 Consider deprecating impure push parsers.  They add a lot of complexity, for
 114 a bad feature.  On the other hand, that would make it much harder to sit
 115 push parsers on top of pull parser.  Which is currently not relevant, since
 116 push parsers are measurably slower.
 117
 118 ** %define parse.error formatted
 119 How about pushing Bistromathic's yyreport_syntax_error as another standard
 120 way to generate the error message, and leave to the user the task of
 121 providing the message formats?  Currently in bistro, it reads:
 122
 123     const char *
 124     error_format_string (int argc)
 125     {
 126       switch (argc)
 127         {
 128         default: /* Avoid compiler warnings. */
 129         case 0: return _("%@: syntax error");
 130         case 1: return _("%@: syntax error: unexpected %u");
 131           // TRANSLATORS: '%@' is a location in a file, '%u' is an
 132           // "unexpected token", and '%0e', '%1e'... are expected tokens
 133           // at this point.
 134           //
 135           // For instance on the expression "1 + * 2", you'd get
 136           //
 137           // 1.5: syntax error: expected - or ( or number or function or variable before *
 138         case 2: return _("%@: syntax error: expected %0e before %u");
 139         case 3: return _("%@: syntax error: expected %0e or %1e before %u");
 140         case 4: return _("%@: syntax error: expected %0e or %1e or %2e before %u");
 141         case 5: return _("%@: syntax error: expected %0e or %1e or %2e or %3e before %u");
 142         case 6: return _("%@: syntax error: expected %0e or %1e or %2e or %3e or %4e before %u");
 143         case 7: return _("%@: syntax error: expected %0e or %1e or %2e or %3e or %4e or %5e before %u");
 144         case 8: return _("%@: syntax error: expected %0e or %1e or %2e or %3e or %4e or %5e or %6e before %u");
 145         }
 146     }
 147
 148 The message would have to be generated in a string, and pushed to yyerror.
 149 Which will be a pain in the neck in yacc.c.
 150
 151 If we want to do that, we should think very carefully about the syntax of
 152 the format string.
 153
 154 ** yyclearin does not invoke the lookahead token's %destructor
 155 https://lists.gnu.org/r/bug-bison/2018-02/msg00000.html
 156 Rici:
 157
 158 > Modifying yyclearin so that it calls yydestruct seems like the simplest
 159 > solution to this issue, but it is conceivable that such a change would
 160 > break programs which already perform some kind of workaround in order to
 161 > destruct the lookahead symbol. So it might be necessary to use some kind of
 162 > compatibility %define, or to create a new replacement macro with a
 163 > different name such as yydiscardin.
 164 >
 165 > At a minimum, the fact that yyclearin does not invoke the %destructor
 166 > should be highlighted in the documentation, since it is not at all obvious.
 167
 168 ** Issues in i18n
 169
 170 Les catégories d'avertissements incluent :
 171   conflicts-sr      conflits S/R (activé par défaut)
 172   conflicts-rr      conflits R/R (activé par défaut)
 173   dangling-alias    l'alias chaîne n'est pas attaché à un symbole
 174   deprecated        construction obsolète
 175   empty-rule        règle vide sans %empty
 176   midrule-values    valeurs de règle intermédiaire non définies ou inutilisées
 177   precedence        priorité et associativité inutiles
 178   yacc              incompatibilités avec POSIX Yacc
 179   other             tous les autres avertissements (activé par défaut)
 180   all               tous les avertissements sauf « dangling-alias » et « yacc »
 181   no-CATEGORY       désactiver les avertissements dans CATEGORIE
 182   none              désactiver tous les avertissements
 183   error[=CATEGORY]  traiter les avertissements comme des erreurs
 184
 185 Line -1 and -3 should mention CATEGORIE, not CATEGORY.
 186
 187 * Bison 3.8
 188 ** Rewrite glr.cc (currently glr2.cc)
 189 *** Remove jumps
 190 We can probably replace setjmp/longjmp with exceptions.  That would help
 191 tremendously other languages such as D and Java that probably have no
 192 similar feature.  If we remove jumps, we probably no longer need _Noreturn,
 193 so simplify `b4_attribute_define([noreturn])` into `b4_attribute_define`.
 194
 195 After discussing with Valentin, it was decided that it's better to stay with
 196 jumps, since in some places exceptions are ruled out from C++.
 197
 198 *** Coding style
 199 Move to our coding conventions.  In particular names such as yy_glr_stack,
 200 not yyGLRStack.
 201
 202 *** yydebug
 203 It should be a member of the parser object, see lalr1.cc.  Let the parser
 204 object decide what the debug stream is, rather than open coding std::cerr.
 205
 206 *** Avoid pointers
 207 There are many places where pointers should be replaced with references.
 208 Some occurrences were fixed, but now some have improper names:
 209
 210 -yygetToken (int *yycharp, ]b4_namespace_ref[::]b4_parser_class[& yyparser][]b4_pure_if([, glr_stack* yystackp])[]b4_user_formals[)
 211 +yygetToken (int& yycharp, ]b4_namespace_ref[::]b4_parser_class[& yyparser][]b4_pure_if([, glr_stack* yystackp])[]b4_user_formals[)
 212
 213 yycharp is no longer a Pointer.  And yystackp should probably also be a reference.
 214
 215 *** parse.assert
 216 Currently all the assertions are enabled.  Once we are confident in glr2.cc,
 217 let parse.assert use the same approach as in lalr1.cc.
 218
 219 *** debug_stream
 220 Stop using std::cerr everywhere.
 221
 222 *** glr.c
 223 When glr2.cc fully replaces glr.cc, get rid of the glr.cc scaffolding in
 224 glr.c.
 225
 226 * Chains
 227 ** Unit rules / Injection rules (Akim Demaille)
 228 Maybe we could expand unit rules (or "injections", see
 229 https://homepages.cwi.nl/~daybuild/daily-books/syntax/2-sdf/sdf.html), i.e.,
 230 transform
 231
 232         exp: arith | bool;
 233         arith: exp '+' exp;
 234         bool: exp '&' exp;
 235
 236 into
 237
 238         exp: exp '+' exp | exp '&' exp;
 239
 240 when there are no actions.  This can significantly speed up some grammars.
 241 I can't find the papers.  In particular the book 'LR parsing: Theory and
 242 Practice' is impossible to find, but according to 'Parsing Techniques: a
 243 Practical Guide', it includes information about this issue.  Does anybody
 244 have it?
 245
 246 ** clean up (Akim Demaille)
 247 Do not work on these items now, as I (Akim) have branches with a lot of
 248 changes in this area (hitting several files), and no desire to have to fix
 249 conflicts.  Addressing these items will happen after my branches have been
 250 merged.
 251
 252 *** lalr.c
 253 Introduce a goto struct, and use it in place of from_state/to_state.
 254 Rename states1 as path, length as pathlen.
 255 Introduce inline functions for things such as nullable[*rp - ntokens]
 256 where we need to map from symbol number to nterm number.
 257
 258 There are probably a significant part of the relations management that
 259 should be migrated on top of a bitsetv.
 260
 261 *** closure
 262 It should probably take a "state*" instead of two arguments.
 263
 264 *** traces
 265 The "automaton" and "set" categories are not so useful.  We should probably
 266 introduce lr(0) and lalr, just the way we have ielr categories.  The
 267 "closure" function is too verbose, it should probably have its own category.
 268
 269 "set" can still be used for summarizing the important sets.  That would make
 270 tests easy to maintain.
 271
 272 *** complain.*
 273 Rename these guys as "diagnostics.*" (or "diagnose.*"), since that's the
 274 name they have in GCC, clang, etc.  Likewise for the complain_* series of
 275 functions.
 276
 277 *** ritem
 278 states/nstates, rules/nrules, ..., ritem/nritems
 279 Fix the latter.
 280
 281 *** m4: slot, type, type_tag
 282 The meaning of type_tag varies depending on api.value.type.  We should avoid
 283 that and using clear definitions with stable semantics.
 284
 285 * D programming language
 286 There's a number of features that are missing, here sorted in _suggested_
 287 order of implementation.
 288
 289 When copying code from other skeletons, keep the comments exactly as they
 290 are.  Keep the same variable names.  If you change the wording in one place,
 291 do it in the others too.  In other words: make sure to keep the
 292 maintenance *simple* by avoiding any gratuitous difference.
 293
 294 ** CI
 295 Check when gdc and ldc.
 296
 297 ** Token Constructors
 298 It is possible to mix incorrectly kinds and values, and for instance:
 299
 300         return parser.Symbol (TokenKind.NUM, "Hello, World!\n");
 301
 302 attaches a string value to NUM kind (wrong, of course).  When
 303 api.token.constructor is set, in C++, Bison generated "token constructors":
 304 parser.make_NUM. parser.make_PLUS, parser.make_STRING, etc.  The previous
 305 example becomes
 306
 307         return parser.make_NUM ("Hello, World!\n");
 308
 309 which would easily be caught by the type checker.
 310
 311 ** Push Parser
 312 Add support for push parser.  Do not start a nice skeleton, just enhance the
 313 current one to support push parsers.  This is going to be a tougher nut to
 314 crack.
 315
 316 First, you need to understand well how the push parser is expected to work.
 317 To this end:
 318 - read the doc
 319 - look at examples/c/pushcalc
 320 - create an example of a Java push parser.
 321 - have a look at the generated parser in Java, which has the advantage of
 322   being already based on a parser object, instead of just a function.
 323
 324 The C case is harder to read, but it may help too.  Keep in mind that
 325 because there's no object to maintain state, the C push parser uses some
 326 struct (yypstate) to preserve this state.  We don't need this in D, the
 327 parser object will suffice.
 328
 329 I think working directly on the skeleton to add push-parser support is not
 330 the simplest path.  I suggest that you (1) transform a generated parser into
 331 a push parser by hand, and then (2) transform lalr1.d to generate such a
 332 parser.
 333
 334 Use `git commit` frequently to make sure you keep track of your progress.
 335
 336 *** (1.a) Prepare pull parser by hand
 337 Copy again one of the D examples into say examples/d/pushcalc.  Also
 338 check-in the generated parser to facilitate experimentation.
 339
 340 - find local variables of yyparse should become members of the parser object
 341   (so that we preserve state from one call to the next).
 342
 343 - do it in your generated D parser.  We don't need an equivalent for
 344   yypstate, because we already have it: that the parser object itself.
 345
 346 - have your *pull*-parser (i.e., the good old yy::parser::parse()) work
 347   properly this way.  Write and run tests.  That's one of the reasons I
 348   suggest using examples/d/calc as a starting point: it already has tests,
 349   you can/should add more.
 350
 351 At this point you have a pull-parser which you prepared to turn into a
 352 push-parser.
 353
 354 *** (1.b) Turn pull parser into push parser by hand
 355
 356 - look again at how push parsers are implemented in Java/C to see what needs
 357   to change in yyparse so that the control is inverted: parse() will
 358   be *given* the tokens, instead of having to call yylex itself.  When I say
 359   "look at C", I think your best option are (i) yacc.c (look for b4_push_if)
 360   and (ii) examples/c/pushcalc.
 361
 362 - rename parse() as push_parse(Symbol yyla) (or push_parse(TokenKind, Value,
 363   Location)) that takes the symbol as argument.  That's the push parser we
 364   are looking for.
 365
 366 - define a new parse() function which has the same signature as the usual
 367   pull-parser, that repeatedly calls the push_parse function.  Something
 368   like this:
 369
 370 int parse ()
 371 {
 372  int status = 0;
 373  do {
 374   status = this->push_parse (yylex());
 375  } while (status == YYPUSH_MORE);
 376  return status;
 377 }
 378
 379 - show me that parser, so that we can validate the approach.
 380
 381 *** (2) Port that into the skeleton
 382 - once we agree on the API of the push parser, implement it into lalr1.d.
 383   You will probaby need help on this regard, but imitation, again, should
 384   help.
 385
 386 - have example/d/pushcalc work properly and pass tests
 387
 388 - add tests in the "real" test suite.  Do that in tests/calc.at.  I can
 389   help.
 390
 391 - document
 392
 393 ** GLR Parser
 394 This is very ambitious.  That's the final boss.  There are currently no
 395 "clean" implementation to get inspiration from.
 396
 397 glr.c is very clean but:
 398 - is low-level C
 399 - is a different skeleton from yacc.c
 400
 401 glr.cc is (currently) an ugly hack: a C++ shell around glr.c.  Valentin
 402 Tolmer is currently rewriting glr.cc to be clean C++, but he is not
 403 finished.  There will be a lot a common code between lalr1.cc and glr.cc, so
 404 eventually I would like them to be fused into a single skeleton, supporting
 405 both deterministic and generalized parsing.
 406
 407 It would be great for D to also support this.
 408
 409 The basic ideas of GLR are explained here:
 410
 411 https://www.codeproject.com/Articles/5259825/GLR-Parsing-in-Csharp-How-to-Use-The-Most-Powerful
 412
 413 * Better error messages
 414 The users are not provided with enough tools to forge their error messages.
 415 See for instance "Is there an option to change the message produced by
 416 YYERROR_VERBOSE?" by Simon Sobisch, on bison-help.
 417
 418 See also
 419 https://www.cs.tufts.edu/~nr/cs257/archive/clinton-jefferey/lr-error-messages.pdf
 420 https://research.swtch.com/yyerror
 421 http://gallium.inria.fr/~fpottier/publis/fpottier-reachability-cc2016.pdf
 422
 423 * Modernization
 424 Fix data/skeletons/yacc.c so that it defines YYPTRDIFF_T properly for modern
 425 and older C++ compilers.  Currently the code defaults to defining it to
 426 'long' for non-GCC compilers, but it should use the proper C++ magic to
 427 define it to the same type as the C ptrdiff_t type.
 428
 429 * Completion
 430 Several features are not available in all the back-ends.
 431
 432 - push parsers: glr.c, glr.cc, lalr1.cc (not very difficult)
 433 - token constructors: Java, C, D (a bit difficult)
 434 - glr: D, Java (super difficult)
 435
 436 * Bugs
 437 ** Autotest has quotation issues
 438 tests/input.at:1730:AT_SETUP([%define errors])
 439
 440 ->
 441
 442 $ ./tests/testsuite -l | grep errors | sed q
 443   38: input.at:1730      errors
 444
 445 * Short term
 446 ** Get rid of YYPRINT and b4_toknum
 447 Besides yytoknum is wrong when api.token.raw is defined.
 448
 449 ** Better design for diagnostics
 450 The current implementation of diagnostics is ad hoc, it grew organically.
 451 It works as a series of calls to several functions, with dependency of the
 452 latter calls on the former.  For instance:
 453
 454       complain (&sym->location,
 455                 sym->content->status == needed ? complaint : Wother,
 456                 _("symbol %s is used, but is not defined as a token"
 457                   " and has no rules; did you mean %s?"),
 458                 quote_n (0, sym->tag),
 459                 quote_n (1, best->tag));
 460       if (feature_flag & feature_caret)
 461         location_caret_suggestion (sym->location, best->tag, stderr);
 462
 463 We should rewrite this in a more FP way:
 464
 465 1. build a rich structure that denotes the (complete) diagnostic.
 466    "Complete" in the sense that it also contains the suggestions, the list
 467    of possible matches, etc.
 468
 469 2. send this to the pretty-printing routine.  The diagnostic structure
 470    should be sufficient so that we can generate all the 'format' of
 471    diagnostics, including the fixits.
 472
 473 If properly done, this diagnostic module can be detached from Bison and be
 474 put in gnulib.  It could be used, for instance, for errors caught by
 475 xgettext.
 476
 477 There's certainly already something alike in GCC.  At least that's the
 478 impression I get from reading the "-fdiagnostics-format=FORMAT" part of this
 479 page:
 480
 481 https://gcc.gnu.org/onlinedocs/gcc/Diagnostic-Message-Formatting-Options.html
 482
 483 ** Graphviz display code thoughts
 484 The code for the --graph option is over two files: print_graph, and
 485 graphviz. This is because Bison used to also produce VCG graphs, but since
 486 this is no longer true, maybe we could consider these files for fusion.
 487
 488 An other consideration worth noting is that print_graph.c (correct me if I
 489 am wrong) should contain generic functions, whereas graphviz.c and other
 490 potential files should contain just the specific code for that output
 491 format. It will probably prove difficult to tell if the implementation is
 492 actually generic whilst only having support for a single format, but it
 493 would be nice to keep stuff a bit tidier: right now, the construction of the
 494 bitset used to show reductions is in the graphviz-specific code, and on the
 495 opposite side we have some use of \l, which is graphviz-specific, in what
 496 should be generic code.
 497
 498 Little effort seems to have been given to factoring these files and their
 499 print{,-xml} counterpart. We would very much like to re-use the pretty format
 500 of states from .output for the graphs, etc.
 501
 502 Since graphviz dies on medium-to-big grammars, maybe consider an other tool?
 503
 504 ** push-parser
 505 Check it too when checking the different kinds of parsers.  And be
 506 sure to check that the initial-action is performed once per parsing.
 507
 508 ** m4 names
 509 b4_shared_declarations is no longer what it is.  Make it
 510 b4_parser_declaration for instance.
 511
 512 ** yychar in lalr1.cc
 513 There is a large difference bw maint and master on the handling of
 514 yychar (which was removed in lalr1.cc).  See what needs to be
 515 back-ported.
 516
 517
 518     /* User semantic actions sometimes alter yychar, and that requires
 519        that yytoken be updated with the new translation.  We take the
 520        approach of translating immediately before every use of yytoken.
 521        One alternative is translating here after every semantic action,
 522        but that translation would be missed if the semantic action
 523        invokes YYABORT, YYACCEPT, or YYERROR immediately after altering
 524        yychar.  In the case of YYABORT or YYACCEPT, an incorrect
 525        destructor might then be invoked immediately.  In the case of
 526        YYERROR, subsequent parser actions might lead to an incorrect
 527        destructor call or verbose syntax error message before the
 528        lookahead is translated.  */
 529
 530     /* Make sure we have latest lookahead translation.  See comments at
 531        user semantic actions for why this is necessary.  */
 532     yytoken = yytranslate_ (yychar);
 533
 534
 535 ** Get rid of fake #lines [Bison: ...]
 536 Possibly as simple as checking whether the column number is nonnegative.
 537
 538 I have seen messages like the following from GCC.
 539
 540 <built-in>:0: fatal error: opening dependency file .deps/libltdl/argz.Tpo: No such file or directory
 541
 542
 543 ** Discuss about %printer/%destroy in the case of C++.
 544 It would be very nice to provide the symbol classes with an operator<<
 545 and a destructor.  Unfortunately the syntax we have chosen for
 546 %destroy and %printer make them hard to reuse.  For instance, the user
 547 is invited to write something like
 548
 549    %printer { debug_stream() << $$; } <my_type>;
 550
 551 which is hard to reuse elsewhere since it wants to use
 552 "debug_stream()" to find the stream to use.  The same applies to
 553 %destroy: we told the user she could use the members of the Parser
 554 class in the printers/destructors, which is not good for an operator<<
 555 since it is no longer bound to a particular parser, it's just a
 556 (standalone symbol).
 557
 558 * Various
 559 ** Rewrite glr.cc in C++ (Valentin Tolmer)
 560 As a matter of fact, it would be very interesting to see how much we can
 561 share between lalr1.cc and glr.cc.  Most of the skeletons should be common.
 562 It would be a very nice source of inspiration for the other languages.
 563
 564 Valentin Tolmer is working on this.
 565
 566 * From lalr1.cc to yacc.c
 567 ** Single stack
 568 Merging the three stacks in lalr1.cc simplified the code, prompted for
 569 other improvements and also made it faster (probably because memory
 570 management is performed once instead of three times).  I suggest that
 571 we do the same in yacc.c.
 572
 573 (Some time later): it's also very nice to have three stacks: it's more dense
 574 as we don't lose bits to padding.  For instance the typical stack for states
 575 will use 8 bits, while it is likely to consume 32 bits in a struct.
 576
 577 We need trustworthy benchmarks for Bison, for all our backends.  Akim has a
 578 few things scattered around; we need to put them in the repo, and make them
 579 more useful.
 580
 581 * Report
 582
 583 ** Figures
 584 Some statistics about the grammar and the parser would be useful,
 585 especially when asking the user to send some information about the
 586 grammars she is working on.  We should probably also include some
 587 information about the variables (I'm not sure for instance we even
 588 specify what LR variant was used).
 589
 590 ** GLR
 591 How would Paul like to display the conflicted actions?  In particular,
 592 what when two reductions are possible on a given lookahead token, but one is
 593 part of $default.  Should we make the two reductions explicit, or just
 594 keep $default?  See the following point.
 595
 596 ** Disabled Reductions
 597 See 'tests/conflicts.at (Defaulted Conflicted Reduction)', and decide
 598 what we want to do.
 599
 600 ** Documentation
 601 Extend with error productions.  The hard part will probably be finding
 602 the right rule so that a single state does not exhibit too many yet
 603 undocumented ''features''.  Maybe an empty action ought to be
 604 presented too.  Shall we try to make a single grammar with all these
 605 features, or should we have several very small grammars?
 606
 607 * Extensions
 608 ** More languages?
 609 Well, only if there is really some demand for it.
 610
 611 *** PHP
 612 https://github.com/scfc/bison-php/blob/master/data/lalr1.php
 613
 614 *** Python
 615 https://lists.gnu.org/r/bison-patches/2013-09/msg00000.html and following
 616
 617 ** Multiple start symbols
 618 Would be very useful when parsing closely related languages.  The idea is to
 619 declare several start symbols, for instance
 620
 621     %start stmt expr
 622     %%
 623     stmt: ...
 624     expr: ...
 625
 626 and to generate parse(), parse_stmt() and parse_expr().  Technically, the
 627 above grammar would be transformed into
 628
 629    %start yy_start
 630    %token YY_START_STMT YY_START_EXPR
 631    %%
 632    yy_start: YY_START_STMT stmt | YY_START_EXPR expr
 633
 634 so that there are no new conflicts in the grammar (as would undoubtedly
 635 happen with yy_start: stmt | expr).  Then adjust the skeletons so that this
 636 initial token (YY_START_STMT, YY_START_EXPR) be shifted first in the
 637 corresponding parse function.
 638
 639 *** Number of useless symbols
 640 AT_TEST(
 641 [[%start exp;
 642 exp: exp;]],
 643 [[input.y: warning: 2 nonterminals useless in grammar [-Wother]
 644 input.y: warning: 2 rules useless in grammar [-Wother]
 645 input.y:2.8-10: error: start symbol exp does not derive any sentence]])
 646
 647 We should say "1 nonterminal": the other one is $accept, which should not
 648 participate in the count.
 649
 650 *** Tokens
 651 Do we want to disallow terminal start symbols?  The limitation is not
 652 technical.  Can it be useful to someone to "parse" a token?
 653
 654 ** %include
 655 This is a popular demand.  We already made many changes in the parser that
 656 should make this reasonably easy to implement.
 657
 658 Bruce Mardle <marblypup@yahoo.co.uk>
 659 https://lists.gnu.org/archive/html/bison-patches/2015-09/msg00000.html
 660
 661 However, there are many other things to do before having such a feature,
 662 because I don't want a % equivalent to #include (which we all learned to
 663 hate).  I want something that builds "modules" of grammars, and assembles
 664 them together, paying attention to keep separate bits separated, in pseudo
 665 name spaces.
 666
 667 ** Push parsers
 668 There is demand for push parsers in C++.
 669
 670 ** Generate code instead of tables
 671 This is certainly quite a lot of work.  See
 672 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4539.
 673
 674 ** $-1
 675 We should find a means to provide an access to values deep in the
 676 stack.  For instance, instead of
 677
 678         baz: qux { $$ = $<foo>-1 + $<bar>0 + $1; }
 679
 680 we should be able to have:
 681
 682   foo($foo) bar($bar) baz($bar): qux($qux) { $baz = $foo + $bar + $qux; }
 683
 684 Or something like this.
 685
 686 ** %if and the like
 687 It should be possible to have %if/%else/%endif.  The implementation is
 688 not clear: should it be lexical or syntactic.  Vadim Maslow thinks it
 689 must be in the scanner: we must not parse what is in a switched off
 690 part of %if.  Akim Demaille thinks it should be in the parser, so as
 691 to avoid falling into another CPP mistake.
 692
 693 (Later): I'm sure there's actually good case for this.  People who need that
 694 feature can use m4/cpp on top of Bison.  I don't think it is worth the
 695 trouble in Bison itself.
 696
 697 ** XML Output
 698 There are couple of available extensions of Bison targeting some XML
 699 output.  Some day we should consider including them.  One issue is
 700 that they seem to be quite orthogonal to the parsing technique, and
 701 seem to depend mostly on the possibility to have some code triggered
 702 for each reduction.  As a matter of fact, such hooks could also be
 703 used to generate the yydebug traces.  Some generic scheme probably
 704 exists in there.
 705
 706 XML output for GNU Bison and gcc
 707    http://www.cs.may.ie/~jpower/Research/bisonXML/
 708
 709 XML output for GNU Bison
 710    http://yaxx.sourceforge.net/
 711
 712 * Coding system independence
 713 Paul notes:
 714
 715         Currently Bison assumes 8-bit bytes (i.e. that UCHAR_MAX is
 716         255).  It also assumes that the 8-bit character encoding is
 717         the same for the invocation of 'bison' as it is for the
 718         invocation of 'cc', but this is not necessarily true when
 719         people run bison on an ASCII host and then use cc on an EBCDIC
 720         host.  I don't think these topics are worth our time
 721         addressing (unless we find a gung-ho volunteer for EBCDIC or
 722         PDP-10 ports :-) but they should probably be documented
 723         somewhere.
 724
 725         More importantly, Bison does not currently allow NUL bytes in
 726         tokens, either via escapes (e.g., "x\0y") or via a NUL byte in
 727         the source code.  This should get fixed.
 728
 729 * Broken options?
 730 ** %token-table
 731 ** Skeleton strategy
 732 Must we keep %token-table?
 733
 734 * Precedence
 735
 736 ** Partial order
 737 It is unfortunate that there is a total order for precedence.  It
 738 makes it impossible to have modular precedence information.  We should
 739 move to partial orders (sounds like series/parallel orders to me).
 740
 741 This is a prerequisite for modules.
 742
 743 * Pre and post actions.
 744 From: Florian Krohm <florian@edamail.fishkill.ibm.com>
 745 Subject: YYACT_EPILOGUE
 746 To: bug-bison@gnu.org
 747 X-Sent: 1 week, 4 days, 14 hours, 38 minutes, 11 seconds ago
 748
 749 The other day I had the need for explicitly building the parse tree. I
 750 used %locations for that and defined YYLLOC_DEFAULT to call a function
 751 that returns the tree node for the production. Easy. But I also needed
 752 to assign the S-attribute to the tree node. That cannot be done in
 753 YYLLOC_DEFAULT, because it is invoked before the action is executed.
 754 The way I solved this was to define a macro YYACT_EPILOGUE that would
 755 be invoked after the action. For reasons of symmetry I also added
 756 YYACT_PROLOGUE. Although I had no use for that I can envision how it
 757 might come in handy for debugging purposes.
 758 All is needed is to add
 759
 760 #if YYLSP_NEEDED
 761     YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen, yyloc, (yylsp - yylen));
 762 #else
 763     YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen);
 764 #endif
 765
 766 at the proper place to bison.simple. Ditto for YYACT_PROLOGUE.
 767
 768 I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
 769 to bison. If you're interested, I'll work on a patch.
 770
 771 * Better graphics
 772 Equip the parser with a means to create the (visual) parse tree.
 773
 774
 775 -----
 776
 777 # LocalWords:  Cex gnulib gl Bistromathic TokenKinds yylex enum YYEOF EOF
 778 # LocalWords:  YYerror gettext af hb YYERRCODE undef calc FIXME dev yyerror
 779 # LocalWords:  Autoconf YYUNDEFTOK lexemes parsers Bistromathic's yyreport
 780 # LocalWords:  const argc yacc yyclearin lookahead destructor Rici incluent
 781 # LocalWords:  yydestruct yydiscardin catégories d'avertissements sr activé
 782 # LocalWords:  conflits défaut rr l'alias chaîne n'est attaché un symbole
 783 # LocalWords:  obsolète règle vide midrule valeurs de intermédiaire ou avec
 784 # LocalWords:  définies inutilisées priorité associativité inutiles POSIX
 785 # LocalWords:  incompatibilités tous les autres avertissements sauf dans rp
 786 # LocalWords:  désactiver CATEGORIE traiter comme des erreurs glr Akim bool
 787 # LocalWords:  Demaille arith lalr goto struct pathlen nullable ntokens lr
 788 # LocalWords:  nterm bitsetv ielr ritem nstates nrules nritems yysymbol EQ
 789 # LocalWords:  SymbolKind YYEMPTY YYUNDEF YYTNAME NUM yyntokens yytname sed
 790 # LocalWords:  nonterminals yykind yycode YYNAMES yynames init getName conv
 791 # LocalWords:  TokenKind ival yychar yylval yylexer Tolmer hoc
 792 # LocalWords:  Sobisch YYPTRDIFF ptrdiff Autotest YYPRINT toknum yytoknum
 793 # LocalWords:  sym Wother stderr FP fixits xgettext fdiagnostics Graphviz
 794 # LocalWords:  graphviz VCG bitset xml bw maint yytoken YYABORT deps
 795 # LocalWords:  YYACCEPT yytranslate nonnegative destructors yyerrlab repo
 796 # LocalWords:  backends stmt expr yy Mardle baz qux Vadim Maslow CPP cpp
 797 # LocalWords:  yydebug gcc UCHAR EBCDIC gung PDP NUL Pre Florian Krohm utf
 798 # LocalWords:  YYACT YYLLOC YYLSP yyval yyvsp yylen yyloc yylsp endif
 799 # LocalWords:  ispell american
 800
 801 Local Variables:
 802 mode: outline
 803 coding: utf-8
 804 fill-column: 76
 805 ispell-dictionary: "american"
 806 End:
 807
 808 Copyright (C) 2001-2004, 2006, 2008-2015, 2018-2020 Free Software
 809 Foundation, Inc.
 810
 811 This file is part of Bison, the GNU Compiler Compiler.
 812
 813 Permission is granted to copy, distribute and/or modify this document
 814 under the terms of the GNU Free Documentation License, Version 1.3 or
 815 any later version published by the Free Software Foundation; with no
 816 Invariant Sections, with no Front-Cover Texts, and with no Back-Cover
 817 Texts.  A copy of the license is included in the "GNU Free
 818 Documentation License" file as part of this distribution.