TODO

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