]> git.saurik.com Git - bison.git/blame - TODO
Regen.
[bison.git] / TODO
CommitLineData
416bd7a9
MA
1-*- outline -*-
2
dd704c35 3* Short term
1e034807
AD
4** Use b4_symbol in all the skeleton
5Then remove the older system, including the tables generated by
6output.c
7
8** Update the documentation on gnu.org
9
10** Get rid of fake #lines [Bison: ...]
11Possibly as simple as checking whether the column number is nonnegative.
12
13I have seen messages like the following from GCC.
14
15<built-in>:0: fatal error: opening dependency file .deps/libltdl/argz.Tpo: No such file or directory
16
17
dd704c35
AD
18** Document %define assert
19
20** Discuss about %printer/%destroy in the case of C++.
21It would be very nice to provide the symbol classes with an operator<<
22and a destructor. Unfortunately the syntax we have chosen for
23%destroy and %printer make them hard to reuse. For instance, the user
24is invited to write something like
25
26 %printer { debug_stream() << $$; } <my_type>;
27
28which is hard to reuse elsewhere since it wants to use
29"debug_stream()" to find the stream to use. The same applies to
30%destroy: we told the user she could use the members of the Parser
31class in the printers/destructors, which is not good for an operator<<
32since it is no longer bound to a particular parser, it's just a
33(standalone symbol).
34
35** Rename LR0.cc
36as lr0.cc, why upper case?
37
38** bench several bisons.
39Enhance bench.pl with %b to run different bisons.
40
41** Use b4_symbol everywhere.
42Move its definition in the more standard places and deploy it in other
43skeletons.
44
42f832d6 45* Various
865f1e9f
AD
46** YYPRINT
47glr.c inherits its symbol_print function from c.m4, which supports
48YYPRINT. But to use YYPRINT yytoknum is needed, which not defined by
49glr.c.
50
51Anyway, IMHO YYPRINT is obsolete and should be restricted to yacc.c.
52
42f832d6
AD
53** YYERRCODE
54Defined to 256, but not used, not documented. Probably the token
55number for the error token, which POSIX wants to be 256, but which
56Bison might renumber if the user used number 256. Keep fix and doc?
57Throw away?
58
fc2476c7
AD
59We could (should?) also treat the case of the undef_token, which is
60numbered 257 for yylex, and 2 internal. Both appear for instance in
61toknum:
62
63 const unsigned short int
64 parser::yytoken_number_[] =
65 {
66 0, 256, 257, 258, 259, 260, 261, 262, 263, 264,
67
68while here
69
70 enum yytokentype {
71 TOK_EOF = 0,
72 TOK_EQ = 258,
73
74so both 256 and 257 are "mysterious".
75
76 const char*
77 const parser::yytname_[] =
78 {
79 "\"end of command\"", "error", "$undefined", "\"=\"", "\"break\"",
80
81
42f832d6
AD
82** YYFAIL
83It is seems to be *really* obsolete now, shall we remove it?
84
85** YYBACKUP
86There is no test about it, no examples in the doc, and I'm not sure
87what it should look like. For instance what follows crashes.
88
89 %error-verbose
90 %debug
91 %pure-parser
92 %code {
93 # include <stdio.h>
94 # include <stdlib.h>
95 # include <assert.h>
96
97 static void yyerror (const char *msg);
98 static int yylex (YYSTYPE *yylval);
99 }
100 %%
101 exp:
102 'a' { printf ("a: %d\n", $1); }
103 | 'b' { YYBACKUP('a', 123); }
104 ;
105 %%
106 static int
107 yylex (YYSTYPE *yylval)
108 {
109 static char const input[] = "b";
110 static size_t toknum;
111 assert (toknum < sizeof input);
112 *yylval = (toknum + 1) * 10;
113 return input[toknum++];
114 }
115
116 static void
117 yyerror (const char *msg)
118 {
119 fprintf (stderr, "%s\n", msg);
120 }
121
122 int
123 main (void)
124 {
125 yydebug = !!getenv("YYDEBUG");
126 return yyparse ();
127 }
128
27cb5b59
AD
129** yychar == yyempty_
130The code in yyerrlab reads:
131
132 if (yychar <= YYEOF)
133 {
134 /* Return failure if at end of input. */
135 if (yychar == YYEOF)
136 YYABORT;
137 }
138
139There are only two yychar that can be <= YYEOF: YYEMPTY and YYEOF.
140But I can't produce the situation where yychar is YYEMPTY here, is it
141really possible? The test suite does not exercise this case.
142
143This shows that it would be interesting to manage to install skeleton
144coverage analysis to the test suite.
42f832d6 145
a2e3fa77
AD
146** Table definitions
147It should be very easy to factor the definition of the various tables,
148including the separation bw declaration and definition. See for
149instance b4_table_define in lalr1.cc. This way, we could even factor
150C vs. C++ definitions.
151
00a8a083
AD
152* From lalr1.cc to yacc.c
153** Single stack
154Merging the three stacks in lalr1.cc simplified the code, prompted for
155other improvements and also made it faster (probably because memory
156management is performed once instead of three times). I suggest that
157we do the same in yacc.c.
158
dada3cd1 159** yysyntax_error
2b008529
AD
160The code bw glr.c and yacc.c is really alike, we can certainly factor
161some parts.
dada3cd1 162
3c146b5e
AD
163* Header guards
164
32f0598d 165From Franc,ois: should we keep the directory part in the CPP guard?
3c146b5e
AD
166
167
c19988b7
AD
168* Yacc.c: CPP Macros
169
170Do some people use YYPURE, YYLSP_NEEDED like we do in the test suite?
171They should not: it is not documented. But if they need to, let's
172find something clean (not like YYLSP_NEEDED...).
173
174
5d278082
PE
175* Installation
176
88bce5a2 177* Documentation
959e5f51
AD
178Before releasing, make sure the documentation ("Understanding your
179parser") refers to the current `output' format.
88bce5a2 180
2ab9a04f 181* Report
ec3bc396 182
2ab9a04f
AD
183** GLR
184How would Paul like to display the conflicted actions? In particular,
742e4900 185what when two reductions are possible on a given lookahead token, but one is
2ab9a04f
AD
186part of $default. Should we make the two reductions explicit, or just
187keep $default? See the following point.
d7215705 188
2ab9a04f
AD
189** Disabled Reductions
190See `tests/conflicts.at (Defaulted Conflicted Reduction)', and decide
191what we want to do.
d7215705 192
2ab9a04f 193** Documentation
bc933ef1
AD
194Extend with error productions. The hard part will probably be finding
195the right rule so that a single state does not exhibit too many yet
196undocumented ``features''. Maybe an empty action ought to be
197presented too. Shall we try to make a single grammar with all these
198features, or should we have several very small grammars?
ec3bc396 199
2ab9a04f
AD
200** --report=conflict-path
201Provide better assistance for understanding the conflicts by providing
202a sample text exhibiting the (LALR) ambiguity. See the paper from
203DeRemer and Penello: they already provide the algorithm.
204
38eb7751
PE
205** Statically check for potential ambiguities in GLR grammars. See
206<http://www.i3s.unice.fr/~schmitz/papers.html#expamb> for an approach.
207
ec3bc396 208
948be909 209* Extensions
2ab9a04f 210
d2aaf69e 211** Labeling the symbols
959e5f51
AD
212Have a look at the Lemon parser generator: instead of $1, $2 etc. they
213can name the values. This is much more pleasant. For instance:
214
215 exp (res): exp (a) '+' exp (b) { $res = $a + $b; };
216
217I love this. I have been bitten too often by the removal of the
218symbol, and forgetting to shift all the $n to $n-1. If you are
219unlucky, it compiles...
220
d2aaf69e
AD
221But instead of using $a etc., we can use regular variables. And
222instead of using (), I propose to use `:' (again). Paul suggests
223supporting `->' in addition to `:' to separate LHS and RHS. In other
224words:
225
226 r:exp -> a:exp '+' b:exp { r = a + b; };
227
228That requires an significant improvement of the grammar parser. Using
229GLR would be nice. It also requires that Bison know the type of the
230symbols (which will be useful for %include anyway). So we have some
231time before...
232
233Note that there remains the problem of locations: `@r'?
234
235
959e5f51
AD
236** $-1
237We should find a means to provide an access to values deep in the
238stack. For instance, instead of
239
240 baz: qux { $$ = $<foo>-1 + $<bar>0 + $1; }
241
242we should be able to have:
243
244 foo($foo) bar($bar) baz($bar): qux($qux) { $baz = $foo + $bar + $qux; }
245
246Or something like this.
247
f0e48240
AD
248** %if and the like
249It should be possible to have %if/%else/%endif. The implementation is
250not clear: should it be lexical or syntactic. Vadim Maslow thinks it
251must be in the scanner: we must not parse what is in a switched off
252part of %if. Akim Demaille thinks it should be in the parser, so as
253to avoid falling into another CPP mistake.
254
ca752c34
AD
255** XML Output
256There are couple of available extensions of Bison targeting some XML
257output. Some day we should consider including them. One issue is
258that they seem to be quite orthogonal to the parsing technique, and
259seem to depend mostly on the possibility to have some code triggered
260for each reduction. As a matter of fact, such hooks could also be
261used to generate the yydebug traces. Some generic scheme probably
262exists in there.
263
264XML output for GNU Bison and gcc
265 http://www.cs.may.ie/~jpower/Research/bisonXML/
266
267XML output for GNU Bison
268 http://yaxx.sourceforge.net/
f0e48240 269
fa770c86
AD
270* Unit rules
271Maybe we could expand unit rules, i.e., transform
272
273 exp: arith | bool;
274 arith: exp '+' exp;
275 bool: exp '&' exp;
276
277into
278
279 exp: exp '+' exp | exp '&' exp;
280
281when there are no actions. This can significantly speed up some
d7215705
AD
282grammars. I can't find the papers. In particular the book `LR
283parsing: Theory and Practice' is impossible to find, but according to
284`Parsing Techniques: a Practical Guide', it includes information about
285this issue. Does anybody have it?
fa770c86 286
51dec47b 287
51dec47b 288
2ab9a04f 289* Documentation
51dec47b 290
2ab9a04f
AD
291** History/Bibliography
292Some history of Bison and some bibliography would be most welcome.
293Are there any Texinfo standards for bibliography?
294
295
296
948be909
PE
297* Java, Fortran, etc.
298
948be909 299
2ab9a04f
AD
300* Coding system independence
301Paul notes:
302
303 Currently Bison assumes 8-bit bytes (i.e. that UCHAR_MAX is
304 255). It also assumes that the 8-bit character encoding is
305 the same for the invocation of 'bison' as it is for the
306 invocation of 'cc', but this is not necessarily true when
307 people run bison on an ASCII host and then use cc on an EBCDIC
308 host. I don't think these topics are worth our time
309 addressing (unless we find a gung-ho volunteer for EBCDIC or
310 PDP-10 ports :-) but they should probably be documented
311 somewhere.
fa770c86 312
d521d95a
PE
313 More importantly, Bison does not currently allow NUL bytes in
314 tokens, either via escapes (e.g., "x\0y") or via a NUL byte in
315 the source code. This should get fixed.
aef1ffd5 316
bcb05e75 317* --graph
45567173 318Show reductions.
bcb05e75 319
704a47c4 320* Broken options ?
45567173
AD
321** %token-table
322** Skeleton strategy
728c4be2 323Must we keep %token-table?
416bd7a9 324
0e95c1dd 325* BTYacc
f0e48240 326See if we can integrate backtracking in Bison. Charles-Henri de
df72984a
AD
327Boysson <de-boy_c@epita.fr> has been working on this, but never gave
328the results.
329
330Vadim Maslow, the maintainer of BTYacc was once contacted. Adjusting
331the Bison grammar parser will be needed to support some extra BTYacc
332features. This is less urgent.
0e95c1dd 333
2ab9a04f
AD
334** Keeping the conflicted actions
335First, analyze the differences between byacc and btyacc (I'm referring
336to the executables). Find where the conflicts are preserved.
337
338** Compare with the GLR tables
948be909 339See how isomorphic the way BTYacc and the way the GLR adjustments in
2ab9a04f
AD
340Bison are compatible. *As much as possible* one should try to use the
341same implementation in the Bison executables. I insist: it should be
342very feasible to use the very same conflict tables.
343
344** Adjust the skeletons
345Import the skeletons for C and C++.
346
0e95c1dd
AD
347
348* Precedence
2ab9a04f
AD
349
350** Partial order
0e95c1dd
AD
351It is unfortunate that there is a total order for precedence. It
352makes it impossible to have modular precedence information. We should
2ab9a04f 353move to partial orders (sounds like series/parallel orders to me).
0e95c1dd 354
2ab9a04f
AD
355** RR conflicts
356See if we can use precedence between rules to solve RR conflicts. See
357what POSIX says.
358
359
69991a58
AD
360* $undefined
361From Hans:
362- If the Bison generated parser experiences an undefined number in the
363character range, that character is written out in diagnostic messages, an
364addition to the $undefined value.
365
366Suggest: Change the name $undefined to undefined; looks better in outputs.
367
2ab9a04f 368
69991a58
AD
369* Default Action
370From Hans:
371- For use with my C++ parser, I transported the "switch (yyn)" statement
372that Bison writes to the bison.simple skeleton file. This way, I can remove
373the current default rule $$ = $1 implementation, which causes a double
374assignment to $$ which may not be OK under C++, replacing it with a
375"default:" part within the switch statement.
376
377Note that the default rule $$ = $1, when typed, is perfectly OK under C,
378but in the C++ implementation I made, this rule is different from
379$<type_name>$ = $<type_name>1. I therefore think that one should implement
380a Bison option where every typed default rule is explicitly written out
381(same typed ruled can of course be grouped together).
382
383* Pre and post actions.
384From: Florian Krohm <florian@edamail.fishkill.ibm.com>
385Subject: YYACT_EPILOGUE
386To: bug-bison@gnu.org
387X-Sent: 1 week, 4 days, 14 hours, 38 minutes, 11 seconds ago
388
389The other day I had the need for explicitly building the parse tree. I
390used %locations for that and defined YYLLOC_DEFAULT to call a function
391that returns the tree node for the production. Easy. But I also needed
392to assign the S-attribute to the tree node. That cannot be done in
393YYLLOC_DEFAULT, because it is invoked before the action is executed.
394The way I solved this was to define a macro YYACT_EPILOGUE that would
395be invoked after the action. For reasons of symmetry I also added
396YYACT_PROLOGUE. Although I had no use for that I can envision how it
397might come in handy for debugging purposes.
76551463 398All is needed is to add
69991a58
AD
399
400#if YYLSP_NEEDED
401 YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen, yyloc, (yylsp - yylen));
402#else
403 YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen);
404#endif
405
406at the proper place to bison.simple. Ditto for YYACT_PROLOGUE.
407
408I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
409to bison. If you're interested, I'll work on a patch.
410
35fe0834
PE
411* Better graphics
412Equip the parser with a means to create the (visual) parse tree.
d7215705 413
f294a2c2
AD
414-----
415
df72984a 416Copyright (C) 2001, 2002, 2003, 2004, 2006, 2008 Free Software Foundation,
51cbef6f 417Inc.
f294a2c2 418
51cbef6f 419This file is part of Bison, the GNU Compiler Compiler.
f294a2c2 420
f16b0819 421This program is free software: you can redistribute it and/or modify
f294a2c2 422it under the terms of the GNU General Public License as published by
f16b0819
PE
423the Free Software Foundation, either version 3 of the License, or
424(at your option) any later version.
f294a2c2 425
f16b0819 426This program is distributed in the hope that it will be useful,
f294a2c2
AD
427but WITHOUT ANY WARRANTY; without even the implied warranty of
428MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
429GNU General Public License for more details.
430
431You should have received a copy of the GNU General Public License
f16b0819 432along with this program. If not, see <http://www.gnu.org/licenses/>.