calc
ltcalc
mfcalc
yyparse
yypush_parse
yypull_parse
yystate_new
yystate_delete
yylex
yyerror
Next: Introduction, Up: (dir) [Contents][Index]
This manual (23 January 2015) is for GNU Bison (version 3.0.4), the GNU parser generator.
Copyright © 1988-1993, 1995, 1998-2015 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: | ||
• 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: | Understanding or debugging Bison parsers. | |
• Invocation: | How to run Bison (to produce the parser implementation). | |
• Other Languages: | Creating C++ and Java parsers. | |
• FAQ: | Frequently Asked Questions | |
• Table of Symbols: | All the keywords of the Bison language are explained. | |
• Glossary: | Basic concepts are explained. | |
• Copying This Manual: | License for copying 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: | 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. | |
• 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. | |
Actions in Mid-Rule | ||
• Using Mid-Rule Actions: | Putting an action in the middle of a rule. | |
• Mid-Rule Action Translation: | How mid-rule actions are actually processed. | |
• Mid-Rule Conflicts: | Mid-rule 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. | |
• 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 .
| |
• 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 .
| |
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 | ||
• C++ Bison Interface: | Asking for C++ parser generation | |
• C++ Semantic Values: | %union vs. C++ | |
• C++ Location Values: | The position and location classes | |
• C++ Parser Interface: | Instantiating and running the parser | |
• 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 | |
• 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: | %type and %token 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 | |
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 | |
• 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 | ||
• Copying This Manual: | License for copying this manual. | |
Next: Introduction, Up: (dir) [Contents][Index]