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 ** I18n
  23 Catch up with yacc.c.
  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 * BTYacc
 173 See if we can integrate backtracking in Bison.  Charles-Henri de
 174 Boysson <de-boy_c@epita.fr> has been working on this, but never gave
 175 the results.
 176
 177 Vadim Maslow, the maintainer of BTYacc was once contacted.  Adjusting
 178 the Bison grammar parser will be needed to support some extra BTYacc
 179 features.  This is less urgent.
 180
 181 ** Keeping the conflicted actions
 182 First, analyze the differences between byacc and btyacc (I'm referring
 183 to the executables).  Find where the conflicts are preserved.
 184
 185 ** Compare with the GLR tables
 186 See how isomorphic the way BTYacc and the way the GLR adjustments in
 187 Bison are compatible.  *As much as possible* one should try to use the
 188 same implementation in the Bison executables.  I insist: it should be
 189 very feasible to use the very same conflict tables.
 190
 191 ** Adjust the skeletons
 192 Import the skeletons for C and C++.
 193
 194
 195 * Precedence
 196
 197 ** Partial order
 198 It is unfortunate that there is a total order for precedence.  It
 199 makes it impossible to have modular precedence information.  We should
 200 move to partial orders (sounds like series/parallel orders to me).
 201
 202 ** Correlation b/w precedence and associativity
 203 Also, I fail to understand why we have to assign the same
 204 associativity to operators with the same precedence.  For instance,
 205 why can't I decide that the precedence of * and / is the same, but the
 206 latter is nonassoc?
 207
 208 If there is really no profound motivation, we should find a new syntax
 209 to allow specifying this.
 210
 211 ** RR conflicts
 212 See if we can use precedence between rules to solve RR conflicts.  See
 213 what POSIX says.
 214
 215
 216 * $undefined
 217 From Hans:
 218 - If the Bison generated parser experiences an undefined number in the
 219 character range, that character is written out in diagnostic messages, an
 220 addition to the $undefined value.
 221
 222 Suggest: Change the name $undefined to undefined; looks better in outputs.
 223
 224
 225 * Default Action
 226 From Hans:
 227 - For use with my C++ parser, I transported the "switch (yyn)" statement
 228 that Bison writes to the bison.simple skeleton file. This way, I can remove
 229 the current default rule $$ = $1 implementation, which causes a double
 230 assignment to $$ which may not be OK under C++, replacing it with a
 231 "default:" part within the switch statement.
 232
 233 Note that the default rule $$ = $1, when typed, is perfectly OK under C,
 234 but in the C++ implementation I made, this rule is different from
 235 $<type_name>$ = $<type_name>1. I therefore think that one should implement
 236 a Bison option where every typed default rule is explicitly written out
 237 (same typed ruled can of course be grouped together).
 238
 239 * Pre and post actions.
 240 From: Florian Krohm <florian@edamail.fishkill.ibm.com>
 241 Subject: YYACT_EPILOGUE
 242 To: bug-bison@gnu.org
 243 X-Sent: 1 week, 4 days, 14 hours, 38 minutes, 11 seconds ago
 244
 245 The other day I had the need for explicitly building the parse tree. I
 246 used %locations for that and defined YYLLOC_DEFAULT to call a function
 247 that returns the tree node for the production. Easy. But I also needed
 248 to assign the S-attribute to the tree node. That cannot be done in
 249 YYLLOC_DEFAULT, because it is invoked before the action is executed.
 250 The way I solved this was to define a macro YYACT_EPILOGUE that would
 251 be invoked after the action. For reasons of symmetry I also added
 252 YYACT_PROLOGUE. Although I had no use for that I can envision how it
 253 might come in handy for debugging purposes.
 254 All is needed is to add
 255
 256 #if YYLSP_NEEDED
 257     YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen, yyloc, (yylsp - yylen));
 258 #else
 259     YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen);
 260 #endif
 261
 262 at the proper place to bison.simple. Ditto for YYACT_PROLOGUE.
 263
 264 I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
 265 to bison. If you're interested, I'll work on a patch.
 266
 267 * Better graphics
 268 Equip the parser with a means to create the (visual) parse tree.
 269
 270 -----
 271
 272 Copyright (C) 2001, 2002, 2003, 2004, 2006, 2008 Free Software Foundation,
 273 Inc.
 274
 275 This file is part of Bison, the GNU Compiler Compiler.
 276
 277 This program is free software: you can redistribute it and/or modify
 278 it under the terms of the GNU General Public License as published by
 279 the Free Software Foundation, either version 3 of the License, or
 280 (at your option) any later version.
 281
 282 This program is distributed in the hope that it will be useful,
 283 but WITHOUT ANY WARRANTY; without even the implied warranty of
 284 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 285 GNU General Public License for more details.
 286
 287 You should have received a copy of the GNU General Public License
 288 along with this program.  If not, see <http://www.gnu.org/licenses/>.