Fix tabs.

[bison.git] / TODO

diff --git a/TODO b/TODO
index c056bbbb663c9c1f0226eac3d7b8f497e90ec7a4..b2bca35404a7526ee7e6a077568d62cd6c21541e 100644 (file)
--- a/TODO
+++ b/TODO
@@ -1,149 +1,150 @@
 -*- outline -*-
 
 -*- outline -*-
 

-* Several %unions
-I think this is a pleasant (but useless currently) feature, but in the
-future, I want a means to %include other bits of grammars, and _then_
-it will be important for the various bits to define their needs in
-%union.
+* Header guards

 
 

-When implementing multiple-%union support, bare the following in mind:
+From Franc,ois: should we keep the directory part in the CPP guard?

 
 

-- when --yacc, this must be flagged as an error.  Don't make it fatal
-  though.

 
 

-- The #line must now appear *inside* the definition of yystype.
-  Something like
+* Yacc.c: CPP Macros

 
 

-       {
-       #line 12 "foo.y"
-         int ival;
-       #line 23 "foo.y"
-         char *sval;
-       }
-
-* Experimental report features
-Decide whether they should be enabled, or optional.  For instance, on:
+Do some people use YYPURE, YYLSP_NEEDED like we do in the test suite?
+They should not: it is not documented.  But if they need to, let's
+find something clean (not like YYLSP_NEEDED...).

 
 

-       input:
-         exp
-       | input exp
-       ;

 
 

-       exp:
-         token1 "1"
-       | token2 "2"
-       | token3 "3"
-       ;
+* Installation

 
 

-       token1: token;
-       token2: token;
-       token3: token;
+* Documentation
+Before releasing, make sure the documentation ("Understanding your
+parser") refers to the current `output' format.

 
 

-the traditional Bison reports:
+* lalr1.cc
+** vector
+Move to using vector, drop stack.hh.

 
 

-       state 0
+** I18n
+Catch up with yacc.c.

 
 

-           $axiom  ->  . input $   (rule 0)
+* Report

 
 

-           token       shift, and go to state 1
+**  GLR
+How would Paul like to display the conflicted actions?  In particular,
+what when two reductions are possible on a given lookahead token, but one is
+part of $default.  Should we make the two reductions explicit, or just
+keep $default?  See the following point.

 
 

-           input       go to state 2
-           exp         go to state 3
-           token1      go to state 4
-           token2      go to state 5
-           token3      go to state 6
+** Disabled Reductions
+See `tests/conflicts.at (Defaulted Conflicted Reduction)', and decide
+what we want to do.

 
 

-       state 1
+** Documentation
+Extend with error productions.  The hard part will probably be finding
+the right rule so that a single state does not exhibit too many yet
+undocumented ``features''.  Maybe an empty action ought to be
+presented too.  Shall we try to make a single grammar with all these
+features, or should we have several very small grammars?

 
 

-           token1  ->  token .   (rule 6)
-           token2  ->  token .   (rule 7)
-           token3  ->  token .   (rule 8)
+** --report=conflict-path
+Provide better assistance for understanding the conflicts by providing
+a sample text exhibiting the (LALR) ambiguity.  See the paper from
+DeRemer and Penello: they already provide the algorithm.

 
 

-           "2"         reduce using rule 7 (token2)
-           "3"         reduce using rule 8 (token3)
-           $default    reduce using rule 6 (token1)
+** Statically check for potential ambiguities in GLR grammars.  See
+<http://www.i3s.unice.fr/~schmitz/papers.html#expamb> for an approach.

 
 

-while with --trace, i.e., when enabling both the display of non-core
-item sets and the display of lookaheads, Bison now displays:

 
 

-       state 0
+* Extensions

 
 

-           $axiom  ->  . input $   (rule 0)
-           input  ->  . exp   (rule 1)
-           input  ->  . input exp   (rule 2)
-           exp  ->  . token1 "1"   (rule 3)
-           exp  ->  . token2 "2"   (rule 4)
-           exp  ->  . token3 "3"   (rule 5)
-           token1  ->  . token   (rule 6)
-           token2  ->  . token   (rule 7)
-           token3  ->  . token   (rule 8)
+** Labeling the symbols
+Have a look at the Lemon parser generator: instead of $1, $2 etc. they
+can name the values.  This is much more pleasant.  For instance:

 
 

-           token       shift, and go to state 1
+       exp (res): exp (a) '+' exp (b) { $res = $a + $b; };

 
 

-           input       go to state 2
-           exp         go to state 3
-           token1      go to state 4
-           token2      go to state 5
-           token3      go to state 6
+I love this.  I have been bitten too often by the removal of the
+symbol, and forgetting to shift all the $n to $n-1.  If you are
+unlucky, it compiles...

 
 

-       state 1
+But instead of using $a etc., we can use regular variables.  And
+instead of using (), I propose to use `:' (again).  Paul suggests
+supporting `->' in addition to `:' to separate LHS and RHS. In other
+words:

 
 

-           token1  ->  token .  ["1"]   (rule 6)
-           token2  ->  token .  ["2"]   (rule 7)
-           token3  ->  token .  ["3"]   (rule 8)
+       r:exp -> a:exp '+' b:exp { r = a + b; };

 
 

-           "2"         reduce using rule 7 (token2)
-           "3"         reduce using rule 8 (token3)
-           $default    reduce using rule 6 (token1)
+That requires an significant improvement of the grammar parser.  Using
+GLR would be nice.  It also requires that Bison know the type of the
+symbols (which will be useful for %include anyway).  So we have some
+time before...

 
 

-so decide whether this should be an option, or always enabled.  I'm in
-favor of making it the default, but maybe we should tune the output to
-distinguish core item sets from non core:
+Note that there remains the problem of locations: `@r'?

 
 

-       state 0
-           Core:
-           $axiom  ->  . input $   (rule 0)

 
 

-           Derived:
-           input  ->  . exp   (rule 1)
-           input  ->  . input exp   (rule 2)
-           exp  ->  . token1 "1"   (rule 3)
-           exp  ->  . token2 "2"   (rule 4)
-           exp  ->  . token3 "3"   (rule 5)
-           token1  ->  . token   (rule 6)
-           token2  ->  . token   (rule 7)
-           token3  ->  . token   (rule 8)
+** $-1
+We should find a means to provide an access to values deep in the
+stack.  For instance, instead of

 
 

-           token       shift, and go to state 1
+       baz: qux { $$ = $<foo>-1 + $<bar>0 + $1; }

 
 

-           input       go to state 2
-           exp         go to state 3
-           token1      go to state 4
-           token2      go to state 5
-           token3      go to state 6
+we should be able to have:

 
 

+  foo($foo) bar($bar) baz($bar): qux($qux) { $baz = $foo + $bar + $qux; }

 
 

-> So, it seems clear that it has to be an additional option :)
+Or something like this.

 
 

-Paul:
+** %if and the like
+It should be possible to have %if/%else/%endif.  The implementation is
+not clear: should it be lexical or syntactic.  Vadim Maslow thinks it
+must be in the scanner: we must not parse what is in a switched off
+part of %if.  Akim Demaille thinks it should be in the parser, so as
+to avoid falling into another CPP mistake.

 
 

-       There will be further such options in the future, so I'd make
-       them all operands of the --report option.  E.g., you could do
-       something like this:
+** -D, --define-muscle NAME=VALUE
+To define muscles via cli.  Or maybe support directly NAME=VALUE?

 
 

-       --report=state --report=lookahead --report=itemset
-       --report=conflict-path
+** XML Output
+There are couple of available extensions of Bison targeting some XML
+output.  Some day we should consider including them.  One issue is
+that they seem to be quite orthogonal to the parsing technique, and
+seem to depend mostly on the possibility to have some code triggered
+for each reduction.  As a matter of fact, such hooks could also be
+used to generate the yydebug traces.  Some generic scheme probably
+exists in there.

 
 

-       where "--verbose" is equivalent to "--report=state", and where
-       "--report=conflict-path" reports each path to a conflict
-       state.
+XML output for GNU Bison and gcc
+   http://www.cs.may.ie/~jpower/Research/bisonXML/

 
 

-       (As a minor point, I prefer avoiding plurals in option names.
-       It's partly for brevity, and partly to avoid wearing out the
-       's' keys in our keyboards.  :-)
+XML output for GNU Bison
+   http://yaxx.sourceforge.net/

 
 

-To implement this, see in the Fileutils the latest versions of
-argmatch and so forth.
+* Unit rules
+Maybe we could expand unit rules, i.e., transform
+
+       exp: arith | bool;
+       arith: exp '+' exp;
+       bool: exp '&' exp;
+
+into
+
+       exp: exp '+' exp | exp '&' exp;
+
+when there are no actions.  This can significantly speed up some
+grammars.  I can't find the papers.  In particular the book `LR
+parsing: Theory and Practice' is impossible to find, but according to
+`Parsing Techniques: a Practical Guide', it includes information about
+this issue.  Does anybody have it?
+
+
+
+* Documentation
+
+** History/Bibliography
+Some history of Bison and some bibliography would be most welcome.
+Are there any Texinfo standards for bibliography?
+
+
+
+* Java, Fortran, etc.

 
 
 * Coding system independence
 
 
 * Coding system independence


@@ -159,262 +160,65 @@ Paul notes:
        PDP-10 ports :-) but they should probably be documented
        somewhere.
 
        PDP-10 ports :-) but they should probably be documented
        somewhere.
 

-* Output directory
-Akim:
-
-| I consider this to be a bug in bison:
-|
-| /tmp % mkdir src
-| /tmp % cp ~/src/bison/tests/calc.y src
-| /tmp % mkdir build && cd build
-| /tmp/build % bison ../src/calc.y
-| /tmp/build % cd ..
-| /tmp % ls -l build src
-| build:
-| total 0
-|
-| src:
-| total 32
-| -rw-r--r--    1 akim     lrde        27553 oct  2 16:31 calc.tab.c
-| -rw-r--r--    1 akim     lrde         3335 oct  2 16:31 calc.y
-|
-|
-| Would it be safe to change this behavior to something more reasonable?
-| Do you think some people depend upon this?
-
-Jim:
-
-Is it that behavior documented?
-If so, then it's probably not reasonable to change it.
-I've Cc'd the automake list, because some of automake's
-rules use bison through $(YACC) -- though I'll bet they
-all use it in yacc-compatible mode.
-
-Pavel:
-
-Hello, Jim and others!
-
-> Is it that behavior documented?
-> If so, then it's probably not reasonable to change it.
-> I've Cc'd the automake list, because some of automake's
-> rules use bison through $(YACC) -- though I'll bet they
-> all use it in yacc-compatible mode.
-
-Yes, Automake currently used bison in Automake-compatible mode, but it
-would be fair for Automake to switch to the native mode as long as the
-processed files are distributed and "missing" emulates bison.
-
-In any case, the makefiles should specify the output file explicitly
-instead of relying on weird defaults.
-
-> | src:
-> | total 32
-> | -rw-r--r--    1 akim     lrde        27553 oct  2 16:31 calc.tab.c
-> | -rw-r--r--    1 akim     lrde         3335 oct  2 16:31 calc.y
-
-This is not _that_ ugly as it seems - with Automake you want to put
-sources where they belong - to the source directory.
-
-> | This is not _that_ ugly as it seems - with Automake you want to put
-> | sources where they belong - to the source directory.
->
-> The difference source/build you are referring to is based on Automake
-> concepts.  They have no sense at all for tools such as bison or gcc
-> etc.  They have input and output.  I do not want them to try to grasp
-> source/build.  I want them to behave uniformly: output *here*.
-
-I realize that.
-
-It's unfortunate that the native mode of Bison behaves in a less uniform
-way than the yacc mode. I agree with your point. Bison maintainters may
-want to fix it along with the documentation.
+       More importantly, Bison does not currently allow NUL bytes in
+       tokens, either via escapes (e.g., "x\0y") or via a NUL byte in
+       the source code.  This should get fixed.

 
 

+* --graph
+Show reductions.

 
 

-* Unit rules
-Maybe we could expand unit rules, i.e., transform
+* Broken options ?
+** %token-table
+** Skeleton strategy
+Must we keep %token-table?

 
 

-       exp: arith | bool;
-       arith: exp '+' exp;
-       bool: exp '&' exp;
+* src/print_graph.c
+Find the best graph parameters.

 
 

-into
+* BTYacc
+See if we can integrate backtracking in Bison.  Charles-Henri de
+Boysson <de-boy_c@epita.fr> is working on this, and already has some
+results.  Vadim Maslow, the maintainer of BTYacc was contacted, and we
+stay in touch with him.  Adjusting the Bison grammar parser will be
+needed to support some extra BTYacc features.  This is less urgent.

 
 

-       exp: exp '+' exp | exp '&' exp;
+** Keeping the conflicted actions
+First, analyze the differences between byacc and btyacc (I'm referring
+to the executables).  Find where the conflicts are preserved.

 
 

-when there are no actions.  This can significantly speed up some
-grammars.
-
-* Stupid error messages
-An example shows it easily:
-
-src/bison/tests % ./testsuite -k calc,location,error-verbose -l
-GNU Bison 1.49a test suite test groups:
-
- NUM: FILENAME:LINE      TEST-GROUP-NAME
-      KEYWORDS
-
-  51: calc.at:440        Calculator --locations --yyerror-verbose
-  52: calc.at:442        Calculator --defines --locations --name-prefix=calc --verbose --yacc --yyerror-verbose
-  54: calc.at:445        Calculator --debug --defines --locations --name-prefix=calc --verbose --yacc --yyerror-verbose
-src/bison/tests % ./testsuite 51 -d
-## --------------------------- ##
-## GNU Bison 1.49a test suite. ##
-## --------------------------- ##
- 51: calc.at:440       ok
-## ---------------------------- ##
-## All 1 tests were successful. ##
-## ---------------------------- ##
-src/bison/tests % cd ./testsuite.dir/51
-tests/testsuite.dir/51 % echo "()" | ./calc
-1.2-1.3: parse error, unexpected ')', expecting error or "number" or '-' or '('
-
-* yyerror, yyprint interface
-It should be improved, in particular when using Bison features such as
-locations, and YYPARSE_PARAMS.  For the time being, it is recommended
-to #define yyerror and yyprint to steal internal variables...
-
-* read_pipe.c
-This is not portable to DOS for instance.  Implement a more portable
-scheme.  Sources of inspiration include GNU diff, and Free Recode.
-
-* Memory leaks in the generator
-A round of memory leak clean ups would be most welcome.  Dmalloc,
-Checker GCC, Electric Fence, or Valgrind: you chose your tool.
-
-* Memory leaks in the parser
-The same applies to the generated parsers.  In particular, this is
-critical for user data: when aborting a parsing, when handling the
-error token etc., we often throw away yylval without giving a chance
-of cleaning it up to the user.
+** Compare with the GLR tables
+See how isomorphic the way BTYacc and the way the GLR adjustments in
+Bison are compatible.  *As much as possible* one should try to use the
+same implementation in the Bison executables.  I insist: it should be
+very feasible to use the very same conflict tables.

 
 

-* --graph
-Show reductions.       []
+** Adjust the skeletons
+Import the skeletons for C and C++.

 
 

-* Broken options ?
-** %no-lines           [ok]
-** %no-parser          []
-** %pure-parser                []
-** %token-table                []
-** Options which could use parse_dquoted_param ().
-Maybe transfered in lex.c.
-*** %skeleton          [ok]
-*** %output            []
-*** %file-prefix       []
-*** %name-prefix       []
-
-** Skeleton strategy.  []
-Must we keep %no-parser?
-            %token-table?
-*** New skeletons.     []
+** Improve the skeletons
+Have them support yysymprint, yydestruct and so forth.

 
 

-* src/print_graph.c
-Find the best graph parameters.        []
-
-* doc/bison.texinfo
-** Update
-informations about ERROR_VERBOSE.      []
-** Add explainations about
-skeleton muscles.      []
-%skeleton.             []
-
-* testsuite
-** tests/pure-parser.at        []
-New tests.
-
-* Debugging parsers
-
-From Greg McGary:
-
-akim demaille <akim.demaille@epita.fr> writes:
-
-> With great pleasure!  Nonetheless, things which are debatable
-> (or not, but just `big') should be discuss in `public': something
-> like help- or bug-bison@gnu.org is just fine.  Jesse and I are there,
-> but there is also Jim and some other people.
-
-I have no idea whether it qualifies as big or controversial, so I'll
-just summarize for you.  I proposed this change years ago and was
-surprised that it was met with utter indifference!
-
-This debug feature is for the programs/grammars one develops with
-bison, not for debugging bison itself.  I find that the YYDEBUG
-output comes in a very inconvenient format for my purposes.
-When debugging gcc, for instance, what I want is to see a trace of
-the sequence of reductions and the line#s for the semantic actions
-so I can follow what's happening.  Single-step in gdb doesn't cut it
-because to move from one semantic action to the next takes you through
-lots of internal machinery of the parser, which is uninteresting.
-
-The change I made was to the format of the debug output, so that it
-comes out in the format of C error messages, digestible by emacs
-compile mode, like so:
-
-grammar.y:1234: foo: bar(0x123456) baz(0x345678)
-
-where "foo: bar baz" is the reduction rule, whose semantic action
-appears on line 1234 of the bison grammar file grammar.y.  The hex
-numbers on the rhs tokens are the parse-stack values associated with
-those tokens.  Of course, yytype might be something totally
-incompatible with that representation, but for the most part, yytype
-values are single words (scalars or pointers).  In the case of gcc,
-they're most often pointers to tree nodes.  Come to think of it, the
-right thing to do is to make the printing of stack values be
-user-definable.  It would also be useful to include the filename &
-line# of the file being parsed, but the main filename & line# should
-continue to be that of grammar.y
-
-Anyway, this feature has saved my life on numerous occasions.  The way
-I customarily use it is to first run bison with the traces on, isolate
-the sequence of reductions that interests me, put those traces in a
-buffer and force it into compile-mode, then visit each of those lines
-in the grammar and set breakpoints with C-x SPACE.  Then, I can run
-again under the control of gdb and stop at each semantic action.
-With the hex addresses of tree nodes, I can inspect the values
-associated with any rhs token.
-
-You like?
-
-* input synclines
-Some users create their foo.y files, and equip them with #line.  Bison
-should recognize these, and preserve them.

 
 

-* BTYacc
-See if we can integrate backtracking in Bison.  Contact the BTYacc
-maintainers.
+* Precedence
+
+** Partial order
+It is unfortunate that there is a total order for precedence.  It
+makes it impossible to have modular precedence information.  We should
+move to partial orders (sounds like series/parallel orders to me).
+
+** Correlation b/w precedence and associativity
+Also, I fail to understand why we have to assign the same
+associativity to operators with the same precedence.  For instance,
+why can't I decide that the precedence of * and / is the same, but the
+latter is nonassoc?

 
 

-* Automaton report
-Display more clearly the lookaheads for each item.
+If there is really no profound motivation, we should find a new syntax
+to allow specifying this.

 
 

-* RR conflicts
+** RR conflicts

 See if we can use precedence between rules to solve RR conflicts.  See
 what POSIX says.
 
 See if we can use precedence between rules to solve RR conflicts.  See
 what POSIX says.
 

-* Precedence
-It is unfortunate that there is a total order for precedence.  It
-makes it impossible to have modular precedence information.  We should
-move to partial orders.
-
-This will be possible with a Bison parser for the grammar, as it will
-make it much easier to extend the grammar.
-
-* Parsing grammars
-Rewrite the reader in Flex/Bison.  There will be delicate parts, in
-particular, expect the scanner to be hard to write.  Many interesting
-features cannot be implemented without such a new reader.
-
-* Presentation of the report file
-From: "Baum, Nathan I" <s0009525@chelt.ac.uk>
-Subject: Token Alias Bug
-To: "'bug-bison@gnu.org'" <bug-bison@gnu.org>
-
-I've also noticed something, that whilst not *wrong*, is inconvienient: I
-use the verbose mode to help find the causes of unresolved shift/reduce
-conflicts. However, this mode insists on starting the .output file with a
-list of *resolved* conflicts, something I find quite useless. Might it be
-possible to define a -v mode, and a -vv mode -- Where the -vv mode shows
-everything, but the -v mode only tells you what you need for examining
-conflicts? (Or, perhaps, a "*** This state has N conflicts ***" marker above
-each state with conflicts.)

 
 * $undefined
 From Hans:
 
 * $undefined
 From Hans:


@@ -424,6 +228,7 @@ addition to the $undefined value.
 
 Suggest: Change the name $undefined to undefined; looks better in outputs.
 
 
 Suggest: Change the name $undefined to undefined; looks better in outputs.
 

+

 * Default Action
 From Hans:
 - For use with my C++ parser, I transported the "switch (yyn)" statement
 * Default Action
 From Hans:
 - For use with my C++ parser, I transported the "switch (yyn)" statement


@@ -440,8 +245,6 @@ a Bison option where every typed default rule is explicitly written out
 
 Note: Robert Anisko handles this.  He knows how to do it.
 
 
 Note: Robert Anisko handles this.  He knows how to do it.
 

-* Documenting C++ output
-Write a first documentation for C++ output.

 
 * Warnings
 It would be nice to have warning support.  See how Autoconf handles
 
 * Warnings
 It would be nice to have warning support.  See how Autoconf handles


@@ -453,6 +256,7 @@ Don't work on this without first announcing you do, as I already have
 thought about it, and know many of the components that can be used to
 implement it.
 
 thought about it, and know many of the components that can be used to
 implement it.
 

+

 * Pre and post actions.
 From: Florian Krohm <florian@edamail.fishkill.ibm.com>
 Subject: YYACT_EPILOGUE
 * Pre and post actions.
 From: Florian Krohm <florian@edamail.fishkill.ibm.com>
 Subject: YYACT_EPILOGUE


@@ -481,23 +285,25 @@ at the proper place to bison.simple. Ditto for YYACT_PROLOGUE.
 I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
 to bison. If you're interested, I'll work on a patch.
 
 I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
 to bison. If you're interested, I'll work on a patch.
 

+* Better graphics
+Equip the parser with a means to create the (visual) parse tree.
+

 -----
 
 -----
 

-Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+Copyright (C) 2001, 2002, 2003, 2004, 2006 Free Software Foundation,
+Inc.

 
 

-This file is part of GNU Autoconf.
+This file is part of Bison, the GNU Compiler Compiler.

 
 

-GNU Autoconf is free software; you can redistribute it and/or modify
+This program is free software: you can redistribute it and/or modify

 it under the terms of the GNU General Public License as published by
 it under the terms of the GNU General Public License as published by

-the Free Software Foundation; either version 2, or (at your option)
-any later version.
+the Free Software Foundation, either version 3 of the License, or
+(at your option) any later version.

 
 

-GNU Autoconf is distributed in the hope that it will be useful,
+This program is distributed in the hope that it will be useful,

 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License

-along with autoconf; see the file COPYING.  If not, write to
-the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA.
+along with this program.  If not, see <http://www.gnu.org/licenses/>.