Bison 1.24

This manual documents version 1.24 of Bison.

• Introduction
• Conditions
• Copying The GNU General Public License says how you can copy and share Bison

  Tutorial sections:

• Concepts Basic concepts for understanding Bison.
• Examples Three simple explained examples of using Bison.

  Reference sections:

• Grammar File Writing Bison declarations and rules.
• Interface C-language interface to the parser function yyparse.
• Algorithm How the Bison parser works at run-time.
• Error Recovery Writing rules for error recovery.
• Context Dependency What to do if your language syntax is too messy for Bison to handle straightforwardly.
• Debugging Debugging Bison parsers that parse wrong.
• Invocation How to run Bison (to produce the parser source file).
• Table of Symbols All the keywords of the Bison language are explained.
• Glossary Basic concepts are explained.
• Index Cross-references to the text.

  --- The Detailed Node Listing --- The Concepts of Bison

• Language and Grammar Languages and context-free grammars, as mathematical ideas.
• Grammar in Bison How we represent grammars for Bison's sake.
• Semantic Values Each token or syntactic grouping can have a semantic value (the value of an integer, the name of an identifier, etc.).
• Semantic Actions Each rule can have an action containing C code.
• Bison Parser What are Bison's input and output, how is the output used?
• Stages Stages in writing and running Bison grammars.
• Grammar Layout Overall structure of a Bison grammar file.

  Examples

• RPN Calc Reverse polish notation calculator; a first example with no operator precedence.
• Infix Calc Infix (algebraic) notation calculator. Operator precedence is introduced.
• Simple Error Recovery Continuing after syntax errors.
• Multi-function Calc Calculator with memory and trig functions. It uses multiple data-types for semantic values.
• Exercises Ideas for improving the multi-function calculator.

  Reverse Polish Notation Calculator

• Decls Bison and C declarations for rpcalc.
• Rules Grammar Rules for rpcalc, with explanation.
• Lexer The lexical analyzer.
• Main The controlling function.
• Error The error reporting function.
• Gen Running Bison on the grammar file.
• Comp Run the C compiler on the output code.

  Grammar Rules for rpcalc

• Rpcalc Input
• Rpcalc Line
• Rpcalc Expr

  Multi-Function Calculator: mfcalc

• Decl Bison declarations for multi-function calculator.
• Rules Grammar rules for the calculator.
• Symtab Symbol table management subroutines.

  Bison Grammar Files

• Grammar Outline Overall layout of the grammar file.
• Symbols Terminal and nonterminal symbols.
• Rules How to write grammar rules.
• Recursion Writing recursive rules.
• Semantics Semantic values and actions.
• Declarations All kinds of Bison declarations are described here.
• Multiple Parsers Putting more than one Bison parser in one program.

  Outline of a Bison Grammar

• C Declarations Syntax and usage of the C declarations section.
• Bison Declarations Syntax and usage of the Bison declarations section.
• Grammar Rules Syntax and usage of the grammar rules section.
• C Code Syntax and usage of the additional C code section.

  Defining Language Semantics

• Value Type Specifying one data type for all semantic values.
• Multiple Types Specifying several alternative data types.
• Actions An action is the semantic definition of a grammar rule.
• Action Types Specifying data types for actions to operate on.
• Mid-Rule Actions Most actions go at the end of a rule. This says when, why and how to use the exceptional action in the middle of a rule.

  Bison Declarations

• Token Decl Declaring terminal symbols.
• Precedence Decl Declaring terminals with precedence and associativity.
• Union Decl Declaring the set of all semantic value types.
• Type Decl Declaring the choice of type for a nonterminal symbol.
• Expect Decl Suppressing warnings about shift/reduce conflicts.
• Start Decl Specifying the start symbol.
• Pure Decl Requesting a reentrant parser.
• Decl Summary Table of all Bison declarations.

  Parser C-Language Interface

• Parser Function How to call yyparse and what it returns.
• Lexical You must supply a function yylex which reads tokens.
• Error Reporting You must supply a function yyerror.
• Action Features Special features for use in actions.

  The Lexical Analyzer Function yylex

• Calling Convention How yyparse calls yylex.
• Token Values How yylex must return the semantic value of the token it has read.
• Token Positions How yylex must return the text position (line number, etc.) of the token, if the actions want that.
• Pure Calling How the calling convention differs in a pure parser (see Pure Decl).

  The Bison Parser Algorithm

• Look-Ahead Parser looks one token ahead when deciding what to do.
• Shift/Reduce Conflicts: when either shifting or reduction is valid.
• Precedence Operator precedence works by resolving conflicts.
• Contextual Precedence When an operator's precedence depends on context.
• Parser States The parser is a finite-state-machine with stack.
• Reduce/Reduce When two rules are applicable in the same situation.
• Mystery Conflicts Reduce/reduce conflicts that look unjustified.
• Stack Overflow What happens when stack gets full. How to avoid it.

  Operator Precedence

• Why Precedence An example showing why precedence is needed.
• Using Precedence How to specify precedence in Bison grammars.
• Precedence Examples How these features are used in the previous example.
• How Precedence How they work.

  Handling Context Dependencies

• Semantic Tokens Token parsing can depend on the semantic context.
• Lexical Tie-ins Token parsing can depend on the syntactic context.
• Tie-in Recovery Lexical tie-ins have implications for how error recovery rules must be written.

  Invoking Bison

• Bison Options All the options described in detail, in alphabetical order by short options.
• Option Cross Key Alphabetical list of long options.
• VMS Invocation Bison command syntax on VMS.