;
@end example
+For a more detailed exposition of @acronym{LALR}(1) parsers and parser
+generators, please see:
+Frank DeRemer and Thomas Pennello, Efficient Computation of
+@acronym{LALR}(1) Look-Ahead Sets, @cite{@acronym{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
@section Generalized @acronym{LR} (@acronym{GLR}) Parsing
@cindex @acronym{GLR} parsing
@c - Always pure
@c - initial action
-The C++ parser LALR(1) skeleton is named @file{lalr1.cc}. To select
+The C++ parser @acronym{LALR}(1) skeleton is named @file{lalr1.cc}. To select
it, you may either pass the option @option{--skeleton=lalr1.cc} to
Bison, or include the directive @samp{%skeleton "lalr1.cc"} in the
grammar preamble. When run, @command{bison} will create several
follows. The first part includes the CPP guard and imports the
required standard library components.
+@comment file: calc++-driver.hh
@example
#ifndef CALCXX_DRIVER_HH
# define CALCXX_DRIVER_HH
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 calcxx_parser; @}
+namespace yy
+@{
+ class location;
+ class calcxx_parser;
+@}
class calcxx_driver;
@end example
the signature of @code{yylex} to be defined in the macro
@code{YY_DECL}, and the C++ parser expects it to be declared. We can
factor both as follows.
+
+@comment file: calc++-driver.hh
@example
// Announce to Flex the prototype we want for lexing function, ...
-# define YY_DECL \
+# define YY_DECL \
int yylex (YYSTYPE* yylval, yy::location* yylloc, calcxx_driver& driver)
// ... and declare it for the parser's sake.
YY_DECL;
The @code{calcxx_driver} class is then declared with its most obvious
members.
+@comment file: calc++-driver.hh
@example
// Conducting the whole scanning and parsing of Calc++.
class calcxx_driver
have two members function to open and close the scanning phase.
members.
+@comment file: calc++-driver.hh
@example
// Handling the scanner.
void scan_begin ();
@noindent
Similarly for the parser itself.
+@comment file: calc++-driver.hh
@example
// Handling the parser.
void parse (const std::string& f);
compiler driver using the following two member functions. Finally, we
close the class declaration and CPP guard.
+@comment file: calc++-driver.hh
@example
// Error handling.
void error (const yy::location& l, const std::string& m);
are simple stubs, they should actually register the located error
messages and set error state.
+@comment file: calc++-driver.cc
@example
#include "calc++-driver.hh"
#include "calc++-parser.hh"
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.
+
+@comment file: calc++-parser.yy
@example
%skeleton "lalr1.cc" /* -*- C++ -*- */
%define "parser_class_name" "calcxx_parser"
This provides a simple but effective pure interface, not relying on
global variables.
+@comment file: calc++-parser.yy
@example
// The parsing context.
%parse-param @{ calcxx_driver& driver @}
relatively to the previous locations: the file name will be
automatically propagated.
+@comment file: calc++-parser.yy
@example
%locations
%initial-action
Use the two following directives to enable parser tracing and verbose
error messages.
+@comment file: calc++-parser.yy
@example
%debug
%error-verbose
Semantic values cannot use ``real'' objects, but only pointers to
them.
+@comment file: calc++-parser.yy
@example
// Symbols.
%union
symbol. Note that the tokens names are prefixed by @code{TOKEN_} to
avoid name clashes.
+@comment file: calc++-parser.yy
@example
%token YYEOF 0 "end of file"
%token TOKEN_ASSIGN ":="
To enable memory deallocation during error recovery, use
@code{%destructor}.
+@comment file: calc++-parser.yy
@example
%printer @{ debug_stream () << *$$; @} "identifier"
%destructor @{ delete $$; @} "identifier"
@noindent
The grammar itself is straightforward.
+@comment file: calc++-parser.yy
@example
%%
%start unit;
Finally the @code{error} member function registers the errors to the
driver.
+@comment file: calc++-parser.yy
@example
void
-yy::calcxx_parser::error (const location_type& l, const std::string& m)
+yy::calcxx_parser::error (const yy::calcxx_parser::location_type& l,
+ const std::string& m)
@{
driver.error (l, m);
@}
The Flex scanner first includes the driver declaration, then the
parser's to get the set of defined tokens.
+@comment file: calc++-scanner.ll
@example
%@{ /* -*- C++ -*- */
# include <string>
actual file, this is not an interactive session with the user.
Finally we enable the scanner tracing features.
+@comment file: calc++-scanner.ll
@example
%option noyywrap nounput batch debug
@end example
@noindent
Abbreviations allow for more readable rules.
+@comment file: calc++-scanner.ll
@example
id [a-zA-Z][a-zA-Z_0-9]*
int [0-9]+
is moved onto the end cursor to effectively ignore the blanks
preceding tokens. Comments would be treated equally.
+@comment file: calc++-scanner.ll
@example
+%@{
+# define YY_USER_ACTION yylloc->columns (yyleng);
+%@}
%%
%@{
yylloc->step ();
-# define YY_USER_ACTION yylloc->columns (yyleng);
%@}
@{blank@}+ yylloc->step ();
[\n]+ yylloc->lines (yyleng); yylloc->step ();
The rules are simple, just note the use of the driver to report
errors.
+@comment file: calc++-scanner.ll
@example
[-+*/] return yytext[0];
":=" return TOKEN_ASSIGN;
Finally, because the scanner related driver's member function depend
on the scanner's data, it is simpler to implement them in this file.
+@comment file: calc++-scanner.ll
@example
void
calcxx_driver::scan_begin ()
The top level file, @file{calc++.cc}, poses no problem.
+@comment file: calc++.cc
@example
#include <iostream>
#include "calc++-driver.hh"
projects / bison.git / blobdiff