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