* data/glr.c (yynewGLRStackItem, YY_RESERVE_GLRSTACK): New.

[bison.git] / TODO

diff --git a/TODO b/TODO
index 51d8d4603a498b67bbe8dff7af917f57e84c0b37..a44f64ece477177531dc7e42dd733d5b37d12751 100644 (file)
--- a/TODO
+++ b/TODO
@@ -1,42 +1,98 @@
 -*- outline -*-
 
 -*- outline -*-
 

-* URGENT: Documenting C++ output
-Write a first documentation for C++ output.
+* Header guards

 
 

-* value_components_used
-Was defined but not used: where was it coming from?  It can't be to
-check if %union is used, since the user is free to $<foo>n on her
-union, doesn't she?
+From Franc,ois: should we keep the directory part in the CPP guard?

 
 

-* 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...

 
 

-* documentation
-Explain $axiom (and maybe change its name: BTYacc names it `goal',
-byacc `$accept' probably based on AT&T Yacc, Meta `Start'...).
-Complete the glossary (item, axiom, ?).
+* Yacc.c: CPP Macros

 
 

-* Error messages
-Some are really funky.  For instance
+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...).

 
 

-       type clash (`%s' `%s') on default action

 
 

-is really weird.  Revisit them all.
+* Documentation
+Before releasing, make sure the documentation ("Understanding your
+parser") refers to the current `output' format.

 
 

-* Report documentation
-Extend with error.  The hard part will probably be finding the right
-rule so that a single state does not exhibit to 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?
+* lalr1.cc
+** vector
+Move to using vector, drop stack.hh.

 
 

-* Documentation
-Some history of Bison and some bibliography would be most welcome.
-Are there any Texinfo standards for bibliography?
+** I18n
+Catch up with yacc.c.
+
+* Report
+
+**  GLR
+How would Paul like to display the conflicted actions?  In particular,
+what when two reductions are possible on a given look-ahead token, but one is
+part of $default.  Should we make the two reductions explicit, or just
+keep $default?  See the following point.
+
+** Disabled Reductions
+See `tests/conflicts.at (Defaulted Conflicted Reduction)', and decide
+what we want to do.
+
+** 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?
+
+** --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.
+
+
+* Extensions
+
+** 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:
+
+       exp (res): exp (a) '+' exp (b) { $res = $a + $b; };
+
+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...
+
+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:
+
+       r:exp -> a:exp '+' b:exp { r = a + b; };
+
+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...
+
+Note that there remains the problem of locations: `@r'?
+
+
+** $-1
+We should find a means to provide an access to values deep in the
+stack.  For instance, instead of

 
 

-* Several %unions
+       baz: qux { $$ = $<foo>-1 + $<bar>0 + $1; }
+
+we should be able to have:
+
+  foo($foo) bar($bar) baz($bar): qux($qux) { $baz = $foo + $bar + $qux; }
+
+Or something like this.
+
+** yysymprint interface
+It should be improved, in particular when using Bison features such as
+locations, and YYPARSE_PARAMS.  For the time being, it is almost
+recommended to yyprint to steal internal variables...
+
+** 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
 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


@@ -57,23 +113,30 @@ When implementing multiple-%union support, bare the following in mind:
          char *sval;
        }
 
          char *sval;
        }
 

-* --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.
+** %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.

 
 

-* Coding system independence
-Paul notes:
+** -D, --define-muscle NAME=VALUE
+To define muscles via cli.  Or maybe support directly NAME=VALUE?

 
 

-       Currently Bison assumes 8-bit bytes (i.e. that UCHAR_MAX is
-       255).  It also assumes that the 8-bit character encoding is
-       the same for the invocation of 'bison' as it is for the
-       invocation of 'cc', but this is not necessarily true when
-       people run bison on an ASCII host and then use cc on an EBCDIC
-       host.  I don't think these topics are worth our time
-       addressing (unless we find a gung-ho volunteer for EBCDIC or
-       PDP-10 ports :-) but they should probably be documented
-       somewhere.
+** 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.
+
+XML output for GNU Bison and gcc
+   http://www.cs.may.ie/~jpower/Research/bisonXML/
+
+XML output for GNU Bison
+   http://yaxx.sourceforge.net/

 
 * Unit rules
 Maybe we could expand unit rules, i.e., transform
 
 * Unit rules
 Maybe we could expand unit rules, i.e., transform


@@ -92,57 +155,62 @@ 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?
 
 `Parsing Techniques: a Practical Guide', it includes information about
 this issue.  Does anybody have it?
 

-* 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 '('
-
-* 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.
+
+
+* Documentation
+
+** History/Bibliography
+Some history of Bison and some bibliography would be most welcome.
+Are there any Texinfo standards for bibliography?
+
+
+
+* Java, Fortran, etc.
+
+
+** Java
+
+There are a couple of proposed outputs:
+
+- BYACC/J
+  which is based on Byacc.
+  <http://troi.lincom-asg.com/~rjamison/byacc/>
+
+- Bison Java
+  which is based on Bison.
+  <http://www.goice.co.jp/member/mo/hack-progs/bison-java.html>
+
+Sebastien Serrurier (serrur_s@epita.fr) is working on this: he is
+expected to contact the authors, design the output, and implement it
+into Bison.
+
+
+* Coding system independence
+Paul notes:
+
+       Currently Bison assumes 8-bit bytes (i.e. that UCHAR_MAX is
+       255).  It also assumes that the 8-bit character encoding is
+       the same for the invocation of 'bison' as it is for the
+       invocation of 'cc', but this is not necessarily true when
+       people run bison on an ASCII host and then use cc on an EBCDIC
+       host.  I don't think these topics are worth our time
+       addressing (unless we find a gung-ho volunteer for EBCDIC or
+       PDP-10 ports :-) but they should probably be documented
+       somewhere.
+
+       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.       []
 
 * Broken options ?
 
 * --graph
 Show reductions.       []
 
 * Broken options ?

-** %no-lines           [ok]

 ** %no-parser          []
 ** %no-parser          []

-** %pure-parser                []

 ** %token-table                []
 ** %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?
 ** Skeleton strategy.  []
 Must we keep %no-parser?
             %token-table?

-*** New skeletons.     []

 
 * src/print_graph.c
 Find the best graph parameters.        []
 
 * src/print_graph.c
 Find the best graph parameters.        []


@@ -150,7 +218,7 @@ Find the best graph parameters.     []
 * doc/bison.texinfo
 ** Update
 informations about ERROR_VERBOSE.      []
 * doc/bison.texinfo
 ** Update
 informations about ERROR_VERBOSE.      []

-** Add explainations about
+** Add explanations about

 skeleton muscles.      []
 %skeleton.             []
 
 skeleton muscles.      []
 %skeleton.             []
 


@@ -158,26 +226,54 @@ skeleton muscles. []
 ** tests/pure-parser.at        []
 New tests.
 
 ** tests/pure-parser.at        []
 New tests.
 

-* input synclines
-Some users create their foo.y files, and equip them with #line.  Bison
-should recognize these, and preserve them.
-

 * BTYacc
 * BTYacc

-See if we can integrate backtracking in Bison.  Contact the BTYacc
-maintainers.
+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.
+
+** Keeping the conflicted actions
+First, analyze the differences between byacc and btyacc (I'm referring
+to the executables).  Find where the conflicts are preserved.
+
+** 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.
+
+** Adjust the skeletons
+Import the skeletons for C and C++.
+
+** Improve the skeletons
+Have them support yysymprint, yydestruct and so forth.

 
 

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

 
 * Precedence
 
 * 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
 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.
+move to partial orders (sounds like series/parallel orders to me).

 
 This will be possible with a Bison parser for the grammar, as it will
 make it much easier to extend the grammar.
 
 
 This will be possible with a Bison parser for the grammar, as it will
 make it much easier to extend the grammar.
 

+** 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?
+
+If there is really no profound motivation, we should find a new syntax
+to allow specifying this.
+
+** RR conflicts
+See if we can use precedence between rules to solve RR conflicts.  See
+what POSIX says.
+
+

 * $undefined
 From Hans:
 - If the Bison generated parser experiences an undefined number in the
 * $undefined
 From Hans:
 - If the Bison generated parser experiences an undefined number in the


@@ -186,6 +282,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


@@ -202,6 +299,7 @@ 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.
 

+

 * Warnings
 It would be nice to have warning support.  See how Autoconf handles
 them, it is fairly well described there.  It would be very nice to
 * Warnings
 It would be nice to have warning support.  See how Autoconf handles
 them, it is fairly well described there.  It would be very nice to


@@ -212,6 +310,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


@@ -246,7 +345,7 @@ 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 Free Software Foundation, Inc.

 
 This file is part of GNU Bison.
 
 
 This file is part of GNU Bison.
 


@@ -262,5 +361,5 @@ GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 along with Bison; see the file COPYING.  If not, write to
 
 You should have received a copy of the GNU General Public License
 along with Bison; see the file COPYING.  If not, write to

-the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA.
+the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA.