TODO

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