The Bison Manual: The Yacc-Compatible Parser Generator

by Donnelly, Charles; Stallman, Riachard M.; Stallman, Richard M.

• ISBN13: 9781882114344
• ISBN10: 1882114345
• Format: Paperback
• Copyright: 2002-06-01
• Publisher: Free Software Foundation

Table of Contents

Introduction	1	(3)
Conditions for Using Bison	3	(2)
GNU GENERAL PUBLIC LICENSE	5	(94)
Preamble	5	(1)
Terms and Conditions for Copying, Distribution and Modification	6	(5)
Appendix: How to Apply These Terms to Your New Programs	11	(2)
The Concepts of Bison	13	(6)
Languages and Context-Free Grammars	13	(1)
From Formal Rules to Bison Input	14	(1)
Semantic Values	15	(1)
Semantic Actions	16	(1)
Locations	16	(1)
Bison Output: the Parser File	16	(1)
Stages in Using Bison	17	(1)
The Overall Layout of a Bison Grammar	18	(1)
Examples	19	(20)
Reverse Polish Notation Calculator	19	(6)
Declarations for rpcalc	19	(1)
Grammar Rules for rpcalc	20	(1)
Explanation of input	20	(1)
Explanation of line	21	(1)
Explanation of expr	21	(1)
The rpcalc Lexical Analyzer	22	(2)
The Controlling Function	24	(1)
The Error Reporting Routine	24	(1)
Running Bison to Make the Parser	24	(1)
Compiling the Parser File	25	(1)
Infix Notation Calculator: calc	25	(2)
Simple Error Recovery	27	(1)
Location Tracking Calculator: ltcalc	27	(4)
Declarations for ltcalc	28	(1)
Grammar Rules for ltcalc	28	(1)
The ltcalc Lexical Analyzer	29	(2)
Multi-Function Calculator: mfcalc	31	(6)
Declarations for mfcalc	31	(1)
Grammar Rules for mfcalc	32	(1)
The mfcalc Symbol Table	33	(4)
Exercises	37	(2)
Bison Grammar Files	39	(20)
Outline of a Bison Grammar	39	(1)
The prologue	39	(1)
The Bison Declarations Section	40	(1)
The Grammar Rules Section	40	(1)
The epilogue	40	(1)
Symbols, Terminal and Nonterminal	40	(2)
Syntax of Grammar Rules	42	(1)
Recursive Rules	43	(1)
Defining Language Semantics	44	(5)
Data Types of Semantic Values	44	(1)
More Than One Value Type	45	(1)
Actions	45	(1)
Data Types of Values in Actions	46	(1)
Actions in Mid-Rule	47	(2)
Tracking Locations	49	(2)
Data Type of Locations	49	(1)
Actions and Locations	49	(1)
Default Action for Locations	50	(1)
Bison Declarations	51	(6)
Token Type Names	51	(1)
Operator Precedence	52	(1)
The Collection of Value Types	53	(1)
Nonterminal Symbols	53	(1)
Suppressing Conflict Warnings	53	(1)
The Start-Symbol	54	(1)
A Pure (Reentrant) Parser	54	(1)
Bison Declaration Summary	55	(2)
Multiple Parsers in the Same Program	57	(2)
Parser C-Language Interface	59	(8)
The Parser Function yyparse	59	(1)
The Lexical Analyzer Function yylex	59	(4)
Calling Convention for yylex	59	(2)
Semantic Values of Tokens	61	(1)
Textual Positions of Tokens	61	(1)
Calling Conventions for Pure Parsers	62	(1)
The Error Reporting Function yyerror	63	(1)
Special Features for Use in Actions	64	(3)
The Bison Parser Algorithm	67	(12)
Look-Ahead Tokens	67	(1)
Shift/Reduce Conflicts	68	(1)
Operator Precedence	69	(2)
When Precedence is Needed	70	(1)
Specifying Operator Precedence	70	(1)
Precedence Examples	71	(1)
How Precedence Works	71	(1)
Context-Dependent Precedence	71	(1)
Parser States	72	(1)
Reduce/Reduce Conflicts	72	(2)
Mysterious Reduce/Reduce Conflicts	74	(2)
Stack Overflow, and How to Avoid It	76	(3)
Error Recovery	79	(2)
Handling Context Dependencies	81	(4)
Semantic Info in Token Types	81	(1)
Lexical Tie-ins	82	(1)
Lexical Tie-ins and Error Recovery	83	(2)
Debugging Your Parser	85	(10)
Understanding Your Parser	85	(6)
Tracing Your Parser	91	(4)
Invoking Bison	95	(4)
Bison Options	95	(2)
Environment Variables	97	(1)
Option Cross Key	98	(1)
Invoking Bison under VMS	98	(1)
Appendix A Bison Symbols	99	(4)
Appendix B Glossary	103	(4)
Appendix C Copying This Manual	107	(8)
C.1 GNU Free Documentation License	107	(8)
C.1.1 Addendum: How to use this License for your documents	113	(2)
Appendix D Free Software Needs Free Documentation	115	(2)
Index	117	(10)
Bison 1.49 Quick Reference	127