]> git.saurik.com Git - bison.git/blame_incremental - TODO
tests: please clang and use ".cc", not ".c", for C++ input
[bison.git] / TODO
... / ...
CommitLineData
1* Short term
2** Graphviz display code thoughts
3The code for the --graph option is over two files: print_graph, and
4graphviz. I believe this is because Bison used to also produce VCG graphs,
5but since this is no longer true, maybe we could consider these files for
6fusion.
7
8Little effort factoring seems to have been given to factoring in these files,
9and their print-xml and print counterpart. We would very much like to re-use
10the pretty format of states from .output in the .dot
11
12Also, the underscore in print_graph.[ch] isn't very fitting considering
13the dashes in the other filenames.
14
15** push-parser
16Check it too when checking the different kinds of parsers. And be
17sure to check that the initial-action is performed once per parsing.
18
19** m4 names
20b4_shared_declarations is no longer what it is. Make it
21b4_parser_declaration for instance.
22
23** yychar in lalr1.cc
24There is a large difference bw maint and master on the handling of
25yychar (which was removed in lalr1.cc). See what needs to be
26back-ported.
27
28
29 /* User semantic actions sometimes alter yychar, and that requires
30 that yytoken be updated with the new translation. We take the
31 approach of translating immediately before every use of yytoken.
32 One alternative is translating here after every semantic action,
33 but that translation would be missed if the semantic action
34 invokes YYABORT, YYACCEPT, or YYERROR immediately after altering
35 yychar. In the case of YYABORT or YYACCEPT, an incorrect
36 destructor might then be invoked immediately. In the case of
37 YYERROR, subsequent parser actions might lead to an incorrect
38 destructor call or verbose syntax error message before the
39 lookahead is translated. */
40
41 /* Make sure we have latest lookahead translation. See comments at
42 user semantic actions for why this is necessary. */
43 yytoken = yytranslate_ (yychar);
44
45
46** stack.hh
47Get rid of it. The original idea is nice, but actually it makes
48the code harder to follow, and uselessly different from the other
49skeletons.
50
51** Variable names.
52What should we name `variant' and `lex_symbol'?
53
54** Get rid of fake #lines [Bison: ...]
55Possibly as simple as checking whether the column number is nonnegative.
56
57I have seen messages like the following from GCC.
58
59<built-in>:0: fatal error: opening dependency file .deps/libltdl/argz.Tpo: No such file or directory
60
61
62** Discuss about %printer/%destroy in the case of C++.
63It would be very nice to provide the symbol classes with an operator<<
64and a destructor. Unfortunately the syntax we have chosen for
65%destroy and %printer make them hard to reuse. For instance, the user
66is invited to write something like
67
68 %printer { debug_stream() << $$; } <my_type>;
69
70which is hard to reuse elsewhere since it wants to use
71"debug_stream()" to find the stream to use. The same applies to
72%destroy: we told the user she could use the members of the Parser
73class in the printers/destructors, which is not good for an operator<<
74since it is no longer bound to a particular parser, it's just a
75(standalone symbol).
76
77** Rename LR0.cc
78as lr0.cc, why upper case?
79
80** bench several bisons.
81Enhance bench.pl with %b to run different bisons.
82
83* Various
84** YYERRCODE
85Defined to 256, but not used, not documented. Probably the token
86number for the error token, which POSIX wants to be 256, but which
87Bison might renumber if the user used number 256. Keep fix and doc?
88Throw away?
89
90Also, why don't we output the token name of the error token in the
91output? It is explicitly skipped:
92
93 /* Skip error token and tokens without identifier. */
94 if (sym != errtoken && id)
95
96Of course there are issues with name spaces, but if we disable we have
97something which seems to be more simpler and more consistent instead
98of the special case YYERRCODE.
99
100 enum yytokentype {
101 error = 256,
102 // ...
103 };
104
105
106We could (should?) also treat the case of the undef_token, which is
107numbered 257 for yylex, and 2 internal. Both appear for instance in
108toknum:
109
110 const unsigned short int
111 parser::yytoken_number_[] =
112 {
113 0, 256, 257, 258, 259, 260, 261, 262, 263, 264,
114
115while here
116
117 enum yytokentype {
118 TOK_EOF = 0,
119 TOK_EQ = 258,
120
121so both 256 and 257 are "mysterious".
122
123 const char*
124 const parser::yytname_[] =
125 {
126 "\"end of command\"", "error", "$undefined", "\"=\"", "\"break\"",
127
128
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.
145
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
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
159** yysyntax_error
160The code bw glr.c and yacc.c is really alike, we can certainly factor
161some parts.
162
163
164* Report
165
166** Figures
167Some statistics about the grammar and the parser would be useful,
168especially when asking the user to send some information about the
169grammars she is working on. We should probably also include some
170information about the variables (I'm not sure for instance we even
171specify what LR variant was used).
172
173** GLR
174How would Paul like to display the conflicted actions? In particular,
175what when two reductions are possible on a given lookahead token, but one is
176part of $default. Should we make the two reductions explicit, or just
177keep $default? See the following point.
178
179** Disabled Reductions
180See `tests/conflicts.at (Defaulted Conflicted Reduction)', and decide
181what we want to do.
182
183** Documentation
184Extend with error productions. The hard part will probably be finding
185the right rule so that a single state does not exhibit too many yet
186undocumented ``features''. Maybe an empty action ought to be
187presented too. Shall we try to make a single grammar with all these
188features, or should we have several very small grammars?
189
190** --report=conflict-path
191Provide better assistance for understanding the conflicts by providing
192a sample text exhibiting the (LALR) ambiguity. See the paper from
193DeRemer and Penello: they already provide the algorithm.
194
195** Statically check for potential ambiguities in GLR grammars. See
196<http://www.i3s.unice.fr/~schmitz/papers.html#expamb> for an approach.
197
198
199* Extensions
200
201** $-1
202We should find a means to provide an access to values deep in the
203stack. For instance, instead of
204
205 baz: qux { $$ = $<foo>-1 + $<bar>0 + $1; }
206
207we should be able to have:
208
209 foo($foo) bar($bar) baz($bar): qux($qux) { $baz = $foo + $bar + $qux; }
210
211Or something like this.
212
213** %if and the like
214It should be possible to have %if/%else/%endif. The implementation is
215not clear: should it be lexical or syntactic. Vadim Maslow thinks it
216must be in the scanner: we must not parse what is in a switched off
217part of %if. Akim Demaille thinks it should be in the parser, so as
218to avoid falling into another CPP mistake.
219
220** XML Output
221There are couple of available extensions of Bison targeting some XML
222output. Some day we should consider including them. One issue is
223that they seem to be quite orthogonal to the parsing technique, and
224seem to depend mostly on the possibility to have some code triggered
225for each reduction. As a matter of fact, such hooks could also be
226used to generate the yydebug traces. Some generic scheme probably
227exists in there.
228
229XML output for GNU Bison and gcc
230 http://www.cs.may.ie/~jpower/Research/bisonXML/
231
232XML output for GNU Bison
233 http://yaxx.sourceforge.net/
234
235* Unit rules
236Maybe we could expand unit rules, i.e., transform
237
238 exp: arith | bool;
239 arith: exp '+' exp;
240 bool: exp '&' exp;
241
242into
243
244 exp: exp '+' exp | exp '&' exp;
245
246when there are no actions. This can significantly speed up some
247grammars. I can't find the papers. In particular the book `LR
248parsing: Theory and Practice' is impossible to find, but according to
249`Parsing Techniques: a Practical Guide', it includes information about
250this issue. Does anybody have it?
251
252
253
254* Documentation
255
256** History/Bibliography
257Some history of Bison and some bibliography would be most welcome.
258Are there any Texinfo standards for bibliography?
259
260* Coding system independence
261Paul notes:
262
263 Currently Bison assumes 8-bit bytes (i.e. that UCHAR_MAX is
264 255). It also assumes that the 8-bit character encoding is
265 the same for the invocation of 'bison' as it is for the
266 invocation of 'cc', but this is not necessarily true when
267 people run bison on an ASCII host and then use cc on an EBCDIC
268 host. I don't think these topics are worth our time
269 addressing (unless we find a gung-ho volunteer for EBCDIC or
270 PDP-10 ports :-) but they should probably be documented
271 somewhere.
272
273 More importantly, Bison does not currently allow NUL bytes in
274 tokens, either via escapes (e.g., "x\0y") or via a NUL byte in
275 the source code. This should get fixed.
276
277* --graph
278Show reductions.
279
280* Broken options ?
281** %token-table
282** Skeleton strategy
283Must we keep %token-table?
284
285* Precedence
286
287** Partial order
288It is unfortunate that there is a total order for precedence. It
289makes it impossible to have modular precedence information. We should
290move to partial orders (sounds like series/parallel orders to me).
291
292** RR conflicts
293See if we can use precedence between rules to solve RR conflicts. See
294what POSIX says.
295
296
297* $undefined
298From Hans:
299- If the Bison generated parser experiences an undefined number in the
300character range, that character is written out in diagnostic messages, an
301addition to the $undefined value.
302
303Suggest: Change the name $undefined to undefined; looks better in outputs.
304
305
306* Default Action
307From Hans:
308- For use with my C++ parser, I transported the "switch (yyn)" statement
309that Bison writes to the bison.simple skeleton file. This way, I can remove
310the current default rule $$ = $1 implementation, which causes a double
311assignment to $$ which may not be OK under C++, replacing it with a
312"default:" part within the switch statement.
313
314Note that the default rule $$ = $1, when typed, is perfectly OK under C,
315but in the C++ implementation I made, this rule is different from
316$<type_name>$ = $<type_name>1. I therefore think that one should implement
317a Bison option where every typed default rule is explicitly written out
318(same typed ruled can of course be grouped together).
319
320* Pre and post actions.
321From: Florian Krohm <florian@edamail.fishkill.ibm.com>
322Subject: YYACT_EPILOGUE
323To: bug-bison@gnu.org
324X-Sent: 1 week, 4 days, 14 hours, 38 minutes, 11 seconds ago
325
326The other day I had the need for explicitly building the parse tree. I
327used %locations for that and defined YYLLOC_DEFAULT to call a function
328that returns the tree node for the production. Easy. But I also needed
329to assign the S-attribute to the tree node. That cannot be done in
330YYLLOC_DEFAULT, because it is invoked before the action is executed.
331The way I solved this was to define a macro YYACT_EPILOGUE that would
332be invoked after the action. For reasons of symmetry I also added
333YYACT_PROLOGUE. Although I had no use for that I can envision how it
334might come in handy for debugging purposes.
335All is needed is to add
336
337#if YYLSP_NEEDED
338 YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen, yyloc, (yylsp - yylen));
339#else
340 YYACT_EPILOGUE (yyval, (yyvsp - yylen), yylen);
341#endif
342
343at the proper place to bison.simple. Ditto for YYACT_PROLOGUE.
344
345I was wondering what you think about adding YYACT_PROLOGUE/EPILOGUE
346to bison. If you're interested, I'll work on a patch.
347
348* Better graphics
349Equip the parser with a means to create the (visual) parse tree.
350
351* Complaint submessage indentation.
352We already have an implementation that works fairly well for named
353reference messages, but it would be nice to use it consistently for all
354submessages from Bison. For example, the "previous definition"
355submessage or the list of correct values for a %define variable might
356look better with indentation.
357
358However, the current implementation makes the assumption that the
359location printed on the first line is not usually much shorter than the
360locations printed on the submessage lines that follow. That assumption
361may not hold true as often for some kinds of submessages especially if
362we ever support multiple grammar files.
363
364Here's a proposal for how a new implementation might look:
365
366 http://lists.gnu.org/archive/html/bison-patches/2009-09/msg00086.html
367
368
369Local Variables:
370mode: outline
371coding: utf-8
372End:
373
374-----
375
376Copyright (C) 2001-2004, 2006, 2008-2013 Free Software Foundation, Inc.
377
378This file is part of Bison, the GNU Compiler Compiler.
379
380This program is free software: you can redistribute it and/or modify
381it under the terms of the GNU General Public License as published by
382the Free Software Foundation, either version 3 of the License, or
383(at your option) any later version.
384
385This program is distributed in the hope that it will be useful,
386but WITHOUT ANY WARRANTY; without even the implied warranty of
387MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
388GNU General Public License for more details.
389
390You should have received a copy of the GNU General Public License
391along with this program. If not, see <http://www.gnu.org/licenses/>.