TODO

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