Lex and Yacc

by Levine, John R.

• ISBN13: 9781565920002
• ISBN10: 1565920007
• Edition: 2nd
• Format: Paperback
• Copyright: 1992-10-01
• Publisher: Oreilly & Associates Inc

Summary

This book shows you how to use two Unix utilities,lexandyacc,in program development. These tools help programmers build compilers and interpreters, but they also have a wider range of applications.The second edition contains completely revised tutorial sections for novice users and reference sections for advanced users. This edition is twice the size of the first and has an expanded index.The following material has been added: Each utility is explained in a chapter that covers basic usage and simple, stand-alone applications How to implement a full SQL grammar, with full sample code Major MS-DOS and Unix versions oflexandyaccare explored in depth, including AT&Tlexandyacc, Berkeleyyacc, Berkeley/GNU Flex, GNU Bison, MKSlexandyacc, and Abraxas PCYACC

Author Biography

Gregory Satir helps develop online publishing tools in the Portland, Oregon, office of Electronic Book Technologies. He graduated with a B.S. in computer science from Brown University. Doug Brown is a consultant/contractor in Beaverton, Oregon. He has been developing software for circuit simulation, synthesis, and testing since 1977. Doug coauthored lex & yacc, another O'Reilly & Associates Nutshell Handbook. He received an M.S. in electrical engineering from the University of Illinois at Urbana-Champaign in 1976.

John R. Levine writes, lectures, and consults on Unix and compiler topics. He moderates the online comp.compilers discussion group at Usenet. He worked on Unix versions Lotus 1-2-3 and the Norton Utilities and was one of the architects of AIX for the IBM RT PC. He received a Ph.D in computer science from Yale in 1984.

Tony Mason is currently a member of the AFS development team at Transarc Corporation, a small start-up company specializing in distributed systems software. Previously, he worked with the Distributed Systems Group at Stanford University in the area of distributed operating systems and data communications. He received a B.S. in mathematics from the University of Chicago in 1987.

Table of Contents

Preface	xvii	(1)
What's New in the Second Edition	xvii	(1)
Scope of This Book	xviii	(2)
Availability of Lex and Yacc	xx	(1)
Sample Programs	xx	(1)
Conventions Used in This Handbook	xxi	(1)
Acknowledgments	xxii
1: Lex and Yacc	1	(26)
The Simplest Lex Program	2	(1)
Recognizing Words with Lex	3	(10)
Symbol Tables	9	(4)
Grammars	13	(8)
Parser-Lexer Communication	14	(1)
The Parts of Speech Lexer	15	(2)
A Yacc Parser	17	(1)
The Rules Section	18	(3)
Running Lex and Yacc	21	(1)
Lex vs. Hand-written Lexers	22	(3)
Exercises	25	(2)
2: Using Lex	27	(24)
Regular Expressions	28	(4)
Examples of Regular Expressions	30	(2)
A Word Counting Program	32	(6)
Parsing a Command Line	38	(7)
Start States	42	(3)
A C Source Code Analyzer	45	(3)
Summary	48	(1)
Exercises	49	(2)
3: Using Yacc	51	(30)
Grammars	51	(2)
Recursive Rules	53	(1)
Shift/Reduce Parsing	53	(3)
What Yacc Cannot Parse	55	(1)
A Yacc Parser	56	(2)
The Definition Section	56	(1)
The Rules Section	56	(1)
Symbol Values and Actions	57	(1)
The Lexer	58	(2)
Compiling and Running a Simple Parser	59	(1)
Arithmetic Expressions and Ambiguity	60	(4)
When Not to Use Precedence Rules	63	(1)
Variables and Typed Tokens	64	(3)
Symbol Values and %union	65	(2)
Symbol Tables	67	(4)
Functions and Reserved Words	71	(6)
Reserved Words in the Symbol Table	72	(4)
Interchangeable Function and Variable Names	76	(1)
Building Parsers with Make	77	(1)
Summary	78	(1)
Exercises	78	(3)
4: A Menu Generation Language	81	(28)
Overview of the MGL	81	(2)
Developing the MGL	83	(9)
Building the MGL	92	(5)
Initialization	95	(2)
Screen Processing	97	(3)
Termination	100	(2)
Sample MGL Code	102	(5)
Exercises	107	(2)
5: Parsing SQL	109	(38)
A Quick Overview of SQL	109	(5)
Relational Data Bases	110	(1)
Manipulating Relations	111	(1)
Three Ways to Use SQL	112	(2)
The Syntax Checker	114	(5)
The Lexer	114	(4)
Error and Main Routines	118	(1)
The Parser	119	(22)
Definitions	119	(1)
Top Level Rules	120	(1)
The Schema Sublanguage	121	(5)
The Module Sublanguage	126	(2)
The Manipulation Sublanguage	128	(11)
Odds and Ends	139	(1)
Using the Syntax Checker	140	(1)
Embedded SQL	141	(5)
Changes to the Lexer	141	(2)
Changes to the Parser	143	(1)
Auxiliary Routines	144	(1)
Using the Preprocessor	145	(1)
Exercises	146	(1)
6: A Reference for Lex Specifications	147	(34)
Structure of a Lex Specification	147	(2)
Definition Section	147	(1)
Rules Section	148	(1)
User Subroutines	148	(1)
BEGIN	149	(1)
Bugs	149	(1)
Ambiguous Lookahead	149	(1)
AT&T Lex	149	(1)
Flex	150	(1)
Character Translations	150	(1)
Context Sensitivity	151	(2)
Left Context	152	(1)
Right Context	152	(1)
Definitions (Substitutions)	153	(1)
ECHO	154	(1)
Include Operations (Logical Nesting of Files)	154	(2)
File Chaining with yywrap()	154	(1)
File Nesting	155	(1)
Input from Strings	156	(2)
AT&T Lex	156	(1)
Flex	156	(1)
Abraxas Pclex	157	(1)
MKS Lex	157	(1)
POSIX Lex	158	(1)
input()	158	(1)
Internal Tables (%N Declarations)	159	(1)
lex Library	160	(1)
main()	160	(1)
Other Library Routines	160	(1)
Line Numbers and yylineno	160	(1)
Literal Block	161	(1)
Multiple Lexers in One Program	161	(4)
Combined Lexers	161	(1)
Multiple Lexers	162	(3)
output()	165	(1)
Portability of Lex Lexers	166	(1)
Porting Lex Specifications	166	(1)
Porting Generated C Lexers	166	(1)
Regular Expression Syntax	167	(3)
Metacharacters	167	(3)
POSIX Extensions	170	(1)
REJECT	170	(1)
Returning Values from yylex()	171	(1)
Start States	171	(2)
unput()	173	(1)
yyinput(), yyoutput(), yyunput()	174	(1)
yyleng	174	(1)
yyless()	174	(1)
yylex()	175	(2)
User Code in yylex()	176	(1)
yymore()	177	(1)
yytext	177	(2)
Enlarging yytext	178	(1)
yywrap()	179	(2)
7: A Reference for Yacc Grammars	181	(36)
Structure of a Yacc Grammar	181	(1)
Symbols	181	(1)
Definition Section	182	(1)
Rules Section	182	(1)
User Subroutines Section	182	(1)
Actions	182	(2)
Embedded Actions	183	(1)
Symbol Types for Embedded Actions	184	(1)
Obsolescent Feature	184	(1)
Ambiguity and Conflicts	184	(2)
Types of Conflicts	185	(1)
Bugs in Yacc	186	(2)
Real Bugs	186	(1)
Infinite Recursion	187	(1)
Unreal Bugs	187	(1)
End Marker	188	(1)
Error Token and Error Recovery	188	(1)
%ident Declaration	189	(1)
Inherited Attributes ($0)	189	(2)
Symbol Types for Inherited Attributes	190	(1)
Lexical Feedback	191	(1)
Literal Block	192	(1)
Literal Tokens	192	(1)
Portability of Yacc Parsers	193	(1)
Porting Yacc Grammars	193	(1)
Porting Generated C Lexers	194	(1)
Precedence, Associativity, and Operator Declarations	194	(3)
Precedence and Associativity	195	(1)
Operator Declarations	195	(1)
Using Precedence and Associativity to Resolve Conflicts	196	(1)
Typical Uses of Precedence	196	(1)
Recursive Rules	197	(1)
Left and Right Recursion	197	(1)
Rules	198	(1)
Special Characters	199	(2)
Start Declaration	201	(1)
Symbol Values	201	(1)
Declaring Symbol Types	201	(1)
Example	201	(1)
Explicit Symbol Types	202	(1)
Tokens	202	(2)
Token Numbers	203	(1)
Token Values	203	(1)
%type Declaration	204	(1)
%union Declaration	205	(1)
Variant and Multiple Grammars	205	(5)
Combined Parsers	206	(1)
Multiple Parsers	207	(2)
Recursive Parsing	209	(1)
Lexers for Multiple Parsers	210	(1)
y.output Files	210	(1)
Yacc Library	211	(1)
main()	211	(1)
yyerror()	212	(1)
YYABORT	212	(1)
YYACCEPT	212	(1)
YYBACKUP	213	(1)
yyclearin	213	(1)
yydebug and YYDEBUG	213	(1)
YYDEBUG	214	(1)
yydebug	214	(1)
yyerrok	214	(1)
YYERROR	215	(1)
yyerror()	215	(1)
yyparse()	216	(1)
YYRECOVERING()	216	(1)
8: Yacc Ambiguities and Conflicts	217	(26)
The Pointer Model and Conflicts	217	(12)
Types of Conflicts	220	(1)
Parser States	221	(2)
Contents of y.output	223	(5)
Review of Conflicts in y.output	228	(1)
Common Examples of Conflicts	229	(4)
Expression Grammars	229	(2)
IF--THEN--ELSE	231	(1)
Nested List Grammars	232	(1)
How Do I Fix the Conflict?	233	(7)
IF--THEN--ELSE (Shift/Reduce)	233	(2)
Loop Within a Loop (Shift/Reduce)	235	(1)
Expression Precedence (Shift/Reduce)	236	(1)
Limited Lookahead (Shift/Reduce or Reduce/Reduce)	237	(1)
Overlap of Alternatives (Reduce/Reduce)	238	(2)
Summary	240	(1)
Exercises	241	(2)
9: Error Reporting and Recovery	243	(10)
Error Reporting	243	(4)
Better Lex Error Reports	246	(1)
Error Recovery	247	(5)
Yacc Error Recovery	248	(3)
Where to Put Error Tokens	251	(1)
Compiler Error Recovery	251	(1)
Exercises Exercises	252	(1)
A: AT&T Lex	253	(8)
Error Messages	254	(7)
B: AT&T Yacc	261	(10)
Options	261	(1)
Error Messages	262	(9)
C: Berkeley Yacc	271	(6)
Options	271	(1)
Error Messages	271	(6)
Fatal Errors	271	(1)
Regular Errors	272	(2)
Warnings	274	(1)
Informative Messages	275	(2)
D: GNU Bison	277	(2)
Differences	277	(2)
E: Flex	279	(10)
Flex Differences	279	(1)
Options	280	(1)
Error Messages	281	(4)
Flex Versions of Lexer Examples	285	(4)
F: MKS lex and yacc	289	(2)
Differences	289	(1)
New Features	290	(1)
G: Abraxas lex and yacc	291	(2)
Differences	291	(1)
New Features	291	(2)
H: POSIX lex and yacc	293	(2)
Options	293	(1)
Differences	294	(1)
I: MGL Compiler Code	295	(14)
MGL Yacc Source	295	(4)
MGL Lex Source	299	(1)
Supporting C Code	300	(9)
J: SQL Parser Code	309	(24)
Yacc Parser	309	(17)
Cross-reference	320	(6)
Lex Scanner	326	(3)
Supporting Code	329	(4)
Glossary	333	(6)
Bibliography	339	(2)
Index	341