X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/dada3cd19e2754d16b999fd43183a8e8a9d88d30..0149d39e6e5cb4384c07d92c00908d0099d5e009:/TODO diff --git a/TODO b/TODO index 9dbd6b42..09fce089 100644 --- a/TODO +++ b/TODO @@ -1,4 +1,89 @@ --*- outline -*- +* Short term +** Graphviz display code thoughts +The code for the --graph option is over two files: print_graph, and +graphviz. This is because Bison used to also produce VCG graphs, but since +this is no longer true, maybe we could consider these files for fusion. + +An other consideration worth noting is that print_graph.c (correct me if I +am wrong) should contain generic functions, whereas graphviz.c and other +potential files should contain just the specific code for that output +format. It will probably prove difficult to tell if the implementation is +actually generic whilst only having support for a single format, but it +would be nice to keep stuff a bit tidier: right now, the construction of the +bitset used to show reductions is in the graphviz-specific code, and on the +opposite side we have some use of \l, which is graphviz-specific, in what +should be generic code. + +Little effort seems to have been given to factoring these files and their +rint{,-xml} counterpart. We would very much like to re-use the pretty format +of states from .output for the graphs, etc. + +Also, the underscore in print_graph.[ch] isn't very fitting considering the +dashes in the other filenames. + +Since graphviz dies on medium-to-big grammars, maybe consider an other tool? + +** push-parser +Check it too when checking the different kinds of parsers. And be +sure to check that the initial-action is performed once per parsing. + +** m4 names +b4_shared_declarations is no longer what it is. Make it +b4_parser_declaration for instance. + +** yychar in lalr1.cc +There is a large difference bw maint and master on the handling of +yychar (which was removed in lalr1.cc). See what needs to be +back-ported. + + + /* User semantic actions sometimes alter yychar, and that requires + that yytoken be updated with the new translation. We take the + approach of translating immediately before every use of yytoken. + One alternative is translating here after every semantic action, + but that translation would be missed if the semantic action + invokes YYABORT, YYACCEPT, or YYERROR immediately after altering + yychar. In the case of YYABORT or YYACCEPT, an incorrect + destructor might then be invoked immediately. In the case of + YYERROR, subsequent parser actions might lead to an incorrect + destructor call or verbose syntax error message before the + lookahead is translated. */ + + /* Make sure we have latest lookahead translation. See comments at + user semantic actions for why this is necessary. */ + yytoken = yytranslate_ (yychar); + + +** stack.hh +Get rid of it. The original idea is nice, but actually it makes +the code harder to follow, and uselessly different from the other +skeletons. + +** Get rid of fake #lines [Bison: ...] +Possibly as simple as checking whether the column number is nonnegative. + +I have seen messages like the following from GCC. + +:0: fatal error: opening dependency file .deps/libltdl/argz.Tpo: No such file or directory + + +** Discuss about %printer/%destroy in the case of C++. +It would be very nice to provide the symbol classes with an operator<< +and a destructor. Unfortunately the syntax we have chosen for +%destroy and %printer make them hard to reuse. For instance, the user +is invited to write something like + + %printer { debug_stream() << $$; } ; + +which is hard to reuse elsewhere since it wants to use +"debug_stream()" to find the stream to use. The same applies to +%destroy: we told the user she could use the members of the Parser +class in the printers/destructors, which is not good for an operator<< +since it is no longer bound to a particular parser, it's just a +(standalone symbol). + +** Rename LR0.cc +as lr0.cc, why upper case? * Various ** YYERRCODE @@ -7,62 +92,54 @@ number for the error token, which POSIX wants to be 256, but which Bison might renumber if the user used number 256. Keep fix and doc? Throw away? -** YYFAIL -It is seems to be *really* obsolete now, shall we remove it? - -** YYBACKUP -There is no test about it, no examples in the doc, and I'm not sure -what it should look like. For instance what follows crashes. - - %error-verbose - %debug - %pure-parser - %code { - # include - # include - # include - - static void yyerror (const char *msg); - static int yylex (YYSTYPE *yylval); - } - %% - exp: - 'a' { printf ("a: %d\n", $1); } - | 'b' { YYBACKUP('a', 123); } - ; - %% - static int - yylex (YYSTYPE *yylval) - { - static char const input[] = "b"; - static size_t toknum; - assert (toknum < sizeof input); - *yylval = (toknum + 1) * 10; - return input[toknum++]; - } - - static void - yyerror (const char *msg) +Also, why don't we output the token name of the error token in the +output? It is explicitly skipped: + + /* Skip error token and tokens without identifier. */ + if (sym != errtoken && id) + +Of course there are issues with name spaces, but if we disable we have +something which seems to be more simpler and more consistent instead +of the special case YYERRCODE. + + enum yytokentype { + error = 256, + // ... + }; + + +We could (should?) also treat the case of the undef_token, which is +numbered 257 for yylex, and 2 internal. Both appear for instance in +toknum: + + const unsigned short int + parser::yytoken_number_[] = { - fprintf (stderr, "%s\n", msg); - } + 0, 256, 257, 258, 259, 260, 261, 262, 263, 264, + +while here + + enum yytokentype { + TOK_EOF = 0, + TOK_EQ = 258, + +so both 256 and 257 are "mysterious". - int - main (void) + const char* + const parser::yytname_[] = { - yydebug = !!getenv("YYDEBUG"); - return yyparse (); - } + "\"end of command\"", "error", "$undefined", "\"=\"", "\"break\"", + ** yychar == yyempty_ The code in yyerrlab reads: if (yychar <= YYEOF) - { - /* Return failure if at end of input. */ - if (yychar == YYEOF) - YYABORT; - } + { + /* Return failure if at end of input. */ + if (yychar == YYEOF) + YYABORT; + } There are only two yychar that can be <= YYEOF: YYEMPTY and YYEOF. But I can't produce the situation where yychar is YYEMPTY here, is it @@ -71,12 +148,6 @@ really possible? The test suite does not exercise this case. This shows that it would be interesting to manage to install skeleton coverage analysis to the test suite. -** Table definitions -It should be very easy to factor the definition of the various tables, -including the separation bw declaration and definition. See for -instance b4_table_define in lalr1.cc. This way, we could even factor -C vs. C++ definitions. - * From lalr1.cc to yacc.c ** Single stack Merging the three stacks in lalr1.cc simplified the code, prompted for @@ -85,33 +156,19 @@ management is performed once instead of three times). I suggest that we do the same in yacc.c. ** yysyntax_error -In lalr1.cc we invoke it with the translated lookahead (yytoken), and -yacc.c uses yychar. I don't see why. - -** yysyntax_error -The use of switch to select yyfmt in lalr1.cc seems simpler than -what's done in yacc.c. +The code bw glr.c and yacc.c is really alike, we can certainly factor +some parts. -* Header guards - -From Franc,ois: should we keep the directory part in the CPP guard? - - -* Yacc.c: CPP Macros - -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...). - - -* Installation - -* Documentation -Before releasing, make sure the documentation ("Understanding your -parser") refers to the current `output' format. * Report +** Figures +Some statistics about the grammar and the parser would be useful, +especially when asking the user to send some information about the +grammars she is working on. We should probably also include some +information about the variables (I'm not sure for instance we even +specify what LR variant was used). + ** 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 @@ -119,13 +176,13 @@ 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 +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 +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? @@ -140,36 +197,11 @@ 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 - baz: qux { $$ = $-1 + $0 + $1; } + baz: qux { $$ = $-1 + $0 + $1; } we should be able to have: @@ -202,18 +234,18 @@ XML output for GNU Bison * Unit rules Maybe we could expand unit rules, i.e., transform - exp: arith | bool; - arith: exp '+' exp; - bool: exp '&' exp; + exp: arith | bool; + arith: exp '+' exp; + bool: exp '&' exp; into - exp: exp '+' exp | exp '&' exp; + 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 +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 +'Parsing Techniques: a Practical Guide', it includes information about this issue. Does anybody have it? @@ -224,59 +256,28 @@ this issue. Does anybody have it? Some history of Bison and some bibliography would be most welcome. Are there any Texinfo standards for bibliography? - - -* Java, Fortran, etc. - - * 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. + 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. -* --graph -Show reductions. + 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. * Broken options ? ** %token-table ** Skeleton strategy Must we keep %token-table? -* BTYacc -See if we can integrate backtracking in Bison. Charles-Henri de -Boysson has been working on this, but never gave -the results. - -Vadim Maslow, the maintainer of BTYacc was once contacted. 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++. - - * Precedence ** Partial order @@ -343,10 +344,32 @@ 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. +* Complaint submessage indentation. +We already have an implementation that works fairly well for named +reference messages, but it would be nice to use it consistently for all +submessages from Bison. For example, the "previous definition" +submessage or the list of correct values for a %define variable might +look better with indentation. + +However, the current implementation makes the assumption that the +location printed on the first line is not usually much shorter than the +locations printed on the submessage lines that follow. That assumption +may not hold true as often for some kinds of submessages especially if +we ever support multiple grammar files. + +Here's a proposal for how a new implementation might look: + + http://lists.gnu.org/archive/html/bison-patches/2009-09/msg00086.html + + +Local Variables: +mode: outline +coding: utf-8 +End: + ----- -Copyright (C) 2001, 2002, 2003, 2004, 2006, 2008 Free Software Foundation, -Inc. +Copyright (C) 2001-2004, 2006, 2008-2013 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler.