Writing @acronym{GLR} Parsers
-* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars
-* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities
-* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler
+* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars
+* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities
+* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler
Examples
Bison Declarations
+* Require Decl:: Requiring a Bison version.
* Token Decl:: Declaring terminal symbols.
* Precedence Decl:: Declaring terminals with precedence and associativity.
* Union Decl:: Declaring the set of all semantic value types.
merged result.
@menu
-* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars
-* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities
-* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler
+* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars
+* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities
+* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler
@end menu
@node Simple GLR Parsers
This also includes numerous identifiers used for internal purposes.
Therefore, you should avoid using C identifiers starting with @samp{yy}
or @samp{YY} in the Bison grammar file except for the ones defined in
-this manual.
+this manual. Also, you should avoid using the C identifiers
+@samp{malloc} and @samp{free} for anything other than their usual
+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 non-@acronym{GNU} hosts, @code{<alloca.h>},
+headers. On some non-@acronym{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
Grammars}).
@menu
+* Require Decl:: Requiring a Bison version.
* Token Decl:: Declaring terminal symbols.
* Precedence Decl:: Declaring terminals with precedence and associativity.
* Union Decl:: Declaring the set of all semantic value types.
* Decl Summary:: Table of all Bison declarations.
@end menu
+@node Require Decl
+@subsection Require a Version of Bison
+@cindex version requirement
+@cindex requiring a version of Bison
+@findex %require
+
+You may require the minimum version of Bison to process the grammar. If
+the requirement is not met, @command{bison} exits with an error.
+
+@example
+%require "@var{version}"
+@end example
+
@node Token Decl
@subsection Token Type Names
@cindex declaring token type names
For instance, if your locations use a file name, you may use
@example
-%parse-param @{ const char *file @};
+%parse-param @{ char const *file_name @};
%initial-action
@{
- @@$.begin.file = @@$.end.file = file;
+ @@$.begin.filename = @@$.end.filename = file_name;
@};
@end example
(Reentrant) Parser}).
@end deffn
+@deffn {Directive} %require "@var{version}"
+Specify that version @var{version} or higher of Bison required for the
+grammar.
+@xref{Require Decl, , Require a Version of Bison}.
+@end deffn
+
@deffn {Directive} %token-table
Generate an array of token names in the parser file. The name of the
array is @code{yytname}; @code{yytname[@var{i}]} is the name of the
The value returned by @code{yyparse} is 0 if parsing was successful (return
is due to end-of-input).
-The value is 1 if parsing failed (return is due to a syntax error).
+The value is 1 if parsing failed because of invalid input, i.e., input
+that contains a syntax error or that causes @code{YYABORT} to be
+invoked.
+
+The value is 2 if parsing failed due to memory exhaustion.
@end deftypefun
In an action, you can cause immediate return from @code{yyparse} by using
@vindex yynerrs
The variable @code{yynerrs} contains the number of syntax errors
-encountered so far. Normally this variable is global; but if you
+reported so far. Normally this variable is global; but if you
request a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser})
then it is a local variable which only the actions can access.
The @code{%union} directive works as for C, see @ref{Union Decl, ,The
Collection of Value Types}. In particular it produces a genuine
@code{union}@footnote{In the future techniques to allow complex types
-within pseudo-unions (variants) might be implemented to alleviate
-these issues.}, which have a few specific features in C++.
+within pseudo-unions (similar to Boost variants) might be implemented to
+alleviate these issues.}, which have a few specific features in C++.
@itemize @minus
@item
-The name @code{YYSTYPE} also denotes @samp{union YYSTYPE}. You may
-forward declare it just with @samp{union YYSTYPE;}.
+The type @code{YYSTYPE} is defined but its use is discouraged: rather
+you should refer to the parser's encapsulated type
+@code{yy::parser::semantic_type}.
@item
Non POD (Plain Old Data) types cannot be used. C++ forbids any
instance of classes with constructors in unions: only @emph{pointers}
@c - %locations
@c - class Position
@c - class Location
-@c - %define "file_type" "const symbol::Symbol"
+@c - %define "filename_type" "const symbol::Symbol"
When the directive @code{%locations} is used, the C++ parser supports
location tracking, see @ref{Locations, , Locations Overview}. Two
The name of the file. It will always be handled as a pointer, the
parser will never duplicate nor deallocate it. As an experimental
feature you may change it to @samp{@var{type}*} using @samp{%define
-"file_type" "@var{type}"}.
+"filename_type" "@var{type}"}.
@end deftypemethod
@deftypemethod {position} {unsigned int} line
The declaration of this driver class, @file{calc++-driver.hh}, is as
follows. The first part includes the CPP guard and imports the
-required standard library components.
+required standard library components, and the declaration of the parser
+class.
@comment file: calc++-driver.hh
@example
# define CALCXX_DRIVER_HH
# include <string>
# include <map>
+# include "calc++-parser.hh"
@end example
-@noindent
-Then come forward declarations. Because the parser uses the parsing
-driver and reciprocally, simple inclusions of header files will not
-do. Because the driver's declaration is the one that will be imported
-by the rest of the project, it is saner to forward declare the
-parser's information here.
-
-@comment file: calc++-driver.hh
-@example
-// Forward declarations.
-union YYSTYPE;
-namespace yy
-@{
- class location;
- class calcxx_parser;
-@}
-class calcxx_driver;
-@end example
@noindent
Then comes the declaration of the scanning function. Flex expects
@example
// Announce to Flex the prototype we want for lexing function, ...
# define YY_DECL \
- int yylex (YYSTYPE* yylval, yy::location* yylloc, calcxx_driver& driver)
+ int yylex (yy::calcxx_parser::semantic_type* yylval, \
+ yy::calcxx_parser::location_type* yylloc, \
+ calcxx_driver& driver)
// ... and declare it for the parser's sake.
YY_DECL;
@end example
@node Calc++ Parser
@subsection Calc++ Parser
-The parser definition file @file{calc++-parser.yy} starts by asking
-for the C++ skeleton, the creation of the parser header file, and
-specifies the name of the parser class. It then includes the required
-headers.
+The parser definition file @file{calc++-parser.yy} starts by asking for
+the C++ LALR(1) skeleton, the creation of the parser header file, and
+specifies the name of the parser class. Because the C++ skeleton
+changed several times, it is safer to require the version you designed
+the grammar for.
@comment file: calc++-parser.yy
@example
%skeleton "lalr1.cc" /* -*- C++ -*- */
-%define "parser_class_name" "calcxx_parser"
+%require "2.1a"
%defines
+%define "parser_class_name" "calcxx_parser"
+@end example
+
+@noindent
+Then come the declarations/inclusions needed to define the
+@code{%union}. Because the parser uses the parsing driver and
+reciprocally, both cannot include the header of the other. Because the
+driver's header needs detailed knowledge about the parser class (in
+particular its inner types), it is the parser's header which will simply
+use a forward declaration of the driver.
+
+@comment file: calc++-parser.yy
+@example
%@{
# include <string>
-# include "calc++-driver.hh"
+class calcxx_driver;
%@}
@end example
%initial-action
@{
// Initialize the initial location.
- @@$.begin.file = @@$.end.file = &driver.file;
+ @@$.begin.filename = @@$.end.filename = &driver.file;
@};
@end example
@};
@end example
+@noindent
+The code between @samp{%@{} and @samp{%@}} after the introduction of the
+@samp{%union} is output in the @file{*.cc} file; it needs detailed
+knowledge about the driver.
+
+@comment file: calc++-parser.yy
+@example
+%@{
+# include "calc++-driver.hh"
+%@}
+@end example
+
+
@noindent
The token numbered as 0 corresponds to end of file; the following line
allows for nicer error messages referring to ``end of file'' instead
@comment file: calc++-parser.yy
@example
-%token YYEOF 0 "end of file"
-%token TOKEN_ASSIGN ":="
-%token <sval> TOKEN_IDENTIFIER "identifier"
-%token <ival> TOKEN_NUMBER "number"
-%type <ival> exp "expression"
+%token END 0 "end of file"
+%token ASSIGN ":="
+%token <sval> IDENTIFIER "identifier"
+%token <ival> NUMBER "number"
+%type <ival> exp "expression"
@end example
@noindent
assignments: assignments assignment @{@}
| /* Nothing. */ @{@};
-assignment: TOKEN_IDENTIFIER ":=" exp @{ driver.variables[*$1] = $3; @};
+assignment: "identifier" ":=" exp @{ driver.variables[*$1] = $3; @};
%left '+' '-';
%left '*' '/';
| exp '-' exp @{ $$ = $1 - $3; @}
| exp '*' exp @{ $$ = $1 * $3; @}
| exp '/' exp @{ $$ = $1 / $3; @}
- | TOKEN_IDENTIFIER @{ $$ = driver.variables[*$1]; @}
- | TOKEN_NUMBER @{ $$ = $1; @};
+ | "identifier" @{ $$ = driver.variables[*$1]; @}
+ | "number" @{ $$ = $1; @};
%%
@end example
@end example
@noindent
-The rules are simple, just note the use of the driver to report
-errors.
+The rules are simple, just note the use of the driver to report errors.
+It is convenient to use a typedef to shorten
+@code{yy::calcxx_parser::token::identifier} into
+@code{token::identifier} for isntance.
@comment file: calc++-scanner.ll
@example
+%@{
+ typedef yy::calcxx_parser::token token;
+%@}
+
[-+*/] return yytext[0];
-":=" return TOKEN_ASSIGN;
+":=" return token::ASSIGN;
@{int@} @{
errno = 0;
long n = strtol (yytext, NULL, 10);
if (! (INT_MIN <= n && n <= INT_MAX && errno != ERANGE))
driver.error (*yylloc, "integer is out of range");
yylval->ival = n;
- return TOKEN_NUMBER;
+ return token::NUMBER;
@}
-@{id@} yylval->sval = new std::string (yytext); return TOKEN_IDENTIFIER;
+@{id@} yylval->sval = new std::string (yytext); return token::IDENTIFIER;
. driver.error (*yylloc, "invalid character");
%%
@end example
@xref{Pure Decl, ,A Pure (Reentrant) Parser}.
@end deffn
+@deffn {Directive} %require "@var{version}"
+Specify that version @var{version} or higher of Bison required for the
+grammar.
+@xref{Require Decl, , Require a Version of Bison}.
+@end deffn
+
@deffn {Directive} %right
Bison declaration to assign right associativity to token(s).
@xref{Precedence Decl, ,Operator Precedence}.
@end deffn
@deffn {Variable} yynerrs
-Global variable which Bison increments each time there is a syntax error.
+Global variable which Bison increments each time it reports a syntax error.
(In a pure parser, it is a local variable within @code{yyparse}.)
@xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}.
@end deffn
reserved for future Bison extensions. If not defined,
@code{YYSTACK_USE_ALLOCA} defaults to 0.
-If you define @code{YYSTACK_USE_ALLOCA} to 1, it is your
-responsibility to make sure that @code{alloca} is visible, e.g., by
-using @acronym{GCC} or by including @code{<stdlib.h>}. Furthermore,
-in the all-too-common case where your code may run on a host with a
+In the all-too-common case where your code may run on a host with a
limited stack and with unreliable stack-overflow checking, you should
set @code{YYMAXDEPTH} to a value that cannot possibly result in
unchecked stack overflow on any of your target hosts when
projects / bison.git / blobdiff