[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Mega patch for GLR parsing
|
From: |
Paul Hilfinger |
|
Subject: |
Mega patch for GLR parsing |
|
Date: |
Thu, 27 Jun 2002 19:43:14 -0700 |
I have just checked in a bunch of changes implementing an experimental
GLR parsing feature in Bison. There are still numerous rough edges
for those of you looking for something to do with your copious spare
time.
Paul Hilfinger
ChangeLog:
2002-06-27 Paul Hilfinger <address@hidden>
Accumulated changelog for new GLR parsing features.
* src/conflicts.c (count_total_conflicts): Change name to
conflicts_total_count.
* src/conflicts.h: Ditto.
* src/output.c (token_actions): Use the new name.
(output_conflicts): Change conflp => conflict_list_heads, and
confl => conflict_list for better readability.
* data/glr.c: Use the new names.
* NEWS: Add self to GLR announcement.
* src/reader.c (free_merger_functions): Cleanup: XFREE->free.
* doc/bison.texinfo (GLR Parsers): Make corrections suggested by
Akim Demaille.
* data/bison.glr: Change name to glr.c
* data/glr.c: Renamed from bison.glr.
* data/Makefile.am: Add glr.c
* src/getargs.c:
* src/symlist.h: Add dprec and merger fields to symbol_list_s.
* src/symlist.c (symbol_list_new): Initialize dprec and merger fields.
Originally 2002-06-16 Paul Hilfinger <address@hidden>
* data/bison.glr: Be sure to restore the
current #line when returning to the skeleton contents after having
exposed the input file's #line.
Originally 2002-06-13 Paul Hilfinger <address@hidden>
* data/bison.glr: Bring up to date with changes to bison.simple.
Originally 2002-06-03 Paul Hilfinger <address@hidden>
* data/bison.glr: Correct definitions that use b4_prefix.
Various reformatting.
(GLRStack): Make yychar (in YYPURE case) and yytokenp as part of stack.
(yyreportParseError, yyrecoverParseError, yyprocessOneStack): remove
yytokenp argument; now part of stack.
(yychar): Define to behave as documented.
(yyclearin): Ditto.
Originally 2002-05-14 Paul Hilfinger <address@hidden>
* src/reader.h: Add declaration for free_merger_functions.
* src/reader.c (merge_functions): New variable.
(get_merge_function): New function.
(free_merger_functions): New function.
(readgram): Check for %prec that is not followed by a symbol.
Handle %dprec and %merge declarations.
(packgram): Initialize dprec and merger fields in rules array.
* src/output.c (conflict_tos, conflrow, conflict_table, conflict_list,
conflict_list_cnt, conflict_list_free): New variables.
(table_grow): Also grow conflict_table.
(prepare_rules): Output dprec and merger tables.
(conflict_row): New function.
(action_row): Output conflict lists for GLR parser. Don't use
default reduction in conflicted states for GLR parser so that there
are spaces for the conflict lists.
(save_row): Also save conflict information.
(token_actions): Allocate conflict list.
(merger_output): New function.
(pack_vector): Pack conflict table, too.
(output_conflicts): New function to output yyconflp and yyconfl.
(output_check): Allocate conflict_tos.
(output_actions): Output conflict tables, also.
(output_skeleton): Output b4_mergers definition.
(prepare): Output b4_max_rhs_length definition.
Use 'bison.glr' as default skeleton for GLR parsers.
* src/gram.c (glr_parser): New flag.
(grammar_free): Call free_merger_functions.
* src/conflicts.c (count_rr_conflicts): Augment to optionally count
all pairs of conflicting reductions, rather than just all tokens
causing conflicts. Needed to size conflict tables.
(conflicts_output): Modify call to count_rr_conflicts for new
interface.
(conflicts_print): Ditto.
(count_total_conflicts): New function.
* src/reader.h (merger_list): New type.
(merge_functions): New variable.
* src/lex.h (tok_dprec, tok_merge): New token types.
* src/gram.h (rule_s): Add dprec and merger fields.
(glr_parser): New flag.
* src/conflicts.h (count_total_conflicts): New function.
* src/options.c (option_table): Add %dprec, %merge, and %glr-parser.
* doc/bison.texinfo (Generalized LR Parsing): New section.
(GLR Parsers): New section.
(Language and Grammar): Mention GLR parsing.
(Table of Symbols): Add %dprec, %glr-parser, %merge, GLR
Correct typo ("tge" -> "the").
* data/bison.glr: New skeleton for GLR parsing.
* tests/cxx-gram.at: New tests for GLR parsing.
* tests/testsuite.at: Include cxx-gram.at.
* tests/Makefile.am: Add cxx-gram.at.
* src/parse-gram.y:
* src/scan-gram.l: Add %dprec, %glr-parser, %merge.
* src/parse-gram.y: Grammar for %dprec, %merge, %glr-parser.
Index: bison-1_5.27/doc/bison.texinfo
--- bison-1_5.27/doc/bison.texinfo Thu, 27 Jun 2002 10:13:05 -0700 hilfingr
(glrbison/26_bison.texi 1.1.1.2.1.1.1.1 644)
+++ bison-1_5.27(w)/doc/bison.texinfo Thu, 27 Jun 2002 18:52:08 -0700 hilfingr
(glrbison/26_bison.texi 1.1.1.2.1.1.1.1 644)
@@ -282,6 +282,7 @@ The Bison Parser Algorithm
* Parser States:: The parser is a finite-state-machine with stack.
* Reduce/Reduce:: When two rules are applicable in the same situation.
* Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
+* Generalized LR Parsing:: Parsing arbitrary context-free grammars.
* Stack Overflow:: What happens when stack gets full. How to avoid it.
Operator Precedence
@@ -388,6 +389,7 @@ use Bison or Yacc, we suggest you start
a semantic value (the value of an integer,
the name of an identifier, etc.).
* Semantic Actions:: Each rule can have an action containing C code.
+* GLR Parsers:: Writing parsers for general context-free languages
* Locations Overview:: Tracking Locations.
* Bison Parser:: What are Bison's input and output,
how is the output used?
@@ -418,8 +420,12 @@ specify the language Algol 60. Any gram
context-free grammar. The input to Bison is essentially machine-readable
BNF.
-Not all context-free languages can be handled by Bison, only those
-that are LALR(1). In brief, this means that it must be possible to
address@hidden LALR(1) grammars
address@hidden LR(1) grammars
+There are various important subclasses of context-free grammar. Although it
+can handle almost all context-free grammars, Bison is optimized for what
+are called LALR(1) grammars.
+In brief, in these grammars, it must be possible to
tell how to parse any portion of an input string with just a single
token of look-ahead. Strictly speaking, that is a description of an
LR(1) grammar, and LALR(1) involves additional restrictions that are
@@ -427,6 +433,24 @@ hard to explain simply; but it is rare i
LR(1) grammar that fails to be LALR(1). @xref{Mystery Conflicts, ,
Mysterious Reduce/Reduce Conflicts}, for more information on this.
address@hidden GLR parsing
address@hidden generalized LR (GLR) parsing
address@hidden ambiguous grammars
address@hidden non-deterministic parsing
+Parsers for LALR(1) grammars are @dfn{deterministic}, meaning roughly that
+the next grammar rule to apply at any point in the input is uniquely
+determined by the preceding input and a fixed, finite portion (called
+a @dfn{look-ahead}) of the remaining input.
+A context-free grammar can be @dfn{ambiguous}, meaning that
+there are multiple ways to apply the grammar rules to get the some inputs.
+Even unambiguous grammars can be @dfn{non-deterministic}, meaning that no
+fixed look-ahead always suffices to determine the next grammar rule to apply.
+With the proper declarations, Bison is also able to parse these more general
+context-free grammars, using a technique known as GLR parsing (for
+Generalized LR). Bison's GLR parsers are able to handle any context-free
+grammar for which the number of possible parses of any given string
+is finite.
+
@cindex symbols (abstract)
@cindex token
@cindex syntactic grouping
@@ -632,6 +656,180 @@ expr: expr '+' expr @{ $$ = $1 + $3; @
The action says how to produce the semantic value of the sum expression
from the values of the two subexpressions.
address@hidden GLR Parsers
address@hidden Writing GLR Parsers
address@hidden GLR parsing
address@hidden generalized LR (GLR) parsing
address@hidden %glr-parser
address@hidden conflicts
address@hidden shift/reduce conflicts
+
+In some grammars, there will be cases where Bison's standard LALR(1)
+parsing algorithm cannot decide whether to apply a certain grammar rule
+at a given point. That is, it may not be able to decide (on the basis
+of the input read so far) which of two possible reductions (applications
+of a grammar rule) applies, or whether to apply a reduction or read more
+of the input and apply a reduction later in the input. These are known
+respectively as @dfn{reduce/reduce} conflicts (@pxref{Reduce/Reduce}),
+and @dfn{shift/reduce} conflicts (@pxref{Shift/Reduce}).
+
+To use a grammar that is not easily modified to be LALR(1), a more
+general parsing algorithm is sometimes necessary. If you include
address@hidden among the Bison declarations in your file
+(@pxref{Grammar Outline}), the result will be a Generalized LR (GLR)
+parser. These parsers handle Bison grammars that contain no unresolved
+conflicts (i.e., after applying precedence declarations) identically to
+LALR(1) parsers. However, when faced with unresolved shift/reduce and
+reduce/reduce conflicts, GLR parsers use the simple expedient of doing
+both, effectively cloning the parser to follow both possibilities. Each
+of the resulting parsers can again split, so that at any given time,
+there can be any number of possible parses being explored. The parsers
+proceed in lockstep; that is, all of them consume (shift) a given input
+symbol before any of them proceed to the next. Each of the cloned
+parsers eventually meets one of two possible fates: either it runs into
+a parsing error, in which case it simply vanishes, or it merges with
+another parser, because the two of them have reduced the input to an
+identical set of symbols.
+
+During the time that there are multiple parsers, semantic actions are
+recorded, but not performed. When a parser disappears, its recorded
+semantic actions disappear as well, and are never performed. When a
+reduction makes two parsers identical, causing them to merge, Bison
+records both sets of semantic actions. Whenever the last two parsers
+merge, reverting to the single-parser case, Bison resolves all the
+outstanding actions either by precedences given to the grammar rules
+involved, or by performing both actions, and then calling a designated
+user-defined function on the resulting values to produce an arbitrary
+merged result.
+
+Let's consider an example, vastly simplified from C++.
+
address@hidden
address@hidden
+ #define YYSTYPE const char*
address@hidden
+
+%token TYPENAME ID
+
+%right '='
+%left '+'
+
+%glr-parser
+
+%%
+
+prog :
+ | prog stmt @{ printf ("\n"); @}
+ ;
+
+stmt : expr ';' %dprec 1
+ | decl %dprec 2
+ ;
+
+expr : ID @{ printf ("%s ", $$); @}
+ | TYPENAME '(' expr ')'
+ @{ printf ("%s <cast> ", $1); @}
+ | expr '+' expr @{ printf ("+ "); @}
+ | expr '=' expr @{ printf ("= "); @}
+ ;
+
+decl : TYPENAME declarator ';'
+ @{ printf ("%s <declare> ", $1); @}
+ | TYPENAME declarator '=' expr ';'
+ @{ printf ("%s <init-declare> ", $1); @}
+ ;
+
+declarator : ID @{ printf ("\"%s\" ", $1); @}
+ | '(' declarator ')'
+ ;
address@hidden example
+
address@hidden
+This models a problematic part of the C++ grammar---the ambiguity between
+certain declarations and statements. For example,
+
address@hidden
+T (x) = y+z;
address@hidden example
+
address@hidden
+parses as either an @code{expr} or a @code{stmt}
+(assuming that @samp{T} is recognized as a TYPENAME and @samp{x} as an ID).
+Bison detects this as a reduce/reduce conflict between the rules
address@hidden : ID} and @code{declarator : ID}, which it cannot resolve at the
+time it encounters @code{x} in the example above. The two @code{%dprec}
+declarations, however, give precedence to interpreting the example as a
address@hidden, which implies that @code{x} is a declarator.
+The parser therefore prints
+
address@hidden
+"x" y z + T <init-declare>
address@hidden example
+
+Consider a different input string for this parser:
+
address@hidden
+T (x) + y;
address@hidden example
+
address@hidden
+Here, there is no ambiguity (this cannot be parsed as a declaration).
+However, at the time the Bison parser encounters @code{x}, it does not
+have enough information to resolve the reduce/reduce conflict (again,
+between @code{x} as an @code{expr} or a @code{declarator}). In this
+case, no precedence declaration is used. Instead, the parser splits
+into two, one assuming that @code{x} is an @code{expr}, and the other
+assuming @code{x} is a @code{declarator}. The second of these parsers
+then vanishes when it sees @code{+}, and the parser prints
+
address@hidden
+x T <cast> y +
address@hidden example
+
+Suppose that instead of resolving the ambiguity, you wanted to see all
+the possibilities. For this purpose, we must @dfn{merge} the semantic
+actions of the two possible parsers, rather than choosing one over the
+other. To do so, you could change the declaration of @code{stmt} as
+follows:
+
address@hidden
+stmt : expr ';' %merge <stmtMerge>
+ | decl %merge <stmtMerge>
+ ;
address@hidden example
+
address@hidden
+
+and define the @code{stmtMerge} function as:
+
address@hidden
+static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1)
address@hidden
+ printf ("<OR> ");
+ return "";
address@hidden
address@hidden example
+
address@hidden
+with an accompanying forward declaration
+in the C declarations at the beginning of the file:
+
address@hidden
address@hidden
+ #define YYSTYPE const char*
+ static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1);
address@hidden
address@hidden example
+
address@hidden
+With these declarations, the resulting parser will parse the first example
+as both an @code{expr} and a @code{decl}, and print
+
address@hidden
+"x" y z + T <init-declare> x T <cast> y z + = <OR>
address@hidden example
+
+
@node Locations Overview
@section Locations
@cindex location
@@ -2913,7 +3111,7 @@ the location of the grouping (the result
is an array holding locations of all right hand side elements of the rule
being matched. The last one is the size of the right hand side rule.
-By default, it is defined this way:
+By default, it is defined this way for simple LALR(1) parsers:
@example
@group
@@ -2925,6 +3123,19 @@ By default, it is defined this way:
@end group
@end example
address@hidden
+and like this for GLR parsers:
+
address@hidden
address@hidden
+#define YYLLOC_DEFAULT(Current, Rhs, N) \
+ Current.first_line = YYRHSLOC(Rhs,1).first_line; \
+ Current.first_column = YYRHSLOC(Rhs,1).first_column; \
+ Current.last_line = YYRHSLOC(Rhs,N).last_line; \
+ Current.last_column = YYRHSLOC(Rhs,N).last_column;
address@hidden group
address@hidden example
+
When defining @code{YYLLOC_DEFAULT}, you should consider that:
@itemize @bullet
@@ -3890,6 +4101,7 @@ Return immediately from @code{yyparse},
@findex YYBACKUP
Unshift a token. This macro is allowed only for rules that reduce
a single value, and only when there is no look-ahead token.
+It is also disallowed in GLR parsers.
It installs a look-ahead token with token type @var{token} and
semantic value @var{value}; then it discards the value that was
going to be reduced by this rule.
@@ -4030,6 +4242,7 @@ This kind of parser is known in the lite
* Parser States:: The parser is a finite-state-machine with stack.
* Reduce/Reduce:: When two rules are applicable in the same situation.
* Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
+* Generalized LR Parsing:: Parsing arbitrary context-free grammars.
* Stack Overflow:: What happens when stack gets full. How to avoid it.
@end menu
@@ -4624,6 +4837,82 @@ return_spec:
;
@end example
address@hidden Generalized LR Parsing
address@hidden Generalized LR (GLR) Parsing
address@hidden GLR parsing
address@hidden generalized LR (GLR) parsing
address@hidden ambiguous grammars
address@hidden non-deterministic parsing
+
+Bison produces @emph{deterministic} parsers that choose uniquely
+when to reduce and which reduction to apply
+based on a summary of the preceding input and on one extra token of lookahead.
+As a result, normal Bison handles a proper subset of the family of
+context-free languages.
+Ambiguous grammars, since they have strings with more than one possible
+sequence of reductions cannot have deterministic parsers in this sense.
+The same is true of languages that require more than one symbol of
+lookahead, since the parser lacks the information necessary to make a
+decision at the point it must be made in a shift-reduce parser.
+Finally, as previously mentioned (@pxref{Mystery Conflicts}),
+there are languages where Bison's particular choice of how to
+summarize the input seen so far loses necessary information.
+
+When you use the @samp{%glr-parser} declaration in your grammar file,
+Bison generates a parser that uses a different algorithm, called
+Generalized LR (or GLR). A Bison GLR parser uses the same basic
+algorithm for parsing as an ordinary Bison parser, but behaves
+differently in cases where there is a shift-reduce conflict that has not
+been resolved by precedence rules (@pxref{Precedence}) or a
+reduce-reduce conflict. When a GLR parser encounters such a situation, it
+effectively @emph{splits} into a several parsers, one for each possible
+shift or reduction. These parsers then proceed as usual, consuming
+tokens in lock-step. Some of the stacks may encounter other conflicts
+and split further, with the result that instead of a sequence of states,
+a Bison GLR parsing stack is what is in effect a tree of states.
+
+In effect, each stack represents a guess as to what the proper parse
+is. Additional input may indicate that a guess was wrong, in which case
+the appropriate stack silently disappears. Otherwise, the semantics
+actions generated in each stack are saved, rather than being executed
+immediately. When a stack disappears, its saved semantic actions never
+get executed. When a reduction causes two stacks to become equivalent,
+their sets of semantic actions are both saved with the state that
+results from the reduction. We say that two stacks are equivalent
+when they both represent the same sequence of states,
+and each pair of corresponding states represents a
+grammar symbol that produces the same segment of the input token
+stream.
+
+Whenever the parser makes a transition from having multiple
+states to having one, it reverts to the normal LALR(1) parsing
+algorithm, after resolving and executing the saved-up actions.
+At this transition, some of the states on the stack will have semantic
+values that are sets (actually multisets) of possible actions. The
+parser tries to pick one of the actions by first finding one whose rule
+has the highest dynamic precedence, as set by the @samp{%dprec}
+declaration. Otherwise, if the alternative actions are not ordered by
+precedence, but there the same merging function is declared for both
+rules by the @samp{%merge} declaration,
+Bison resolves and evaluates both and then calls the merge function on
+the result. Otherwise, it reports an ambiguity.
+
+It is possible to use a data structure for the GLR parsing tree that
+permits the processing of any LALR(1) grammar in linear time (in the
+size of the input), any unambiguous (not necessarily LALR(1)) grammar in
+quadratic worst-case time, and any general (possibly ambiguous)
+context-free grammar in cubic worst-case time. However, Bison currently
+uses a simpler data structure that requires time proportional to the
+length of the input times the maximum number of stacks required for any
+prefix of the input. Thus, really ambiguous or non-deterministic
+grammars can require exponential time and space to process. Such badly
+behaving examples, however, are not generally of practical interest.
+Usually, non-determinism in a grammar is local---the parser is ``in
+doubt'' only for a few tokens at a time. Therefore, the current data
+structure should generally be adequate. On LALR(1) portions of a
+grammar, in particular, it is only slightly slower than with the default
+Bison parser.
+
@node Stack Overflow
@section Stack Overflow, and How to Avoid It
@cindex stack overflow
@@ -5912,10 +6201,17 @@ Equip the parser for debugging. @xref{D
Bison declaration to create a header file meant for the scanner.
@xref{Decl Summary}.
address@hidden %dprec
+Bison declaration to assign a precedence to a rule that is used at parse
+time to resolve reduce/reduce conflicts. @xref{GLR Parsers}.
+
@item %file-prefix="@var{prefix}"
-Bison declaration to set tge prefix of the output files. @xref{Decl
+Bison declaration to set the prefix of the output files. @xref{Decl
Summary}.
address@hidden %glr-parser
+Bison declaration to produce a GLR parser. @xref{GLR Parsers}.
+
@c @item %source-extension
@c Bison declaration to specify the generated parser output file extension.
@c @xref{Decl Summary}.
@@ -5928,6 +6224,12 @@ Summary}.
Bison declaration to assign left associativity to token(s).
@xref{Precedence Decl, ,Operator Precedence}.
address@hidden %merge
+Bison declaration to assign a merging function to a rule. If there is a
+reduce/reduce conflict with a rule having the same merging function, the
+function is applied to the two semantic values to get a single result.
address@hidden Parsers}.
+
@item %name-prefix="@var{prefix}"
Bison declaration to rename the external symbols. @xref{Decl Summary}.
@@ -6039,6 +6341,13 @@ machine moves from state to state as spe
machine. In the case of the parser, the input is the language being
parsed, and the states correspond to various stages in the grammar
rules. @xref{Algorithm, ,The Bison Parser Algorithm }.
+
address@hidden Generalized LR (GLR)
+A parsing algorithm that can handle all context-free grammars, including those
+that are not LALR(1). It resolves situations that Bison's usual LALR(1)
+algorithm cannot by effectively splitting off multiple parsers, trying all
+possible parsers, and discarding those that fail in the light of additional
+right context. @xref{Generalized LR Parsing, ,Generalized LR Parsing}.
@item Grouping
A language construct that is (in general) grammatically divisible;
Index: bison-1_5.27/doc/version.texi
--- bison-1_5.27/doc/version.texi Sun, 12 May 2002 19:40:04 -0700 hilfingr
(glrbison/27_version.te 1.1.1.2 644)
+++ bison-1_5.27(w)/doc/version.texi Thu, 27 Jun 2002 18:52:09 -0700 hilfingr
(glrbison/27_version.te 1.1.1.2 644)
@@ -1,4 +1,4 @@
address@hidden UPDATED 7 May 2002
address@hidden UPDATED-MONTH May 2002
address@hidden UPDATED 27 June 2002
address@hidden UPDATED-MONTH June 2002
@set EDITION 1.49b
@set VERSION 1.49b
Index: bison-1_5.27/doc/stamp-vti
--- bison-1_5.27/doc/stamp-vti Sun, 12 May 2002 19:40:04 -0700 hilfingr
(glrbison/28_stamp-vti 1.1.1.2 644)
+++ bison-1_5.27(w)/doc/stamp-vti Thu, 27 Jun 2002 18:52:09 -0700 hilfingr
(glrbison/28_stamp-vti 1.1.1.2 644)
@@ -1,4 +1,4 @@
address@hidden UPDATED 7 May 2002
address@hidden UPDATED-MONTH May 2002
address@hidden UPDATED 27 June 2002
address@hidden UPDATED-MONTH June 2002
@set EDITION 1.49b
@set VERSION 1.49b
Index: bison-1_5.27/src/reader.c
--- bison-1_5.27/src/reader.c Thu, 27 Jun 2002 10:13:05 -0700 hilfingr
(glrbison/44_reader.c 1.1.1.3.1.1.1.1.1.1.1.1.1.1.1.2.1.1.1.1.1.1 644)
+++ bison-1_5.27(w)/src/reader.c Thu, 27 Jun 2002 18:52:09 -0700 hilfingr
(glrbison/44_reader.c 1.1.1.3.1.1.1.1.1.1.1.1.1.1.1.2.1.1.1.1.1.1 644)
@@ -37,6 +37,7 @@
int lineno;
static symbol_list_t *grammar = NULL;
static int start_flag = 0;
+merger_list *merge_functions;
/* Nonzero if %union has been seen. */
int typed = 0;
@@ -105,6 +106,60 @@ epilogue_set (const char *epilogue, loca
+ /*-------------------------------------------------------------------.
+| Return the merger index for a merging function named NAME, whose |
+| arguments have type TYPE. Records the function, if new, in |
+| merger_list. |
+`-------------------------------------------------------------------*/
+
+static int
+get_merge_function (const char* name, const char* type)
+{
+ merger_list *syms;
+ merger_list head;
+ int n;
+
+ if (! glr_parser)
+ return 0;
+
+ if (type == NULL)
+ type = "";
+
+ head.next = merge_functions;
+ for (syms = &head, n = 1; syms->next != NULL; syms = syms->next, n += 1)
+ if (strcmp (name, syms->next->name) == 0)
+ break;
+ if (syms->next == NULL) {
+ syms->next = XMALLOC (merger_list, 1);
+ syms->next->name = strdup (name);
+ syms->next->type = strdup (type);
+ syms->next->next = NULL;
+ merge_functions = head.next;
+ } else if (strcmp (type, syms->next->type) != 0)
+ warn (_("result type clash on merge function %s: `%s' vs. `%s'"),
+ name, type, syms->next->type);
+ return n;
+}
+
+/*--------------------------------------.
+| Free all merge-function definitions. |
+`--------------------------------------*/
+
+void
+free_merger_functions (void)
+{
+ merger_list *L0;
+ if (! glr_parser)
+ return;
+ L0 = merge_functions;
+ while (L0 != NULL)
+ {
+ merger_list *L1 = L0->next;
+ free (L0);
+ L0 = L1;
+ }
+}
+
/*-------------------------------------------------------------------.
| Generate a dummy symbol, a nonterminal, whose name cannot conflict |
| with the user's names. |
@@ -307,6 +362,34 @@ grammar_current_rule_prec_set (symbol_t
current_rule->ruleprec = precsym;
}
+/* Attach dynamic precedence DPREC to the current rule. */
+
+void
+grammar_current_rule_dprec_set (int dprec, location_t location)
+{
+ if (! glr_parser)
+ warn_at (location, _("%%dprec affects only GLR parsers"));
+ if (dprec <= 0)
+ complain_at (location, _("%%dprec must be followed by positive number"));
+ else if (current_rule->dprec != 0)
+ complain_at (location, _("only one %%dprec allowed per rule"));
+ current_rule->dprec = dprec;
+}
+
+/* Attach a merge function NAME with argument type TYPE to current
+ rule. */
+
+void
+grammar_current_rule_merge_set (const char* name, location_t location)
+{
+ if (! glr_parser)
+ warn_at (location, _("%%merge affects only GLR parsers"));
+ if (current_rule->merger != 0)
+ complain_at (location, _("only one %%merge allowed per rule"));
+ current_rule->merger =
+ get_merge_function (name, current_rule->sym->type_name);
+}
+
/* Attach a SYMBOL to the current rule. If needed, move the previous
action as a mid-rule action. */
@@ -319,7 +402,6 @@ grammar_current_rule_symbol_append (symb
grammar_symbol_append (symbol, location);
}
-
/* Attach an ACTION to the current rule. If needed, move the previous
action as a mid-rule action. */
@@ -363,6 +445,8 @@ packgram (void)
rules[ruleno].useful = TRUE;
rules[ruleno].action = p->action;
rules[ruleno].action_location = p->action_location;
+ rules[ruleno].dprec = p->dprec;
+ rules[ruleno].merger = p->merger;
p = p->next;
while (p && p->sym)
Index: bison-1_5.27/src/output.c
--- bison-1_5.27/src/output.c Thu, 27 Jun 2002 10:13:05 -0700 hilfingr
(glrbison/48_output.c 1.1.1.3.1.1.1.2.1.1.1.2.1.1.1.1.1.1.1.1 644)
+++ bison-1_5.27(w)/src/output.c Thu, 27 Jun 2002 18:52:09 -0700 hilfingr
(glrbison/48_output.c 1.1.1.3.1.1.1.2.1.1.1.2.1.1.1.1.1.1.1.1 644)
@@ -115,14 +115,21 @@ static int nvectors;
static int nentries;
static short **froms = NULL;
static short **tos = NULL;
+static unsigned int **conflict_tos = NULL;
static short *tally = NULL;
static short *width = NULL;
static short *actrow = NULL;
+static short *conflrow = NULL;
static short *state_count = NULL;
static short *order = NULL;
static short *base = NULL;
static short *pos = NULL;
+static unsigned int *conflict_table = NULL;
+static unsigned int *conflict_list = NULL;
+static int conflict_list_cnt;
+static int conflict_list_free;
+
/* TABLE_SIZE is the allocated size of both TABLE and CHECK.
We start with the original hard-coded value: SHRT_MAX
(yes, not USHRT_MAX). */
@@ -157,6 +164,8 @@ table_grow (size_t desired)
table = XREALLOC (table, short, table_size);
check = XREALLOC (check, short, table_size);
+ if (glr_parser)
+ conflict_table = XREALLOC (conflict_table, unsigned int, table_size);
for (/* Nothing. */; old_size < table_size; ++old_size)
{
@@ -278,7 +287,7 @@ prepare_tokens (void)
/*-------------------------------------------------------------.
| Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
-| rline. |
+| rline, dprec, merger |
`-------------------------------------------------------------*/
static void
@@ -291,6 +300,8 @@ prepare_rules (void)
unsigned int *rline = XMALLOC (unsigned int, nrules + 1);
symbol_number_t *r1 = XMALLOC (symbol_number_t, nrules + 1);
unsigned int *r2 = XMALLOC (unsigned int, nrules + 1);
+ short *dprec = XMALLOC (short, nrules + 1);
+ short *merger = XMALLOC (short, nrules + 1);
for (r = 1; r < nrules + 1; ++r)
{
@@ -308,6 +319,10 @@ prepare_rules (void)
rhs[i++] = -1;
/* Line where rule was defined. */
rline[r] = rules[r].location.first_line;
+ /* Dynamic precedence (GLR) */
+ dprec[r] = rules[r].dprec;
+ /* Merger-function index (GLR) */
+ merger[r] = rules[r].merger;
}
assert (i == nritems);
@@ -316,12 +331,16 @@ prepare_rules (void)
muscle_insert_unsigned_int_table ("rline", rline, 0, 1, nrules + 1);
muscle_insert_symbol_number_table ("r1", r1, 0, 1, nrules + 1);
muscle_insert_unsigned_int_table ("r2", r2, 0, 1, nrules + 1);
+ muscle_insert_short_table ("dprec", dprec, 0, 1, nrules + 1);
+ muscle_insert_short_table ("merger", merger, 0, 1, nrules + 1);
free (rhs);
free (prhs);
free (rline);
free (r1);
free (r2);
+ free (dprec);
+ free (merger);
}
/*--------------------------------------------.
@@ -341,6 +360,50 @@ prepare_states (void)
}
+/*-------------------------------------------------------------------.
+| For GLR parsers, for each conflicted token in STATE, as indicated |
+| by non-zero entries in conflrow, create a list of possible |
+| reductions that are alternatives to the shift or reduction |
+| currently recorded for that token in STATE. Store the alternative |
+| reductions followed by a 0 in conflict_list, updating |
+| conflict_list_cnt, and storing an index to the start of the list |
+| back into conflrow. |
+`-------------------------------------------------------------------*/
+
+static void
+conflict_row (state_t *state)
+{
+ int i, j;
+
+ if (! glr_parser)
+ return;
+
+ for (j = 0; j < ntokens; j += 1)
+ if (conflrow[j])
+ {
+ conflrow[j] = conflict_list_cnt;
+
+ /* find all reductions for token j, and record all that do
+ * not match actrow[j] */
+ for (i = 0; i < state->nlookaheads; i += 1)
+ if (bitset_test (state->lookaheads[i], j)
+ && actrow[j] != -state->lookaheads_rule[i]->number)
+ {
+ assert (conflict_list_free > 0);
+ conflict_list[conflict_list_cnt]
+ = state->lookaheads_rule[i]->number;
+ conflict_list_cnt += 1;
+ conflict_list_free -= 1;
+ }
+
+ /* Leave a 0 at the end */
+ assert (conflict_list_free > 0);
+ conflict_list_cnt += 1;
+ conflict_list_free -= 1;
+ }
+}
+
+
/*------------------------------------------------------------------.
| Decide what to do for each type of token if seen as the lookahead |
| token in specified state. The value returned is used as the |
@@ -353,6 +416,11 @@ prepare_states (void)
| This is where conflicts are resolved. The loop over lookahead |
| rules considered lower-numbered rules last, and the last rule |
| considered that likes a token gets to handle it. |
+| |
+| For GLR parsers, also sets conflrow[SYM] to an index into |
+| conflict_list iff there is an unresolved conflict (s/r or r/r) |
+| with symbol SYM. The default reduction is not used for a symbol |
+| that has any such conflicts. |
`------------------------------------------------------------------*/
static int
@@ -365,9 +433,10 @@ action_row (state_t *state)
errs *errp = state->errs;
/* set nonzero to inhibit having any default reduction */
int nodefault = 0;
+ int conflicted = 0;
for (i = 0; i < ntokens; i++)
- actrow[i] = 0;
+ actrow[i] = conflrow[i] = 0;
if (redp->nreds >= 1)
{
@@ -381,7 +450,11 @@ action_row (state_t *state)
/* and record this rule as the rule to use if that
token follows. */
if (bitset_test (state->lookaheads[i], j))
- actrow[j] = -state->lookaheads_rule[i]->number;
+ {
+ if (actrow[j] != 0)
+ conflicted = conflrow[j] = 1;
+ actrow[j] = -state->lookaheads_rule[i]->number;
+ }
}
/* Now see which tokens are allowed for shifts in this state. For
@@ -399,6 +472,8 @@ action_row (state_t *state)
if (ISVAR (symbol))
break;
+ if (actrow[symbol] != 0)
+ conflicted = conflrow[symbol] = 1;
actrow[symbol] = shift_state;
/* Do not use any default reduction if there is a shift for
@@ -442,18 +517,20 @@ action_row (state_t *state)
}
}
- /* actions which match the default are replaced with zero,
- which means "use the default" */
+ /* GLR parsers need space for conflict lists, so we can't
+ default conflicted entries. For non-conflicted entries
+ or as long as we are not building a GLR parser,
+ actions that match the default are replaced with zero,
+ which means "use the default". */
if (max > 0)
{
int j;
for (j = 0; j < ntokens; j++)
- if (actrow[j] == default_rule)
+ if (actrow[j] == default_rule && ! (glr_parser && conflrow[j]))
actrow[j] = 0;
-
- default_rule = -default_rule;
}
+ default_rule = -default_rule;
}
}
@@ -465,6 +542,9 @@ action_row (state_t *state)
if (actrow[i] == SHRT_MIN)
actrow[i] = 0;
+ if (conflicted)
+ conflict_row (state);
+
return default_rule;
}
@@ -477,6 +557,7 @@ save_row (int state)
short *sp;
short *sp1;
short *sp2;
+ unsigned int *sp3;
count = 0;
for (i = 0; i < ntokens; i++)
@@ -488,12 +569,18 @@ save_row (int state)
froms[state] = sp1 = sp = XCALLOC (short, count);
tos[state] = sp2 = XCALLOC (short, count);
+ if (glr_parser)
+ conflict_tos[state] = sp3 = XCALLOC (unsigned int, count);
+ else
+ conflict_tos[state] = NULL;
for (i = 0; i < ntokens; i++)
if (actrow[i] != 0)
{
*sp1++ = i;
*sp2++ = actrow[i];
+ if (glr_parser)
+ *sp3++ = conflrow[i];
}
tally[state] = count;
@@ -513,9 +600,22 @@ static void
token_actions (void)
{
size_t i;
+ int nconflict = conflicts_total_count ();
+
short *yydefact = XCALLOC (short, nstates);
actrow = XCALLOC (short, ntokens);
+
+ conflrow = XCALLOC (short, ntokens);
+ if (glr_parser)
+ {
+ conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict);
+ conflict_list_free = 2 * nconflict;
+ conflict_list_cnt = 1;
+ }
+ else
+ conflict_list_free = conflict_list_cnt = 0;
+
for (i = 0; i < nstates; ++i)
{
yydefact[i] = action_row (states[i]);
@@ -525,6 +625,7 @@ token_actions (void)
muscle_insert_short_table ("defact", yydefact,
yydefact[0], 1, nstates);
XFREE (actrow);
+ XFREE (conflrow);
XFREE (yydefact);
}
@@ -555,6 +656,28 @@ actions_output (FILE *out)
fputs ("]])\n\n", out);
}
+/*--------------------------------------.
+| Output the merge functions to OUT. |
+`--------------------------------------*/
+
+void
+merger_output (FILE *out)
+{
+ int n;
+ merger_list* p;
+
+ fputs ("m4_define([b4_mergers], \n[[", out);
+ for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
+ {
+ if (p->type[0] == '\0')
+ fprintf (out, " case %d: yyval = %s (*yy0, *yy1); break;\n",
+ n, p->name);
+ else
+ fprintf (out, " case %d: yyval.%s = %s (*yy0, *yy1); break;\n",
+ n, p->type, p->name);
+ }
+ fputs ("]])\n\n", out);
+}
/*---------------------------------------.
| Output the tokens definition to OOUT. |
@@ -844,6 +967,7 @@ pack_vector (int vector)
int loc = 0;
short *from = froms[i];
short *to = tos[i];
+ unsigned int *conflict_to = conflict_tos[i];
assert (t);
@@ -872,6 +996,8 @@ pack_vector (int vector)
{
loc = j + from[k];
table[loc] = to[k];
+ if (glr_parser && conflict_to != NULL)
+ conflict_table[loc] = conflict_to[k];
check[loc] = from[k];
}
@@ -900,6 +1026,8 @@ pack_table (void)
base = XCALLOC (short, nvectors);
pos = XCALLOC (short, nentries);
table = XCALLOC (short, table_size);
+ if (glr_parser)
+ conflict_table = XCALLOC (unsigned int, table_size);
check = XCALLOC (short, table_size);
lowzero = 0;
@@ -928,14 +1056,16 @@ pack_table (void)
{
XFREE (froms[i]);
XFREE (tos[i]);
+ XFREE (conflict_tos[i]);
}
XFREE (froms);
XFREE (tos);
+ XFREE (conflict_tos);
XFREE (pos);
}
-/* the following functions output yytable, yycheck
+/* the following functions output yytable, yycheck, yyconflp, yyconfl,
and the vectors whose elements index the portion starts */
static void
@@ -962,6 +1092,28 @@ output_table (void)
static void
+output_conflicts (void)
+{
+ /* GLR parsing slightly modifies yytable and yycheck
+ (and thus yypact) so that in states with unresolved conflicts,
+ the default reduction is not used in the conflicted entries, so
+ that there is a place to put a conflict pointer. This means that
+ yyconflp and yyconfl are nonsense for a non-GLR parser, so we
+ avoid accidents by not writing them out in that case. */
+ if (! glr_parser)
+ return;
+
+ muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
+ conflict_table[0], 1, high+1);
+ muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
+ conflict_list[0], 1, conflict_list_cnt);
+
+ XFREE (conflict_table);
+ XFREE (conflict_list);
+}
+
+
+static void
output_check (void)
{
muscle_insert_short_table ("check", check,
@@ -982,6 +1134,7 @@ output_actions (void)
froms = XCALLOC (short *, nvectors);
tos = XCALLOC (short *, nvectors);
+ conflict_tos = XCALLOC (unsigned int *, nvectors);
tally = XCALLOC (short, nvectors);
width = XCALLOC (short, nvectors);
@@ -999,6 +1152,7 @@ output_actions (void)
output_base ();
output_table ();
+ output_conflicts ();
output_check ();
@@ -1084,6 +1238,7 @@ output_skeleton (void)
fputs ("m4_init()\n", out);
actions_output (out);
+ merger_output (out);
token_definitions_output (out);
symbol_destructors_output (out);
symbol_printers_output (out);
@@ -1140,7 +1295,12 @@ prepare (void)
/* Find the right skeleton file. */
if (!skeleton)
- skeleton = "yacc.c";
+ {
+ if (glr_parser)
+ skeleton = "glr.c";
+ else
+ skeleton = "yacc.c";
+ }
/* Parse the skeleton file and output the needed parsers. */
muscle_insert ("skeleton", skeleton);
Index: bison-1_5.27/src/gram.c
--- bison-1_5.27/src/gram.c Sun, 16 Jun 2002 13:39:03 -0700 hilfingr
(glrbison/b/2_gram.c 1.1.1.3.1.1.1.1.1.1 644)
+++ bison-1_5.27(w)/src/gram.c Thu, 27 Jun 2002 18:52:10 -0700 hilfingr
(glrbison/b/2_gram.c 1.1.1.3.1.1.1.1.1.1 644)
@@ -43,6 +43,7 @@ symbol_number_t *token_translations = NU
int max_user_token_number = 256;
+int glr_parser = 0;
int pure_parser = 0;
@@ -249,4 +250,5 @@ grammar_free (void)
XFREE (token_translations);
/* Free the symbol table data structure. */
symbols_free ();
+ free_merger_functions ();
}
Index: bison-1_5.27/src/conflicts.c
--- bison-1_5.27/src/conflicts.c Sun, 16 Jun 2002 13:39:03 -0700 hilfingr
(glrbison/b/5_conflicts. 1.1.1.2.1.1.1.1.1.1.1.1 644)
+++ bison-1_5.27(w)/src/conflicts.c Thu, 27 Jun 2002 18:52:10 -0700 hilfingr
(glrbison/b/5_conflicts. 1.1.1.2.1.1.1.1.1.1.1.1 644)
@@ -331,12 +331,15 @@ count_sr_conflicts (state_t *state)
}
-/*----------------------------------------------.
-| Count the number of reduce/reduce conflicts. |
-`----------------------------------------------*/
+/*----------------------------------------------------------------.
+| Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, |
+| count one conflict for each token that has any reduce/reduce |
+| conflicts. Otherwise, count one conflict for each pair of |
+| conflicting reductions. |
++`----------------------------------------------------------------*/
static int
-count_rr_conflicts (state_t *state)
+count_rr_conflicts (state_t *state, int one_per_token)
{
int i;
int rrc_count = 0;
@@ -353,7 +356,7 @@ count_rr_conflicts (state_t *state)
count++;
if (count >= 2)
- rrc_count++;
+ rrc_count += one_per_token ? 1 : count-1;
}
return rrc_count;
@@ -412,13 +415,37 @@ conflicts_output (FILE *out)
{
fprintf (out, _("State %d contains "), i);
fputs (conflict_report (count_sr_conflicts (states[i]),
- count_rr_conflicts (states[i])), out);
+ count_rr_conflicts (states[i], TRUE)), out);
printed_sth = TRUE;
}
if (printed_sth)
fputs ("\n\n", out);
}
+/*--------------------------------------------------------.
+| Total the number of S/R and R/R conflicts. Unlike the |
+| code in conflicts_output, however, count EACH pair of |
+| reductions for the same state and lookahead as one |
+| conflict. |
+`--------------------------------------------------------*/
+
+int
+conflicts_total_count (void)
+{
+ int i;
+ int count;
+
+ /* Conflicts by state. */
+ count = 0;
+ for (i = 0; i < nstates; i++)
+ if (conflicts[i])
+ {
+ count += count_sr_conflicts (states[i]);
+ count += count_rr_conflicts (states[i], FALSE);
+ }
+ return count;
+}
+
/*------------------------------------------.
| Reporting the total number of conflicts. |
@@ -442,7 +469,7 @@ conflicts_print (void)
if (conflicts[i])
{
src_total += count_sr_conflicts (states[i]);
- rrc_total += count_rr_conflicts (states[i]);
+ rrc_total += count_rr_conflicts (states[i], TRUE);
}
src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);
Index: bison-1_5.27/src/reader.h
--- bison-1_5.27/src/reader.h Thu, 20 Jun 2002 12:56:37 -0700 hilfingr
(glrbison/b/20_reader.h 1.1.1.3.1.1.1.2.1.1.1.1 644)
+++ bison-1_5.27(w)/src/reader.h Thu, 27 Jun 2002 18:52:10 -0700 hilfingr
(glrbison/b/20_reader.h 1.1.1.3.1.1.1.2.1.1.1.1 644)
@@ -24,6 +24,14 @@
# include "symlist.h"
# include "parse-gram.h"
+typedef struct merger_list
+{
+ struct merger_list* next;
+ const char* name;
+ const char* type;
+}
+merger_list;
+
typedef struct gram_control_s
{
int errcode;
@@ -70,12 +78,21 @@ void grammar_rule_end PARAMS ((location_
void grammar_midrule_action PARAMS ((void));
void grammar_current_rule_prec_set PARAMS ((symbol_t *precsym,
location_t l));
+void grammar_current_rule_dprec_set PARAMS ((int dprec,
+ location_t l));
+void grammer_current_rule_merge_set PARAMS ((const char* name,
+ location_t l));
+
void grammar_current_rule_symbol_append PARAMS ((symbol_t *symbol,
location_t l));
void grammar_current_rule_action_append PARAMS ((const char *action,
location_t l));
extern symbol_list_t *current_rule;
void reader PARAMS ((void));
+void free_merger_functions PARAMS ((void));
+
+extern merger_list *merge_functions;
+
extern int typed;
#endif /* !READER_H_ */
Index: bison-1_5.27/src/gram.h
--- bison-1_5.27/src/gram.h Sun, 16 Jun 2002 13:39:03 -0700 hilfingr
(glrbison/b/25_gram.h 1.1.1.3.1.1.1.1.1.1 644)
+++ bison-1_5.27(w)/src/gram.h Thu, 27 Jun 2002 18:52:10 -0700 hilfingr
(glrbison/b/25_gram.h 1.1.1.3.1.1.1.1.1.1 644)
@@ -68,6 +68,10 @@
RULES[R].assoc -- the associativity of R.
+ RULES[R].dprec -- the dynamic precedence level of R (for GLR parsing).
+
+ RULES[R].merger -- index of merging function for R (for GLR parsing).
+
RULES[R].line -- the line where R was defined.
RULES[R].useful -- TRUE iff the rule is used (i.e., FALSE if thrown
@@ -141,6 +145,9 @@ typedef struct rule_s
/* This symbol provides both the associativity, and the precedence. */
symbol_t *prec;
+ short dprec;
+ short merger;
+
/* This symbol was attached to the rule via %prec. */
symbol_t *precsym;
@@ -162,6 +169,12 @@ extern symbol_t **symbols;
extern symbol_number_t *token_translations;
extern int max_user_token_number;
+
+/* GLR_PARSER is nonzero if the input file says to use the GLR
+ (Generalized LR) parser, and to output some additional
+ information used by the GLR algorithm. */
+
+extern int glr_parser;
/* PURE_PARSER is nonzero if should generate a parser that is all pure
and reentrant. */
Index: bison-1_5.27/src/conflicts.h
--- bison-1_5.27/src/conflicts.h Sun, 26 May 2002 14:18:11 -0700 hilfingr
(glrbison/b/29_conflicts. 1.1.1.2 644)
+++ bison-1_5.27(w)/src/conflicts.h Thu, 27 Jun 2002 18:52:10 -0700 hilfingr
(glrbison/b/29_conflicts. 1.1.1.2 644)
@@ -24,6 +24,7 @@
void conflicts_solve PARAMS ((void));
void conflicts_print PARAMS ((void));
+int conflicts_total_count PARAMS ((void));
void conflicts_output PARAMS ((FILE *out));
void conflicts_free PARAMS ((void));
Index: bison-1_5.27/NEWS
--- bison-1_5.27/NEWS Tue, 18 Jun 2002 17:04:55 -0700 hilfingr
(glrbison/c/23_NEWS 1.1.1.3.1.1.1.1.1.1.1.1 644)
+++ bison-1_5.27(w)/NEWS Thu, 27 Jun 2002 18:52:11 -0700 hilfingr
(glrbison/c/23_NEWS 1.1.1.3.1.1.1.1.1.1.1.1 644)
@@ -3,6 +3,14 @@ Bison News
Changes in version 1.49b:
+* GLR parsing
+ The declaration
+ %glr-parser
+ causes Bison to produce a Generalized LR (GLR) parser, capable of handling
+ almost any context-free grammar, ambiguous or not. The new declarations
+ %dprec and %merge on grammar rules allow parse-time resolution of
+ ambiguities. Contributed by Paul Hilfinger.
+
* Output Directory
When not in Yacc compatibility mode, when the output file was not
specified, runnning `bison foo/bar.y' created `foo/bar.c'. It
Index: bison-1_5.27/tests/testsuite.at
--- bison-1_5.27/tests/testsuite.at Thu, 02 May 2002 15:41:15 -0700 hilfingr
(glrbison/c/41_testsuite. 1.1.1.1 644)
+++ bison-1_5.27(w)/tests/testsuite.at Thu, 27 Jun 2002 18:52:11 -0700 hilfingr
(glrbison/c/41_testsuite. 1.1.1.1 644)
@@ -61,3 +61,6 @@ m4_include([existing.at])
# Some old bugs.
m4_include([regression.at])
+
+# GLR tests: C++ types, simplified
+m4_include([cxx-type.at])
Index: bison-1_5.27/tests/Makefile.am
--- bison-1_5.27/tests/Makefile.am Thu, 02 May 2002 15:41:15 -0700 hilfingr
(glrbison/c/45_Makefile.a 1.1.1.1 644)
+++ bison-1_5.27(w)/tests/Makefile.am Thu, 27 Jun 2002 18:52:11 -0700 hilfingr
(glrbison/c/45_Makefile.a 1.1.1.1 644)
@@ -49,7 +49,8 @@ TESTSUITE_AT = \
output.at sets.at reduce.at \
synclines.at headers.at actions.at conflicts.at \
calc.at \
- torture.at existing.at regression.at
+ torture.at existing.at regression.at \
+ cxx-type.at
TESTSUITE = $(srcdir)/testsuite
Index: bison-1_5.27/data/Makefile.am
--- bison-1_5.27/data/Makefile.am Thu, 27 Jun 2002 10:13:05 -0700 hilfingr
(glrbison/f/3_Makefile.a 1.2 644)
+++ bison-1_5.27(w)/data/Makefile.am Thu, 27 Jun 2002 18:52:14 -0700 hilfingr
(glrbison/f/3_Makefile.a 1.2 644)
@@ -15,7 +15,7 @@
## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
## 02111-1307 USA
-dist_pkgdata_DATA = yacc.c lalr1.cc
+dist_pkgdata_DATA = yacc.c lalr1.cc glr.c
m4sugardir = $(pkgdatadir)/m4sugar
dist_m4sugar_DATA = m4sugar/m4sugar.m4 m4sugar/version.m4
Index: bison-1_5.27/src/scan-gram.l
--- bison-1_5.27/src/scan-gram.l Thu, 20 Jun 2002 12:56:37 -0700 hilfingr
(glrbison/g/8_scan-gram. 1.1.1.1.1.1.1.1.1.1.1.1 644)
+++ bison-1_5.27(w)/src/scan-gram.l Thu, 27 Jun 2002 18:52:15 -0700 hilfingr
(glrbison/g/8_scan-gram. 1.1.1.1.1.1.1.1.1.1.1.1 644)
@@ -124,12 +124,15 @@ blanks [ \t\f]+
"%define" return PERCENT_DEFINE;
"%defines" return PERCENT_DEFINES;
"%destructor" return PERCENT_DESTRUCTOR;
+ "%dprec" return PERCENT_DPREC;
"%error"[-_]"verbose" return PERCENT_ERROR_VERBOSE;
"%expect" return PERCENT_EXPECT;
"%file-prefix" return PERCENT_FILE_PREFIX;
"%fixed"[-_]"output"[-_]"files" return PERCENT_YACC;
+ "%glr"[-_]"parser" return PERCENT_GLR_PARSER;
"%left" return PERCENT_LEFT;
"%locations" return PERCENT_LOCATIONS;
+ "%merge" return PERCENT_MERGE;
"%name"[-_]"prefix" return PERCENT_NAME_PREFIX;
"%no"[-_]"lines" return PERCENT_NO_LINES;
"%nonassoc" return PERCENT_NONASSOC;
Index: bison-1_5.27/src/parse-gram.y
--- bison-1_5.27/src/parse-gram.y Thu, 20 Jun 2002 12:56:37 -0700 hilfingr
(glrbison/g/11_parse-gram 1.1.1.2.1.1.1.1 644)
+++ bison-1_5.27(w)/src/parse-gram.y Thu, 27 Jun 2002 18:52:15 -0700 hilfingr
(glrbison/g/11_parse-gram 1.1.1.2.1.1.1.1 644)
@@ -114,6 +114,8 @@ braced_code_t current_braced_code = acti
%token PERCENT_EXPECT "%expect"
%token PERCENT_START "%start"
%token PERCENT_PREC "%prec"
+%token PERCENT_DPREC "%dprec"
+%token PERCENT_MERGE "%merge"
%token PERCENT_VERBOSE "%verbose"
%token PERCENT_ERROR_VERBOSE "%error-verbose"
@@ -123,6 +125,7 @@ braced_code_t current_braced_code = acti
%token PERCENT_DEFINE "%define"
%token PERCENT_PURE_PARSER "%pure-parser"
+%token PERCENT_GLR_PARSER "%glr-parser"
%token PERCENT_DEFINES "%defines"
@@ -184,6 +187,7 @@ declaration:
| "%no-lines" { no_lines_flag = 1; }
| "%output" "=" string_content { spec_outfile = $3; }
| "%pure-parser" { pure_parser = 1; }
+| "%glr-parser" { glr_parser = 1; }
| "%skeleton" string_content { skeleton = $2; }
| "%token-table" { token_table_flag = 1; }
| "%verbose" { report_flag = 1; }
@@ -355,6 +359,10 @@ rhs:
{ grammar_current_rule_action_append ($2, @2); }
| rhs "%prec" symbol
{ grammar_current_rule_prec_set ($3, @3); }
+| rhs "%dprec" INT
+ { grammar_current_rule_dprec_set ($3, @3); }
+| rhs "%merge" TYPE
+ { grammar_current_rule_merge_set ($3, @3); }
;
symbol:
Index: bison-1_5.27/src/symlist.h
--- bison-1_5.27/src/symlist.h Mon, 17 Jun 2002 14:10:36 -0700 hilfingr
(glrbison/g/18_symlist.h 1.1 644)
+++ bison-1_5.27(w)/src/symlist.h Thu, 27 Jun 2002 18:52:15 -0700 hilfingr
(glrbison/g/18_symlist.h 1.1 644)
@@ -35,6 +35,8 @@ typedef struct symbol_list_s
location_t action_location;
symbol_t *ruleprec;
+ int dprec;
+ int merger;
} symbol_list_t;
Index: bison-1_5.27/src/symlist.c
--- bison-1_5.27/src/symlist.c Mon, 17 Jun 2002 14:10:36 -0700 hilfingr
(glrbison/g/19_symlist.c 1.1 644)
+++ bison-1_5.27(w)/src/symlist.c Thu, 27 Jun 2002 18:52:15 -0700 hilfingr
(glrbison/g/19_symlist.c 1.1 644)
@@ -36,6 +36,8 @@ symbol_list_new (symbol_t *sym, location
res->location = location;
res->action = NULL;
res->ruleprec = NULL;
+ res->dprec = 0;
+ res->merger = 0;
return res;
}
Index: bison-1_5.27/data/Makefile.in
--- bison-1_5.27/data/Makefile.in Thu, 27 Jun 2002 10:13:05 -0700 hilfingr
(glrbison/g/26_Makefile.i 1.1 644)
+++ bison-1_5.27(w)/data/Makefile.in Thu, 27 Jun 2002 18:52:14 -0700 hilfingr
(glrbison/g/26_Makefile.i 1.1 644)
@@ -110,7 +110,7 @@ am__include = @am__include@
am__quote = @am__quote@
install_sh = @install_sh@
-dist_pkgdata_DATA = bison.simple bison.c++ bison.glr
+dist_pkgdata_DATA = yacc.c lalr1.cc glr.c
m4sugardir = $(pkgdatadir)/m4sugar
dist_m4sugar_DATA = m4sugar/m4sugar.m4 m4sugar/version.m4
Index: bison-1_5.27/data/glr.c
--- bison-1_5.27/data/glr.c Thu, 27 Jun 2002 19:37:29 -0700 hilfingr ()
+++ bison-1_5.27(w)/data/glr.c Thu, 27 Jun 2002 18:50:49 -0700 hilfingr
(glrbison/e/14_glr-parser 1.27.1.12 644)
@@ -0,0 +1,1885 @@
+m4_divert(-1) -*- YYC -*-
+
+# b4_sint_type(MAX)
+# -----------------
+# Return the smallest signed int type able to handle the number MAX.
+m4_define([b4_sint_type],
+[m4_if(m4_eval([$1 <= 127]), [1], [signed char],
+ m4_eval([$1 <= 32767]), [1], [signed short],
+ [signed int])])
+
+# b4_uint_type(MAX)
+# -----------------
+# Return the smallest unsigned int type able to handle the number MAX.
+m4_define([b4_uint_type],
+[m4_if(m4_eval([$1 <= 255]), [1], [unsigned char],
+ m4_eval([$1 <= 65535]), [1], [unsigned short],
+ [unsigned int])])
+
+
+# b4_lhs_value([TYPE])
+# --------------------
+# Expansion of $<TYPE>$.
+m4_define([b4_lhs_value],
+[(*yyvalp)[]m4_ifval([$1], [.$1])])
+
+
+# b4_rhs_value(RULE-LENGTH, NUM, [TYPE])
+# --------------------------------------
+# Expansion of $<TYPE>NUM, where the current rule has RULE-LENGTH
+# symbols on RHS.
+m4_define([b4_rhs_value],
+[yyvsp@<:@m4_eval([$2 - $1])@:>@.yystate.yysemantics.yysval[]m4_ifval([$3],
[.$3])])
+
+
+
+## ----------- ##
+## Locations. ##
+## ----------- ##
+
+# b4_location_if(IF-TRUE, IF-FALSE)
+# ---------------------------------
+# Expand IF-TRUE, if locations are used, IF-FALSE otherwise.
+m4_define([b4_location_if],
+[m4_if(b4_locations_flag, [1],
+ [$1],
+ [$2])])
+
+
+# b4_lhs_location()
+# -----------------
+# Expansion of @$.
+m4_define([b4_lhs_location],
+[(*yylocp)])
+
+
+# b4_rhs_location(RULE-LENGTH, NUM)
+# ---------------------------------
+# Expansion of @NUM, where the current rule has RULE-LENGTH symbols
+# on RHS.
+m4_define([b4_rhs_location],
+[yyvsp@<:@m4_eval([$2 - $1])@:>@.yystate.yyloc])
+
+
+
+## -------------- ##
+## %pure-parser. ##
+## -------------- ##
+
+# b4_pure_if(IF-TRUE, IF-FALSE)
+# -----------------------------
+# Expand IF-TRUE, if %pure-parser, IF-FALSE otherwise.
+m4_define([b4_pure_if],
+[m4_if(b4_pure, [1],
+ [$1],
+ [$2])])
+
+
+## ------------------- ##
+## Output file names. ##
+## ------------------- ##
+
+m4_define_default([b4_input_suffix], [.y])
+
+m4_define_default([b4_output_parser_suffix],
+[m4_translit(b4_input_suffix, [yY], [cC])])
+
+m4_define_default([b4_output_parser_name],
+[b4_output_prefix[]b4_output_infix[]b4_output_parser_suffix[]])
+
+
+m4_define_default([b4_output_header_suffix],
+[m4_translit(b4_input_suffix, [yY], [hH])])
+
+m4_define_default([b4_output_header_name],
+[b4_output_prefix[]b4_output_infix[]b4_output_header_suffix[]])
+
+m4_define_default([b4_header_guard],
+ [m4_bpatsubst(m4_toupper([BISON_]b4_output_header_name),
+ [[^ABCDEFGHIJKLMNOPQRSTUVWXYZ]], [_])])
+
+
+## ------------------------- ##
+## Assigning token numbers. ##
+## ------------------------- ##
+
+# b4_token_define(TOKEN-NAME, TOKEN-NUMBER)
+# -----------------------------------------
+# Output the definition of this token as #define.
+m4_define([b4_token_define],
+[#define $1 $2
+])
+
+
+# b4_token_enum(TOKEN-NAME, TOKEN-NUMBER)
+# ---------------------------------------
+# Output the definition of this token as an enum.
+m4_define([b4_token_enum],
+[$1 = $2])
+
+
+# b4_token_defines(LIST-OF-PAIRS-TOKEN-NAME-TOKEN-NUMBER)
+# -------------------------------------------------------
+# Output the definition of the tokens (if there are) as enums and #define.
+m4_define([b4_token_defines],
+[m4_if(address@hidden, [[]], [],
+[/* Tokens. */
+#ifndef YYTOKENTYPE
+# if defined (__STDC__) || defined (__cplusplus)
+ /* Put the tokens into the symbol table, so that GDB and other debuggers
+ know about them. */
+ enum yytokentype {
+m4_map_sep([ b4_token_enum], [,
+],
+ address@hidden)
+ };
+# endif
+ /* POSIX requires `int' for tokens in interfaces. */
+# define YYTOKENTYPE int
+#endif /* !YYTOKENTYPE */
+m4_map([b4_token_define], address@hidden)
+])
+])
+
+
+m4_divert(0)dnl
+#output "b4_output_parser_name"
+[/* Skeleton parser for GLR parsing with Bison,
+ Copyright (C) 2002 Free Software Foundation, Inc.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+/* As a special exception, when this file is copied by Bison into a
+ Bison output file, you may use that output file without restriction.
+ This special exception was added by the Free Software Foundation
+ in version 1.24 of Bison. */
+
+/* This is the parser code for GLR (Generalized LR) parser. */
+
+/* FIXME: minimize these */
+#include <stdlib.h>
+#include <setjmp.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <assert.h>
+
+/* Identify Bison output. */
+#define YYBISON 1
+
+/* Pure parsers. */
+#define YYPURE ]b4_pure[
+
+/* Using locations. */
+#define YYLSP_NEEDED ]b4_locations_flag[
+
+]m4_if(b4_prefix[], [yy], [],
+[/* If NAME_PREFIX is specified substitute the variables and functions
+ names. */
+#define yyparse b4_prefix[]parse
+#define yylex b4_prefix[]lex
+#define yyerror b4_prefix[]error
+#define yylval b4_prefix[]lval
+#define yychar b4_prefix[]char
+#define yydebug b4_prefix[]debug
+#define yynerrs b4_prefix[]nerrs
+b4_location_if([#define yylloc b4_prefix[]lloc])])
+
+/* Copy the first part of user declarations. */
+b4_pre_prologue
+
+b4_token_defines(b4_tokens)[
+
+/* Enabling traces. */
+#ifndef YYDEBUG
+# define YYDEBUG ]b4_debug[
+#endif
+
+/* Enabling verbose error messages. */
+#ifdef YYERROR_VERBOSE
+# undef YYERROR_VERBOSE
+# define YYERROR_VERBOSE 1
+#else
+# define YYERROR_VERBOSE ]b4_error_verbose[
+#endif
+
+#ifndef YYSTYPE
+]m4_ifdef([b4_stype],
+[#line b4_stype_line "b4_filename"
+typedef union b4_stype yystype;
+/* Line __line__ of __file__. */
+#line __oline__ "__ofile__"],
+[typedef int yystype;])[
+# define YYSTYPE yystype
+# define YYSTYPE_IS_TRIVIAL 1
+#endif
+
+#ifndef YYLTYPE
+typedef struct yyltype
+{
+]b4_location_if([
+ int yyfirst_line;
+ int yyfirst_column;
+ int yylast_line;
+ int yylast_column;])[
+} yyltype;
+# define YYLTYPE ]b4_ltype[
+# define YYLTYPE_IS_TRIVIAL 1
+#endif
+
+/* Default (constant) values used for initialization for null
+ right-hand sides. Unlike the standard bison.simple template,
+ here we set the default values of the $$ and $@ to zeroed-out
+ values. Since the default value of these quantities is undefined,
+ this behavior is technically correct. */
+static YYSTYPE yyval_default;
+static YYLTYPE yyloc_default;
+
+/* Copy the second part of user declarations. */
+]b4_post_prologue[
+
+]/* Line __line__ of __file__. */
+#line __oline__ "__ofile__"
+[
+#if ! defined (__cplusplus)
+ typedef char bool;
+# define yytrue 1
+# define yyfalse 0
+#endif
+
+#if ! defined (yy__GNUC__)
+# define inline
+#endif
+
+/* YYFINAL -- State number of the termination state. */
+#define YYFINAL ]b4_final[
+#define YYFLAG ]b4_flag[
+#define YYLAST ]b4_last[
+
+/* YYNTOKENS -- Number of terminals. */
+#define YYNTOKENS ]b4_ntokens[
+/* YYNNTS -- Number of nonterminals. */
+#define YYNNTS ]b4_nnts[
+/* YYNRULES -- Number of rules. */
+#define YYNRULES ]b4_nrules[
+/* YYNRULES -- Number of states. */
+#define YYNSTATES ]b4_nstates[
+/* YYMAXRHS -- Maximum number of symbols on right-hand side of rule. */
+#define YYMAXRHS ]b4_r2_max[
+
+/* YYTRANSLATE(X) -- Bison symbol number corresponding to X. */
+#define YYUNDEFTOK ]b4_undef_token_number[
+#define YYMAXUTOK ]b4_user_token_number_max[
+
+#define YYTRANSLATE(YYX) \
+ ((unsigned)(YYX) <= YYMAXUTOK ? yytranslate[YYX] : YYUNDEFTOK)
+
+/* YYTRANSLATE[YYLEX] -- Bison symbol number corresponding to YYLEX. */
+static const ]b4_uint_type(b4_translate_max)[ yytranslate[] =
+{
+ ]b4_translate[
+};
+
+#if YYDEBUG
+/* YYPRHS[YYN] -- Index of the first RHS symbol of rule number YYN in
+ YYRHS. */
+static const ]b4_uint_type(b4_prhs_max)[ yyprhs[] =
+{
+ ]b4_prhs[
+};
+
+/* YYRHS -- A `-1'-separated list of the rules' RHS. */
+static const ]b4_sint_type(b4_rhs_max)[ yyrhs[] =
+{
+ ]b4_rhs[
+};
+
+/* YYRLINE[YYN] -- source line where rule number YYN was defined. */
+static const ]b4_uint_type(b4_rline_max)[ yyrline[] =
+{
+ ]b4_rline[
+};
+#endif
+
+#if (YYDEBUG) || YYERROR_VERBOSE
+/* YYTNME[SYMBOL-NUM] -- String name of the symbol SYMBOL-NUM.
+ First, the terminals, then, starting at YYNTOKENS, nonterminals. */
+static const char *const yytname[] =
+{
+ ]b4_tname[
+};
+
+#define yytname_size (sizeof (yytname) / sizeof (yytname[0]))
+#endif
+
+/* YYR1[YYN] -- Symbol number of symbol that rule YYN derives. */
+static const ]b4_uint_type(b4_r1_max)[ yyr1[] =
+{
+ ]b4_r1[
+};
+
+/* YYR2[YYN] -- Number of symbols composing right hand side of rule YYN. */
+static const ]b4_uint_type(b4_r2_max)[ yyr2[] =
+{
+ ]b4_r2[
+};
+
+/* YYDPREC[RULE-NUM] -- Dynamic precedence of rule #RULE-NUM (0 if none). */
+static const short yydprec[] =
+{
+ ]b4_dprec[
+};
+
+/* YYMERGER[RULE-NUM] -- Index of merging function for rule #RULE-NUM. */
+static const short yymerger[] =
+{
+ ]b4_merger[
+};
+
+/* YYDEFACT[S] -- default rule to reduce with in state S when YYTABLE
+ doesn't specify something else to do. Zero means the default is an
+ error. */
+static const short yydefact[] =
+{
+ ]b4_defact[
+};
+
+/* YYPGOTO[NTERM-NUM]. */
+static const short yydefgoto[] =
+{
+ ]b4_defgoto[
+};
+
+/* YYPACT[STATE-NUM] -- Index in YYTABLE of the portion describing
+ STATE-NUM. */
+static const short yypact[] =
+{
+ ]b4_pact[
+};
+
+/* YYPGOTO[NTERM-NUM]. */
+static const short yypgoto[] =
+{
+ ]b4_pgoto[
+};
+
+/* YYTABLE[YYPACT[STATE-NUM]]. What to do in state STATE-NUM. If
+ positive, shift that token. If negative, reduce the rule which
+ number is the opposite. If zero, do what YYDEFACT says. */
+static const short yytable[] =
+{
+ ]b4_table[
+};
+
+/* YYCONFLP[YYPACT[STATE-NUM]] -- pointer into yyconfl of start of list
+ of conflicting reductions corresponding to action entry for state
+ STATE-NUM in yytable. 0 means no conflicts. The list in yyconfl
+ is terminated by a rule number of 0. */
+static const short yyconflp[] =
+{
+ ]b4_conflict_list_heads[
+};
+
+/* YYCONFL[I] -- lists of conflicting rule numbers, each terminated
+ by 0, pointed into by YYCONFLP. */
+static const short yyconfl[] =
+{
+ ]b4_conflicting_rules[
+};
+
+static const short yycheck[] =
+{
+ ]b4_check[
+};
+
+
+/* The user can define YYPARSE_PARAM as the name of an argument to be passed
+ into yyparse. The argument should have type void *.
+ It should actually point to an object.
+ Grammar actions can access the variable by casting it
+ to the proper pointer type. */
+
+#ifdef YYPARSE_PARAM
+# define YYPARSE_PARAM_ARG void *YYPARSE_PARAM
+#else /* !YYPARSE_PARAM */
+# define YYPARSE_PARAM_ARG void
+#endif /* !YYPARSE_PARAM */
+
+/* Prevent warning if -Wstrict-prototypes. */
+#ifdef __GNUC__
+# ifdef YYPARSE_PARAM
+int yyparse (void *);
+# else
+int yyparse (void);
+# endif
+#endif
+
+/* Error token number */
+#define YYTERROR 1
+
+/* YYLLOC_DEFAULT -- Compute the default location (before the actions
+ are run). */
+
+#define YYRHSLOC(yyRhs,YYK) (yyRhs[YYK].yystate.yyloc)
+
+#ifndef YYLLOC_DEFAULT
+# define YYLLOC_DEFAULT(yyCurrent, yyRhs, YYN) \
+ yyCurrent.yyfirst_line = YYRHSLOC(yyRhs,1).yyfirst_line; \
+ yyCurrent.yyfirst_column = YYRHSLOC(yyRhs,1).yyfirst_column; \
+ yyCurrent.yylast_line = YYRHSLOC(yyRhs,YYN).yylast_line; \
+ yyCurrent.yylast_column = YYRHSLOC(yyRhs,YYN).yylast_column;
+#endif
+
+/* YYLEX -- calling `yylex' with the right arguments. */
+
+]b4_pure_if(
+[
+#ifdef YYLEX_PARAM
+# define YYLEX yylex (yylvalp, b4_location_if([yyllocp, ])YYLEX_PARAM)
+#else
+# define YYLEX yylex (yylvalp[]b4_location_if([, yyllocp]))
+#endif],
+[#define YYLEX yylex ()])
+
+b4_pure_if(
+[
+#undef yynerrs
+#define yynerrs (yystack->yyerrcnt)
+#undef yychar
+#define yychar (yystack->yyrawchar)],
+[YYSTYPE yylval;
+
+YYLTYPE yylloc;
+
+int yynerrs;
+int yychar;])[
+
+static const int YYEOF = 0;
+static const int YYEMPTY = -2;
+
+typedef enum { yyok, yyaccept, yyabort, yyerr } YYRESULTTAG;
+
+#define YYCHK(YYE) \
+ do { YYRESULTTAG yyflag = YYE; if (yyflag != yyok) return yyflag; }
\
+ while (0)
+
+#if YYDEBUG
+
+#if ! defined (YYFPRINTF)
+# define YYFPRINTF fprintf
+#endif
+
+# define YYDPRINTF(Args) \
+do { \
+ if (yydebug) \
+ YYFPRINTF Args; \
+} while (0)
+/* Nonzero means print parse trace. It is left uninitialized so that
+ multiple parsers can coexist. */
+int yydebug;
+#else /* !YYDEBUG */
+# define YYDPRINTF(Args)
+#endif /* !YYDEBUG */
+
+/* YYINITDEPTH -- initial size of the parser's stacks. */
+#ifndef YYINITDEPTH
+# define YYINITDEPTH ]b4_initdepth[
+#endif
+
+/* YYMAXDEPTH -- maximum size the stacks can grow to (effective only
+ if the built-in stack extension method is used).
+
+ Do not make this value too large; the results are undefined if
+ SIZE_MAX < YYMAXDEPTH * sizeof (GLRStackItem)
+ evaluated with infinite-precision integer arithmetic. */
+
+#if YYMAXDEPTH == 0
+# undef YYMAXDEPTH
+#endif
+
+#ifndef YYMAXDEPTH
+# define YYMAXDEPTH ]b4_maxdepth[
+#endif
+
+/* Minimum number of free items on the stack allowed after an
+ allocation. This is to allow allocation and initialization
+ to be completed by functions that call expandGLRStack before the
+ stack is expanded, thus insuring that all necessary pointers get
+ properly redirected to new data. */
+#define YYHEADROOM 2
+
+#if ! defined (YYSTACKEXPANDABLE) \
+ && (! defined (__cplusplus) || (YYLTYPE_IS_TRIVIAL && YYSTYPE_IS_TRIVIAL))
+#define YYSTACKEXPANDABLE 1
+#else
+#define YYSTACKEXPANDABLE 0
+#endif
+
+/** State numbers, as in LALR(1) machine */
+typedef int yyStateNum;
+
+/** Rule numbers, as in LALR(1) machine */
+typedef int yyRuleNum;
+
+/** Grammar symbol */
+typedef short yySymbol;
+
+/** Item references, as in LALR(1) machine */
+typedef short yyItemNum;
+
+typedef struct yyGLRState yyGLRState;
+typedef struct yySemanticOption yySemanticOption;
+typedef union yyGLRStackItem yyGLRStackItem;
+typedef struct yyGLRStack yyGLRStack;
+typedef struct yyGLRStateSet yyGLRStateSet;
+
+struct yyGLRState {
+ bool yyisState;
+ bool yyresolved;
+ yyStateNum yylrState;
+ yyGLRState* yypred;
+ size_t yyposn;
+ union {
+ yySemanticOption* yyfirstVal;
+ YYSTYPE yysval;
+ } yysemantics;
+ YYLTYPE yyloc;
+};
+
+struct yyGLRStateSet {
+ yyGLRState** yystates;
+ size_t yysize, yycapacity;
+};
+
+struct yySemanticOption {
+ bool yyisState;
+ yyRuleNum yyrule;
+ yyGLRState* yystate;
+ yySemanticOption* yynext;
+};
+
+union yyGLRStackItem {
+ yyGLRState yystate;
+ yySemanticOption yyoption;
+};
+
+struct yyGLRStack {
+ int yyerrflag;
+ int yyerrState;
+]b4_pure_if(
+[
+ int yyerrcnt;
+ int yyrawchar;
+])[
+ yySymbol* yytokenp;
+ jmp_buf yyexception_buffer;
+ yyGLRStackItem* yyitems;
+ yyGLRStackItem* yynextFree;
+ int yyspaceLeft;
+ yyGLRState* yysplitPoint;
+ yyGLRState* yylastDeleted;
+ yyGLRStateSet yytops;
+};
+
+static void yyinitGLRStack (yyGLRStack* yystack, size_t yysize);
+static void yyexpandGLRStack (yyGLRStack* yystack);
+static void yyfreeGLRStack (yyGLRStack* yystack);
+
+static void
+yyFail (yyGLRStack* yystack, const char* yyformat, ...)
+{
+ if (yyformat != NULL)
+ {
+ char yymsg[256];
+ va_list yyap;
+ va_start (yyap, yyformat);
+ yystack->yyerrflag = 1;
+ vsprintf (yymsg, yyformat, yyap);
+ yyerror (yymsg);
+ }
+ longjmp (yystack->yyexception_buffer, 1);
+}
+
+#if YYDEBUG || YYERROR_VERBOSE
+/** A printable representation of TOKEN. Valid until next call to
+ * tokenName. */
+static inline const char*
+yytokenName (yySymbol yytoken)
+{
+ return yytname[yytoken];
+}
+#endif
+
+/** Perform user action for rule number YYN, with RHS length YYRHSLEN,
+ * and top stack item YYVSP. YYLVALP points to place to put semantic
+ * value ($$), and yylocp points to place for location information
+ * (@$). Returns yyok for normal return, yyaccept for YYACCEPT,
+ * yyerr for YYERROR, yyabort for YYABORT. */
+static YYRESULTTAG
+yyuserAction (yyRuleNum yyn, int yyrhslen, yyGLRStackItem* yyvsp,
+ YYSTYPE* yyvalp, YYLTYPE* yylocp, yyGLRStack* yystack)
+{
+ if (yyrhslen == 0)
+ {
+ *yyvalp = yyval_default;
+ *yylocp = yyloc_default;
+ }
+ else
+ {
+ *yyvalp = yyvsp[1-yyrhslen].yystate.yysemantics.yysval;
+ *yylocp = yyvsp[1-yyrhslen].yystate.yyloc;
+ }
+# undef yyval
+# define yyval (*yyvalp)
+# undef yyerrok
+# define yyerrok (yystack->yyerrState = 0)
+# undef YYACCEPT
+# define YYACCEPT return yyaccept
+# undef YYABORT
+# define YYABORT return yyabort
+# undef YYERROR
+# define YYERROR return yyerr
+# undef YYRECOVERING
+# define YYRECOVERING (yystack->yyerrState != 0)
+# undef yyclearin
+# define yyclearin (yychar = *(yystack->yytokenp) = YYEMPTY)
+# undef YYBACKUP
+# define YYBACKUP(Token, Value)
\
+ do { \
+ yyerror ("syntax error: cannot back up"); \
+ YYERROR; \
+ } while (0)
+
+]
+ switch (yyn)
+ {
+ b4_actions
+ }
+
+ return yyok;
+# undef yyval
+# undef yyerrok
+# undef YYABORT
+# undef YYACCEPT
+# undef YYERROR
+# undef YYBACKUP
+# undef yyclearin
+# undef YYRECOVERING
+/* Line __line__ of __file__. */
+#line __oline__ "__ofile__"
+}
+
+
+static YYSTYPE
+yyuserMerge (int yyn, YYSTYPE* yy0, YYSTYPE* yy1)
+{
+ YYSTYPE yyval = *yy0;
+ switch (yyn)
+ {
+ b4_mergers
+ }
+ return yyval;
+}
+[
+ /* Bison grammar-table manipulation */
+
+/** Number of symbols composing the right hand side of rule #RULE. */
+static inline int
+yyrhsLength (yyRuleNum yyrule)
+{
+ return yyr2[yyrule];
+}
+
+/** Left-hand-side symbol for rule #RULE. */
+static inline yySymbol
+yylhsNonterm (yyRuleNum yyrule)
+{
+ return yyr1[yyrule];
+}
+
+/** True iff LR state STATE has only a default reduction (regardless
+ * of token). */
+static inline bool
+yyisDefaultedState (yyStateNum yystate)
+{
+ return yypact[yystate] == YYFLAG;
+}
+
+/** The default reduction for STATE, assuming it has one. */
+static inline yyRuleNum
+yydefaultAction (yyStateNum yystate)
+{
+ return yydefact[yystate];
+}
+
+/** Set *ACTION to the action to take in STATE on seeing TOKEN.
+ * Result R means
+ * R < 0: Reduce on rule -R.
+ * R = 0: Error.
+ * R > 0: Shift to state R.
+ * Set *CONFLICTS to a pointer into yyconfl to 0-terminated list of
+ * conflicting reductions.
+ */
+static inline void
+yygetLRActions (yyStateNum yystate, int yytoken,
+ int* yyaction, const short** yyconflicts)
+{
+ int yyindex = yypact[yystate] + yytoken;
+ if (yyindex < 0 || yyindex > YYLAST || yycheck[yyindex] != yytoken)
+ {
+ *yyaction = -yydefact[yystate];
+ *yyconflicts = yyconfl;
+ }
+ else
+ {
+ *yyaction = yytable[yyindex];
+ *yyconflicts = yyconfl + yyconflp[yyindex];
+ }
+}
+
+static inline yyStateNum
+yyLRgotoState (yyStateNum yystate, yySymbol yylhs)
+{
+ int yyr;
+ yyr = yypgoto[yylhs - YYNTOKENS] + yystate;
+ if (yyr >= 0 && yyr <= YYLAST && yycheck[yyr] == yystate)
+ return yytable[yyr];
+ else
+ return yydefgoto[yylhs - YYNTOKENS];
+}
+
+static inline bool
+yyisShiftAction (int yyaction)
+{
+ return yyaction > 0;
+}
+
+static inline bool
+yyisErrorAction (int yyaction)
+{
+ return yyaction == 0 || yyaction == YYFLAG;
+}
+
+ /* GLRStates */
+
+/** True iff the semantic value of the edge leading to STATE is
+ * resolved. */
+static inline bool
+yyhasResolvedValue (yyGLRState* yystate)
+{
+ return yystate->yyresolved;
+}
+
+void yyaddDeferredAction (yyGLRStack* yystack, yyGLRState* yystate,
+ yyGLRState* yyrhs, yyRuleNum yyrule)
+{
+ yySemanticOption* yynewItem;
+ yynewItem = &yystack->yynextFree->yyoption;
+ yystack->yyspaceLeft -= 1;
+ yystack->yynextFree += 1;
+ yynewItem->yyisState = yyfalse;
+ yynewItem->yystate = yyrhs;
+ yynewItem->yyrule = yyrule;
+ yynewItem->yynext = yystate->yysemantics.yyfirstVal;
+ yystate->yysemantics.yyfirstVal = yynewItem;
+ if (yystack->yyspaceLeft < YYHEADROOM)
+ yyexpandGLRStack (yystack);
+}
+
+ /* GLRStacks */
+
+/** Initialize SET to a singleton set containing an empty stack. */
+static void
+yyinitStateSet (yyGLRStateSet* yyset)
+{
+ yyset->yysize = 1;
+ yyset->yycapacity = 16;
+ yyset->yystates = (yyGLRState**) malloc (16 * sizeof (yyset->yystates[0]));
+ yyset->yystates[0] = NULL;
+}
+
+static void yyfreeStateSet (yyGLRStateSet* yyset)
+{
+ free (yyset->yystates);
+}
+
+/** Initialize STACK to a single empty stack, with total maximum
+ * capacity for all stacks of SIZE. */
+static void
+yyinitGLRStack (yyGLRStack* yystack, size_t yysize)
+{
+ yystack->yyerrflag = 0;
+ yystack->yyerrState = 0;
+ yynerrs = 0;
+ yystack->yyspaceLeft = yysize;
+ yystack->yynextFree = yystack->yyitems =
+ (yyGLRStackItem*) malloc (yysize * sizeof (yystack->yynextFree[0]));
+ yystack->yysplitPoint = NULL;
+ yystack->yylastDeleted = NULL;
+ yyinitStateSet (&yystack->yytops);
+}
+
+#define YYRELOC(YYFROMITEMS,YYTOITEMS,YYX,YYTYPE) \
+ &((YYTOITEMS) - ((YYFROMITEMS) - (yyGLRStackItem*) (YYX)))->YYTYPE
+
+/** If STACK is expandable, extend it. WARNING: Pointers into the
+ stack from outside should be considered invalid after this call.
+ We always expand when there are 1 or fewer items left AFTER an
+ allocation, so that we can avoid having external pointers exist
+ across an allocation. */
+static void
+yyexpandGLRStack (yyGLRStack* yystack)
+{
+#if YYSTACKEXPANDABLE
+ yyGLRStack yynewStack;
+ yyGLRStackItem* yyp0, *yyp1;
+ size_t yysize, yynewSize;
+ size_t yyn;
+ yysize = yystack->yynextFree - yystack->yyitems;
+ if (yysize >= YYMAXDEPTH)
+ yyFail (yystack, "parsing stack overflow (%d items)", yysize);
+ yynewSize = 2*yysize;
+ if (yynewSize > YYMAXDEPTH)
+ yynewSize = YYMAXDEPTH;
+ yyinitGLRStack (&yynewStack, yynewSize);
+ for (yyp0 = yystack->yyitems, yyp1 = yynewStack.yyitems, yyn = yysize;
+ yyn > 0;
+ yyn -= 1, yyp0 += 1, yyp1 += 1)
+ {
+ *yyp1 = *yyp0;
+ if (*(bool*) yyp0)
+ {
+ yyGLRState* yys0 = &yyp0->yystate;
+ yyGLRState* yys1 = &yyp1->yystate;
+ if (yys0->yypred != NULL)
+ yys1->yypred =
+ YYRELOC (yyp0, yyp1, yys0->yypred, yystate);
+ if (! yys0->yyresolved && yys0->yysemantics.yyfirstVal != NULL)
+ yys1->yysemantics.yyfirstVal =
+ YYRELOC(yyp0, yyp1, yys0->yysemantics.yyfirstVal, yyoption);
+ }
+ else
+ {
+ yySemanticOption* yyv0 = &yyp0->yyoption;
+ yySemanticOption* yyv1 = &yyp1->yyoption;
+ if (yyv0->yystate != NULL)
+ yyv1->yystate = YYRELOC (yyp0, yyp1, yyv0->yystate, yystate);
+ if (yyv0->yynext != NULL)
+ yyv1->yynext = YYRELOC (yyp0, yyp1, yyv0->yynext, yyoption);
+ }
+ }
+ if (yystack->yysplitPoint != NULL)
+ yystack->yysplitPoint = YYRELOC (yystack->yyitems, yynewStack.yyitems,
+ yystack->yysplitPoint, yystate);
+
+ for (yyn = 0; yyn < yystack->yytops.yysize; yyn += 1)
+ if (yystack->yytops.yystates[yyn] != NULL)
+ yystack->yytops.yystates[yyn] =
+ YYRELOC (yystack->yyitems, yynewStack.yyitems,
+ yystack->yytops.yystates[yyn], yystate);
+ free (yystack->yyitems);
+ yystack->yyitems = yynewStack.yyitems;
+ yystack->yynextFree = yynewStack.yynextFree + yysize;
+ yystack->yyspaceLeft = yynewStack.yyspaceLeft - yysize;
+
+#else
+
+ yyFail (yystack, "parsing stack overflow (%d items)", yysize);
+
+#endif
+}
+
+static void
+yyfreeGLRStack (yyGLRStack* yystack)
+{
+ free (yystack->yyitems);
+ yyfreeStateSet (&yystack->yytops);
+}
+
+/** Assuming that S is a GLRState somewhere on STACK, update the
+ * splitpoint of STACK, if needed, so that it is at least as deep as
+ * S. */
+static inline void
+yyupdateSplit (yyGLRStack* yystack, yyGLRState* yys)
+{
+ if (yystack->yysplitPoint != NULL && yystack->yysplitPoint > yys)
+ yystack->yysplitPoint = yys;
+}
+
+/** Invalidate stack #K in STACK. */
+static inline void
+yymarkStackDeleted (yyGLRStack* yystack, int yyk)
+{
+ if (yystack->yytops.yystates[yyk] != NULL)
+ yystack->yylastDeleted = yystack->yytops.yystates[yyk];
+ yystack->yytops.yystates[yyk] = NULL;
+}
+
+/** Undelete the last stack that was marked as deleted. Can only be
+ done once after a deletion, and only when all other stacks have
+ been deleted. */
+static void
+yyundeleteLastStack (yyGLRStack* yystack)
+{
+ if (yystack->yylastDeleted == NULL || yystack->yytops.yysize != 0)
+ return;
+ yystack->yytops.yystates[0] = yystack->yylastDeleted;
+ yystack->yytops.yysize = 1;
+ YYDPRINTF ((stderr, "Restoring last deleted stack as stack #0.\n"));
+ yystack->yylastDeleted = NULL;
+}
+
+static inline void
+yyremoveDeletes (yyGLRStack* yystack)
+{
+ int yyi, yyj;
+ yyi = yyj = 0;
+ while (yyj < yystack->yytops.yysize)
+ {
+ if (yystack->yytops.yystates[yyi] == NULL)
+ {
+ if (YYDEBUG && yyi == yyj)
+ YYDPRINTF ((stderr, "Removing dead stacks.\n"));
+ yystack->yytops.yysize -= 1;
+ }
+ else
+ {
+ yystack->yytops.yystates[yyj] = yystack->yytops.yystates[yyi];
+ if (yyj != yyi)
+ YYDPRINTF ((stderr, "Rename stack %d -> %d.\n", yyi, yyj));
+ yyj += 1;
+ }
+ yyi += 1;
+ }
+}
+
+/** Shift to a new state on stack #K of STACK, corresponding to LR state
+ * LRSTATE, at input position POSN, with (resolved) semantic value SVAL. */
+static inline void
+yyglrShift (yyGLRStack* yystack, int yyk, yyStateNum yylrState, size_t yyposn,
+ YYSTYPE yysval, YYLTYPE* yylocp)
+{
+ yyGLRStackItem* yynewItem;
+
+ yynewItem = yystack->yynextFree;
+ yystack->yynextFree += 1;
+ yystack->yyspaceLeft -= 1;
+ yynewItem->yystate.yyisState = yytrue;
+ yynewItem->yystate.yylrState = yylrState;
+ yynewItem->yystate.yyposn = yyposn;
+ yynewItem->yystate.yyresolved = yytrue;
+ yynewItem->yystate.yypred = yystack->yytops.yystates[yyk];
+ yystack->yytops.yystates[yyk] = &yynewItem->yystate;
+ yynewItem->yystate.yysemantics.yysval = yysval;
+ yynewItem->yystate.yyloc = *yylocp;
+ if (yystack->yyspaceLeft < YYHEADROOM)
+ yyexpandGLRStack (yystack);
+}
+
+/** Shift to a new state on stack #K of STACK, to a new state
+ * corresponding to LR state LRSTATE, at input position POSN, with
+ * the (unresolved) semantic value of RHS under the action for RULE. */
+static inline void
+yyglrShiftDefer (yyGLRStack* yystack, int yyk, yyStateNum yylrState,
+ size_t yyposn, yyGLRState* yyrhs, yyRuleNum yyrule)
+{
+ yyGLRStackItem* yynewItem;
+
+ yynewItem = yystack->yynextFree;
+ yynewItem->yystate.yyisState = yytrue;
+ yynewItem->yystate.yylrState = yylrState;
+ yynewItem->yystate.yyposn = yyposn;
+ yynewItem->yystate.yyresolved = yyfalse;
+ yynewItem->yystate.yypred = yystack->yytops.yystates[yyk];
+ yynewItem->yystate.yysemantics.yyfirstVal = NULL;
+ yystack->yytops.yystates[yyk] = &yynewItem->yystate;
+ yystack->yynextFree += 1;
+ yystack->yyspaceLeft -= 1;
+ yyaddDeferredAction (yystack, &yynewItem->yystate, yyrhs, yyrule);
+}
+
+/** Pop the symbols consumed by reduction #RULE from the top of stack
+ * #K of STACK, and perform the appropriate semantic action on their
+ * semantic values. Assumes that all ambiguities in semantic values
+ * have been previously resolved. Set *VALP to the resulting value,
+ * and *LOCP to the computed location (if any). Return value is as
+ * for userAction. */
+static inline int
+yydoAction (yyGLRStack* yystack, int yyk, yyRuleNum yyrule,
+ YYSTYPE* yyvalp, YYLTYPE* yylocp)
+{
+ int yynrhs = yyrhsLength (yyrule);
+
+ if (yystack->yysplitPoint == NULL)
+ {
+ /* Standard special case: single stack. */
+ yyGLRStackItem* yyrhs = (yyGLRStackItem*) yystack->yytops.yystates[yyk];
+ assert (yyk == 0);
+ yystack->yynextFree -= yynrhs;
+ yystack->yyspaceLeft += yynrhs;
+ yystack->yytops.yystates[0] = & yystack->yynextFree[-1].yystate;
+ if (yynrhs == 0)
+ {
+ *yyvalp = yyval_default;
+ *yylocp = yyloc_default;
+ }
+ else
+ {
+ *yyvalp = yyrhs[1-yynrhs].yystate.yysemantics.yysval;
+ *yylocp = yyrhs[1-yynrhs].yystate.yyloc;
+ }
+ return yyuserAction (yyrule, yynrhs, yyrhs, yyvalp, yylocp, yystack);
+ }
+ else
+ {
+ int yyi;
+ yyGLRState* yys;
+ yyGLRStackItem yyrhsVals[YYMAXRHS];
+ for (yyi = yynrhs-1, yys = yystack->yytops.yystates[yyk]; yyi >= 0;
+ yyi -= 1, yys = yys->yypred)
+ {
+ assert (yys->yypred != NULL);
+ yyrhsVals[yyi].yystate.yyresolved = yytrue;
+ yyrhsVals[yyi].yystate.yysemantics.yysval = yys->yysemantics.yysval;
+ yyrhsVals[yyi].yystate.yyloc = yys->yyloc;
+ }
+ yyupdateSplit (yystack, yys);
+ yystack->yytops.yystates[yyk] = yys;
+ if (yynrhs == 0)
+ {
+ *yyvalp = yyval_default;
+ *yylocp = yyloc_default;
+ }
+ else
+ {
+ *yyvalp = yyrhsVals[0].yystate.yysemantics.yysval;
+ *yylocp = yyrhsVals[0].yystate.yyloc;
+ }
+ return yyuserAction (yyrule, yynrhs, yyrhsVals + (yynrhs-1),
+ yyvalp, yylocp, yystack);
+ }
+}
+
+/** Pop items off stack #K of STACK according to grammar rule RULE,
+ * and push back on the resulting nonterminal symbol. Perform the
+ * semantic action associated with RULE and store its value with the
+ * newly pushed state, if FORCEEVAL or if STACK is currently
+ * unambiguous. Otherwise, store the deferred semantic action with
+ * the new state. If the new state would have an identical input
+ * position, LR state, and predecessor to an existing state on the stack,
+ * it is identified with that existing state, eliminating stack #K from
+ * the STACK. In this case, the (necessarily deferred) semantic value is
+ * added to the options for the existing state's semantic value.
+ */
+static inline YYRESULTTAG
+yyglrReduce (yyGLRStack* yystack, int yyk, yyRuleNum yyrule, bool yyforceEval)
+{
+ int yyposn = yystack->yytops.yystates[yyk]->yyposn;
+
+ if (yyforceEval || yystack->yysplitPoint == NULL)
+ {
+ YYSTYPE yysval;
+ YYLTYPE yyloc;
+
+ YYCHK (yydoAction (yystack, yyk, yyrule, &yysval, &yyloc));
+ yyglrShift (yystack, yyk,
+ yyLRgotoState (yystack->yytops.yystates[yyk]->yylrState,
+ yylhsNonterm (yyrule)),
+ yyposn, yysval, &yyloc);
+ YYDPRINTF ((stderr, "Reduced stack %d by rule #%d. Now in state %d.\n",
+ yyk, yyrule-1, yystack->yytops.yystates[yyk]->yylrState));
+ }
+ else
+ {
+ int yyi, yyn;
+ yyGLRState* yys, *yys0 = yystack->yytops.yystates[yyk];
+ yyStateNum yynewLRState;
+
+ for (yys = yystack->yytops.yystates[yyk], yyn = yyrhsLength (yyrule);
+ yyn > 0; yyn -= 1)
+ {
+ yys = yys->yypred;
+ assert (yys != NULL);
+ }
+ yyupdateSplit (yystack, yys);
+ yynewLRState = yyLRgotoState (yys->yylrState, yylhsNonterm (yyrule));
+ YYDPRINTF ((stderr,
+ "Reduced stack %d by rule #%d; action deferred. "
+ "Now in state %d.\n",
+ yyk, yyrule-1, yynewLRState));
+ for (yyi = 0; yyi < yystack->yytops.yysize; yyi += 1)
+ if (yyi != yyk && yystack->yytops.yystates[yyi] != NULL)
+ {
+ yyGLRState* yyp, *yysplit = yystack->yysplitPoint;
+ yyp = yystack->yytops.yystates[yyi];
+ while (yyp != yys && yyp != yysplit && yyp->yyposn >= yyposn)
+ {
+ if (yyp->yylrState == yynewLRState && yyp->yypred == yys)
+ {
+ yyaddDeferredAction (yystack, yyp, yys0, yyrule);
+ yymarkStackDeleted (yystack, yyk);
+ YYDPRINTF ((stderr, "Merging stack %d into stack %d.\n",
+ yyk, yyi));
+ return 0;
+ }
+ yyp = yyp->yypred;
+ }
+ }
+ yystack->yytops.yystates[yyk] = yys;
+ yyglrShiftDefer (yystack, yyk, yynewLRState, yyposn, yys0, yyrule);
+ }
+ return 0;
+}
+
+static int
+yysplitStack (yyGLRStack* yystack, int yyk)
+{
+ if (yystack->yysplitPoint == NULL)
+ {
+ assert (yyk == 0);
+ yystack->yysplitPoint = yystack->yytops.yystates[yyk];
+ }
+ if (yystack->yytops.yysize >= yystack->yytops.yycapacity)
+ {
+ yystack->yytops.yycapacity *= 2;
+ yystack->yytops.yystates =
+ (yyGLRState**) realloc (yystack->yytops.yystates,
+ yystack->yytops.yycapacity
+ * sizeof (yyGLRState*));
+ }
+ yystack->yytops.yystates[yystack->yytops.yysize]
+ = yystack->yytops.yystates[yyk];
+ yystack->yytops.yysize += 1;
+ return yystack->yytops.yysize-1;
+}
+
+/** True iff Y0 and Y1 represent identical options at the top level.
+ * That is, they represent the same rule applied to RHS symbols
+ * that produce the same terminal symbols. */
+static bool
+yyidenticalOptions (yySemanticOption* yyy0, yySemanticOption* yyy1)
+{
+ if (yyy0->yyrule == yyy1->yyrule)
+ {
+ yyGLRState *yys0, *yys1;
+ int yyn;
+ for (yys0 = yyy0->yystate, yys1 = yyy1->yystate,
+ yyn = yyrhsLength (yyy0->yyrule);
+ yyn > 0;
+ yys0 = yys0->yypred, yys1 = yys1->yypred, yyn -= 1)
+ if (yys0->yyposn != yys1->yyposn)
+ return yyfalse;
+ return yytrue;
+ }
+ else
+ return yyfalse;
+}
+
+/** Assuming identicalOptions (Y0,Y1), (destructively) merge the
+ * alternative semantic values for the RHS-symbols of Y1 into the
+ * corresponding semantic value sets of the symbols of Y0. */
+static void
+yymergeOptionSets (yySemanticOption* yyy0, yySemanticOption* yyy1)
+{
+ yyGLRState *yys0, *yys1;
+ int yyn;
+ for (yys0 = yyy0->yystate, yys1 = yyy1->yystate,
+ yyn = yyrhsLength (yyy0->yyrule);
+ yyn > 0;
+ yys0 = yys0->yypred, yys1 = yys1->yypred, yyn -= 1)
+ if (yys0 == yys1)
+ break;
+ else if (! yys0->yyresolved && ! yys1->yyresolved)
+ {
+ yySemanticOption* yyz;
+ for (yyz = yys0->yysemantics.yyfirstVal; yyz->yynext != NULL;
+ yyz = yyz->yynext)
+ ;
+ yyz->yynext = yys1->yysemantics.yyfirstVal;
+ }
+}
+
+/** Y0 and Y1 represent two possible actions to take in a given
+ * parsing state; return 0 if no combination is possible,
+ * 1 if user-mergeable, 2 if Y0 is preferred, 3 if Y1 is preferred. */
+static int
+yypreference (yySemanticOption* yyy0, yySemanticOption* yyy1)
+{
+ yyRuleNum yyr0 = yyy0->yyrule, yyr1 = yyy1->yyrule;
+ int yyp0 = yydprec[yyr0], yyp1 = yydprec[yyr1];
+
+ if (yyp0 == yyp1)
+ {
+ if (yymerger[yyr0] == 0 || yymerger[yyr0] != yymerger[yyr1])
+ return 0;
+ else
+ return 1;
+ }
+ if (yyp0 == 0 || yyp1 == 0)
+ return 0;
+ if (yyp0 < yyp1)
+ return 3;
+ if (yyp0 > yyp1)
+ return 2;
+ return 0;
+}
+
+static YYRESULTTAG yyresolveValue (yySemanticOption* yyoptionList,
+ yyGLRStack* yystack, YYSTYPE* yyvalp,
+ YYLTYPE* yylocp);
+
+static YYRESULTTAG
+yyresolveStates (yyGLRState* yys, int yyn, yyGLRStack* yystack)
+{
+ YYRESULTTAG yyflag;
+ if (yyn > 0)
+ {
+ assert (yys->yypred != NULL);
+ yyflag = yyresolveStates (yys->yypred, yyn-1, yystack);
+ if (yyflag != yyok)
+ return yyflag;
+ if (! yys->yyresolved)
+ {
+ yyflag = yyresolveValue (yys->yysemantics.yyfirstVal, yystack,
+ &yys->yysemantics.yysval, &yys->yyloc);
+ if (yyflag != yyok)
+ return yyflag;
+ yys->yyresolved = yytrue;
+ }
+ }
+ return yyok;
+}
+
+static YYRESULTTAG
+yyresolveAction (yySemanticOption* yyopt, yyGLRStack* yystack,
+ YYSTYPE* yyvalp, YYLTYPE* yylocp)
+{
+ yyGLRStackItem yyrhsVals[YYMAXRHS];
+ int yynrhs, yyi;
+ yyGLRState* yys;
+
+ yynrhs = yyrhsLength (yyopt->yyrule);
+ YYCHK (yyresolveStates (yyopt->yystate, yynrhs, yystack));
+ for (yyi = yynrhs-1, yys = yyopt->yystate; yyi >= 0;
+ yyi -= 1, yys = yys->yypred)
+ {
+ assert (yys->yypred != NULL);
+ yyrhsVals[yyi].yystate.yyresolved = yytrue;
+ yyrhsVals[yyi].yystate.yysemantics.yysval = yys->yysemantics.yysval;
+ yyrhsVals[yyi].yystate.yyloc = yys->yyloc;
+ }
+ return yyuserAction (yyopt->yyrule, yynrhs, yyrhsVals + (yynrhs-1),
+ yyvalp, yylocp, yystack);
+}
+
+#if YYDEBUG
+static yyGLRState YYLEFTMOST_STATE = { 0, NULL, -1, 0, { NULL } };
+
+static void yyreportTree (yySemanticOption* yyx, int yyindent)
+{
+ int yynrhs = yyrhsLength (yyx->yyrule);
+ int yyi;
+ yyGLRState* yys;
+ yyGLRState* yystates[YYMAXRHS];
+
+ for (yyi = yynrhs, yys = yyx->yystate; yyi > 0; yyi -= 1, yys = yys->yypred)
+ yystates[yyi] = yys;
+ if (yys == NULL)
+ yystates[0] = &YYLEFTMOST_STATE;
+ else
+ yystates[0] = yys;
+
+ if (yys->yyposn+1 > yyx->yystate->yyposn)
+ YYFPRINTF (stderr, "%*s%s -> <Rule %d, empty>\n",
+ yyindent, "", yytokenName (yylhsNonterm (yyx->yyrule)),
+ yyx->yyrule);
+ else
+ YYFPRINTF (stderr, "%*s%s -> <Rule %d, tokens %d .. %d>\n",
+ yyindent, "", yytokenName (yylhsNonterm (yyx->yyrule)),
+ yyx->yyrule, yys->yyposn+1, yyx->yystate->yyposn);
+ for (yyi = 1; yyi <= yynrhs; yyi += 1)
+ {
+ if (yystates[yyi]->yyresolved)
+ {
+ if (yystates[yyi-1]->yyposn+1 > yystates[yyi]->yyposn)
+ YYFPRINTF (stderr, "%*s%s <empty>\n", yyindent+2, "",
+ yytokenName (yyrhs[yyprhs[yyx->yyrule]+yyi-1]));
+ else
+ YYFPRINTF (stderr, "%*s%s <tokens %d .. %d>\n", yyindent+2, "",
+ yytokenName (yyrhs[yyprhs[yyx->yyrule]+yyi-1]),
+ yystates[yyi-1]->yyposn+1, yystates[yyi]->yyposn);
+ }
+ else
+ yyreportTree (yystates[yyi]->yysemantics.yyfirstVal, yyindent+2);
+ }
+}
+#endif
+
+static void
+yyreportAmbiguity (yySemanticOption* yyx0, yySemanticOption* yyx1,
+ yyGLRStack* yystack)
+{
+#if YYDEBUG
+ YYFPRINTF (stderr, "Ambiguity detected.\n");
+ YYFPRINTF (stderr, "Option 1,\n");
+ yyreportTree (yyx0, 2);
+ YYFPRINTF (stderr, "\nOption 2,\n");
+ yyreportTree (yyx1, 2);
+ YYFPRINTF (stderr, "\n");
+#endif
+ yyFail (yystack, "ambiguity detected");
+}
+
+
+/** Resolve the ambiguity represented by OPTIONLIST, perform the indicated
+ * actions, and return the result. */
+static YYRESULTTAG
+yyresolveValue (yySemanticOption* yyoptionList, yyGLRStack* yystack,
+ YYSTYPE* yyvalp, YYLTYPE* yylocp)
+{
+ yySemanticOption* yybest;
+ yySemanticOption* yyp;
+ int yymerge;
+
+ yybest = yyoptionList;
+ yymerge = 0;
+ for (yyp = yyoptionList->yynext; yyp != NULL; yyp = yyp->yynext)
+ {
+ if (yyidenticalOptions (yybest, yyp))
+ yymergeOptionSets (yybest, yyp);
+ else
+ switch (yypreference (yybest, yyp))
+ {
+ case 0:
+ yyreportAmbiguity (yybest, yyp, yystack);
+ break;
+ case 1:
+ yymerge = 1;
+ break;
+ case 2:
+ break;
+ case 3:
+ yybest = yyp;
+ yymerge = 0;
+ break;
+ }
+ }
+
+ if (yymerge)
+ {
+ int yyprec = yydprec[yybest->yyrule];
+ YYCHK (yyresolveAction (yybest, yystack, yyvalp, yylocp));
+ for (yyp = yybest->yynext; yyp != NULL; yyp = yyp->yynext)
+ {
+ if (yyprec == yydprec[yyp->yyrule])
+ {
+ YYSTYPE yyval1;
+ YYLTYPE yydummy;
+ YYCHK (yyresolveAction (yyp, yystack, &yyval1, &yydummy));
+ *yyvalp = yyuserMerge (yymerger[yyp->yyrule], yyvalp, &yyval1);
+ }
+ }
+ return yyok;
+ }
+ else
+ return yyresolveAction (yybest, yystack, yyvalp, yylocp);
+}
+
+static YYRESULTTAG
+yyresolveStack (yyGLRStack* yystack)
+{
+ if (yystack->yysplitPoint != NULL)
+ {
+ yyGLRState* yys;
+ int yyn;
+
+ for (yyn = 0, yys = yystack->yytops.yystates[0];
+ yys != yystack->yysplitPoint;
+ yys = yys->yypred, yyn += 1)
+ ;
+ YYCHK (yyresolveStates (yystack->yytops.yystates[0], yyn, yystack));
+ }
+ return yyok;
+}
+
+static void
+yycompressStack (yyGLRStack* yystack)
+{
+ yyGLRState* yyp, *yyq, *yyr;
+
+ if (yystack->yytops.yysize != 1 || yystack->yysplitPoint == NULL)
+ return;
+
+ for (yyp = yystack->yytops.yystates[0], yyq = yyp->yypred, yyr = NULL;
+ yyp != yystack->yysplitPoint;
+ yyr = yyp, yyp = yyq, yyq = yyp->yypred)
+ yyp->yypred = yyr;
+
+ yystack->yyspaceLeft += yystack->yynextFree - yystack->yyitems;
+ yystack->yynextFree = ((yyGLRStackItem*) yystack->yysplitPoint) + 1;
+ yystack->yyspaceLeft -= yystack->yynextFree - yystack->yyitems;
+ yystack->yysplitPoint = NULL;
+ yystack->yylastDeleted = NULL;
+
+ while (yyr != NULL)
+ {
+ yystack->yynextFree->yystate = *yyr;
+ yyr = yyr->yypred;
+ yystack->yynextFree->yystate.yypred = & yystack->yynextFree[-1].yystate;
+ yystack->yytops.yystates[0] = &yystack->yynextFree->yystate;
+ yystack->yynextFree += 1;
+ yystack->yyspaceLeft -= 1;
+ }
+}
+
+static YYRESULTTAG
+yyprocessOneStack (yyGLRStack* yystack, int yyk,
+ size_t yyposn, YYSTYPE* yylvalp, YYLTYPE* yyllocp)
+{
+ int yyaction;
+ const short* yyconflicts;
+ yyRuleNum yyrule;
+ yySymbol* const yytokenp = yystack->yytokenp;
+
+ while (yystack->yytops.yystates[yyk] != NULL)
+ {
+ yyStateNum yystate = yystack->yytops.yystates[yyk]->yylrState;
+
+ assert (yystate != YYFINAL);
+ if (yyisDefaultedState (yystate))
+ {
+ yyrule = yydefaultAction (yystate);
+ if (yyrule == 0)
+ {
+ YYDPRINTF ((stderr, "Stack %d dies.\n", yyk));
+ yymarkStackDeleted (yystack, yyk);
+ return yyok;
+ }
+ YYCHK (yyglrReduce (yystack, yyk, yyrule, yyfalse));
+ }
+ else
+ {
+ if (*yytokenp == YYEMPTY)
+ {
+ yychar = YYLEX;
+ *yytokenp = YYTRANSLATE(yychar);
+ YYDPRINTF ((stderr, "Read token %s\n", yytokenName (*yytokenp)));
+ }
+ yygetLRActions (yystate, *yytokenp, &yyaction, &yyconflicts);
+
+ while (*yyconflicts != 0)
+ {
+ int yynewStack = yysplitStack (yystack, yyk);
+ YYDPRINTF ((stderr, "Splitting off stack %d from %d.\n",
+ yynewStack, yyk));
+ YYCHK (yyglrReduce (yystack, yynewStack, *yyconflicts, yyfalse));
+ YYCHK (yyprocessOneStack (yystack, yynewStack, yyposn,
+ yylvalp, yyllocp));
+ yyconflicts += 1;
+ }
+
+ if (yyisShiftAction (yyaction))
+ {
+ YYDPRINTF ((stderr, "Shifted token %s on stack %d, ",
+ yytokenName (*yytokenp), yyk));
+ yyglrShift (yystack, yyk, yyaction, yyposn+1, *yylvalp, yyllocp);
+ YYDPRINTF ((stderr, "which is now in state #%d\n",
+ yystack->yytops.yystates[yyk]->yylrState));
+ break;
+ }
+ else if (yyisErrorAction (yyaction))
+ {
+ YYDPRINTF ((stderr, "Stack %d dies.\n", yyk));
+ yymarkStackDeleted (yystack, yyk);
+ break;
+ }
+ else
+ YYCHK (yyglrReduce (yystack, yyk, -yyaction, yyfalse));
+ }
+ }
+ return yyok;
+}
+
+static void
+yyreportParseError (yyGLRStack* yystack, YYSTYPE* yylvalp, YYLTYPE* yyllocp)
+{
+ yySymbol* const yytokenp = yystack->yytokenp;
+
+ if (yystack->yyerrState == 0)
+ {
+#if YYERROR_VERBOSE
+ int yyn, yyx, yycount, yysize;
+ char* yyprefix;
+ char* yyp;
+ char* yymsg;
+ yyn = yypact[yystack->yytops.yystates[0]->yylrState];
+ if (yyn > YYFLAG && yyn < YYLAST)
+ {
+ yycount = 0;
+ /* Start YYX at -YYN if negative to avoid negative indexes in
+ YYCHECK. */
+ yysize = sizeof ("parse error, unexpected ")
+ + strlen (yytokenName (*yytokenp));
+ yyprefix = ", expecting ";
+ for (yyx = yyn < 0 ? -yyn : 0; yyx < yytname_size && yycount <= 5;
+ yyx += 1)
+ if (yycheck[yyx + yyn] == yyx)
+ yysize += strlen (yytokenName (yyx)) + strlen (yyprefix),
+ yycount += 1, yyprefix = " or ";
+ yymsg = yyp = (char*) malloc (yysize);
+ yyp += sprintf (yyp, "parse error, unexpected %s",
+ yytokenName (*yytokenp));
+ if (yycount < 5)
+ {
+ yyprefix = ", expecting ";
+ for (yyx = yyn < 0 ? -yyn : 0; yyx < yytname_size; yyx += 1)
+ if (yycheck[yyx + yyn] == yyx)
+ {
+ yyp += sprintf (yyp, "%s%s", yyprefix, yytokenName (yyx));
+ yyprefix = " or ";
+ }
+ }
+ yyerror (yymsg);
+ free (yymsg);
+ }
+ else
+#endif
+ yyerror ("parse error");
+ yynerrs += 1;
+ }
+}
+
+/* Recover from a syntax error on STACK, assuming that TOKENP,
+ YYLVALP, and YYLLOCP point to the syntactic category, semantic
+ value, and location of the lookahead.
+ NOTE: This uses the panic-mode recovery algorithm described in the
+ Bison documentation, which differs from what is in bison.simple.
+ Specifically, this routine performs no reductions before shifting
+ the error token. */
+static void
+yyrecoverParseError (yyGLRStack* yystack, YYSTYPE* yylvalp, YYLTYPE* yyllocp)
+{
+ yySymbol* const yytokenp = yystack->yytokenp;
+ int yyk, yyj;
+
+ if (yystack->yyerrState == 0)
+ yystack->yyerrState = 3;
+ else if (yystack->yyerrState == 3)
+ {
+ /* We just shifted the error token and (perhaps) took some
+ reductions. Skip tokens until we can proceed. */
+ do {
+ if (*yytokenp == YYEOF)
+ yyFail (yystack, NULL);
+ if (*yytokenp != YYEMPTY)
+ YYDPRINTF ((stderr, "Discarding token %s\n",
+ yytokenName (*yytokenp)));
+ yychar = YYLEX;
+ *yytokenp = YYTRANSLATE (yychar);
+ YYDPRINTF ((stderr, "Read token %s\n", yytokenName (*yytokenp)));
+ yyj = yypact[yystack->yytops.yystates[0]->yylrState];
+ if (yyj == YYFLAG)
+ /* Something's not right; we shouldn't be here */
+ yyFail (yystack, NULL);
+ yyj += *yytokenp;
+ if (yyj < 0 || yyj > YYLAST || yycheck[yyj] != *yytokenp)
+ {
+ if (yydefact[yystack->yytops.yystates[0]->yylrState] != 0)
+ return;
+ }
+ else if (yytable[yyj] != 0 && yytable[yyj] != YYFLAG)
+ return;
+ } while (yytrue);
+ }
+
+ /* Reduce to one stack */
+ for (yyk = 0; yyk < yystack->yytops.yysize; yyk += 1)
+ if (yystack->yytops.yystates[yyk] != NULL)
+ break;
+ if (yyk >= yystack->yytops.yysize)
+ yyFail (yystack, NULL);
+ for (yyk += 1; yyk < yystack->yytops.yysize; yyk += 1)
+ yymarkStackDeleted (yystack, yyk);
+ yyremoveDeletes (yystack);
+ yycompressStack (yystack);
+
+ /* Now pop stack until we find a state that shifts the error token. */
+ while (yystack->yytops.yystates[0] != NULL)
+ {
+ yyj = yypact[yystack->yytops.yystates[0]->yylrState] + YYTERROR;
+ if (yyj != YYFLAG + YYTERROR && yyj >= 0 && yyj <= YYLAST &&
+ yycheck[yyj] == YYTERROR && yyisShiftAction (yytable[yyj]))
+ {
+ yyglrShift (yystack, 0, yytable[yyj],
+ yystack->yytops.yystates[0]->yyposn, *yylvalp, yyllocp);
+ break;
+ }
+ yystack->yytops.yystates[0] = yystack->yytops.yystates[0]->yypred;
+ yystack->yynextFree -= 1;
+ yystack->yyspaceLeft += 1;
+ }
+ if (yystack->yytops.yystates[0] == NULL)
+ yyFail (yystack, NULL);
+}
+
+#define YYCHK1(YYE) \
+ do { \
+ switch (YYE) { \
+ default: \
+ break; \
+ case yyabort: \
+ yystack.yyerrflag = 1; \
+ goto yyDone; \
+ case yyaccept: \
+ yystack.yyerrflag = 0; \
+ goto yyDone; \
+ case yyerr:
\
+ goto yyuser_error; \
+ } \
+ } while (0)
+
+int
+yyparse (YYPARSE_PARAM_ARG)
+{
+ yySymbol yytoken;
+ yyGLRStack yystack;
+ size_t yyposn;
+]b4_pure_if(
+[
+ YYSTYPE yylval;
+ YYLTYPE yylloc;
+ #undef yychar
+ #define yychar (yystack.yyrawchar)
+])[
+
+ YYSTYPE* const yylvalp = &yylval;
+ YYLTYPE* const yyllocp = &yylloc;
+
+ yyinitGLRStack (&yystack, YYINITDEPTH);
+ yystack.yytokenp = &yytoken;
+
+ if (setjmp (yystack.yyexception_buffer) != 0)
+ goto yyDone;
+
+ yyglrShift (&yystack, 0, 0, 0, yyval_default, &yyloc_default);
+ yytoken = YYEMPTY;
+ yyposn = 0;
+
+ while (yytrue)
+ {
+ /* For efficiency, we have two loops, of which the first of which
+ * is specialized to deterministic operation (single stack, no
+ * potential ambiguity). */
+
+ /* Standard mode */
+ while (yytrue)
+ {
+ yyRuleNum yyrule;
+ int yyaction;
+ const short* yyconflicts;
+
+ yyStateNum yystate = yystack.yytops.yystates[0]->yylrState;
+ if (yystate == YYFINAL)
+ goto yyDone;
+ if (yyisDefaultedState (yystate))
+ {
+ yyrule = yydefaultAction (yystate);
+ if (yyrule == 0)
+ {
+ yyreportParseError (&yystack, yylvalp, yyllocp);
+ goto yyuser_error;
+ }
+ YYCHK1 (yyglrReduce (&yystack, 0, yyrule, yytrue));
+ }
+ else
+ {
+ if (yytoken == YYEMPTY)
+ {
+ yychar = YYLEX;
+ yytoken = YYTRANSLATE (yychar);
+ YYDPRINTF ((stderr, "Read token %s\n",
+ yytokenName (yytoken)));
+ }
+ yygetLRActions (yystate, yytoken, &yyaction, &yyconflicts);
+ if (*yyconflicts != 0)
+ break;
+ if (yyisShiftAction (yyaction))
+ {
+ YYDPRINTF ((stderr, "Shifted token %s. ",
+ yytokenName (yytoken)));
+ if (yytoken != YYEOF)
+ yytoken = YYEMPTY;
+ yyposn += 1;
+ yyglrShift (&yystack, 0, yyaction, yyposn, yylval, yyllocp);
+ if (yystack.yyerrState > 0)
+ yystack.yyerrState -= 1;
+ YYDPRINTF ((stderr, "Now in state #%d\n",
+ yystack.yytops.yystates[0]->yylrState));
+ }
+ else if (yyisErrorAction (yyaction))
+ {
+ yyreportParseError (&yystack, yylvalp, yyllocp);
+ goto yyuser_error;
+ }
+ else
+ YYCHK1 (yyglrReduce (&yystack, 0, -yyaction, yytrue));
+ }
+ }
+
+ while (yytrue)
+ {
+ int yys;
+ int yyn = yystack.yytops.yysize;
+ for (yys = 0; yys < yyn; yys += 1)
+ YYCHK1 (yyprocessOneStack (&yystack, yys, yyposn,
+ yylvalp, yyllocp));
+ yytoken = YYEMPTY;
+ yyposn += 1;
+ yyremoveDeletes (&yystack);
+ if (yystack.yytops.yysize == 0)
+ {
+ yyundeleteLastStack (&yystack);
+ if (yystack.yytops.yysize == 0)
+ yyFail (&yystack, "parse error");
+ YYCHK1 (yyresolveStack (&yystack));
+ YYDPRINTF ((stderr, "Returning to deterministic operation.\n"));
+ yyreportParseError (&yystack, yylvalp, yyllocp);
+ goto yyuser_error;
+ }
+ else if (yystack.yytops.yysize == 1)
+ {
+ YYCHK1 (yyresolveStack (&yystack));
+ YYDPRINTF ((stderr, "Returning to deterministic operation.\n"));
+ yycompressStack (&yystack);
+ break;
+ }
+ }
+ continue;
+ yyuser_error:
+ yyrecoverParseError (&yystack, yylvalp, yyllocp);
+ yyposn = yystack.yytops.yystates[0]->yyposn;
+ }
+ yyDone:
+ ;
+
+ yyfreeGLRStack (&yystack);
+ return yystack.yyerrflag;
+}
+
+/* DEBUGGING ONLY */
+
+void
+yypstates (yyGLRState* yyst)
+{
+ void yy_yypstack (yyGLRState* yys)
+ {
+ if (yys->yypred == NULL)
+ fprintf (stderr, "address@hidden", yys->yylrState, yys->yyposn);
+ else
+ {
+ yy_yypstack (yys->yypred);
+ fprintf (stderr, " -> address@hidden", yys->yylrState, yys->yyposn);
+ }
+ }
+
+ if (yyst == NULL)
+ fprintf (stderr, "<null>");
+ else
+ yy_yypstack (yyst);
+ fprintf (stderr, "\n");
+}
+
+void
+yypstack (yyGLRStack* yystack, int yyk)
+{
+ yypstates (yystack->yytops.yystates[yyk]);
+}
+
+#define YYINDEX(YYX) \
+ ((YYX) == NULL ? -1 : (yyGLRStackItem*) (YYX) - yystack->yyitems)
+
+
+void
+yypdumpstack (yyGLRStack* yystack)
+{
+ yyGLRStackItem* yyp;
+ int yyi;
+ for (yyp = yystack->yyitems; yyp < yystack->yynextFree; yyp += 1)
+ {
+ fprintf (stderr, "%3d. ", yyp - yystack->yyitems);
+ if (*(bool*) yyp)
+ {
+ fprintf (stderr, "Res: %d, LR State: %d, posn: %d, pred: %d",
+ yyp->yystate.yyresolved, yyp->yystate.yylrState,
+ yyp->yystate.yyposn,
+ YYINDEX(yyp->yystate.yypred));
+ if (! yyp->yystate.yyresolved)
+ fprintf (stderr, ", firstVal: %d",
+ YYINDEX (yyp->yystate.yysemantics.yyfirstVal));
+ }
+ else
+ {
+ fprintf (stderr, "Option. rule: %d, state: %d, next: %d",
+ yyp->yyoption.yyrule, YYINDEX (yyp->yyoption.yystate),
+ YYINDEX (yyp->yyoption.yynext));
+ }
+ fprintf (stderr, "\n");
+ }
+ fprintf (stderr, "Tops:");
+ for (yyi = 0; yyi < yystack->yytops.yysize; yyi += 1)
+ fprintf (stderr, "%d: %d; ", yyi, YYINDEX (yystack->yytops.yystates[yyi]));
+ fprintf (stderr, "\n");
+}
+
+]
+
+b4_epilogue
+m4_if(b4_defines_flag, 0, [],
+[#output "b4_output_header_name"
+#ifndef b4_header_guard
+# define b4_header_guard
+
+b4_token_defines(b4_tokens)
+
+#ifndef YYSTYPE
+m4_ifdef([b4_stype],
+[#line b4_stype_line "b4_filename"
+typedef union b4_stype yystype;
+/* Line __line__ of __file__. */
+#line __oline__ "__ofile__"],
+[typedef int yystype;])
+# define YYSTYPE yystype
+#endif
+
+b4_pure_if([],
+[extern YYSTYPE b4_prefix[]lval;])
+
+b4_location_if(
+[#ifndef YYLTYPE
+typedef struct yyltype
+{
+ int yyfirst_line;
+ int yyfirst_column;
+ int yylast_line;
+ int yylast_column;
+} yyltype;
+# define YYLTYPE yyltype
+#endif
+
+m4_if(b4_pure, [0],
+[extern YYLTYPE b4_prefix[]lloc;])
+])
+#endif /* not b4_header_guard */
+])
Index: bison-1_5.25/tests/cxx-type.at
--- bison-1_5.25/tests/cxx-type.at Thu, 27 Jun 2002 19:39:00 -0700 hilfingr ()
+++ bison-1_5.27(w)/tests/cxx-type.at Wed, 15 May 2002 16:45:40 -0700 hilfingr
(glrbison/g/23_cxx-type.a 1.1 644)
@@ -0,0 +1,248 @@
+# Checking the output filenames. -*- Autotest -*-
+# Copyright 2000, 2001 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2, or (at your option)
+# any later version.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+# 02111-1307, USA.
+
+AT_BANNER([[C++ Type Syntax (GLR).]])
+
+# _AT_TEST_GLR_CALC(`$1',DECL, RESOLVE1, RESOLVE2)
+# (first argument is a literal $1; it's a trick).
+# Store into types.y the calc program, with DECL inserted as a declaration,
+# and with RESOLVE1 and RESOLVE2 as annotations on the conflicted rule for
+# stmt. Then compile the result.
+m4_define([_AT_TEST_GLR_CALC],
+[AT_DATA([types.y],
+[[/* Simplified C++ Type and Expression Grammar */
+
+$2
+
+%{
+ #include <stdio.h>
+ #define YYSTYPE const char*
+ static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1);
+ #define YYINITDEPTH 10
+%}
+
+%token TYPENAME ID
+
+%right '='
+%left '+'
+
+%glr-parser
+
+%%
+
+prog :
+ | prog stmt { printf ("\n"); }
+ ;
+
+stmt : expr ';' $3
+ | decl $4
+ | error ';'
+ | '@' { YYACCEPT; }
+ ;
+
+expr : ID { printf ("%s ", $$); }
+ | TYPENAME '(' expr ')'
+ { printf ("%s <cast> ", $1); }
+ | expr '+' expr { printf ("+ "); }
+ | expr '=' expr { printf ("= "); }
+ ;
+
+decl : TYPENAME declarator ';'
+ { printf ("%s <declare> ", $1); }
+ | TYPENAME declarator '=' expr ';'
+ { printf ("%s <init-declare> ", $1); }
+ ;
+
+declarator : ID { printf ("\"%s\" ", $1); }
+ | '(' declarator ')'
+ ;
+
+%%
+
+#include <ctype.h>
+#include <strings.h>
+
+main (int argc, char** argv)
+{
+ freopen (argv[1], "r", stdin);
+ exit (yyparse ());
+}
+
+#if YYPURE
+int yylex (YYSTYPE *lvalp)
+#define yylval (*lvalp)
+#else
+int yylex ()
+#endif
+{
+ char buffer[256];
+ int c;
+ while (1) {
+ c = getchar ();
+ switch (c) {
+ case EOF:
+ return 0;
+ case ' ': case '\t': case '\n': case '\f':
+ break;
+ default:
+ if (isalpha (c)) {
+ ungetc (c, stdin);
+ scanf ("%[A-Za-z0-9_]", buffer);
+ yylval = strdup (buffer);
+ return isupper (buffer[0]) ? TYPENAME : ID;
+ }
+ return c;
+ }
+ }
+}
+
+int
+yyerror (const char *s)
+{
+ fprintf (stderr, "%s\n", s);
+ return 0;
+}
+
+static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1)
+{
+ printf ("<OR> ");
+ return "";
+}
+]])
+
+AT_DATA([test-input],
+[[
+
+z + q;
+
+T x;
+
+T x = y;
+
+x = y;
+
+T (x) + y;
+
+T (x);
+
+T (y) = z + q;
+
+T (y y) = z + q;
+
+z + q;
+
+@
+
+This is total garbage, but it should be ignored.
+]])
+
+AT_CHECK([bison types.y], 0, [], ignore)
+AT_CHECK([gcc -o types types.tab.c], 0, [], ignore)
+])
+
+m4_define([_AT_RESOLVED_GLR_OUTPUT],
+[[z q +
+"x" T <declare>
+"x" y T <init-declare>
+x y =
+x T <cast> y +
+"x" T <declare>
+"y" z q + T <init-declare>
+y
+z q +
+]])
+
+m4_define([_AT_AMBIG_GLR_OUTPUT],
+[[z q +
+"x" T <declare>
+"x" y T <init-declare>
+x y =
+x T <cast> y +
+"x" T <declare> x T <cast> <OR>
+"y" z q + T <init-declare> y T <cast> z q + = <OR>
+y
+z q +
+]])
+
+m4_define([_AT_GLR_STDERR],
+[[parse error
+]])
+
+m4_define([_AT_VERBOSE_GLR_STDERR],
+[[parse error, unexpected ID, expecting '=' or '+' or ')'
+]])
+
+## ---------------------------------------------------- ##
+## Compile the grammar described in the documentation. ##
+## ---------------------------------------------------- ##
+
+AT_SETUP([GLR: Resolve ambiguity, impure, no locations])
+_AT_TEST_GLR_CALC([$1],[],[%dprec 1],[%dprec 2])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0, _AT_RESOLVED_GLR_OUTPUT,
+ _AT_GLR_STDERR)
+AT_CLEANUP
+
+AT_SETUP([GLR: Resolve ambiguity, impure, locations])
+_AT_TEST_GLR_CALC([$1],[%locations],[%dprec 1],[%dprec 2])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0, _AT_RESOLVED_GLR_OUTPUT,
+ _AT_GLR_STDERR)
+AT_CLEANUP
+
+AT_SETUP([GLR: Resolve ambiguity, pure, no locations])
+_AT_TEST_GLR_CALC([$1],[%pure-parser],[%dprec 1],[%dprec 2])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0, _AT_RESOLVED_GLR_OUTPUT,
+ _AT_GLR_STDERR)
+AT_CLEANUP
+
+AT_SETUP([GLR: Resolve ambiguity, pure, locations])
+_AT_TEST_GLR_CALC([$1],[%pure-parser
+%locations],[%dprec 1],[%dprec 2])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0, _AT_RESOLVED_GLR_OUTPUT,
+ _AT_GLR_STDERR)
+AT_CLEANUP
+
+AT_SETUP([GLR: Merge conflicting parses, impure, no locations])
+_AT_TEST_GLR_CALC([$1],[],[%merge <stmtMerge>],[%merge <stmtMerge>])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0, _AT_AMBIG_GLR_OUTPUT,
+ _AT_GLR_STDERR)
+AT_CLEANUP
+
+AT_SETUP([GLR: Merge conflicting parses, impure, locations])
+_AT_TEST_GLR_CALC([$1],[%locations],[%merge <stmtMerge>],[%merge <stmtMerge>])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0, _AT_AMBIG_GLR_OUTPUT,
+ _AT_GLR_STDERR)
+AT_CLEANUP
+
+AT_SETUP([GLR: Merge conflicting parses, pure, no locations])
+_AT_TEST_GLR_CALC([$1],[%pure-parser],[%merge <stmtMerge>],[%merge
<stmtMerge>])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0, _AT_AMBIG_GLR_OUTPUT,
+ _AT_GLR_STDERR)
+AT_CLEANUP
+AT_SETUP([GLR: Merge conflicting parses, pure, locations])
+_AT_TEST_GLR_CALC([$1],[%pure-parser
+%locations],[%merge <stmtMerge>],[%merge <stmtMerge>])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0, _AT_AMBIG_GLR_OUTPUT,
+ _AT_GLR_STDERR)
+AT_CLEANUP
+
+AT_SETUP([GLR: Verbose messages, resolve ambiguity, impure, no locations])
+_AT_TEST_GLR_CALC([$1],[%error-verbose],
+[%merge <stmtMerge>],[%merge <stmtMerge>])
+AT_CHECK([[./types test-input | sed 's/ *$//']], 0,
+ _AT_AMBIG_GLR_OUTPUT, _AT_VERBOSE_GLR_STDERR)
+AT_CLEANUP
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- Mega patch for GLR parsing,
Paul Hilfinger <=