Bison - GNU

1 BisonThe Yacc-compatible Parser Generator10 September 2021, Bison Version Charles Donnelly and Richard StallmanThis manual (10 September 2021) is for GNU Bison (version ), the GNU parser 1988 1993, 1995, 1998 2015, 2018 2021 Free Software Foundation, is granted to copy, distribute and/or modify this document underthe terms of the GNU Free Documentation License, Version or any laterversion published by the Free Software Foundation; with no Invariant Sections,with the Front-Cover texts being A GNU Manual, and with the Back-CoverTexts 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 modifythis GNU manual. Buying copies from the FSF supports it in developing GNUand promoting software freedom. Published by the Free Software Foundation51 Franklin Street, Fifth FloorBoston, MA 02110-1301 USAP rinted copies are available from the Free Software 1-882114-44-2 Cover art by Etienne of for Using GENERAL PUBLIC The Concepts of Languages and Context-Free Grammars.

2 From Formal Rules to Bison Input.. Semantic Values.. Semantic Actions.. Writing GLR Parsers.. Using GLR on Unambiguous Grammars.. Using GLR to Resolve Ambiguities.. GLR Semantic Actions.. Deferred semantic actions.. YYERROR.. Restrictions on semantic values and locations.. Controlling a Parse with Arbitrary Predicates.. Locations.. Bison Output: the Parser Implementation File.. Stages in Using Bison .. The Overall Layout of a Bison Grammar..262 Reverse Polish Notation Calculator.. Declarations forrpcalc.. Grammar Rules forrpcalc.. Explanation ofinput.. Explanation ofline.. Explanation ofexp.. TherpcalcLexical Analyzer.. The Controlling Function.. The Error Reporting Routine.. Running Bison to Make the Parser.. Compiling the Parser Implementation File.

3 Infix Notation Calculator:calc.. Simple Error Recovery.. Location Tracking Calculator:ltcalc.. Declarations forltcalc.. Grammar Rules forltcalc.. TheltcalcLexical .. Multi-Function Calculator:mfcalc.. Declarations formfcalc.. Grammar Rules formfcalc.. ThemfcalcSymbol Table.. ThemfcalcLexer.. ThemfcalcMain.. Exercises..463 Bison Grammar Outline of a Bison Grammar.. The prologue.. Prologue Alternatives.. The Bison Declarations Section.. The Grammar Rules Section.. The epilogue.. Symbols, Terminal and Nonterminal.. Grammar Rules.. Syntax of Grammar Rules.. Empty Rules.. Recursive Rules.. Defining Language Semantics.. Data Types of Semantic Values.. More Than One Value Type.. Generating the Semantic Value Type.. The Union Declaration.

4 Providing a Structured Semantic Value Type.. Actions.. Data Types of Values in Actions.. Actions in Midrule.. Using Midrule Actions.. Typed Midrule Actions.. Midrule Action Translation.. Conflicts due to Midrule Actions.. Tracking Locations.. Data Type of Locations.. Actions and Locations.. Printing Locations.. Default Action for Locations.. Named References.. Bison Declarations.. Require a Version of Bison .. Token Kind Names.. Operator Precedence.. Nonterminal Symbols.. Syntax of Symbol Declarations.. Performing Actions before Parsing.. Freeing Discarded Symbols.. Printing Semantic Values.. Suppressing Conflict Warnings.. The Start-Symbol.. A Pure (Reentrant) Parser.. A Push Parser.. Bison Declaration Summary.. %define Summary.

5 %code Summary.. Multiple Parsers in the Same Program..974 Parser C-Language The Parser Functionyyparse.. Push Parser Interface.. The Lexical Analyzer Functionyylex.. Calling Convention foryylex.. Special Tokens.. Finding Tokens by String Literals.. Semantic Values of Tokens.. Textual Locations of Tokens.. Calling Conventions for Pure Parsers.. Error Reporting.. The Error Reporting Functionyyerror.. The Syntax Error ReportingFunctionyyreport_syntax_error.. Special Features for Use in Actions.. Parser Internationalization.. Enabling Internationalization.. Token Internationalization..1115 The Bison Parser Lookahead Tokens.. Shift/Reduce Conflicts.. Operator Precedence.. When Precedence is Needed.. Specifying Operator Precedence.. Specifying Precedence Only.

6 Precedence Examples.. How Precedence Works.. Using Precedence For Non Operators.. Context-Dependent Precedence.. Parser States.. Reduce/Reduce Conflicts.. Mysterious Conflicts.. Tuning LR.. LR Table Construction.. Default Reductions.. LAC.. Unreachable States.. Generalized LR (GLR) Parsing.. Memory Management, and How to Avoid Memory Exhaustion..1296 Error Handling Context Semantic Info in Token Kinds.. Lexical Tie-ins.. Lexical Tie-ins and Error Recovery..1358 Debugging Your Generation of Counterexamples.. Understanding Your Parser.. Visualizing Your Parser.. Visualizing your parser in multiple formats.. Tracing Your Parser.. Enabling Traces.. Enabling Debug Traces formfcalc..1519 Invoking Bison Options.. Operation Modes.

7 Diagnostics.. Tuning the Parser.. Output Files.. Option Cross Key.. Yacc Library..16510 Parsers Written In Other C++ Parsers.. A Simple C++ Example.. C++ Bison Interface.. C++ Parser Interface.. C++ Semantic Values.. C++ Unions.. C++ Variants.. C++ Location Values.. C++position.. C++location.. Exposing the Location Classes.. User Defined Location Type.. C++ Parser Context.. C++ Scanner Interface.. Split Symbols.. Complete Symbols.. A Complete C++ Example.. Calc++ C++ Calculator.. Calc++ Parsing Driver.. Calc++ Parser.. Calc++ Scanner.. Calc++ Top Level.. D Parsers.. D Bison Interface.. D Semantic Values.. D Location Values.. D Parser Interface.. D Parser Context Interface.. D Scanner Interface.. Special Features for Use in D Actions.

8 D Push Parser Interface.. D Complete Symbols.. Java Parsers.. Java Bison Interface.. Java Semantic Values.. Java Location Values.. Java Parser Interface.. Java Parser Context Interface.. Java Scanner Interface.. Special Features for Use in Java Actions.. Java Push Parser Interface.. Differences between C/C++ and Java Grammars.. Java Declarations Summary..20211 A Brief History of the Greater The ancestral Yacc.. yacchack.. Berkeley Yacc.. Bison .. Other Ungulates..20612 Bison Version Compatibility: Best Frequently Asked Memory Exhausted.. How Can I Reset the Parser.. Strings are Destroyed.. Implementing Gotos/Loops.. Multiple start-symbols.. Secure? Conform?.. Enabling Relocatability.. I can t build Bison .. Where can I find help?

9 Bug Reports.. More Languages.. Beta Testing.. Mailing Lists..214 Appendix A Bison B C GNU Free Documentation of a general-purpose parser generator that converts an annotated context-free gram-mar into a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1)or canonical LR(1) parser tables. Once you are proficient with Bison , you can use it todevelop a wide range of language parsers, from those used in simple desk calculators tocomplex programming is upward compatible with Yacc: all properly-written Yacc grammars ought towork with Bison with no change. Anyone familiar with Yacc should be able to use Bisonwith little trouble. You need to be fluent in C, C++, D or Java programming in order touse Bison or to understand this begin with tutorial chapters that explain the basic concepts of using Bison and showthree explained examples, each building on the last.

10 If you don t know Bison or Yacc, startby reading these chapters. Reference chapters follow, which describe specific aspects ofBison in was written originally by Robert Corbett. Richard Stallman made it Yacc-compatible. Wilfred Hansen of Carnegie Mellon University added multi-character stringliterals and other features. Since then, Bison has grown more robust and evolved manyother new features thanks to the hard work of a long list of volunteers. For details, see theTHANKSandChangeLogfiles included in the Bison edition corresponds to version of for Using BisonThe distribution terms for Bison -generated parsers permit using the parsers in nonfreeprograms. Before Bison version , these extra permissions applied only when Bison wasgenerating LALR(1) parsers in C. And before Bison version , Bison -generated parserscould be used only in programs that were free other GNU programming tools, such as the GNU C compiler, have never had sucha requirement.