TODO

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