[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: don't use @acronym in bison.texinfo
|
From: |
Joel E. Denny |
|
Subject: |
Re: don't use @acronym in bison.texinfo |
|
Date: |
Sat, 8 Jan 2011 14:09:43 -0500 (EST) |
|
User-agent: |
Alpine 2.00 (DEB 1167 2008-08-23) |
Hi Akim,
On Wed, 5 Jan 2011, Akim Demaille wrote:
> Le 4 janv. 2011 à 01:24, Joel E. Denny a écrit :
> > In my current work on bison.texinfo, I'm finding it tedious to write
> > @acronym{...} around every GNU, LR, LALR, IELR, LAC, etc. Lately, it
> > seems people are discouraging its usage anyway:
> >
> > http://lists.gnu.org/archive/html/bug-gnulib/2010-03/msg00321.html
> > http://lists.gnu.org/archive/html/bug-gnulib/2010-11/msg00220.html
> >
> > Would anyone object to a patch to remove it entirely from bison.texinfo?
>
> Fine with me.
Thanks. I pushed the following to master and something similar to
branch-2.5.
>From 8a4281b987577d911e418e8a37aef0c9c7121bf8 Mon Sep 17 00:00:00 2001
From: Joel E. Denny <address@hidden>
Date: Sat, 8 Jan 2011 13:52:05 -0500
Subject: [PATCH] doc: don't use @acronym.
Lately, many GNU packages are dropping it. See
<http://lists.gnu.org/archive/html/bison-patches/2011-01/msg00003.html>.
* doc/bison.texinfo: Remove all uses.
---
ChangeLog | 7 +
doc/bison.texinfo | 472 ++++++++++++++++++++++++++--------------------------
2 files changed, 243 insertions(+), 236 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index b23c971..ac74891 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2011-01-08 Joel E. Denny <address@hidden>
+
+ doc: don't use @acronym.
+ Lately, many GNU packages are dropping it. See
+ <http://lists.gnu.org/archive/html/bison-patches/2011-01/msg00003.html>.
+ * doc/bison.texinfo: Remove all uses.
+
2011-01-05 Alex Rozenman <address@hidden>
Do not allow identifiers that start with a negative number.
diff --git a/doc/bison.texinfo b/doc/bison.texinfo
index 8ba7578..cc1e064 100644
--- a/doc/bison.texinfo
+++ b/doc/bison.texinfo
@@ -30,31 +30,31 @@
@copying
-This manual (@value{UPDATED}) is for @acronym{GNU} Bison (version
address@hidden), the @acronym{GNU} parser generator.
+This manual (@value{UPDATED}) is for GNU Bison (version
address@hidden), the GNU parser generator.
Copyright @copyright{} 1988-1993, 1995, 1998-2011 Free Software
Foundation, Inc.
@quotation
Permission is granted to copy, distribute and/or modify this document
-under the terms of the @acronym{GNU} Free Documentation License,
+under the terms of the GNU Free Documentation License,
Version 1.3 or any later version published by the Free Software
Foundation; with no Invariant Sections, with the Front-Cover texts
-being ``A @acronym{GNU} Manual,'' and with the Back-Cover Texts as in
+being ``A GNU Manual,'' and with the Back-Cover Texts as in
(a) below. A copy of the license is included in the section entitled
address@hidden Free Documentation License.''
+``GNU Free Documentation License.''
(a) The FSF's Back-Cover Text is: ``You have the freedom to copy and
-modify this @acronym{GNU} manual. Buying copies from the @acronym{FSF}
-supports it in developing @acronym{GNU} and promoting software
+modify this GNU manual. Buying copies from the FSF
+supports it in developing GNU and promoting software
freedom.''
@end quotation
@end copying
@dircategory Software development
@direntry
-* bison: (bison). @acronym{GNU} parser generator (Yacc replacement).
+* bison: (bison). GNU parser generator (Yacc replacement).
@end direntry
@titlepage
@@ -72,7 +72,7 @@ Published by the Free Software Foundation @*
51 Franklin Street, Fifth Floor @*
Boston, MA 02110-1301 USA @*
Printed copies are available from the Free Software address@hidden
address@hidden 1-882114-44-2
+ISBN 1-882114-44-2
@sp 2
Cover art by Etienne Suvasa.
@end titlepage
@@ -88,7 +88,7 @@ Cover art by Etienne Suvasa.
@menu
* Introduction::
* Conditions::
-* Copying:: The @acronym{GNU} General Public License says
+* Copying:: The GNU General Public License says
how you can copy and share Bison.
Tutorial sections:
@@ -130,13 +130,13 @@ The Concepts of Bison
* Stages:: Stages in writing and running Bison grammars.
* Grammar Layout:: Overall structure of a Bison grammar file.
-Writing @acronym{GLR} Parsers
+Writing GLR Parsers
-* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars.
-* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities.
+* Simple GLR Parsers:: Using GLR parsers on unambiguous grammars.
+* Merging GLR Parses:: Using GLR parsers to resolve ambiguities.
* GLR Semantic Actions:: Considerations for semantic values and deferred
actions.
* Semantic Predicates:: Controlling a parse with arbitrary computations.
-* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler.
+* Compiler Requirements:: GLR parsers require a modern C compiler.
Examples
@@ -333,7 +333,7 @@ Frequently Asked Questions
* Strings are Destroyed:: @code{yylval} Loses Track of Strings
* Implementing Gotos/Loops:: Control Flow in the Calculator
* Multiple start-symbols:: Factoring closely related grammars
-* Secure? Conform?:: Is Bison @acronym{POSIX} safe?
+* Secure? Conform?:: Is Bison POSIX safe?
* I can't build Bison:: Troubleshooting
* Where can I find help?:: Troubleshouting
* Bug Reports:: Troublereporting
@@ -353,9 +353,9 @@ Copying This Manual
@cindex introduction
@dfn{Bison} is a general-purpose parser generator that converts an
-annotated context-free grammar into a deterministic @acronym{LR} or
-generalized @acronym{LR} (@acronym{GLR}) parser employing
address@hidden(1), @acronym{IELR}(1), or canonical @acronym{LR}(1)
+annotated context-free grammar into a deterministic LR or
+generalized LR (GLR) parser employing
+LALR(1), IELR(1), or canonical LR(1)
parser tables.
Once you are proficient with Bison, you can use it to develop a wide
range of language parsers, from those used in simple desk calculators to
@@ -382,11 +382,11 @@ This edition corresponds to version @value{VERSION} of
Bison.
The distribution terms for Bison-generated parsers permit using the
parsers in nonfree programs. Before Bison version 2.2, these extra
-permissions applied only when Bison was generating @acronym{LALR}(1)
+permissions applied only when Bison was generating LALR(1)
parsers in address@hidden And before Bison version 1.24, Bison-generated
parsers could be used only in programs that were free software.
-The other @acronym{GNU} programming tools, such as the @acronym{GNU} C
+The other GNU programming tools, such as the GNU C
compiler, have never
had such a requirement. They could always be used for nonfree
software. The reason Bison was different was not due to a special
@@ -397,7 +397,7 @@ The output of the Bison utility---the Bison parser
file---contains a
verbatim copy of a sizable piece of Bison, which is the code for the
parser's implementation. (The actions from your grammar are inserted
into this implementation at one point, but most of the rest of the
-implementation is not changed.) When we applied the @acronym{GPL}
+implementation is not changed.) When we applied the GPL
terms to the skeleton code for the parser's implementation,
the effect was to restrict the use of Bison output to free software.
@@ -406,7 +406,7 @@ make software proprietary. @strong{Software should be
free.} But we
concluded that limiting Bison's use to free software was doing little to
encourage people to make other software free. So we decided to make the
practical conditions for using Bison match the practical conditions for
-using the other @acronym{GNU} tools.
+using the other GNU tools.
This exception applies when Bison is generating code for a parser.
You can tell whether the exception applies to a Bison output file by
@@ -456,36 +456,36 @@ can be made of a minus sign and another expression''.
Another would be,
recursive, but there must be at least one rule which leads out of the
recursion.
address@hidden @acronym{BNF}
address@hidden BNF
@cindex Backus-Naur form
The most common formal system for presenting such rules for humans to read
-is @dfn{Backus-Naur Form} or address@hidden'', which was developed in
+is @dfn{Backus-Naur Form} or ``BNF'', which was developed in
order to specify the language Algol 60. Any grammar expressed in
address@hidden is a context-free grammar. The input to Bison is
-essentially machine-readable @acronym{BNF}.
+BNF is a context-free grammar. The input to Bison is
+essentially machine-readable BNF.
address@hidden @acronym{LALR}(1) grammars
address@hidden @acronym{IELR}(1) grammars
address@hidden @acronym{LR}(1) grammars
address@hidden LALR(1) grammars
address@hidden IELR(1) grammars
address@hidden LR(1) grammars
There are various important subclasses of context-free grammars.
Although it can handle almost all context-free grammars, Bison is
-optimized for what are called @acronym{LR}(1) grammars.
+optimized for what are called LR(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 lookahead.
For historical reasons, Bison by default is limited by the additional
-restrictions of @acronym{LALR}(1), which is hard to explain simply.
+restrictions of LALR(1), which is hard to explain simply.
@xref{Mystery Conflicts, ,Mysterious Reduce/Reduce Conflicts}, for
more information on this.
As an experimental feature, you can escape these additional restrictions by
-requesting @acronym{IELR}(1) or canonical @acronym{LR}(1) parser tables.
+requesting IELR(1) or canonical LR(1) parser tables.
@xref{Decl Summary,,lr.type}, to learn how.
address@hidden @acronym{GLR} parsing
address@hidden generalized @acronym{LR} (@acronym{GLR}) parsing
address@hidden GLR parsing
address@hidden generalized LR (GLR) parsing
@cindex ambiguous grammars
@cindex nondeterministic parsing
-Parsers for @acronym{LR}(1) grammars are @dfn{deterministic}, meaning
+Parsers for LR(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{lookahead}) of the remaining input. A context-free
@@ -494,8 +494,8 @@ apply the grammar rules to get the same inputs. Even
unambiguous
grammars can be @dfn{nondeterministic}, meaning that no fixed
lookahead 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 @acronym{GLR}
-parsing (for Generalized @acronym{LR}). Bison's @acronym{GLR} parsers
+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.
@@ -706,16 +706,16 @@ The action says how to produce the semantic value of the
sum expression
from the values of the two subexpressions.
@node GLR Parsers
address@hidden Writing @acronym{GLR} Parsers
address@hidden @acronym{GLR} parsing
address@hidden generalized @acronym{LR} (@acronym{GLR}) parsing
address@hidden Writing GLR Parsers
address@hidden GLR parsing
address@hidden generalized LR (GLR) parsing
@findex %glr-parser
@cindex conflicts
@cindex shift/reduce conflicts
@cindex reduce/reduce conflicts
In some grammars, Bison's deterministic
address@hidden(1) parsing algorithm cannot decide whether to apply a
+LR(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
@@ -724,15 +724,15 @@ 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 @acronym{LR}(1), a
+To use a grammar that is not easily modified to be LR(1), a
more general parsing algorithm is sometimes necessary. If you include
@code{%glr-parser} among the Bison declarations in your file
-(@pxref{Grammar Outline}), the result is a Generalized @acronym{LR}
-(@acronym{GLR}) parser. These parsers handle Bison grammars that
+(@pxref{Grammar Outline}), the result is a Generalized LR
+(GLR) parser. These parsers handle Bison grammars that
contain no unresolved conflicts (i.e., after applying precedence
declarations) identically to deterministic parsers. However, when
faced with unresolved shift/reduce and reduce/reduce conflicts,
address@hidden parsers use the simple expedient of doing both,
+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
@@ -755,25 +755,25 @@ user-defined function on the resulting values to produce
an arbitrary
merged result.
@menu
-* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars.
-* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities.
+* Simple GLR Parsers:: Using GLR parsers on unambiguous grammars.
+* Merging GLR Parses:: Using GLR parsers to resolve ambiguities.
* GLR Semantic Actions:: Considerations for semantic values and deferred
actions.
* Semantic Predicates:: Controlling a parse with arbitrary computations.
-* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler.
+* Compiler Requirements:: GLR parsers require a modern C compiler.
@end menu
@node Simple GLR Parsers
address@hidden Using @acronym{GLR} on Unambiguous Grammars
address@hidden @acronym{GLR} parsing, unambiguous grammars
address@hidden generalized @acronym{LR} (@acronym{GLR}) parsing, unambiguous
grammars
address@hidden Using GLR on Unambiguous Grammars
address@hidden GLR parsing, unambiguous grammars
address@hidden generalized LR (GLR) parsing, unambiguous grammars
@findex %glr-parser
@findex %expect-rr
@cindex conflicts
@cindex reduce/reduce conflicts
@cindex shift/reduce conflicts
-In the simplest cases, you can use the @acronym{GLR} algorithm
-to parse grammars that are unambiguous but fail to be @acronym{LR}(1).
+In the simplest cases, you can use the GLR algorithm
+to parse grammars that are unambiguous but fail to be LR(1).
Such grammars typically require more than one symbol of lookahead.
Consider a problem that
@@ -788,7 +788,7 @@ type enum = (a, b, c);
@noindent
The original language standard allows only numeric
literals and constant identifiers for the subrange bounds (@samp{lo}
-and @samp{hi}), but Extended Pascal (@acronym{ISO}/@acronym{IEC}
+and @samp{hi}), but Extended Pascal (ISO/IEC
10206) and many other
Pascal implementations allow arbitrary expressions there. This gives
rise to the following situation, containing a superfluous pair of
@@ -811,7 +811,7 @@ type enum = (a);
valid, and more-complicated cases can come up in practical programs.)
These two declarations look identical until the @samp{..} token.
-With normal @acronym{LR}(1) one-token lookahead it is not
+With normal LR(1) one-token lookahead 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
@@ -834,8 +834,8 @@ value of @samp{a} from the outer scope. So this approach
cannot
work.
A simple solution to this problem is to declare the parser to
-use the @acronym{GLR} algorithm.
-When the @acronym{GLR} parser reaches the critical state, it
+use the GLR algorithm.
+When the GLR parser reaches the critical state, it
merely 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
@@ -850,11 +850,11 @@ 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
-lookahead than the underlying @acronym{LR}(1) algorithm actually allows
-for. In this example, @acronym{LR}(2) would suffice, but also some cases
-that are not @acronym{LR}(@math{k}) for any @math{k} can be handled this way.
+lookahead than the underlying LR(1) algorithm actually allows
+for. In this example, LR(2) would suffice, but also some cases
+that are not LR(@math{k}) for any @math{k} can be handled this way.
-In general, a @acronym{GLR} parser can take quadratic or cubic worst-case time,
+In general, a 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.
@@ -905,7 +905,7 @@ expr : '(' expr ')'
@end group
@end example
-When used as a normal @acronym{LR}(1) grammar, Bison correctly complains
+When used as a normal LR(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
@@ -915,7 +915,7 @@ recognized:
type t = (a) .. b;
@end example
-The parser can be turned into a @acronym{GLR} parser, while also telling Bison
+The parser can be turned into a GLR parser, while also telling Bison
to be silent about the one known reduce/reduce conflict, by
adding these two declarations to the Bison input file (before the first
@samp{%%}):
@@ -931,18 +931,18 @@ parser recognizes all valid declarations, according to the
limited syntax above, transparently. In fact, the user does not even
notice when the parser splits.
-So here we have a case where we can use the benefits of @acronym{GLR},
+So here we have a case where we can use the benefits of GLR,
almost without disadvantages. Even in simple cases like this, however,
there are at least two potential problems to beware. First, always
-analyze the conflicts reported by Bison to make sure that @acronym{GLR}
-splitting is only done where it is intended. A @acronym{GLR} parser
+analyze the conflicts reported by Bison to make sure that GLR
+splitting is only done where it is intended. A GLR parser
splitting inadvertently may cause problems less obvious than an
address@hidden parser statically choosing the wrong alternative in a
+LR parser statically choosing the wrong alternative in a
conflict. Second, consider interactions with the lexer (@pxref{Semantic
Tokens}) 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 be
-eliminated by using @acronym{GLR} to shift the complications from the
+eliminated by using GLR to shift the complications from the
lexer to the parser. You must check the remaining cases for
correctness.
@@ -954,9 +954,9 @@ the type declaration is completed, it actually makes no
difference since
they cannot be used within the same enumerated type declaration.
@node Merging GLR Parses
address@hidden Using @acronym{GLR} to Resolve Ambiguities
address@hidden @acronym{GLR} parsing, ambiguous grammars
address@hidden generalized @acronym{LR} (@acronym{GLR}) parsing, ambiguous
grammars
address@hidden Using GLR to Resolve Ambiguities
address@hidden GLR parsing, ambiguous grammars
address@hidden generalized LR (GLR) parsing, ambiguous grammars
@findex %dprec
@findex %merge
@cindex conflicts
@@ -1022,7 +1022,7 @@ parses as either an @code{expr} or a @code{stmt}
Bison detects this as a reduce/reduce conflict between the rules
@code{expr : ID} and @code{declarator : ID}, which it cannot resolve at the
time it encounters @code{x} in the example above. Since this is a
address@hidden parser, it therefore splits the problem into two parses, one for
+GLR parser, it therefore splits the problem into two parses, one for
each choice of resolving the reduce/reduce conflict.
Unlike the example from the previous section (@pxref{Simple GLR Parsers}),
however, neither of these parses ``dies,'' because the grammar as it stands is
@@ -1031,7 +1031,7 @@ the other reduces @code{stmt : decl}, after which both
parsers are in an
identical state: they've seen @samp{prog stmt} and have the same unprocessed
input remaining. We say that these parses have @dfn{merged.}
-At this point, the @acronym{GLR} parser requires a specification in the
+At this point, the GLR parser requires a specification in the
grammar of how to choose between the competing parses.
In the example above, the two @code{%dprec}
declarations specify that Bison is to give precedence
@@ -1051,7 +1051,7 @@ T (x) + y;
@end example
@noindent
-This is another example of using @acronym{GLR} to parse an unambiguous
+This is another example of using GLR to parse an unambiguous
construct, as shown in the previous section (@pxref{Simple GLR Parsers}).
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
@@ -1118,7 +1118,7 @@ the offending merge.
@node GLR Semantic Actions
@subsection GLR Semantic Actions
-The nature of @acronym{GLR} parsing and the structure of the generated
+The nature of GLR parsing and the structure of the generated
parsers give rise to certain restrictions on semantic values and actions.
@subsubsection Deferred semantic actions
@@ -1126,14 +1126,14 @@ parsers give rise to certain restrictions on semantic
values and actions.
By definition, a deferred semantic action is not performed at the same time as
the associated reduction.
This raises caveats for several Bison features you might use in a semantic
-action in a @acronym{GLR} parser.
+action in a GLR parser.
@vindex yychar
address@hidden @acronym{GLR} parsers and @code{yychar}
address@hidden GLR parsers and @code{yychar}
@vindex yylval
address@hidden @acronym{GLR} parsers and @code{yylval}
address@hidden GLR parsers and @code{yylval}
@vindex yylloc
address@hidden @acronym{GLR} parsers and @code{yylloc}
address@hidden GLR parsers and @code{yylloc}
In any semantic action, you can examine @code{yychar} to determine the type of
the lookahead token present at the time of the associated reduction.
After checking that @code{yychar} is not set to @code{YYEMPTY} or @code{YYEOF},
@@ -1144,7 +1144,7 @@ influence syntax analysis.
@xref{Lookahead, ,Lookahead Tokens}.
@findex yyclearin
address@hidden @acronym{GLR} parsers and @code{yyclearin}
address@hidden GLR parsers and @code{yyclearin}
In a deferred semantic action, it's too late to influence syntax analysis.
In this case, @code{yychar}, @code{yylval}, and @code{yylloc} are set to
shallow copies of the values they had at the time of the associated reduction.
@@ -1157,11 +1157,11 @@ memory referenced by @code{yylval}.
@subsubsection YYERROR
@findex YYERROR
address@hidden @acronym{GLR} parsers and @code{YYERROR}
address@hidden GLR parsers and @code{YYERROR}
Another Bison feature requiring special consideration is @code{YYERROR}
(@pxref{Action Features}), which you can invoke in a semantic action to
initiate error recovery.
-During deterministic @acronym{GLR} operation, the effect of @code{YYERROR} is
+During deterministic GLR operation, the effect of @code{YYERROR} is
the same as its effect in a deterministic parser.
The effect in a deferred action is similar, but the precise point of the
error is undefined; instead, the parser reverts to deterministic operation,
@@ -1171,17 +1171,17 @@ parsing, @code{YYERROR} silently prunes
the parse that invoked the test.
@subsubsection Restrictions on semantic values and locations
address@hidden parsers require that you use POD (Plain Old Data) types for
+GLR parsers require that you use POD (Plain Old Data) types for
semantic values and location types when using the generated parsers as
C++ code.
@node Semantic Predicates
@subsection Controlling a Parse with Arbitrary Predicates
@findex %?
address@hidden Semantic predicates in @acronym{GLR} parsers
address@hidden Semantic predicates in GLR parsers
In addition to the @code{%dprec} and @code{%merge} directives,
address@hidden parsers
+GLR parsers
allow you to reject parses on the basis of arbitrary computations executed
in user code, without having Bison treat this rejection as an error
if there are alternative parses. (This feature is experimental and may
@@ -1226,7 +1226,7 @@ false). However, this
does @emph{not} have the same effect if @code{new_args} and @code{old_args}
have overlapping syntax.
Since the mid-rule actions testing @code{new_syntax} are deferred,
-a @acronym{GLR} parser first encounters the unresolved ambiguous reduction
+a GLR parser first encounters the unresolved ambiguous reduction
for cases where @code{new_args} and @code{old_args} recognize the same string
@emph{before} performing the tests of @code{new_syntax}. It therefore
reports an error.
@@ -1235,11 +1235,11 @@ Finally, be careful in writing predicates: deferred
actions have not been
evaluated, so that using them in a predicate will have undefined effects.
@node Compiler Requirements
address@hidden Considerations when Compiling @acronym{GLR} Parsers
address@hidden Considerations when Compiling GLR Parsers
@cindex @code{inline}
address@hidden @acronym{GLR} parsers and @code{inline}
address@hidden GLR parsers and @code{inline}
-The @acronym{GLR} parsers require a compiler for @acronym{ISO} C89 or
+The GLR parsers require a compiler for ISO C89 or
later. In addition, they use the @code{inline} keyword, which is not
C89, but is C99 and is a common extension in pre-C99 compilers. It is
up to the user of these parsers to handle
@@ -1342,7 +1342,7 @@ meanings.
In some cases the Bison parser file includes system headers, and in
those cases your code should respect the identifiers reserved by those
-headers. On some address@hidden hosts, @code{<alloca.h>}, @code{<malloc.h>},
+headers. On some non-GNU hosts, @code{<alloca.h>}, @code{<malloc.h>},
@code{<stddef.h>}, and @code{<stdlib.h>} are included as needed to
declare memory allocators and related types. @code{<libintl.h>} is
included if message translation is in use
@@ -1720,7 +1720,7 @@ or sequences of characters into tokens. The Bison parser
gets its
tokens by calling the lexical analyzer. @xref{Lexical, ,The Lexical
Analyzer Function @code{yylex}}.
-Only a simple lexical analyzer is needed for the @acronym{RPN}
+Only a simple lexical analyzer is needed for the RPN
calculator. This
lexical analyzer skips blanks and tabs, then reads in numbers as
@code{double} and returns them as @code{NUM} tokens. Any other character
@@ -2707,7 +2707,7 @@ appropriate delimiters:
@end example
Comments enclosed in @samp{/* @dots{} */} may appear in any of the sections.
-As a @acronym{GNU} extension, @samp{//} introduces a comment that
+As a GNU extension, @samp{//} introduces a comment that
continues until end of line.
@menu
@@ -3125,7 +3125,7 @@ By convention, it should be all lower case.
Symbol names can contain letters, underscores, periods, dashes, and (not
at the beginning) digits. Dashes in symbol names are a GNU
-extension, incompatible with @acronym{POSIX} Yacc. Terminal symbols
+extension, incompatible with POSIX Yacc. Terminal symbols
that contain periods or dashes make little sense: since they are not
valid symbols (in most programming languages) they are not exported as
token names.
@@ -3232,14 +3232,14 @@ characters in the following C-language string:
The @code{yylex} function and Bison must use a consistent character set
and encoding for character tokens. For example, if you run Bison in an
address@hidden environment, but then compile and run the resulting
+ASCII environment, but then compile and run the resulting
program in an environment that uses an incompatible character set like
address@hidden, the resulting program may not work because the tables
-generated by Bison will assume @acronym{ASCII} numeric values for
+EBCDIC, the resulting program may not work because the tables
+generated by Bison will assume ASCII numeric values for
character tokens. It is standard practice for software distributions to
contain C source files that were generated by Bison in an
address@hidden environment, so installers on platforms that are
-incompatible with @acronym{ASCII} must rebuild those files before
+ASCII environment, so installers on platforms that are
+incompatible with ASCII must rebuild those files before
compiling them.
The symbol @code{error} is a terminal symbol reserved for error recovery
@@ -3452,7 +3452,7 @@ the numbers associated with @var{x} and @var{y}.
In a simple program it may be sufficient to use the same data type for
the semantic values of all language constructs. This was true in the
address@hidden and infix calculator examples (@pxref{RPN Calc, ,Reverse Polish
+RPN and infix calculator examples (@pxref{RPN Calc, ,Reverse Polish
Notation Calculator}).
Bison normally uses the type @code{int} for semantic values if your
@@ -4078,7 +4078,7 @@ This location is stored in @code{yylloc}.
@node Location Default Action
@subsection Default Action for Locations
@vindex YYLLOC_DEFAULT
address@hidden @acronym{GLR} parsers and @code{YYLLOC_DEFAULT}
address@hidden GLR parsers and @code{YYLLOC_DEFAULT}
Actually, actions are not the best place to compute locations. Since
locations are much more general than semantic values, there is room in
@@ -4086,7 +4086,7 @@ the output parser to redefine the default action to take
for each
rule. The @code{YYLLOC_DEFAULT} macro is invoked each time a rule is
matched, before the associated action is run. It is also invoked
while processing a syntax error, to compute the error's location.
-Before reporting an unresolvable syntactic ambiguity, a @acronym{GLR}
+Before reporting an unresolvable syntactic ambiguity, a GLR
parser invokes @code{YYLLOC_DEFAULT} recursively to compute the location
of that ambiguity.
@@ -4098,7 +4098,7 @@ the location of the grouping (the result of the
computation). When a
rule is matched, the second parameter identifies locations of
all right hand side elements of the rule being matched, and the third
parameter is the size of the rule's right hand side.
-When a @acronym{GLR} parser reports an ambiguity, which of multiple candidate
+When a GLR parser reports an ambiguity, which of multiple candidate
right hand sides it passes to @code{YYLLOC_DEFAULT} is undefined.
When processing a syntax error, the second parameter identifies locations
of the symbols that were discarded during error processing, and the third
@@ -4383,7 +4383,7 @@ This says that the two alternative types are
@code{double} and @code{symrec
in the @code{%token} and @code{%type} declarations to pick one of the types
for a terminal or nonterminal symbol (@pxref{Type Decl, ,Nonterminal Symbols}).
-As an extension to @acronym{POSIX}, a tag is allowed after the
+As an extension to POSIX, a tag is allowed after the
@code{union}. For example:
@example
@@ -4400,7 +4400,7 @@ specifies the union tag @code{value}, so the
corresponding C type is
@code{union value}. If you do not specify a tag, it defaults to
@code{YYSTYPE}.
-As another extension to @acronym{POSIX}, you may specify multiple
+As another extension to POSIX, you may specify multiple
@code{%union} declarations; their contents are concatenated. However,
only the first @code{%union} declaration can specify a tag.
@@ -4665,11 +4665,11 @@ from @var{n}, or if there are any reduce/reduce
conflicts.
For deterministic parsers, reduce/reduce conflicts are more
serious, and should be eliminated entirely. Bison will always report
-reduce/reduce conflicts for these parsers. With @acronym{GLR}
+reduce/reduce conflicts for these parsers. With GLR
parsers, however, both kinds of conflicts are routine; otherwise,
-there would be no need to use @acronym{GLR} parsing. Therefore, it is
+there would be no need to use GLR parsing. Therefore, it is
also possible to specify an expected number of reduce/reduce conflicts
-in @acronym{GLR} parsers, using the declaration:
+in GLR parsers, using the declaration:
@example
%expect-rr @var{n}
@@ -4690,7 +4690,7 @@ go back to the beginning.
@item
Add an @code{%expect} declaration, copying the number @var{n} from the
-number which Bison printed. With @acronym{GLR} parsers, add an
+number which Bison printed. With GLR parsers, add an
@code{%expect-rr} declaration as well.
@end itemize
@@ -5229,7 +5229,7 @@ Boolean.
@findex %define lr.default-reductions
@cindex delayed syntax errors
@cindex syntax errors delayed
address@hidden @acronym{LAC}
address@hidden LAC
@findex %nonassoc
@itemize @bullet
@@ -5254,12 +5254,12 @@ The disadvantage is that, when the generated parser
encounters a
syntactically unacceptable token, the parser might then perform
unnecessary default reductions before it can detect the syntax error.
Such delayed syntax error detection is usually inherent in
address@hidden and @acronym{IELR} parser tables anyway due to
address@hidden state merging (@pxref{Decl Summary,,lr.type}).
+LALR and IELR parser tables anyway due to
+LR state merging (@pxref{Decl Summary,,lr.type}).
Furthermore, the use of @code{%nonassoc} can contribute to delayed
-syntax error detection even in the case of canonical @acronym{LR}.
+syntax error detection even in the case of canonical LR.
As an experimental feature, delayed syntax error detection can be
-overcome in all cases by enabling @acronym{LAC} (@pxref{Decl
+overcome in all cases by enabling LAC (@pxref{Decl
Summary,,parse.lac}, for details, including a discussion of the effects
of delayed syntax error detection).
@@ -5272,7 +5272,7 @@ However, the parser recognizes the ability to ignore the
lookahead token
in this way only when such a reduction is encoded as a default
reduction.
Thus, if default reductions are permitted only in consistent states,
-then a canonical @acronym{LR} parser that does not employ
+then a canonical LR parser that does not employ
@code{%nonassoc} detects a syntax error as soon as it @emph{needs} the
syntactically unacceptable token from the scanner.
@@ -5280,7 +5280,7 @@ syntactically unacceptable token from the scanner.
@cindex accepting state
In the accepting state, the default reduction is actually the accept
action.
-In this case, a canonical @acronym{LR} parser that does not employ
+In this case, a canonical LR parser that does not employ
@code{%nonassoc} detects a syntax error as soon as it @emph{reaches} the
syntactically unacceptable token in the input.
That is, it does not perform any extra reductions.
@@ -5343,85 +5343,85 @@ However, Bison does not compute which goto actions are
useless.
@item lr.type
@findex %define lr.type
address@hidden @acronym{LALR}
address@hidden @acronym{IELR}
address@hidden @acronym{LR}
address@hidden LALR
address@hidden IELR
address@hidden LR
@itemize @bullet
@item Language(s): all
@item Purpose: Specify the type of parser tables within the
address@hidden(1) family.
+LR(1) family.
(This feature is experimental.
More user feedback will help to stabilize it.)
@item Accepted Values:
@itemize
@item @code{lalr}.
-While Bison generates @acronym{LALR} parser tables by default for
-historical reasons, @acronym{IELR} or canonical @acronym{LR} is almost
+While Bison generates LALR parser tables by default for
+historical reasons, IELR or canonical LR is almost
always preferable for deterministic parsers.
-The trouble is that @acronym{LALR} parser tables can suffer from
+The trouble is that LALR parser tables can suffer from
mysterious conflicts and thus may not accept the full set of sentences
-that @acronym{IELR} and canonical @acronym{LR} accept.
+that IELR and canonical LR accept.
@xref{Mystery Conflicts}, for details.
-However, there are at least two scenarios where @acronym{LALR} may be
+However, there are at least two scenarios where LALR may be
worthwhile:
@itemize
address@hidden @acronym{GLR} with @acronym{LALR}
address@hidden When employing @acronym{GLR} parsers (@pxref{GLR Parsers}), if
you
address@hidden GLR with LALR
address@hidden When employing GLR parsers (@pxref{GLR Parsers}), if you
do not resolve any conflicts statically (for example, with @code{%left}
or @code{%prec}), then the parser explores all potential parses of any
given input.
-In this case, the use of @acronym{LALR} parser tables is guaranteed not
+In this case, the use of LALR parser tables is guaranteed not
to alter the language accepted by the parser.
address@hidden parser tables are the smallest parser tables Bison can
+LALR parser tables are the smallest parser tables Bison can
currently generate, so they may be preferable.
Nevertheless, once you begin to resolve conflicts statically,
address@hidden begins to behave more like a deterministic parser, and so
address@hidden and canonical @acronym{LR} can be helpful to avoid
address@hidden's mysterious behavior.
+GLR begins to behave more like a deterministic parser, and so
+IELR and canonical LR can be helpful to avoid
+LALR's mysterious behavior.
@item Occasionally during development, an especially malformed grammar
-with a major recurring flaw may severely impede the @acronym{IELR} or
-canonical @acronym{LR} parser table generation algorithm.
address@hidden can be a quick way to generate parser tables in order to
+with a major recurring flaw may severely impede the IELR or
+canonical LR parser table generation algorithm.
+LALR can be a quick way to generate parser tables in order to
investigate such problems while ignoring the more subtle differences
-from @acronym{IELR} and canonical @acronym{LR}.
+from IELR and canonical LR.
@end itemize
@item @code{ielr}.
address@hidden is a minimal @acronym{LR} algorithm.
-That is, given any grammar (@acronym{LR} or address@hidden),
address@hidden and canonical @acronym{LR} always accept exactly the same
+IELR is a minimal LR algorithm.
+That is, given any grammar (LR or non-LR),
+IELR and canonical LR always accept exactly the same
set of sentences.
-However, as for @acronym{LALR}, the number of parser states is often an
-order of magnitude less for @acronym{IELR} than for canonical
address@hidden
-More importantly, because canonical @acronym{LR}'s extra parser states
-may contain duplicate conflicts in the case of address@hidden
-grammars, the number of conflicts for @acronym{IELR} is often an order
+However, as for LALR, the number of parser states is often an
+order of magnitude less for IELR than for canonical
+LR.
+More importantly, because canonical LR's extra parser states
+may contain duplicate conflicts in the case of non-LR
+grammars, the number of conflicts for IELR is often an order
of magnitude less as well.
This can significantly reduce the complexity of developing of a grammar.
@item @code{canonical-lr}.
@cindex delayed syntax errors
@cindex syntax errors delayed
address@hidden @acronym{LAC}
address@hidden LAC
@findex %nonassoc
-While inefficient, canonical @acronym{LR} parser tables can be an
+While inefficient, canonical LR parser tables can be an
interesting means to explore a grammar because they have a property that
address@hidden and @acronym{LALR} tables do not.
+IELR and LALR tables do not.
That is, if @code{%nonassoc} is not used and default reductions are left
disabled (@pxref{Decl Summary,,lr.default-reductions}), then, for every
-left context of every canonical @acronym{LR} state, the set of tokens
+left context of every canonical LR state, the set of tokens
accepted by that state is guaranteed to be the exact set of tokens that
is syntactically acceptable in that left context.
-It might then seem that an advantage of canonical @acronym{LR} parsers
+It might then seem that an advantage of canonical LR parsers
in production is that, under the above constraints, they are guaranteed
to detect a syntax error as soon as possible without performing any
unnecessary reductions.
-However, @acronym{IELR} parsers using @acronym{LAC} (@pxref{Decl
+However, IELR parsers using LAC (@pxref{Decl
Summary,,parse.lac}) are also able to achieve this behavior without
sacrificing @code{%nonassoc} or default reductions.
@end itemize
@@ -5485,16 +5485,16 @@ ones.
@c ================================================== parse.lac
@item parse.lac
@findex %define parse.lac
address@hidden @acronym{LAC}
address@hidden LAC
@cindex lookahead correction
@itemize
@item Languages(s): C
address@hidden Purpose: Enable @acronym{LAC} (lookahead correction) to improve
address@hidden Purpose: Enable LAC (lookahead correction) to improve
syntax error handling.
-Canonical @acronym{LR}, @acronym{IELR}, and @acronym{LALR} can suffer
+Canonical LR, IELR, and LALR can suffer
from a couple of problems upon encountering a syntax error. First, the
parser might perform additional parser stack reductions before
discovering the syntax error. Such reductions perform user semantic
@@ -5507,13 +5507,13 @@ error message can both contain invalid tokens and omit
valid tokens.
The culprits for the above problems are @code{%nonassoc}, default
reductions in inconsistent states, and parser state merging. Thus,
address@hidden and @acronym{LALR} suffer the most. Canonical
address@hidden can suffer only if @code{%nonassoc} is used or if default
+IELR and LALR suffer the most. Canonical
+LR can suffer only if @code{%nonassoc} is used or if default
reductions are enabled for inconsistent states.
address@hidden is a new mechanism within the parsing algorithm that
-completely solves these problems for canonical @acronym{LR},
address@hidden, and @acronym{LALR} without sacrificing @code{%nonassoc},
+LAC is a new mechanism within the parsing algorithm that
+completely solves these problems for canonical LR,
+IELR, and LALR without sacrificing @code{%nonassoc},
default reductions, or state mering. Conceptually, the mechanism is
straight-forward. Whenever the parser fetches a new token from the
scanner so that it can determine the next parser action, it immediately
@@ -5527,7 +5527,7 @@ error messages are enabled, the parser must then discover
the list of
expected tokens, so it performs a separate exploratory parse for each
token in the grammar.
-There is one subtlety about the use of @acronym{LAC}. That is, when in
+There is one subtlety about the use of LAC. That is, when in
a consistent parser state with a default reduction, the parser will not
attempt to fetch a token from the scanner because no lookahead is needed
to determine the next parser action. Thus, whether default reductions
@@ -5538,16 +5538,16 @@ eventually @emph{needs} that token as a lookahead. The
latter behavior
is probably more intuitive, so Bison currently provides no way to
achieve the former behavior while default reductions are fully enabled.
-Thus, when @acronym{LAC} is in use, for some fixed decision of whether
+Thus, when LAC is in use, for some fixed decision of whether
to enable default reductions in consistent states, canonical
address@hidden and @acronym{IELR} behave exactly the same for both
+LR and IELR behave exactly the same for both
syntactically acceptable and syntactically unacceptable input. While
address@hidden still does not support the full language-recognition
-power of canonical @acronym{LR} and @acronym{IELR}, @acronym{LAC} at
-least enables @acronym{LALR}'s syntax error handling to correctly
-reflect @acronym{LALR}'s language-recognition power.
+LALR still does not support the full language-recognition
+power of canonical LR and IELR, LAC at
+least enables LALR's syntax error handling to correctly
+reflect LALR's language-recognition power.
-Because @acronym{LAC} requires many parse actions to be performed twice,
+Because LAC requires many parse actions to be performed twice,
it can have a performance penalty. However, not all parse actions must
be performed twice. Specifically, during a series of default reductions
in consistent states and shift actions, the parser never has to initiate
@@ -5557,7 +5557,7 @@ scanner, and the user's semantic actions, but none of
these are
performed during the exploratory parse. Finally, the base of the
temporary stack used during an exploratory parse is a pointer into the
normal parser state stack so that the stack is never physically copied.
-In our experience, the performance penalty of @acronym{LAC} has proven
+In our experience, the performance penalty of LAC has proven
insignificant for practical grammars.
@item Accepted Values: @code{none}, @code{full}
@@ -6307,7 +6307,7 @@ immediately return 1.
Obviously, in location tracking pure parsers, @code{yyerror} should have
an access to the current location.
-This is indeed the case for the @acronym{GLR}
+This is indeed the case for the GLR
parsers, but not for the Yacc parser, for historical reasons. I.e., if
@samp{%locations %define api.pure} is passed then the prototypes for
@code{yyerror} are:
@@ -6324,7 +6324,7 @@ void yyerror (int *nastiness, char const *msg); /* Yacc
parsers. */
void yyerror (int *nastiness, char const *msg); /* GLR parsers. */
@end example
-Finally, @acronym{GLR} and Yacc parsers share the same @code{yyerror} calling
+Finally, GLR and Yacc parsers share the same @code{yyerror} calling
convention for absolutely pure parsers, i.e., when the calling
convention of @code{yylex} @emph{and} the calling convention of
@samp{%define api.pure} are pure.
@@ -6414,7 +6414,7 @@ Return immediately from @code{yyparse}, indicating
success.
@findex YYBACKUP
Unshift a token. This macro is allowed only for rules that reduce
a single value, and only when there is no lookahead token.
-It is also disallowed in @acronym{GLR} parsers.
+It is also disallowed in GLR parsers.
It installs a lookahead 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.
@@ -6540,19 +6540,19 @@ also supports outputting diagnostics in the user's
native language. To
make this work, the user should set the usual environment variables.
@xref{Users, , The User's View, gettext, GNU @code{gettext} utilities}.
For example, the shell command @samp{export LC_ALL=fr_CA.UTF-8} might
-set the user's locale to French Canadian using the @acronym{UTF}-8
+set the user's locale to French Canadian using the UTF-8
encoding. The exact set of available locales depends on the user's
installation.
The maintainer of a package that uses a Bison-generated parser enables
the internationalization of the parser's output through the following
-steps. Here we assume a package that uses @acronym{GNU} Autoconf and
address@hidden Automake.
+steps. Here we assume a package that uses GNU Autoconf and
+GNU Automake.
@enumerate
@item
@cindex bison-i18n.m4
-Into the directory containing the @acronym{GNU} Autoconf macros used
+Into the directory containing the GNU Autoconf macros used
by the package---often called @file{m4}---copy the
@file{bison-i18n.m4} file installed by Bison under
@samp{share/aclocal/bison-i18n.m4} in Bison's installation directory.
@@ -6934,7 +6934,7 @@ whose precedence is a little higher, and so on.
@subsection Specifying Precedence Only
@findex %precedence
-Since @acronym{POSIX} Yacc defines only @code{%left}, @code{%right}, and
+Since POSIX Yacc defines only @code{%left}, @code{%right}, and
@code{%nonassoc}, which all defines precedence and associativity, little
attention is paid to the fact that precedence cannot be defined without
defining associativity. Yet, sometimes, when trying to solve a
@@ -7282,12 +7282,12 @@ name_list:
It would seem that this grammar can be parsed with only a single token
of lookahead: when a @code{param_spec} is being read, an @code{ID} is
a @code{name} if a comma or colon follows, or a @code{type} if another
address@hidden follows. In other words, this grammar is @acronym{LR}(1).
address@hidden follows. In other words, this grammar is LR(1).
address@hidden @acronym{LR}(1)
address@hidden @acronym{LALR}(1)
address@hidden LR(1)
address@hidden LALR(1)
However, for historical reasons, Bison cannot by default handle all
address@hidden(1) grammars.
+LR(1) grammars.
In this grammar, two contexts, that after an @code{ID} at the beginning
of a @code{param_spec} and likewise at the beginning of a
@code{return_spec}, are similar enough that Bison assumes they are the
@@ -7298,21 +7298,21 @@ a @code{type}. Bison is unable to determine at that
stage of processing
that the rules would require different lookahead tokens in the two
contexts, so it makes a single parser state for them both. Combining
the two contexts causes a conflict later. In parser terminology, this
-occurrence means that the grammar is not @acronym{LALR}(1).
+occurrence means that the grammar is not LALR(1).
For many practical grammars (specifically those that fall into the
address@hidden(1) class), the limitations of @acronym{LALR}(1) result in
+non-LR(1) class), the limitations of LALR(1) result in
difficulties beyond just mysterious reduce/reduce conflicts.
The best way to fix all these problems is to select a different parser
table generation algorithm.
-Either @acronym{IELR}(1) or canonical @acronym{LR}(1) would suffice, but
+Either IELR(1) or canonical LR(1) would suffice, but
the former is more efficient and easier to debug during development.
@xref{Decl Summary,,lr.type}, for details.
-(Bison's @acronym{IELR}(1) and canonical @acronym{LR}(1) implementations
+(Bison's IELR(1) and canonical LR(1) implementations
are experimental.
More user feedback will help to stabilize them.)
-If you instead wish to work around @acronym{LALR}(1)'s limitations, you
+If you instead wish to work around LALR(1)'s limitations, you
can often fix a mysterious conflict by identifying the two parser states
that are being confused, and adding something to make them look
distinct. In the above example, adding one rule to
@@ -7358,17 +7358,17 @@ return_spec:
;
@end example
-For a more detailed exposition of @acronym{LALR}(1) parsers and parser
+For a more detailed exposition of LALR(1) parsers and parser
generators, please see:
Frank DeRemer and Thomas Pennello, Efficient Computation of
address@hidden(1) Look-Ahead Sets, @address@hidden Transactions on
+LALR(1) Look-Ahead Sets, @cite{ACM Transactions on
Programming Languages and Systems}, Vol.@: 4, No.@: 4 (October 1982),
pp.@: 615--649 @uref{http://doi.acm.org/10.1145/69622.357187}.
@node Generalized LR Parsing
address@hidden Generalized @acronym{LR} (@acronym{GLR}) Parsing
address@hidden @acronym{GLR} parsing
address@hidden generalized @acronym{LR} (@acronym{GLR}) parsing
address@hidden Generalized LR (GLR) Parsing
address@hidden GLR parsing
address@hidden generalized LR (GLR) parsing
@cindex ambiguous grammars
@cindex nondeterministic parsing
@@ -7388,18 +7388,18 @@ 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 @acronym{LR} (or @acronym{GLR}). A Bison @acronym{GLR}
+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 @acronym{GLR} parser encounters such 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 @acronym{GLR} parsing stack is what is in effect a tree 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
@@ -7427,10 +7427,10 @@ 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 @acronym{GLR} parsing tree that
-permits the processing of any @acronym{LR}(1) grammar in linear time (in the
+It is possible to use a data structure for the GLR parsing tree that
+permits the processing of any LR(1) grammar in linear time (in the
size of the input), any unambiguous (not necessarily
address@hidden(1)) grammar in
+LR(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
@@ -7440,13 +7440,13 @@ grammars can require exponential time and space to
process. Such badly
behaving examples, however, are not generally of practical interest.
Usually, nondeterminism 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 @acronym{LR}(1) portions of a
+structure should generally be adequate. On LR(1) portions of a
grammar, in particular, it is only slightly slower than with the
-deterministic @acronym{LR}(1) Bison parser.
+deterministic LR(1) Bison parser.
-For a more detailed exposition of @acronym{GLR} parsers, please see: Elizabeth
+For a more detailed exposition of GLR parsers, please see: Elizabeth
Scott, Adrian Johnstone and Shamsa Sadaf Hussain, Tomita-Style
-Generalised @acronym{LR} Parsers, Royal Holloway, University of
+Generalised LR Parsers, Royal Holloway, University of
London, Department of Computer Science, TR-00-12,
@uref{http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps},
(2000-12-24).
@@ -7661,7 +7661,7 @@ This looks like a function call statement, but if
@code{foo} is a typedef
name, then this is actually a declaration of @code{x}. How can a Bison
parser for C decide how to parse this input?
-The method used in @acronym{GNU} C is to have two different token types,
+The method used in GNU C is to have two different token types,
@code{IDENTIFIER} and @code{TYPENAME}. When @code{yylex} finds an
identifier, it looks up the current declaration of the identifier in order
to decide which token type to return: @code{TYPENAME} if the identifier is
@@ -8266,14 +8266,14 @@ There are several means to enable compilation of trace
facilities:
@item the macro @code{YYDEBUG}
@findex YYDEBUG
Define the macro @code{YYDEBUG} to a nonzero value when you compile the
-parser. This is compliant with @acronym{POSIX} Yacc. You could use
+parser. This is compliant with POSIX Yacc. You could use
@samp{-DYYDEBUG=1} as a compiler option or you could put @samp{#define
YYDEBUG 1} in the prologue of the grammar file (@pxref{Prologue, , The
Prologue}).
@item the option @option{-t}, @option{--debug}
Use the @samp{-t} option when you run Bison (@pxref{Invocation,
-,Invoking Bison}). This is @acronym{POSIX} compliant too.
+,Invoking Bison}). This is POSIX compliant too.
@item the directive @samp{%debug}
@findex %debug
@@ -8287,7 +8287,7 @@ Add the @samp{%define parse.trace} directive (@pxref{Decl
Summary,
,Bison Declaration Summary}), or pass the @option{-Dparse.trace} option
(@pxref{Bison Options}). This is a Bison extension, which is especially
useful for languages that don't use a preprocessor. Unless
address@hidden and Yacc portability matter to you, this is the
+POSIX and Yacc portability matter to you, this is the
preferred solution.
@end table
@@ -8409,7 +8409,7 @@ bison -d -o @var{output.c++} @var{infile.y}
@noindent
will produce @file{output.c++} and @file{outfile.h++}.
-For compatibility with @acronym{POSIX}, the standard Bison
+For compatibility with POSIX, the standard Bison
distribution also contains a shell script called @command{yacc} that
invokes Bison with the @option{-y} option.
@@ -8464,7 +8464,7 @@ Also, if generating a deterministic parser in C, generate
@code{#define}
statements in addition to an @code{enum} to associate token numbers with token
names.
Thus, the following shell script can substitute for Yacc, and the Bison
-distribution contains such a script for compatibility with @acronym{POSIX}:
+distribution contains such a script for compatibility with POSIX:
@example
#! /bin/sh
@@ -8503,7 +8503,7 @@ be false alarms in existing grammars employing the Yacc
constructs
@item yacc
-Incompatibilities with @acronym{POSIX} Yacc.
+Incompatibilities with POSIX Yacc.
@item all
All the warnings.
@@ -8515,7 +8515,7 @@ Treat warnings as errors.
A category can be turned off by prefixing its name with @samp{no-}. For
instance, @option{-Wno-yacc} will hide the warnings about
address@hidden Yacc incompatibilities.
+POSIX Yacc incompatibilities.
@end table
@noindent
@@ -8662,7 +8662,7 @@ described under the @samp{-v} and @samp{-d} options.
@itemx address@hidden
Output a graphical representation of the parser's
automaton computed by Bison, in @uref{http://www.graphviz.org/, Graphviz}
address@hidden://www.graphviz.org/doc/info/lang.html, @acronym{DOT}} format.
address@hidden://www.graphviz.org/doc/info/lang.html, DOT} format.
@address@hidden is optional.
If omitted and the grammar file is @file{foo.y}, the output file will be
@file{foo.dot}.
@@ -8693,10 +8693,10 @@ the corresponding short option and directive.
The Yacc library contains default implementations of the
@code{yyerror} and @code{main} functions. These default
-implementations are normally not useful, but @acronym{POSIX} requires
+implementations are normally not useful, but POSIX requires
them. To use the Yacc library, link your program with the
@option{-ly} option. Note that Bison's implementation of the Yacc
-library is distributed under the terms of the @acronym{GNU} General
+library is distributed under the terms of the GNU General
Public License (@pxref{Copying}).
If you use the Yacc library's @code{yyerror} function, you should
@@ -9765,7 +9765,7 @@ Java.
Push parsers are currently unsupported in Java and @code{%define
api.push-pull} have no effect.
address@hidden parsers are currently unsupported in Java. Do not use the
+GLR parsers are currently unsupported in Java. Do not use the
@code{glr-parser} directive.
No header file can be generated for Java parsers. Do not use the
@@ -10355,7 +10355,7 @@ are addressed.
* Strings are Destroyed:: @code{yylval} Loses Track of Strings
* Implementing Gotos/Loops:: Control Flow in the Calculator
* Multiple start-symbols:: Factoring closely related grammars
-* Secure? Conform?:: Is Bison @acronym{POSIX} safe?
+* Secure? Conform?:: Is Bison POSIX safe?
* I can't build Bison:: Troubleshooting
* Where can I find help?:: Troubleshouting
* Bug Reports:: Troublereporting
@@ -10542,11 +10542,11 @@ i.e., precisely those that have a straightforward
execution model:
execute simple instructions one after the others.
@cindex abstract syntax tree
address@hidden @acronym{AST}
address@hidden AST
If you want a richer model, you will probably need to use the parser
to construct a tree that does represent the structure it has
recovered; this tree is usually called the @dfn{abstract syntax tree},
-or @address@hidden for short. Then, walking through this tree,
+or @dfn{AST} for short. Then, walking through this tree,
traversing it in various ways, will enable treatments such as its
execution or its translation, which will result in an interpreter or a
compiler.
@@ -10613,7 +10613,7 @@ Is Bison secure? Does it conform to POSIX?
If you're looking for a guarantee or certification, we don't provide it.
However, Bison is intended to be a reliable program that conforms to the
address@hidden specification for Yacc. If you run into problems,
+POSIX specification for Yacc. If you run into problems,
please send us a bug report.
@node I can't build Bison
@@ -10786,7 +10786,7 @@ Grammar}.
@deffn {Directive} address@hidden@address@hidden
Predicate actions. This is a type of action clause that may appear in
rules. The expression is evaluated, and if false, causes a syntax error. In
address@hidden parsers during nondeterministic operation,
+GLR parsers during nondeterministic operation,
this silently causes an alternative parse to die. During deterministic
operation, it is the same as the effect of YYERROR.
@xref{Semantic Predicates}.
@@ -10885,7 +10885,7 @@ discarded symbols. @xref{Destructor Decl, , Freeing
Discarded Symbols}.
@deffn {Directive} %dprec
Bison declaration to assign a precedence to a rule that is used at parse
time to resolve reduce/reduce conflicts. @xref{GLR Parsers, ,Writing
address@hidden Parsers}.
+GLR Parsers}.
@end deffn
@deffn {Symbol} $end
@@ -10914,8 +10914,8 @@ Summary}.
@end deffn
@deffn {Directive} %glr-parser
-Bison declaration to produce a @acronym{GLR} parser. @xref{GLR
-Parsers, ,Writing @acronym{GLR} Parsers}.
+Bison declaration to produce a GLR parser. @xref{GLR
+Parsers, ,Writing GLR Parsers}.
@end deffn
@deffn {Directive} %initial-action
@@ -10942,7 +10942,7 @@ for Pure Parsers}.
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, ,Writing @acronym{GLR} Parsers}.
address@hidden Parsers, ,Writing GLR Parsers}.
@end deffn
@deffn {Directive} %name-prefix "@var{prefix}"
@@ -11262,7 +11262,7 @@ A state whose only action is the accept action.
The accepting state is thus a consistent state.
@xref{Understanding,,}.
address@hidden Backus-Naur Form (@acronym{BNF}; also called ``Backus Normal
Form'')
address@hidden Backus-Naur Form (BNF; also called ``Backus Normal Form'')
Formal method of specifying context-free grammars originally proposed
by John Backus, and slightly improved by Peter Naur in his 1960-01-02
committee document contributing to what became the Algol 60 report.
@@ -11303,31 +11303,31 @@ 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 @acronym{LR} (@acronym{GLR})
address@hidden Generalized LR (GLR)
A parsing algorithm that can handle all context-free grammars, including those
-that are not @acronym{LR}(1). It resolves situations that Bison's
+that are not LR(1). It resolves situations that Bison's
deterministic parsing
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
address@hidden Parsing}.
+LR Parsing}.
@item Grouping
A language construct that is (in general) grammatically divisible;
for example, `expression' or `declaration' in address@hidden
@xref{Language and Grammar, ,Languages and Context-Free Grammars}.
address@hidden @acronym{IELR}(1)
-A minimal @acronym{LR}(1) parser table generation algorithm.
-That is, given any context-free grammar, @acronym{IELR}(1) generates
address@hidden IELR(1)
+A minimal LR(1) parser table generation algorithm.
+That is, given any context-free grammar, IELR(1) generates
parser tables with the full language recognition power of canonical
address@hidden(1) but with nearly the same number of parser states as
address@hidden(1).
+LR(1) but with nearly the same number of parser states as
+LALR(1).
This reduction in parser states is often an order of magnitude.
-More importantly, because canonical @acronym{LR}(1)'s extra parser
+More importantly, because canonical LR(1)'s extra parser
states may contain duplicate conflicts in the case of
address@hidden(1) grammars, the number of conflicts for
address@hidden(1) is often an order of magnitude less as well.
+non-LR(1) grammars, the number of conflicts for
+IELR(1) is often an order of magnitude less as well.
This can significantly reduce the complexity of developing of a grammar.
@xref{Decl Summary,,lr.type}.
@@ -11338,7 +11338,7 @@ performs some operation.
@item Input stream
A continuous flow of data between devices or programs.
address@hidden @acronym{LAC} (Lookahead Correction)
address@hidden LAC (Lookahead Correction)
A parsing mechanism that fixes the problem of delayed syntax error
detection, which is caused by LR state merging, default reductions, and
the use of @code{%nonassoc}. Delayed syntax error detection results in
@@ -11380,12 +11380,12 @@ A token which consists of two or more fixed
characters. @xref{Symbols}.
A token already read but not yet shifted. @xref{Lookahead, ,Lookahead
Tokens}.
address@hidden @acronym{LALR}(1)
address@hidden LALR(1)
The class of context-free grammars that Bison (like most other parser
-generators) can handle by default; a subset of @acronym{LR}(1).
+generators) can handle by default; a subset of LR(1).
@xref{Mystery Conflicts, ,Mysterious Reduce/Reduce Conflicts}.
address@hidden @acronym{LR}(1)
address@hidden LR(1)
The class of context-free grammars in which at most one token of
lookahead is needed to disambiguate the parsing of any piece of input.
--
1.7.0.4