Bison Manual : Using the YACC-Compatible Parser Generator, for Version 1. 875

by Donnelly, Charles; Stallman, Richard M.

• ISBN13: 9781882114238
• ISBN10: 188211423X
• Edition: 8th
• Format: Paperback
• Copyright: 2003-09-01
• Publisher: Free Software Foundation

Table of Contents

Introduction	1	(2)
Conditions for Using Bison	3	(2)
GNU GENERAL PUBLIC LICENSE	5	(8)
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)
1 The Concepts of Bison	13	(10)
1.1 Languages and Context-Free Grammars	13	(2)
1.2 From Formal Rules to Bison Input	15	(1)
1.3 Semantic Values	15	(1)
1.4 Semantic Actions	16	(1)
1.5 Writing GLR Parsers	16	(3)
1.6 Locations	19	(1)
1.7 Bison Output: the Parser File	20	(1)
1.8 Stages in Using Bison	21	(1)
1.9 The Overall Layout of a Bison Grammar	21	(2)
2 Examples	23	(20)
2.1 Reverse Polish Notation Calculator	23	(7)
2.1.1 Declarations for rpcalc	23	(1)
2.1.2 Grammar Rules for rpcalc	24	(2)
2.1.2.1 Explanation of input	25	(1)
2.1.2.2 Explanation of lme	25	(1)
2.1.2.3 Explanation of expr	26	(1)
2.1.3 The rpcal c Lexical Analyzer	26	(2)
2.1.4 The Controlling Function	28	(1)
2.1.5 The Error Reporting Routine	28	(1)
2.1.6 Running Bison to Make the Parser	28	(1)
2.1.7 Compiling the Parser File	29	(1)
2.2 Infix Notation Calculator: calc	30	(1)
2.3 Simple Error Recovery	31	(1)
2.4 Location Tracking Calculator: ltcalc	32	(3)
2.4.1 Declarations for ltcalc	32	(1)
2.4.2 Grammar Rules for ltcalc	33	(1)
2.4.3 The ltcalc Lexical Analyzer	34	(1)
2.5 Multifunction Calculator: mfcalc	35	(7)
2.5.1 Declarations for mfcalc	36	(1)
2.5.2 Grammar Rules for mfcalc	37	(1)
2.5.3 The mfcalc Symbol Table	37	(5)
2.6 Exercises	42	(1)
3 Bison Grammar Files	43	(22)
3.1 Outline of a Bison Grammar	43	(1)
3.1.1 The Prologue	43	(1)
3.1.2 The Bison Declarations Section	44	(1)
3.1.3 The Grammar Rules Section	44	(1)
3.1.4 The Epilogue	44	(1)
3.2 Symbols, Terminal and Nonterminal	44	(3)
3.3 Syntax of Grammar Rules	47	(1)
3.4 Recursive Rules	48	(1)
3.5 Defining Language Semantics	48	(5)
3.5.1 Data Types of Semantic Values	49	(1)
3.5.2 More Than One Value Type	49	(1)
3.5.3 Actions	49	(1)
3.5.4 Data Types of Values in Actions	50	(1)
3.5.5 Actions in Mid-Rule	51	(2)
3.6 Tracking Locations	53	(3)
3.6.1 Data Type of Locations	53	(1)
3.6.2 Actions and Locations	54	(1)
3.6.3 Default Action for Locations	55	(1)
3.7 Bison Declarations	56	(8)
3.7.1 Token Type Names	56	(1)
3.7.2 Operator Precedence	57	(1)
3.1.3 The Collection of Value Types	58	(1)
3.7.4 Nonterminal Symbols	58	(1)
3.7.5 Freeing Discarded Symbols	58	(1)
3.7.6 Suppressing Conflict Warnings	59	(1)
3.7.7 The Start-Symbol	60	(1)
3.7.8 A Pure (Reentrant) Parser	60	(1)
3.7.9 Bison Declaration Summary	61	(3)
3.8 Multiple Parsers in the Same Program	64	(1)
4 Parser C-Language Interface	65	(8)
4.1 The Parser Function yyparse	65	(1)
4.2 The Lexical Analyzer Function yylex	66	(3)
4.2.1 Calling Convention for yylex	66	(1)
4.2.2 Semantic Values of Tokens	67	(1)
4.2.3 Textual Locations of Tokens	68	(1)
4.2.4 Calling Conventions for Pure Parsers	68	(1)
4.3 The Error Reporting Function yyerror	69	(2)
4.4 Special Features for Use in Actions	71	(2)
5 The Bison Parser Algorithm	73	(12)
5.1 Look-Ahead Tokens	73	(1)
5.2 Shift/Reduce Conflicts	74	(1)
5.3 Operator Precedence	75
5.3.1 When Precedence is Needed	76	(1)
5.3.2 Specifying Operator Precedence	76	(1)
5.3.3 Precedence Examples	77	(1)
5.3.4 How Precedence Works	77
5.4 Context-Dependent Precedence	71	(7)
5.5 Parser States	78	(1)
5.6 Reduce/Reduce Conflicts	78	(2)
5.7 Mysterious Reduce/Reduce Conflicts	80	(2)
5.8 Generalized LR (GLR) Parsing	82	(2)
5.9 Stack Overflow, and How to Avoid it	84	(1)
6 Error Recovery	85
7 Handling Context-Dependencies	81	(10)
7.1 Semantic Info in Token Types	87	(1)
7.2 Lexical Tie-Ins	88	(1)
7.3 Lexical Tie-ins and Error Recovery	89	(2)
8 Debugging Your Parser	91	(10)
8.1 Understanding Your Parser	91	(6)
8.2 Tracing Your Parser	97	(4)
9 Invoking Bison	101	(4)
9.1 Bison Options	101	(3)
9.2 Option Cross Key	104	(1)
9.3 Yacc Library	104	(1)
10 Frequently Asked Questions	105	(4)
10.1 Parser Stack Overflow	105	(1)
10.2 How Can I Reset the Parser	105	(1)
10.3 Strings are Destroyed	106	(1)
10.4 C++ Parsers	107	(1)
10.5 Implementing Loops	107	(2)
Appendix A Bison Symbols	109	(6)
Appendix B Glossary	115	(4)
Appendix C Copying This Manual	119	(8)
C.1 GNU Free Documentation License	119	(7)
C.1.1 ADDENDUM: How to use this License for your documents	126	(1)
Appendix D Free Software and Free Manuals	127	(2)
Index	129