-These two declarations look identical until the @samp{..} token.
-With normal @acronym{LALR}(1) one-token look-ahead it is not
-possible to decide between the two forms when the identifier
-@samp{a} is parsed. It is, however, desirable
-for a parser to decide this, since in the latter case
-@samp{a} must become a new identifier to represent the enumeration
-value, while in the former case @samp{a} must be evaluated with its
-current meaning, which may be a constant or even a function call.
-
-You could parse @samp{(a)} as an ``unspecified identifier in parentheses'',
-to be resolved later, but this typically requires substantial
-contortions in both semantic actions and large parts of the
-grammar, where the parentheses are nested in the recursive rules for
-expressions.
-
-You might think of using the lexer to distinguish between the two
-forms by returning different tokens for currently defined and
-undefined identifiers. But if these declarations occur in a local
-scope, and @samp{a} is defined in an outer scope, then both forms
-are possible---either locally redefining @samp{a}, or using the
-value of @samp{a} from the outer scope. So this approach cannot
-work.
-
-A solution to this problem is to use a @acronym{GLR} parser in its simplest
-form, i.e., without using special features such as @samp{%dprec} and
-@samp{%merge}. When the @acronym{GLR} parser reaches the critical state, it
-simply splits into two branches and pursues both syntax rules
-simultaneously. Sooner or later, one of them runs into a parsing
-error. If there is a @samp{..} token before the next
-@samp{;}, the rule for enumerated types fails since it cannot
-accept @samp{..} anywhere; otherwise, the subrange type rule
-fails since it requires a @samp{..} token. So one of the branches
-fails silently, and the other one continues normally, performing
-all the intermediate actions that were postponed during the split.
-
-If the input is syntactically incorrect, both branches fail and the parser
-reports a syntax error as usual.
-
-The effect of all this is that the parser seems to ``guess'' the
-correct branch to take, or in other words, it seems to use more
-look-ahead than the underlying @acronym{LALR}(1) algorithm actually allows
-for. In this example, @acronym{LALR}(2) would suffice, but also some cases
-that are not @acronym{LALR}(@math{k}) for any @math{k} can be handled this way.
-
-Since there can be only two branches and at least one of them
-must fail, you need not worry about merging the branches by
-using dynamic precedence or @samp{%merge}.
-
-Another potential problem of @acronym{GLR} does not arise here, either. In
-general, a @acronym{GLR} parser can take quadratic or cubic worst-case time,
-and the current Bison parser even takes exponential time and space
-for some grammars. In practice, this rarely happens, and for many
-grammars it is possible to prove that it cannot happen. In
-in the present example, there is only one conflict between two
-rules, and the type-declaration context where the conflict
-arises cannot be nested. So the number of
-branches that can exist at any time is limited by the constant 2,
-and the parsing time is still linear.
-
-So here we have a case where we can use the benefits of @acronym{GLR}, almost
-without disadvantages. There are two things to note, though.
-First, one should carefully analyze the conflicts reported by
-Bison to make sure that @acronym{GLR} splitting is done only where it is
-intended to be. A @acronym{GLR} parser splitting inadvertently may cause
-problems less obvious than an @acronym{LALR} parser statically choosing the
-wrong alternative in a conflict.
-
-Second, interactions with the lexer (@pxref{Semantic Tokens}) must
-be considered with great care. Since a split parser consumes tokens
-without performing any actions during the split, the lexer cannot
-obtain information via parser actions. Some cases of
-lexer interactions can simply be eliminated by using @acronym{GLR}, i.e.,
-shifting the complications from the lexer to the parser. Remaining
-cases have to be checked for safety.
-
-In our example, it would be safe for the lexer to return tokens
-based on their current meanings in some symbol table, because no new
-symbols are defined in the middle of a type declaration. Though it
-is possible for a parser to define the enumeration
-constants as they are parsed, before the type declaration is
-completed, it actually makes no difference since they cannot be used
-within the same enumerated type declaration.
-
-Here is a Bison grammar corresponding to the example above. It
-parses a vastly simplified form of Pascal type declarations.
-
-@example
-%token TYPE DOTDOT ID
-
-@group
-%left '+' '-'
-%left '*' '/'
-@end group
-
-%%
-
-@group
-type_decl:
- TYPE ID '=' type ';'
-;
-@end group
-
-@group
-type: '(' id_list ')'
- | expr DOTDOT expr
-;
-@end group
-
-@group
-id_list: ID
- | id_list ',' ID
-;
-@end group
-
-@group
-expr: '(' expr ')'
- | expr '+' expr
- | expr '-' expr
- | expr '*' expr
- | expr '/' expr
- | ID
-;
-@end group
-@end example
-
-When used as a normal @acronym{LALR}(1) grammar, Bison correctly complains
-about one reduce/reduce conflict. In the conflicting situation the
-parser chooses one of the alternatives, arbitrarily the one
-declared first. Therefore the following correct input is not
-recognized:
-
-@example
-type t = (a) .. b;
-@end example
-
-The parser can be turned into a @acronym{GLR} parser, while also telling Bison
-to be silent about the one known reduce/reduce conflict, simply by
-adding these two declarations to the Bison input file:
-
-@example
-%glr-parser
-%expect-rr 1
-@end example
-
-@noindent
-No change in the grammar itself is required. Now the
-parser recognizes all valid declarations, according to the
-limited syntax above, transparently. In fact, the user does not even
-notice when the parser splits.
-
-@node Locations Overview
-@section Locations
-@cindex location
-@cindex textual location
-@cindex location, textual
-
-Many applications, like interpreters or compilers, have to produce verbose
-and useful error messages. To achieve this, one must be able to keep track of
-the @dfn{textual location}, or @dfn{location}, of each syntactic construct.
-Bison provides a mechanism for handling these locations.
-
-Each token has a semantic value. In a similar fashion, each token has an
-associated location, but the type of locations is the same for all tokens and
-groupings. Moreover, the output parser is equipped with a default data
-structure for storing locations (@pxref{Locations}, for more details).
-
-Like semantic values, locations can be reached in actions using a dedicated
-set of constructs. In the example above, the location of the whole grouping
-is @code{@@$}, while the locations of the subexpressions are @code{@@1} and
-@code{@@3}.
-
-When a rule is matched, a default action is used to compute the semantic value
-of its left hand side (@pxref{Actions}). In the same way, another default
-action is used for locations. However, the action for locations is general
-enough for most cases, meaning there is usually no need to describe for each
-rule how @code{@@$} should be formed. When building a new location for a given
-grouping, the default behavior of the output parser is to take the beginning
-of the first symbol, and the end of the last symbol.
-
-@node Bison Parser
-@section Bison Output: the Parser File
-@cindex Bison parser
-@cindex Bison utility
-@cindex lexical analyzer, purpose
-@cindex parser
-
-When you run Bison, you give it a Bison grammar file as input. The output
-is a C source file that parses the language described by the grammar.
-This file is called a @dfn{Bison parser}. Keep in mind that the Bison
-utility and the Bison parser are two distinct programs: the Bison utility
-is a program whose output is the Bison parser that becomes part of your
-program.
-
-The job of the Bison parser is to group tokens into groupings according to
-the grammar rules---for example, to build identifiers and operators into
-expressions. As it does this, it runs the actions for the grammar rules it
-uses.
-
-The tokens come from a function called the @dfn{lexical analyzer} that
-you must supply in some fashion (such as by writing it in C). The Bison
-parser calls the lexical analyzer each time it wants a new token. It
-doesn't know what is ``inside'' the tokens (though their semantic values
-may reflect this). Typically the lexical analyzer makes the tokens by
-parsing characters of text, but Bison does not depend on this.
-@xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.
projects / bison.git / blobdiff