1 %{/* Bison Grammar Parser -*- C -*-
2
3 Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
4
5 This file is part of Bison, the GNU Compiler Compiler.
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21 */
22
23 #include <config.h>
24 #include "system.h"
25
26 #include "complain.h"
27 #include "conflicts.h"
28 #include "files.h"
29 #include "getargs.h"
30 #include "gram.h"
31 #include "muscle_tab.h"
32 #include "quotearg.h"
33 #include "reader.h"
34 #include "symlist.h"
35 #include "strverscmp.h"
36
37 #define YYLLOC_DEFAULT(Current, Rhs, N) (Current) = lloc_default (Rhs, N)
38 static YYLTYPE lloc_default (YYLTYPE const *, int);
39
40 #define YY_LOCATION_PRINT(File, Loc) \
41 location_print (File, Loc)
42
43 static void version_check (location const *loc, char const *version);
44
45 /* Request detailed syntax error messages, and pass them to GRAM_ERROR.
46 FIXME: depends on the undocumented availability of YYLLOC. */
47 #undef yyerror
48 #define yyerror(Msg) \
49 gram_error (&yylloc, Msg)
50 static void gram_error (location const *, char const *);
51
52 static void add_param (char const *, char *, location);
53
54 static symbol_class current_class = unknown_sym;
55 static uniqstr current_type = 0;
56 static symbol *current_lhs;
57 static location current_lhs_location;
58 static int current_prec = 0;
59
60 #ifdef UINT_FAST8_MAX
61 # define YYTYPE_UINT8 uint_fast8_t
62 #endif
63 #ifdef INT_FAST8_MAX
64 # define YYTYPE_INT8 int_fast8_t
65 #endif
66 #ifdef UINT_FAST16_MAX
67 # define YYTYPE_UINT16 uint_fast16_t
68 #endif
69 #ifdef INT_FAST16_MAX
70 # define YYTYPE_INT16 int_fast16_t
71 #endif
72 %}
73
74 %debug
75 %verbose
76 %defines
77 %locations
78 %pure-parser
79 %error-verbose
80 %defines
81 %name-prefix="gram_"
82
83 %initial-action
84 {
85 /* Bison's grammar can initial empty locations, hence a default
86 location is needed. */
87 @$.start.file = @$.end.file = current_file;
88 @$.start.line = @$.end.line = 1;
89 @$.start.column = @$.end.column = 0;
90 }
91
92 /* Only NUMBERS have a value. */
93 %union
94 {
95 symbol *symbol;
96 symbol_list *list;
97 int integer;
98 char *chars;
99 assoc assoc;
100 uniqstr uniqstr;
101 };
102
103 /* Define the tokens together with their human representation. */
104 %token GRAM_EOF 0 "end of file"
105 %token STRING "string"
106 %token INT "integer"
107
108 %token PERCENT_TOKEN "%token"
109 %token PERCENT_NTERM "%nterm"
110
111 %token PERCENT_TYPE "%type"
112 %token PERCENT_DESTRUCTOR "%destructor {...}"
113 %token PERCENT_PRINTER "%printer {...}"
114
115 %token PERCENT_UNION "%union {...}"
116
117 %token PERCENT_LEFT "%left"
118 %token PERCENT_RIGHT "%right"
119 %token PERCENT_NONASSOC "%nonassoc"
120
121 %token PERCENT_PREC "%prec"
122 %token PERCENT_DPREC "%dprec"
123 %token PERCENT_MERGE "%merge"
124
125
126 /*----------------------.
127 | Global Declarations. |
128 `----------------------*/
129
130 %token
131 PERCENT_DEBUG "%debug"
132 PERCENT_DEFAULT_PREC "%default-prec"
133 PERCENT_DEFINE "%define"
134 PERCENT_DEFINES "%defines"
135 PERCENT_ERROR_VERBOSE "%error-verbose"
136 PERCENT_EXPECT "%expect"
137 PERCENT_EXPECT_RR "%expect-rr"
138 PERCENT_FILE_PREFIX "%file-prefix"
139 PERCENT_GLR_PARSER "%glr-parser"
140 PERCENT_INITIAL_ACTION "%initial-action {...}"
141 PERCENT_LEX_PARAM "%lex-param {...}"
142 PERCENT_LOCATIONS "%locations"
143 PERCENT_NAME_PREFIX "%name-prefix"
144 PERCENT_NO_DEFAULT_PREC "%no-default-prec"
145 PERCENT_NO_LINES "%no-lines"
146 PERCENT_NONDETERMINISTIC_PARSER
147 "%nondeterministic-parser"
148 PERCENT_OUTPUT "%output"
149 PERCENT_PARSE_PARAM "%parse-param {...}"
150 PERCENT_PURE_PARSER "%pure-parser"
151 PERCENT_REQUIRE "%require"
152 PERCENT_SKELETON "%skeleton"
153 PERCENT_START "%start"
154 PERCENT_TOKEN_TABLE "%token-table"
155 PERCENT_VERBOSE "%verbose"
156 PERCENT_YACC "%yacc"
157 ;
158
159 %token TYPE "type"
160 %token EQUAL "="
161 %token SEMICOLON ";"
162 %token PIPE "|"
163 %token ID "identifier"
164 %token ID_COLON "identifier:"
165 %token PERCENT_PERCENT "%%"
166 %token PROLOGUE "%{...%}"
167 %token EPILOGUE "epilogue"
168 %token BRACED_CODE "{...}"
169
170
171 %type <chars> STRING string_content
172 "%destructor {...}"
173 "%initial-action {...}"
174 "%lex-param {...}"
175 "%parse-param {...}"
176 "%printer {...}"
177 "%union {...}"
178 PROLOGUE EPILOGUE
179 %printer { fprintf (stderr, "\"%s\"", $$); }
180 STRING string_content
181 %printer { fprintf (stderr, "{\n%s\n}", $$); }
182 "%destructor {...}"
183 "%initial-action {...}"
184 "%lex-param {...}"
185 "%parse-param {...}"
186 "%printer {...}"
187 "%union {...}"
188 PROLOGUE EPILOGUE
189 %type <uniqstr> TYPE
190 %printer { fprintf (stderr, "<%s>", $$); } TYPE
191 %type <integer> INT
192 %printer { fprintf (stderr, "%d", $$); } INT
193 %type <symbol> ID symbol string_as_id
194 %printer { fprintf (stderr, "%s", $$->tag); } ID symbol string_as_id
195 %type <symbol> ID_COLON
196 %printer { fprintf (stderr, "%s:", $$->tag); } ID_COLON
197 %type <assoc> precedence_declarator
198 %type <list> symbols.1
199 %%
200
201 input:
202 declarations "%%" grammar epilogue.opt
203 ;
204
205
206 /*------------------------------------.
207 | Declarations: before the first %%. |
208 `------------------------------------*/
209
210 declarations:
211 /* Nothing */
212 | declarations declaration
213 ;
214
215 declaration:
216 grammar_declaration
217 | PROLOGUE { prologue_augment ($1, @1); }
218 | "%debug" { debug_flag = true; }
219 | "%define" string_content
220 {
221 static char one[] = "1";
222 muscle_insert ($2, one);
223 }
224 | "%define" string_content string_content { muscle_insert ($2, $3); }
225 | "%defines" { defines_flag = true; }
226 | "%error-verbose" { error_verbose = true; }
227 | "%expect" INT { expected_sr_conflicts = $2; }
228 | "%expect-rr" INT { expected_rr_conflicts = $2; }
229 | "%file-prefix" "=" string_content { spec_file_prefix = $3; }
230 | "%glr-parser"
231 {
232 nondeterministic_parser = true;
233 glr_parser = true;
234 }
235 | "%initial-action {...}"
236 {
237 muscle_code_grow ("initial_action", $1, @1);
238 }
239 | "%lex-param {...}" { add_param ("lex_param", $1, @1); }
240 | "%locations" { locations_flag = true; }
241 | "%name-prefix" "=" string_content { spec_name_prefix = $3; }
242 | "%no-lines" { no_lines_flag = true; }
243 | "%nondeterministic-parser" { nondeterministic_parser = true; }
244 | "%output" "=" string_content { spec_outfile = $3; }
245 | "%parse-param {...}" { add_param ("parse_param", $1, @1); }
246 | "%pure-parser" { pure_parser = true; }
247 | "%require" string_content { version_check (&@2, $2); }
248 | "%skeleton" string_content { skeleton = $2; }
249 | "%token-table" { token_table_flag = true; }
250 | "%verbose" { report_flag = report_states; }
251 | "%yacc" { yacc_flag = true; }
252 | /*FIXME: Err? What is this horror doing here? */ ";"
253 ;
254
255 grammar_declaration:
256 precedence_declaration
257 | symbol_declaration
258 | "%start" symbol
259 {
260 grammar_start_symbol_set ($2, @2);
261 }
262 | "%union {...}"
263 {
264 char const *body = $1;
265
266 if (typed)
267 {
268 /* Concatenate the union bodies, turning the first one's
269 trailing '}' into '\n', and omitting the second one's '{'. */
270 char *code = muscle_find ("stype");
271 code[strlen (code) - 1] = '\n';
272 body++;
273 }
274
275 typed = true;
276 muscle_code_grow ("stype", body, @1);
277 }
278 | "%destructor {...}" symbols.1
279 {
280 symbol_list *list;
281 for (list = $2; list; list = list->next)
282 symbol_destructor_set (list->sym, $1, @1);
283 symbol_list_free ($2);
284 }
285 | "%printer {...}" symbols.1
286 {
287 symbol_list *list;
288 for (list = $2; list; list = list->next)
289 symbol_printer_set (list->sym, $1, @1);
290 symbol_list_free ($2);
291 }
292 | "%default-prec"
293 {
294 default_prec = true;
295 }
296 | "%no-default-prec"
297 {
298 default_prec = false;
299 }
300 ;
301
302 symbol_declaration:
303 "%nterm" { current_class = nterm_sym; } symbol_defs.1
304 {
305 current_class = unknown_sym;
306 current_type = NULL;
307 }
308 | "%token" { current_class = token_sym; } symbol_defs.1
309 {
310 current_class = unknown_sym;
311 current_type = NULL;
312 }
313 | "%type" TYPE symbols.1
314 {
315 symbol_list *list;
316 for (list = $3; list; list = list->next)
317 symbol_type_set (list->sym, $2, @2);
318 symbol_list_free ($3);
319 }
320 ;
321
322 precedence_declaration:
323 precedence_declarator type.opt symbols.1
324 {
325 symbol_list *list;
326 ++current_prec;
327 for (list = $3; list; list = list->next)
328 {
329 symbol_type_set (list->sym, current_type, @2);
330 symbol_precedence_set (list->sym, current_prec, $1, @1);
331 }
332 symbol_list_free ($3);
333 current_type = NULL;
334 }
335 ;
336
337 precedence_declarator:
338 "%left" { $$ = left_assoc; }
339 | "%right" { $$ = right_assoc; }
340 | "%nonassoc" { $$ = non_assoc; }
341 ;
342
343 type.opt:
344 /* Nothing. */ { current_type = NULL; }
345 | TYPE { current_type = $1; }
346 ;
347
348 /* One or more nonterminals to be %typed. */
349
350 symbols.1:
351 symbol { $$ = symbol_list_new ($1, @1); }
352 | symbols.1 symbol { $$ = symbol_list_prepend ($1, $2, @2); }
353 ;
354
355 /* One token definition. */
356 symbol_def:
357 TYPE
358 {
359 current_type = $1;
360 }
361 | ID
362 {
363 symbol_class_set ($1, current_class, @1, true);
364 symbol_type_set ($1, current_type, @1);
365 }
366 | ID INT
367 {
368 symbol_class_set ($1, current_class, @1, true);
369 symbol_type_set ($1, current_type, @1);
370 symbol_user_token_number_set ($1, $2, @2);
371 }
372 | ID string_as_id
373 {
374 symbol_class_set ($1, current_class, @1, true);
375 symbol_type_set ($1, current_type, @1);
376 symbol_make_alias ($1, $2, @$);
377 }
378 | ID INT string_as_id
379 {
380 symbol_class_set ($1, current_class, @1, true);
381 symbol_type_set ($1, current_type, @1);
382 symbol_user_token_number_set ($1, $2, @2);
383 symbol_make_alias ($1, $3, @$);
384 }
385 ;
386
387 /* One or more symbol definitions. */
388 symbol_defs.1:
389 symbol_def
390 | symbol_defs.1 symbol_def
391 ;
392
393
394 /*------------------------------------------.
395 | The grammar section: between the two %%. |
396 `------------------------------------------*/
397
398 grammar:
399 rules_or_grammar_declaration
400 | grammar rules_or_grammar_declaration
401 ;
402
403 /* As a Bison extension, one can use the grammar declarations in the
404 body of the grammar. */
405 rules_or_grammar_declaration:
406 rules
407 | grammar_declaration ";"
408 | error ";"
409 {
410 yyerrok;
411 }
412 ;
413
414 rules:
415 ID_COLON { current_lhs = $1; current_lhs_location = @1; } rhses.1
416 ;
417
418 rhses.1:
419 rhs { grammar_current_rule_end (@1); }
420 | rhses.1 "|" rhs { grammar_current_rule_end (@3); }
421 | rhses.1 ";"
422 ;
423
424 rhs:
425 /* Nothing. */
426 { grammar_current_rule_begin (current_lhs, current_lhs_location); }
427 | rhs symbol
428 { grammar_current_rule_symbol_append ($2, @2); }
429 | rhs action
430 | rhs "%prec" symbol
431 { grammar_current_rule_prec_set ($3, @3); }
432 | rhs "%dprec" INT
433 { grammar_current_rule_dprec_set ($3, @3); }
434 | rhs "%merge" TYPE
435 { grammar_current_rule_merge_set ($3, @3); }
436 ;
437
438 symbol:
439 ID { $$ = $1; }
440 | string_as_id { $$ = $1; }
441 ;
442
443 /* Handle the semantics of an action specially, with a mid-rule
444 action, so that grammar_current_rule_action_append is invoked
445 immediately after the braced code is read by the scanner.
446
447 This implementation relies on the LALR(1) parsing algorithm.
448 If grammar_current_rule_action_append were executed in a normal
449 action for this rule, then when the input grammar contains two
450 successive actions, the scanner would have to read both actions
451 before reducing this rule. That wouldn't work, since the scanner
452 relies on all preceding input actions being processed by
453 grammar_current_rule_action_append before it scans the next
454 action. */
455 action:
456 { grammar_current_rule_action_append (last_string, last_braced_code_loc); }
457 BRACED_CODE
458 ;
459
460 /* A string used as an ID: quote it. */
461 string_as_id:
462 STRING
463 {
464 $$ = symbol_get (quotearg_style (c_quoting_style, $1), @1);
465 symbol_class_set ($$, token_sym, @1, false);
466 }
467 ;
468
469 /* A string used for its contents. Don't quote it. */
470 string_content:
471 STRING
472 { $$ = $1; }
473 ;
474
475
476 epilogue.opt:
477 /* Nothing. */
478 | "%%" EPILOGUE
479 {
480 muscle_code_grow ("epilogue", $2, @2);
481 scanner_last_string_free ();
482 }
483 ;
484
485 %%
486
487
488 /* Return the location of the left-hand side of a rule whose
489 right-hand side is RHS[1] ... RHS[N]. Ignore empty nonterminals in
490 the right-hand side, and return an empty location equal to the end
491 boundary of RHS[0] if the right-hand side is empty. */
492
493 static YYLTYPE
494 lloc_default (YYLTYPE const *rhs, int n)
495 {
496 int i;
497 YYLTYPE loc;
498
499 /* SGI MIPSpro 7.4.1m miscompiles "loc.start = loc.end = rhs[n].end;".
500 The bug is fixed in 7.4.2m, but play it safe for now. */
501 loc.start = rhs[n].end;
502 loc.end = rhs[n].end;
503
504 /* Ignore empty nonterminals the start of the the right-hand side.
505 Do not bother to ignore them at the end of the right-hand side,
506 since empty nonterminals have the same end as their predecessors. */
507 for (i = 1; i <= n; i++)
508 if (! equal_boundaries (rhs[i].start, rhs[i].end))
509 {
510 loc.start = rhs[i].start;
511 break;
512 }
513
514 return loc;
515 }
516
517
518 /* Add a lex-param or a parse-param (depending on TYPE) with
519 declaration DECL and location LOC. */
520
521 static void
add_param(char const * type,char * decl,location loc)522 add_param (char const *type, char *decl, location loc)
523 {
524 static char const alphanum[26 + 26 + 1 + 10] =
525 "abcdefghijklmnopqrstuvwxyz"
526 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
527 "_"
528 "0123456789";
529 char const *name_start = NULL;
530 char *p;
531
532 /* Stop on last actual character. */
533 for (p = decl; p[1]; p++)
534 if ((p == decl
535 || ! memchr (alphanum, p[-1], sizeof alphanum))
536 && memchr (alphanum, p[0], sizeof alphanum - 10))
537 name_start = p;
538
539 /* Strip the surrounding '{' and '}', and any blanks just inside
540 the braces. */
541 while (*--p == ' ' || *p == '\t')
542 continue;
543 p[1] = '\0';
544 while (*++decl == ' ' || *decl == '\t')
545 continue;
546
547 if (! name_start)
548 complain_at (loc, _("missing identifier in parameter declaration"));
549 else
550 {
551 char *name;
552 size_t name_len;
553
554 for (name_len = 1;
555 memchr (alphanum, name_start[name_len], sizeof alphanum);
556 name_len++)
557 continue;
558
559 name = xmalloc (name_len + 1);
560 memcpy (name, name_start, name_len);
561 name[name_len] = '\0';
562 muscle_pair_list_grow (type, decl, name);
563 free (name);
564 }
565
566 scanner_last_string_free ();
567 }
568
569 static void
version_check(location const * loc,char const * version)570 version_check (location const *loc, char const *version)
571 {
572 if (strverscmp (version, PACKAGE_VERSION) > 0)
573 {
574 complain_at (*loc, "require bison %s, but have %s",
575 version, PACKAGE_VERSION);
576 exit (63);
577 }
578 }
579
580 static void
gram_error(location const * loc,char const * msg)581 gram_error (location const *loc, char const *msg)
582 {
583 complain_at (*loc, "%s", msg);
584 }
585
586 char const *
token_name(int type)587 token_name (int type)
588 {
589 return yytname[YYTRANSLATE (type)];
590 }
591