X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/0860e38311eb80b0cba0b026d1fe7a8c81ffeec6..45d4c012d3dab39a65ea71dee825d1146e0ac4a7:/doc/bison.texinfo diff --git a/doc/bison.texinfo b/doc/bison.texinfo index d137e4cb..45125c19 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -320,6 +320,11 @@ C++ Parsers * C++ Scanner Interface:: Exchanges between yylex and parse * A Complete C++ Example:: Demonstrating their use +C++ Location Values + +* C++ position:: One point in the source file +* C++ location:: Two points in the source file + A Complete C++ Example * Calc++ --- C++ Calculator:: The specifications @@ -7688,7 +7693,7 @@ 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 LAC -has proven insignificant for practical grammars. +has proved insignificant for practical grammars. @end itemize While the LAC algorithm shares techniques that have been recognized in the @@ -8276,26 +8281,6 @@ creates a file @file{calc.output} with contents detailed below. The order of the output and the exact presentation might vary, but the interpretation is the same. -The first section includes details on conflicts that were solved thanks -to precedence and/or associativity: - -@example -Conflict in state 8 between rule 2 and token '+' resolved as reduce. -Conflict in state 8 between rule 2 and token '-' resolved as reduce. -Conflict in state 8 between rule 2 and token '*' resolved as shift. -@exdent @dots{} -@end example - -@noindent -The next section lists states that still have conflicts. - -@example -State 8 conflicts: 1 shift/reduce -State 9 conflicts: 1 shift/reduce -State 10 conflicts: 1 shift/reduce -State 11 conflicts: 4 shift/reduce -@end example - @noindent @cindex token, useless @cindex useless token @@ -8303,36 +8288,45 @@ State 11 conflicts: 4 shift/reduce @cindex useless nonterminal @cindex rule, useless @cindex useless rule -The next section reports useless tokens, nonterminal and rules. Useless -nonterminals and rules are removed in order to produce a smaller parser, -but useless tokens are preserved, since they might be used by the -scanner (note the difference between ``useless'' and ``unused'' -below): +The first section reports useless tokens, nonterminals and rules. Useless +nonterminals and rules are removed in order to produce a smaller parser, but +useless tokens are preserved, since they might be used by the scanner (note +the difference between ``useless'' and ``unused'' below): @example -Nonterminals useless in grammar: +Nonterminals useless in grammar useless -Terminals unused in grammar: +Terminals unused in grammar STR -Rules useless in grammar: -#6 useless: STR; +Rules useless in grammar + 6 useless: STR +@end example + +@noindent +The next section lists states that still have conflicts. + +@example +State 8 conflicts: 1 shift/reduce +State 9 conflicts: 1 shift/reduce +State 10 conflicts: 1 shift/reduce +State 11 conflicts: 4 shift/reduce @end example @noindent -The next section reproduces the exact grammar that Bison used: +Then Bison reproduces the exact grammar it used: @example Grammar - Number, Line, Rule - 0 5 $accept -> exp $end - 1 5 exp -> exp '+' exp - 2 6 exp -> exp '-' exp - 3 7 exp -> exp '*' exp - 4 8 exp -> exp '/' exp - 5 9 exp -> NUM + 0 $accept: exp $end + + 1 exp: exp '+' exp + 2 | exp '-' exp + 3 | exp '*' exp + 4 | exp '/' exp + 5 | NUM @end example @noindent @@ -8349,14 +8343,15 @@ $end (0) 0 '/' (47) 4 error (256) NUM (258) 5 +STR (259) @end group @group Nonterminals, with rules where they appear -$accept (8) +$accept (9) on left: 0 -exp (9) +exp (10) on left: 1 2 3 4 5, on right: 0 1 2 3 4 @end group @end example @@ -8373,11 +8368,11 @@ the location of the input cursor. @example state 0 - $accept -> . exp $ (rule 0) + 0 $accept: . exp $end - NUM shift, and go to state 1 + NUM shift, and go to state 1 - exp go to state 2 + exp go to state 2 @end example This reads as follows: ``state 0 corresponds to being at the very @@ -8403,27 +8398,27 @@ you want to see more detail you can invoke @command{bison} with @example state 0 - $accept -> . exp $ (rule 0) - exp -> . exp '+' exp (rule 1) - exp -> . exp '-' exp (rule 2) - exp -> . exp '*' exp (rule 3) - exp -> . exp '/' exp (rule 4) - exp -> . NUM (rule 5) + 0 $accept: . exp $end + 1 exp: . exp '+' exp + 2 | . exp '-' exp + 3 | . exp '*' exp + 4 | . exp '/' exp + 5 | . NUM - NUM shift, and go to state 1 + NUM shift, and go to state 1 - exp go to state 2 + exp go to state 2 @end example @noindent -In the state 1... +In the state 1@dots{} @example state 1 - exp -> NUM . (rule 5) + 5 exp: NUM . - $default reduce using rule 5 (exp) + $default reduce using rule 5 (exp) @end example @noindent @@ -8435,24 +8430,24 @@ jump to state 2 (@samp{exp: go to state 2}). @example state 2 - $accept -> exp . $ (rule 0) - exp -> exp . '+' exp (rule 1) - exp -> exp . '-' exp (rule 2) - exp -> exp . '*' exp (rule 3) - exp -> exp . '/' exp (rule 4) + 0 $accept: exp . $end + 1 exp: exp . '+' exp + 2 | exp . '-' exp + 3 | exp . '*' exp + 4 | exp . '/' exp - $ shift, and go to state 3 - '+' shift, and go to state 4 - '-' shift, and go to state 5 - '*' shift, and go to state 6 - '/' shift, and go to state 7 + $end shift, and go to state 3 + '+' shift, and go to state 4 + '-' shift, and go to state 5 + '*' shift, and go to state 6 + '/' shift, and go to state 7 @end example @noindent In state 2, the automaton can only shift a symbol. For instance, -because of the item @samp{exp -> exp . '+' exp}, if the lookahead is +because of the item @samp{exp: exp . '+' exp}, if the lookahead is @samp{+} it is shifted onto the parse stack, and the automaton -jumps to state 4, corresponding to the item @samp{exp -> exp '+' . exp}. +jumps to state 4, corresponding to the item @samp{exp: exp '+' . exp}. Since there is no default action, any lookahead not listed triggers a syntax error. @@ -8463,14 +8458,14 @@ state}: @example state 3 - $accept -> exp $ . (rule 0) + 0 $accept: exp $end . - $default accept + $default accept @end example @noindent -the initial rule is completed (the start symbol and the end -of input were read), the parsing exits successfully. +the initial rule is completed (the start symbol and the end-of-input were +read), the parsing exits successfully. The interpretation of states 4 to 7 is straightforward, and is left to the reader. @@ -8478,35 +8473,38 @@ the reader. @example state 4 - exp -> exp '+' . exp (rule 1) + 1 exp: exp '+' . exp + + NUM shift, and go to state 1 - NUM shift, and go to state 1 + exp go to state 8 - exp go to state 8 state 5 - exp -> exp '-' . exp (rule 2) + 2 exp: exp '-' . exp - NUM shift, and go to state 1 + NUM shift, and go to state 1 + + exp go to state 9 - exp go to state 9 state 6 - exp -> exp '*' . exp (rule 3) + 3 exp: exp '*' . exp + + NUM shift, and go to state 1 - NUM shift, and go to state 1 + exp go to state 10 - exp go to state 10 state 7 - exp -> exp '/' . exp (rule 4) + 4 exp: exp '/' . exp - NUM shift, and go to state 1 + NUM shift, and go to state 1 - exp go to state 11 + exp go to state 11 @end example As was announced in beginning of the report, @samp{State 8 conflicts: @@ -8515,17 +8513,17 @@ As was announced in beginning of the report, @samp{State 8 conflicts: @example state 8 - exp -> exp . '+' exp (rule 1) - exp -> exp '+' exp . (rule 1) - exp -> exp . '-' exp (rule 2) - exp -> exp . '*' exp (rule 3) - exp -> exp . '/' exp (rule 4) + 1 exp: exp . '+' exp + 1 | exp '+' exp . + 2 | exp . '-' exp + 3 | exp . '*' exp + 4 | exp . '/' exp - '*' shift, and go to state 6 - '/' shift, and go to state 7 + '*' shift, and go to state 6 + '/' shift, and go to state 7 - '/' [reduce using rule 1 (exp)] - $default reduce using rule 1 (exp) + '/' [reduce using rule 1 (exp)] + $default reduce using rule 1 (exp) @end example Indeed, there are two actions associated to the lookahead @samp{/}: @@ -8539,7 +8537,7 @@ NUM}, which corresponds to reducing rule 1. Because in deterministic parsing a single decision can be made, Bison arbitrarily chose to disable the reduction, see @ref{Shift/Reduce, , -Shift/Reduce Conflicts}. Discarded actions are reported in between +Shift/Reduce Conflicts}. Discarded actions are reported between square brackets. Note that all the previous states had a single possible action: either @@ -8558,72 +8556,85 @@ with some set of possible lookahead tokens. When run with @example state 8 - exp -> exp . '+' exp (rule 1) - exp -> exp '+' exp . [$, '+', '-', '/'] (rule 1) - exp -> exp . '-' exp (rule 2) - exp -> exp . '*' exp (rule 3) - exp -> exp . '/' exp (rule 4) + 1 exp: exp . '+' exp + 1 | exp '+' exp . [$end, '+', '-', '/'] + 2 | exp . '-' exp + 3 | exp . '*' exp + 4 | exp . '/' exp - '*' shift, and go to state 6 - '/' shift, and go to state 7 + '*' shift, and go to state 6 + '/' shift, and go to state 7 - '/' [reduce using rule 1 (exp)] - $default reduce using rule 1 (exp) + '/' [reduce using rule 1 (exp)] + $default reduce using rule 1 (exp) +@end example + +Note however that while @samp{NUM + NUM / NUM} is ambiguous (which results in +the conflicts on @samp{/}), @samp{NUM + NUM * NUM} is not: the conflict was +solved thanks to associativity and precedence directives. If invoked with +@option{--report=solved}, Bison includes information about the solved +conflicts in the report: + +@example +Conflict between rule 1 and token '+' resolved as reduce (%left '+'). +Conflict between rule 1 and token '-' resolved as reduce (%left '-'). +Conflict between rule 1 and token '*' resolved as shift ('+' < '*'). @end example + The remaining states are similar: @example @group state 9 - exp -> exp . '+' exp (rule 1) - exp -> exp . '-' exp (rule 2) - exp -> exp '-' exp . (rule 2) - exp -> exp . '*' exp (rule 3) - exp -> exp . '/' exp (rule 4) + 1 exp: exp . '+' exp + 2 | exp . '-' exp + 2 | exp '-' exp . + 3 | exp . '*' exp + 4 | exp . '/' exp - '*' shift, and go to state 6 - '/' shift, and go to state 7 + '*' shift, and go to state 6 + '/' shift, and go to state 7 - '/' [reduce using rule 2 (exp)] - $default reduce using rule 2 (exp) + '/' [reduce using rule 2 (exp)] + $default reduce using rule 2 (exp) @end group @group state 10 - exp -> exp . '+' exp (rule 1) - exp -> exp . '-' exp (rule 2) - exp -> exp . '*' exp (rule 3) - exp -> exp '*' exp . (rule 3) - exp -> exp . '/' exp (rule 4) + 1 exp: exp . '+' exp + 2 | exp . '-' exp + 3 | exp . '*' exp + 3 | exp '*' exp . + 4 | exp . '/' exp - '/' shift, and go to state 7 + '/' shift, and go to state 7 - '/' [reduce using rule 3 (exp)] - $default reduce using rule 3 (exp) + '/' [reduce using rule 3 (exp)] + $default reduce using rule 3 (exp) @end group @group state 11 - exp -> exp . '+' exp (rule 1) - exp -> exp . '-' exp (rule 2) - exp -> exp . '*' exp (rule 3) - exp -> exp . '/' exp (rule 4) - exp -> exp '/' exp . (rule 4) + 1 exp: exp . '+' exp + 2 | exp . '-' exp + 3 | exp . '*' exp + 4 | exp . '/' exp + 4 | exp '/' exp . - '+' shift, and go to state 4 - '-' shift, and go to state 5 - '*' shift, and go to state 6 - '/' shift, and go to state 7 + '+' shift, and go to state 4 + '-' shift, and go to state 5 + '*' shift, and go to state 6 + '/' shift, and go to state 7 - '+' [reduce using rule 4 (exp)] - '-' [reduce using rule 4 (exp)] - '*' [reduce using rule 4 (exp)] - '/' [reduce using rule 4 (exp)] - $default reduce using rule 4 (exp) + '+' [reduce using rule 4 (exp)] + '-' [reduce using rule 4 (exp)] + '*' [reduce using rule 4 (exp)] + '/' [reduce using rule 4 (exp)] + $default reduce using rule 4 (exp) @end group @end example @@ -9318,55 +9329,98 @@ define a @code{position}, a single point in a file, and a @code{location}, a range composed of a pair of @code{position}s (possibly spanning several files). -@deftypemethod {position} {std::string*} file +@tindex uint +In this section @code{uint} is an abbreviation for @code{unsigned int}: in +genuine code only the latter is used. + +@menu +* C++ position:: One point in the source file +* C++ location:: Two points in the source file +@end menu + +@node C++ position +@subsubsection C++ @code{position} + +@deftypeop {Constructor} {position} {} position (std::string* @var{file} = 0, uint @var{line} = 1, uint @var{col} = 1) +Create a @code{position} denoting a given point. Note that @code{file} is +not reclaimed when the @code{position} is destroyed: memory managed must be +handled elsewhere. +@end deftypeop + +@deftypemethod {position} {void} initialize (std::string* @var{file} = 0, uint @var{line} = 1, uint @var{col} = 1) +Reset the position to the given values. +@end deftypemethod + +@deftypeivar {position} {std::string*} file 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 filename_type "@var{type}"}. -@end deftypemethod +@end deftypeivar -@deftypemethod {position} {unsigned int} line +@deftypeivar {position} {uint} line The line, starting at 1. -@end deftypemethod +@end deftypeivar -@deftypemethod {position} {unsigned int} lines (int @var{height} = 1) +@deftypemethod {position} {uint} lines (int @var{height} = 1) Advance by @var{height} lines, resetting the column number. @end deftypemethod -@deftypemethod {position} {unsigned int} column -The column, starting at 0. -@end deftypemethod +@deftypeivar {position} {uint} column +The column, starting at 1. +@end deftypeivar -@deftypemethod {position} {unsigned int} columns (int @var{width} = 1) +@deftypemethod {position} {uint} columns (int @var{width} = 1) Advance by @var{width} columns, without changing the line number. @end deftypemethod -@deftypemethod {position} {position&} operator+= (position& @var{pos}, int @var{width}) -@deftypemethodx {position} {position} operator+ (const position& @var{pos}, int @var{width}) -@deftypemethodx {position} {position&} operator-= (const position& @var{pos}, int @var{width}) -@deftypemethodx {position} {position} operator- (position& @var{pos}, int @var{width}) +@deftypemethod {position} {position&} operator+= (int @var{width}) +@deftypemethodx {position} {position} operator+ (int @var{width}) +@deftypemethodx {position} {position&} operator-= (int @var{width}) +@deftypemethodx {position} {position} operator- (int @var{width}) Various forms of syntactic sugar for @code{columns}. @end deftypemethod -@deftypemethod {position} {position} operator<< (std::ostream @var{o}, const position& @var{p}) +@deftypemethod {position} {bool} operator== (const position& @var{that}) +@deftypemethodx {position} {bool} operator!= (const position& @var{that}) +Whether @code{*this} and @code{that} denote equal/different positions. +@end deftypemethod + +@deftypefun {std::ostream&} operator<< (std::ostream& @var{o}, const position& @var{p}) Report @var{p} on @var{o} like this: @samp{@var{file}:@var{line}.@var{column}}, or @samp{@var{line}.@var{column}} if @var{file} is null. +@end deftypefun + +@node C++ location +@subsubsection C++ @code{location} + +@deftypeop {Constructor} {location} {} location (const position& @var{begin}, const position& @var{end}) +Create a @code{Location} from the endpoints of the range. +@end deftypeop + +@deftypeop {Constructor} {location} {} location (const position& @var{pos} = position()) +@deftypeopx {Constructor} {location} {} location (std::string* @var{file}, uint @var{line}, uint @var{col}) +Create a @code{Location} denoting an empty range located at a given point. +@end deftypeop + +@deftypemethod {location} {void} initialize (std::string* @var{file} = 0, uint @var{line} = 1, uint @var{col} = 1) +Reset the location to an empty range at the given values. @end deftypemethod -@deftypemethod {location} {position} begin -@deftypemethodx {location} {position} end +@deftypeivar {location} {position} begin +@deftypeivarx {location} {position} end The first, inclusive, position of the range, and the first beyond. -@end deftypemethod +@end deftypeivar -@deftypemethod {location} {unsigned int} columns (int @var{width} = 1) -@deftypemethodx {location} {unsigned int} lines (int @var{height} = 1) +@deftypemethod {location} {uint} columns (int @var{width} = 1) +@deftypemethodx {location} {uint} lines (int @var{height} = 1) Advance the @code{end} position. @end deftypemethod -@deftypemethod {location} {location} operator+ (const location& @var{begin}, const location& @var{end}) -@deftypemethodx {location} {location} operator+ (const location& @var{begin}, int @var{width}) -@deftypemethodx {location} {location} operator+= (const location& @var{loc}, int @var{width}) +@deftypemethod {location} {location} operator+ (const location& @var{end}) +@deftypemethodx {location} {location} operator+ (int @var{width}) +@deftypemethodx {location} {location} operator+= (int @var{width}) Various forms of syntactic sugar. @end deftypemethod @@ -9374,6 +9428,16 @@ Various forms of syntactic sugar. Move @code{begin} onto @code{end}. @end deftypemethod +@deftypemethod {location} {bool} operator== (const location& @var{that}) +@deftypemethodx {location} {bool} operator!= (const location& @var{that}) +Whether @code{*this} and @code{that} denote equal/different ranges of +positions. +@end deftypemethod + +@deftypefun {std::ostream&} operator<< (std::ostream& @var{o}, const location& @var{p}) +Report @var{p} on @var{o}, taking care of special cases such as: no +@code{filename} defined, or equal filename/line or column. +@end deftypefun @node C++ Parser Interface @subsection C++ Parser Interface @@ -10345,7 +10409,7 @@ created with the correct @code{%param}s and/or @code{%lex-param}s. Use @code{%code init} for code added to the start of the constructor body. This is especially useful to initialize superclasses. Use -@samp{%define init_throws} to specify any uncatch exceptions. +@samp{%define init_throws} to specify any uncaught exceptions. @end deftypeop @deftypemethod {YYParser} {boolean} parse () @@ -11961,7 +12025,7 @@ London, Department of Computer Science, TR-00-12 (December 2000). @c LocalWords: NUM exp subsubsection kbd Ctrl ctype EOF getchar isdigit nonfree @c LocalWords: ungetc stdin scanf sc calc ulator ls lm cc NEG prec yyerrok rr @c LocalWords: longjmp fprintf stderr yylloc YYLTYPE cos ln Stallman Destructor -@c LocalWords: symrec val tptr FNCT fnctptr func struct sym enum +@c LocalWords: symrec val tptr FNCT fnctptr func struct sym enum IEC syntaxes @c LocalWords: fnct putsym getsym fname arith fncts atan ptr malloc sizeof Lex @c LocalWords: strlen strcpy fctn strcmp isalpha symbuf realloc isalnum DOTDOT @c LocalWords: ptypes itype YYPRINT trigraphs yytname expseq vindex dtype Unary @@ -11971,35 +12035,36 @@ London, Department of Computer Science, TR-00-12 (December 2000). @c LocalWords: strncmp intval tindex lvalp locp llocp typealt YYBACKUP subrange @c LocalWords: YYEMPTY YYEOF YYRECOVERING yyclearin GE def UMINUS maybeword loc @c LocalWords: Johnstone Shamsa Sadaf Hussain Tomita TR uref YYMAXDEPTH inline -@c LocalWords: YYINITDEPTH stmts ref initdcl maybeasm notype Lookahead +@c LocalWords: YYINITDEPTH stmts ref initdcl maybeasm notype Lookahead yyoutput @c LocalWords: hexflag STR exdent itemset asis DYYDEBUG YYFPRINTF args Autoconf @c LocalWords: infile ypp yxx outfile itemx tex leaderfill Troubleshouting sqrt @c LocalWords: hbox hss hfill tt ly yyin fopen fclose ofirst gcc ll lookahead @c LocalWords: nbar yytext fst snd osplit ntwo strdup AST Troublereporting th @c LocalWords: YYSTACK DVI fdl printindex IELR nondeterministic nonterminals ps @c LocalWords: subexpressions declarator nondeferred config libintl postfix LAC -@c LocalWords: preprocessor nonpositive unary nonnumeric typedef extern rhs -@c LocalWords: yytokentype destructor multicharacter nonnull EBCDIC +@c LocalWords: preprocessor nonpositive unary nonnumeric typedef extern rhs sr +@c LocalWords: yytokentype destructor multicharacter nonnull EBCDIC nterm LR's @c LocalWords: lvalue nonnegative XNUM CHR chr TAGLESS tagless stdout api TOK -@c LocalWords: destructors Reentrancy nonreentrant subgrammar nonassociative +@c LocalWords: destructors Reentrancy nonreentrant subgrammar nonassociative Ph @c LocalWords: deffnx namespace xml goto lalr ielr runtime lex yacc yyps env @c LocalWords: yystate variadic Unshift NLS gettext po UTF Automake LOCALEDIR @c LocalWords: YYENABLE bindtextdomain Makefile DEFS CPPFLAGS DBISON DeRemer -@c LocalWords: autoreconf Pennello multisets nondeterminism Generalised baz +@c LocalWords: autoreconf Pennello multisets nondeterminism Generalised baz ACM @c LocalWords: redeclare automata Dparse localedir datadir XSLT midrule Wno -@c LocalWords: Graphviz multitable headitem hh basename Doxygen fno +@c LocalWords: Graphviz multitable headitem hh basename Doxygen fno filename @c LocalWords: doxygen ival sval deftypemethod deallocate pos deftypemethodx @c LocalWords: Ctor defcv defcvx arg accessors arithmetics CPP ifndef CALCXX @c LocalWords: lexer's calcxx bool LPAREN RPAREN deallocation cerrno climits @c LocalWords: cstdlib Debian undef yywrap unput noyywrap nounput zA yyleng -@c LocalWords: errno strtol ERANGE str strerror iostream argc argv Javadoc +@c LocalWords: errno strtol ERANGE str strerror iostream argc argv Javadoc PSLR @c LocalWords: bytecode initializers superclass stype ASTNode autoboxing nls @c LocalWords: toString deftypeivar deftypeivarx deftypeop YYParser strictfp @c LocalWords: superclasses boolean getErrorVerbose setErrorVerbose deftypecv @c LocalWords: getDebugStream setDebugStream getDebugLevel setDebugLevel url @c LocalWords: bisonVersion deftypecvx bisonSkeleton getStartPos getEndPos -@c LocalWords: getLVal defvar deftypefn deftypefnx gotos msgfmt Corbett -@c LocalWords: subdirectory Solaris nonassociativity +@c LocalWords: getLVal defvar deftypefn deftypefnx gotos msgfmt Corbett LALR's +@c LocalWords: subdirectory Solaris nonassociativity perror schemas Malloy +@c LocalWords: Scannerless ispell american @c Local Variables: @c ispell-dictionary: "american"