TODO

   1 -*- outline -*-
   2
   3 * Various
   4 ** YYERRCODE
   5 Defined to 256, but not used, not documented.  Probably the token
   6 number for the error token, which POSIX wants to be 256, but which
   7 Bison might renumber if the user used number 256.  Keep fix and doc?
   8 Throw away?
   9
  10 ** YYFAIL
  11 It is seems to be *really* obsolete now, shall we remove it?
  12
  13 ** YYBACKUP
  14 There is no test about it, no examples in the doc, and I'm not sure
  15 what it should look like.  For instance what follows crashes.
  16
  17   %error-verbose
  18   %debug
  19   %pure-parser
  20   %code {
  21   # include <stdio.h>
  22   # include <stdlib.h>
  23   # include <assert.h>
  24
  25     static void yyerror (const char *msg);
  26     static int yylex (YYSTYPE *yylval);
  27   }
  28   %%
  29   exp:
  30     'a'   { printf ("a: %d\n", $1); }
  31   | 'b'   { YYBACKUP('a', 123); }
  32   ;
  33   %%
  34   static int
  35   yylex (YYSTYPE *yylval)
  36   {
  37     static char const input[] = "b";
  38     static size_t toknum;
  39     assert (toknum < sizeof input);
  40     *yylval = (toknum + 1) * 10;
  41     return input[toknum++];
  42   }
  43
  44   static void
  45   yyerror (const char *msg)
  46   {
  47     fprintf (stderr, "%s\n", msg);
  48   }
  49
  50   int
  51   main (void)
  52   {
  53     yydebug = !!getenv("YYDEBUG");
  54     return yyparse ();
  55   }
  56
  57
  58 * Header guards
  59
  60 From Franc,ois: should we keep the directory part in the CPP guard?
  61
  62
  63 * Yacc.c: CPP Macros
  64
  65 Do some people use YYPURE, YYLSP_NEEDED like we do in the test suite?
  66 They should not: it is not documented.  But if they need to, let's
  67 find something clean (not like YYLSP_NEEDED...).
  68
  69
  70 * Installation
  71
  72 * Documentation
  73 Before releasing, make sure the documentation ("Understanding your
  74 parser") refers to the current `output' format.
  75
  76 * lalr1.cc
  77 ** I18n
  78 Catch up with yacc.c.
  79
  80 * Report
  81
  82 **  GLR
  83 How would Paul like to display the conflicted actions?  In particular,
  84 what when two reductions are possible on a given lookahead token, but one is
  85 part of $default.  Should we make the two reductions explicit, or just
  86 keep $default?  See the following point.
  87
  88 ** Disabled Reductions
  89 See `tests/conflicts.at (Defaulted Conflicted Reduction)', and decide
  90 what we want to do.
  91
  92 ** Documentation
  93 Extend with error productions.  The hard part will probably be finding
  94 the right rule so that a single state does not exhibit too many yet
  95 undocumented ``features''.  Maybe an empty action ought to be
  96 presented too.  Shall we try to make a single grammar with all these
  97 features, or should we have several very small grammars?
  98
  99 ** --report=conflict-path
 100 Provide better assistance for understanding the conflicts by providing
 101 a sample text exhibiting the (LALR) ambiguity.  See the paper from
 102 DeRemer and Penello: they already provide the algorithm.
 103
 104 ** Statically check for potential ambiguities in GLR grammars.  See
 105 <http://www.i3s.unice.fr/~schmitz/papers.html#expamb> for an approach.
 106
 107
 108 * Extensions
 109
 110 ** Labeling the symbols
 111 Have a look at the Lemon parser generator: instead of $1, $2 etc. they
 112 can name the values.  This is much more pleasant.  For instance:
 113
 114        exp (res): exp (a) '+' exp (b) { $res = $a + $b; };
 115
 116 I love this.  I have been bitten too often by the removal of the
 117 symbol, and forgetting to shift all the $n to $n-1.  If you are
 118 unlucky, it compiles...
 119
 120 But instead of using $a etc., we can use regular variables.  And
 121 instead of using (), I propose to use `:' (again).  Paul suggests
 122 supporting `->' in addition to `:' to separate LHS and RHS. In other
 123 words:
 124
 125        r:exp -> a:exp '+' b:exp { r = a + b; };
 126
 127 That requires an significant improvement of the grammar parser.  Using
 128 GLR would be nice.  It also requires that Bison know the type of the
 129 symbols (which will be useful for %include anyway).  So we have some
 130 time before...
 131
 132 Note that there remains the problem of locations: `@r'?
 133
 134
 135 ** $-1
 136 We should find a means to provide an access to values deep in the
 137 stack.  For instance, instead of
 138
 139         baz: qux { $$ = $<foo>-1 + $<bar>0 + $1; }
 140
 141 we should be able to have:
 142
 143   foo($foo) bar($bar) baz($bar): qux($qux) { $baz = $foo + $bar + $qux; }
 144
 145 Or something like this.
 146
 147 ** %if and the like
 148 It should be possible to have %if/%else/%endif.  The implementation is
 149 not clear: should it be lexical or syntactic.  Vadim Maslow thinks it
 150 must be in the scanner: we must not parse what is in a switched off
 151 part of %if.  Akim Demaille thinks it should be in the parser, so as
 152 to avoid falling into another CPP mistake.
 153
 154 ** XML Output
 155 There are couple of available extensions of Bison targeting some XML
 156 output.  Some day we should consider including them.  One issue is
 157 that they seem to be quite orthogonal to the parsing technique, and
 158 seem to depend mostly on the possibility to have some code triggered
 159 for each reduction.  As a matter of fact, such hooks could also be
 160 used to generate the yydebug traces.  Some generic scheme probably
 161 exists in there.
 162
 163 XML output for GNU Bison and gcc
 164    http://www.cs.may.ie/~jpower/Research/bisonXML/
 165
 166 XML output for GNU Bison
 167    http://yaxx.sourceforge.net/
 168
 169 * Unit rules
 170 Maybe we could expand unit rules, i.e., transform
 171
 172         exp: arith | bool;
 173         arith: exp '+' exp;
 174         bool: exp '&' exp;
 175
 176 into
 177
 178         exp: exp '+' exp | exp '&' exp;
 179
 180 when there are no actions.  This can significantly speed up some
 181 grammars.  I can't find the papers.  In particular the book `LR
 182 parsing: Theory and Practice' is impossible to find, but according to
 183 `Parsing Techniques: a Practical Guide', it includes information about
 184 this issue.  Does anybody have it?
 185
 186
 187
 188 * Documentation
 189
 190 ** History/Bibliography
 191 Some history of Bison and some bibliography would be most welcome.
 192 Are there any Texinfo standards for bibliography?
 193
 194
 195
 196 * Java, Fortran, etc.
 197
 198
 199 * Coding system independence
 200 Paul notes:
 201
 202         Currently Bison assumes 8-bit bytes (i.e. that UCHAR_MAX is
 203         255).  It also assumes that the 8-bit character encoding is
 204         the same for the invocation of 'bison' as it is for the
 205         invocation of 'cc', but this is not necessarily true when
 206         people run bison on an ASCII host and then use cc on an EBCDIC
 207         host.  I don't think these topics are worth our time
 208         addressing (unless we find a gung-ho volunteer for EBCDIC or
 209         PDP-10 ports :-) but they should probably be documented
 210         somewhere.
 211
 212         More importantly, Bison does not currently allow NUL bytes in
 213         tokens, either via escapes (e.g., "x\0y") or via a NUL byte in
 214         the source code.  This should get fixed.
 215
 216 * --graph
 217 Show reductions.
 218
 219 * Broken options ?
 220 ** %token-table
 221 ** Skeleton strategy
 222 Must we keep %token-table?
 223
 224 * BTYacc
 225 See if we can integrate backtracking in Bison.  Charles-Henri de
 226 Boysson <de-boy_c@epita.fr> has been working on this, but never gave
 227 the results.
 228
 229 Vadim Maslow, the maintainer of BTYacc was once contacted.  Adjusting
 230 the Bison grammar parser will be needed to support some extra BTYacc
 231 features.  This is less urgent.
 232
 233 ** Keeping the conflicted actions
 234 First, analyze the differences between byacc and btyacc (I'm referring
 235 to the executables).  Find where the conflicts are preserved.
 236
 237 ** Compare with the GLR tables
 238 See how isomorphic the way BTYacc and the way the GLR adjustments in
 239 Bison are compatible.  *As much as possible* one should try to use the
 240 same implementation in the Bison executables.  I insist: it should be
 241 very feasible to use the very same conflict tables.
 242
 243 ** Adjust the skeletons
 244 Import the skeletons for C and C++.
 245
 246
 247 * Precedence
 248
 249 ** Partial order
 250 It is unfortunate that there is a total order for precedence.  It
 251 makes it impossible to have modular precedence information.  We should
 252 move to partial orders (sounds like series/parallel orders to me).
 253
 254 ** RR conflicts
 255 See if we can use precedence between rules to solve RR conflicts.  See
 256 what POSIX says.
 257
 258
 259 * $undefined
 260 From Hans:
 261 - If the Bison generated parser experiences an undefined number in the
 262 character range, that character is written out in diagnostic messages, an
 263 addition to the $undefined value.
 264
 265 Suggest: Change the name $undefined to undefined; looks better in outputs.
 266
 267
 268 * Default Action
 269 From Hans:
 270 - For use with my C++ parser, I transported the "switch (yyn)" statement
 271 that Bison writes to the bison.simple skeleton file. This way, I can remove
 272 the current default rule $$ = $1 implementation, which causes a double
 273 assignment to $$ which may not be OK under C++, replacing it with a
 274 "default:" part within the switch statement.
 275
 276 Note that the default rule $$ = $1, when typed, is perfectly OK under C,
 277 but in the C++ implementation I made, this rule is different from
 278 $<type_name>$ = $<type_name>1. I therefore think that one should implement
 279 a Bison option where every typed default rule is explicitly written out
 280 (same typed ruled can of course be grouped together).
 281
 282 * Pre and post actions.
 283 From: Florian Krohm <florian@edamail.fishkill.ibm.com>
 284 Subject: YYACT_EPILOGUE
 285 To: bug-bison@gnu.org
 286 X-Sent: 1 week, 4 days, 14 hours, 38 minutes, 11 seconds ago
 287
 288 The other day I had the need for explicitly building the parse tree. I
 289 used %locations for that and defined YYLLOC_DEFAULT to call a function
 290 that returns the tree node for the production. Easy. But I also needed
 291 to assign the S-attribute to the tree node. That cannot be done in
 292 YYLLOC_DEFAULT, because it is invoked before the action is executed.
 293 The way I solved this was to define a macro YYACT_EPILOGUE that would
 294 be invoked after the action. For reasons of symmetry I also added
 295 YYACT_PROLOGUE. Although I had no use for that I can envision how it
 296 might come in handy for debugging purposes.
 297 All is needed is to add
 298
 299 #if YYLSP_NEEDED
 300     YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen, yyloc, (yylsp - yylen));
 301 #else
 302     YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen);
 303 #endif
 304
 305 at the proper place to bison.simple. Ditto for YYACT_PROLOGUE.
 306
 307 I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
 308 to bison. If you're interested, I'll work on a patch.
 309
 310 * Better graphics
 311 Equip the parser with a means to create the (visual) parse tree.
 312
 313 -----
 314
 315 Copyright (C) 2001, 2002, 2003, 2004, 2006, 2008 Free Software Foundation,
 316 Inc.
 317
 318 This file is part of Bison, the GNU Compiler Compiler.
 319
 320 This program is free software: you can redistribute it and/or modify
 321 it under the terms of the GNU General Public License as published by
 322 the Free Software Foundation, either version 3 of the License, or
 323 (at your option) any later version.
 324
 325 This program is distributed in the hope that it will be useful,
 326 but WITHOUT ANY WARRANTY; without even the implied warranty of
 327 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 328 GNU General Public License for more details.
 329
 330 You should have received a copy of the GNU General Public License
 331 along with this program.  If not, see <http://www.gnu.org/licenses/>.