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