第1页 / 共354页
第2页 / 共354页
第3页 / 共354页
第4页 / 共354页
第5页 / 共354页
第6页 / 共354页
第7页 / 共354页
第8页 / 共354页
lex & yacc 2nd Edition英文版PDF.pdf
Cover
Copyright
Table of Contents
Preface
Chapter 1. Lex and Yacc
Chapter 2. Using Lex
Chapter 3. Using Yacc
Chapter 4. A Menu Generation Language
Chapter 5. Parsing SQL
Chapter 6. A Reference for Lex Specifications
Chapter 7. A Reference for Yacc Grammars
Chapter 8. Yacc Ambiguities and Conflicts
Chapter 9. Error Reporting and Recovery
Appendix A. AT&T Lex
Appendix B. AT&T Yacc
Appendix C. Berkeley Yacc
Appendix D. GNU Bison
Appendix E. Flex
Appendix F. MKS lex and yacc
Appendix G. Abraxas lex and yacc
Appendix H. POSIX lex and yacc
Appendix I. MGL Compiler Code
Appendix J. SQL Parser Code
Appendix K. SQL Parser Code
Glossary
lex & yacc, 2nd Edition
lex & yacc, 2nd Edition
by
Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472.
Revision History for the :
See http://oreilly.com/catalog/errata.csp?isbn=9781565920002 for release details.
ISBN: 978-1-565-92000-2
Table of Contents
Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
— What’s New in the Second Edition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
— Scope of This Book. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
— Availability of Lex and Yacc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
— Sample Programs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
— Conventions Used in This Handbook. . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
— Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi
1. Lex and Yacc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
— The Simplest Lex Program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
— Recognizing Words with Lex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
— Symbol Tables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
— Grammars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
— Parser-Lexer Communication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
— The Parts of Speech Lexer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
— A Yacc Parser. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
— The Rules Section. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
— Running Lex and Yacc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
— Lex vs. Hand-written Lexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
— Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2. Using Lex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
— Regular Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
— Examples of Regular Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
— A Word Counting Program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
— Parsing a Command Line. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
— Start States. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
iii
— A C Source Code Analyzer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
— Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
— Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3. Using Yacc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
— Grammars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
— Recursive Rules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
— Shift/Reduce Parsing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
— What Yacc Cannot Parse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
— A Yacc Parser. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
— The Definition Section. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
— The Rules Section. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
— Symbol Values and Actions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
— The Lexer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
— Compiling and Running a Simple Parser. . . . . . . . . . . . . . . . . . . . . . . 55
— Arithmetic Expressions and Ambiguity. . . . . . . . . . . . . . . . . . . . . . . . 55
— When Not to Use Precedence Rules. . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
— Variables and Typed Tokens. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
— Symbol Values and %union. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
— Symbol Tables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
— Functions and Reserved Words. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
— Reserved Words in the Symbol Table. . . . . . . . . . . . . . . . . . . . . . . . . . 67
— Interchangeable Function and Variable Names. . . . . . . . . . . . . . . . . . 69
— Building Parsers with Make. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
— Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
— Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4. A Menu Generation Language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
— Overview of the MGL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
— Developing the MGL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
— Building the MGL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
— Initialization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
— Screen Processing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
— Termination. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
— Sample MGL Code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
102
— Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. Parsing SQL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
iv
|
Table of Contents
— A Quick Overview of SQL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
— Relational Data Bases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
— Manipulating Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
— Three Ways to Use SQL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
— The Syntax Checker. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
— The Lexer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
— Error and Main Routines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
— The Parser. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
— Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
115
— Top Level Rules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
— The Schema Sublanguage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
— The Module Sublanguage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
— The Manipulation Sublanguage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
— Odds and Ends. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
— Using the Syntax Checker. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
— Embedded SQL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
— Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
140
6. A Reference for Lex Specifications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
— Structure of a Lex Specification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
— Definition Section. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
— Rules Section. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
— User Subroutines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
— BEGIN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
— Bugs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
— AT&T Lex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
— Character Translations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
— Context Sensitivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
— Definitions (Substitutions). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
— ECHO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
— Include Operations (Logical Nesting of Files). . . . . . . . . . . . . . . . . . 150
— Input from Strings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
— AT&T Lex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
— Flex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
— Abraxas Pclex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
— MKS Lex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
152
— POSIX Lex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
Table of Contents
|
v
— input(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
— Internal Tables (%N Declarations). . . . . . . . . . . . . . . . . . . . . . . . . . . 154
— lex Library. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
— Line Numbers and yylineno. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
— Literal Block. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
— Multiple Lexers in One Program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
— Combined Lexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
— Multiple Lexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
— output(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
— Portability of Lex Lexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
— Porting Lex Specifications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
160
— Porting Generated C Lexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
— Regular Expression Syntax. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
— Metacharacters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
— POSIX Extensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
— REJECT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
— Returning Values from yylex(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
— Start States. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
— unput(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
— yyinput(), yyoutput(), yyunput(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
— yyleng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
— yyless(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
169
— yylex(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
— User Code in yylex(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
169
— yymore(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
— yytext. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
— Enlarging yytext. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
— AT&T and MKS Lex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
— yywrap(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
7. A Reference for Yacc Grammars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
— Structure of a Yacc Grammar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
— Symbols. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
— Definition Section. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
— Rules Section. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
— User Subroutines Section. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
— Actions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
vi
|
Table of Contents
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
