calc
ltcalc
mfcalc
yyparse
yypush_parse
yypull_parse
yystate_new
yystate_delete
yylex
yyerror
Next: Introduction [Contents][Index]
This manual (19 January 2020) is for GNU Bison (version 3.5.1), the GNU parser generator.
Copyright © 1988–1993, 1995, 1998–2015, 2018–2020 Free Software Foundation, Inc.
Permission is granted to copy, distribute and/or modify this document 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 GNU Manual,” and with the Back-Cover Texts as in (a) below. A copy of the license is included in the section entitled “GNU Free Documentation License.”
(a) The FSF’s Back-Cover Text is: “You have the freedom to copy and modify this GNU manual. Buying copies from the FSF supports it in developing GNU and promoting software freedom.”
• Introduction | What GNU Bison is. | |
• Conditions | Conditions for using Bison and its output. | |
• 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 | Understanding or debugging Bison parsers. | |
• Invocation | How to run Bison (to produce the parser implementation). | |
• Other Languages | Creating C++ and Java parsers. | |
• History | How Bison came to be | |
• FAQ | Frequently Asked Questions | |
• Table of Symbols | All the keywords of the Bison language are explained. | |
• Glossary | Basic concepts are explained. | |
• GNU Free Documentation License | Copying and sharing this manual | |
• Bibliography | Publications cited in this manual. | |
• Index of Terms | 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. | |
• GLR Parsers | Writing parsers for general context-free languages. | |
• Locations | Overview of location tracking. | |
• 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. | |
Writing GLR Parsers | ||
• 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 for GLR | GLR parsers require a modern C compiler. | |
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. | |
• Location Tracking Calc | Demonstrating the use of @n and @$. | |
• 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 | ||
• Rpcalc Declarations | Prologue (declarations) for rpcalc. | |
• Rpcalc Rules | Grammar Rules for rpcalc, with explanation. | |
• Rpcalc Lexer | The lexical analyzer. | |
• Rpcalc Main | The controlling function. | |
• Rpcalc Error | The error reporting function. | |
• Rpcalc Generate | Running Bison on the grammar file. | |
• Rpcalc Compile | Run the C compiler on the output code. | |
Grammar Rules for | ||
• Rpcalc Input | Explanation of the input nonterminal
| |
• Rpcalc Line | Explanation of the line nonterminal
| |
• Rpcalc Expr | Explanation of the expr nonterminal
| |
Location Tracking Calculator: | ||
• Ltcalc Declarations | Bison and C declarations for ltcalc. | |
• Ltcalc Rules | Grammar rules for ltcalc, with explanations. | |
• Ltcalc Lexer | The lexical analyzer. | |
Multi-Function Calculator: | ||
• Mfcalc Declarations | Bison declarations for multi-function calculator. | |
• Mfcalc Rules | Grammar rules for the calculator. | |
• Mfcalc Symbol Table | Symbol table management subroutines. | |
• Mfcalc Lexer | The lexical analyzer. | |
• Mfcalc Main | The controlling function. | |
Bison Grammar Files | ||
• Grammar Outline | Overall layout of the grammar file. | |
• Symbols | Terminal and nonterminal symbols. | |
• Rules | How to write grammar rules. | |
• Semantics | Semantic values and actions. | |
• Tracking Locations | Locations and actions. | |
• Named References | Using named references in 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 | ||
• Prologue | Syntax and usage of the prologue. | |
• Prologue Alternatives | Syntax and usage of alternatives to the prologue. | |
• Bison Declarations | Syntax and usage of the Bison declarations section. | |
• Grammar Rules | Syntax and usage of the grammar rules section. | |
• Epilogue | Syntax and usage of the epilogue. | |
Grammar Rules | ||
• Rules Syntax | Syntax of the rules. | |
• Empty Rules | Symbols that can match the empty string. | |
• Recursion | Writing recursive rules. | |
Defining Language Semantics | ||
• Value Type | Specifying one data type for all semantic values. | |
• Multiple Types | Specifying several alternative data types. | |
• Type Generation | Generating the semantic value type. | |
• Union Decl | Declaring the set of all semantic value types. | |
• Structured Value Type | Providing a structured semantic value type. | |
• Actions | An action is the semantic definition of a grammar rule. | |
• Action Types | Specifying data types for actions to operate on. | |
• Midrule 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. | |
Actions in Midrule | ||
• Using Midrule Actions | Putting an action in the middle of a rule. | |
• Typed Midrule Actions | Specifying the semantic type of their values. | |
• Midrule Action Translation | How midrule actions are actually processed. | |
• Midrule Conflicts | Midrule actions can cause conflicts. | |
Tracking Locations | ||
• Location Type | Specifying a data type for locations. | |
• Actions and Locations | Using locations in actions. | |
• Location Default Action | Defining a general way to compute locations. | |
Bison Declarations | ||
• Require Decl | Requiring a Bison version. | |
• Token Decl | Declaring terminal symbols. | |
• Precedence Decl | Declaring terminals with precedence and associativity. | |
• Type Decl | Declaring the choice of type for a nonterminal symbol. | |
• Symbol Decls | Summary of the Syntax of Symbol Declarations. | |
• Initial Action Decl | Code run before parsing starts. | |
• Destructor Decl | Declaring how symbols are freed. | |
• Printer Decl | Declaring how symbol values are displayed. | |
• Expect Decl | Suppressing warnings about parsing conflicts. | |
• Start Decl | Specifying the start symbol. | |
• Pure Decl | Requesting a reentrant parser. | |
• Push Decl | Requesting a push parser. | |
• Decl Summary | Table of all Bison declarations. | |
• %define Summary | Defining variables to adjust Bison’s behavior. | |
• %code Summary | Inserting code into the parser source. | |
Parser C-Language Interface | ||
• Parser Function | How to call yyparse and what it returns.
| |
• Push Parser Function | How to call yypush_parse and what it returns.
| |
• Pull Parser Function | How to call yypull_parse and what it returns.
| |
• Parser Create Function | How to call yypstate_new and what it returns.
| |
• Parser Delete Function | How to call yypstate_delete 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. | |
• Internationalization | How to let the parser speak in the user’s native language. | |
The Lexical Analyzer Function | ||
• Calling Convention | How yyparse calls yylex .
| |
• Tokens from Literals | Finding token types from string aliases. | |
• Token Values | How yylex must return the semantic value
of the token it has read.
| |
• Token Locations | How yylex must return the text location
(line number, etc.) of the token, if the
actions want that.
| |
• Pure Calling | How the calling convention differs in a pure parser (see A Pure (Reentrant) Parser). | |
The Bison Parser Algorithm | ||
• Lookahead | 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. | |
• Mysterious Conflicts | Conflicts that look unjustified. | |
• Tuning LR | How to tune fundamental aspects of LR-based parsing. | |
• Generalized LR Parsing | Parsing arbitrary context-free grammars. | |
• Memory Management | What happens when memory is exhausted. How to avoid it. | |
Operator Precedence | ||
• Why Precedence | An example showing why precedence is needed. | |
• Using Precedence | How to specify precedence and associativity. | |
• Precedence Only | How to specify precedence only. | |
• Precedence Examples | How these features are used in the previous example. | |
• How Precedence | How they work. | |
• Non Operators | Using precedence for general conflicts. | |
Tuning LR | ||
• LR Table Construction | Choose a different construction algorithm. | |
• Default Reductions | Disable default reductions. | |
• LAC | Correct lookahead sets in the parser states. | |
• Unreachable States | Keep unreachable parser states for debugging. | |
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. | |
Debugging Your Parser | ||
• Understanding | Understanding the structure of your parser. | |
• Graphviz | Getting a visual representation of the parser. | |
• Xml | Getting a markup representation of the parser. | |
• Tracing | Tracing the execution of your parser. | |
Tracing Your Parser | ||
• Enabling Traces | Activating run-time trace support | |
• Mfcalc Traces | Extending mfcalc to support traces
| |
• The YYPRINT Macro | Obsolete interface for semantic value reports | |
Invoking Bison | ||
• Bison Options | All the options described in detail, in alphabetical order by short options. | |
• Option Cross Key | Alphabetical list of long options. | |
• Yacc Library | Yacc-compatible yylex and main .
| |
Bison Options | ||
• Operation Modes | Options controlling the global behavior of bison
| |
• Diagnostics | Options controlling the diagnostics | |
• Tuning the Parser | Options changing the generated parsers | |
• Output Files | Options controlling the output | |
Parsers Written In Other Languages | ||
• C++ Parsers | The interface to generate C++ parser classes | |
• Java Parsers | The interface to generate Java parser classes | |
C++ Parsers | ||
• A Simple C++ Example | A short introduction to C++ parsers | |
• C++ Bison Interface | Asking for C++ parser generation | |
• C++ Parser Interface | Instantiating and running the parser | |
• C++ Semantic Values | %union vs. C++ | |
• C++ Location Values | The position and location classes | |
• 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 | |
• Exposing the Location Classes | Using the Bison location class in your project | |
• User Defined Location Type | Required interface for locations | |
A Complete C++ Example | ||
• Calc++ --- C++ Calculator | The specifications | |
• Calc++ Parsing Driver | An active parsing context | |
• Calc++ Parser | A parser class | |
• Calc++ Scanner | A pure C++ Flex scanner | |
• Calc++ Top Level | Conducting the band | |
Java Parsers | ||
• Java Bison Interface | Asking for Java parser generation | |
• Java Semantic Values | %token and %nterm vs. Java | |
• Java Location Values | The position and location classes | |
• Java Parser Interface | Instantiating and running the parser | |
• Java Scanner Interface | Specifying the scanner for the parser | |
• Java Action Features | Special features for use in actions | |
• Java Push Parser Interface | Instantiating and running the a push parser | |
• Java Differences | Differences between C/C++ and Java Grammars | |
• Java Declarations Summary | List of Bison declarations used with Java | |
A Brief History of the Greater Ungulates | ||
• Yacc | The original Yacc | |
• yacchack | An obscure early implementation of reentrancy | |
• Byacc | Berkeley Yacc | |
• Bison | This program | |
• Other Ungulates | Similar programs | |
Frequently Asked Questions | ||
• Memory Exhausted | Breaking the Stack Limits | |
• How Can I Reset the Parser | yyparse Keeps some State
| |
• Strings are Destroyed | yylval Loses Track of Strings
| |
• Implementing Gotos/Loops | Control Flow in the Calculator | |
• Multiple start-symbols | Factoring closely related grammars | |
• Enabling Relocatability | Moving Bison/using it through network shares | |
• Secure? Conform? | Is Bison POSIX safe? | |
• I can't build Bison | Troubleshooting | |
• Where can I find help? | Troubleshouting | |
• Bug Reports | Troublereporting | |
• More Languages | Parsers in C++, Java, and so on | |
• Beta Testing | Experimenting development versions | |
• Mailing Lists | Meeting other Bison users | |
Copying This Manual | ||
• GNU Free Documentation License | Copying and sharing this manual | |
Next: Introduction [Contents][Index]