lex & yacc, 2nd Edition

lex & yacc, 2nd Edition

by John Levine, Doug Brown, Tony Mason
Released October 1992
Publisher(s): O'Reilly Media, Inc.
ISBN: 9781565920002

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Buy on Amazon
Start your free trial

Book description

This book shows you how to use two Unix utilities, lex andyacc, 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 of lex and yacc are explored in depth, including AT&T lex and yacc, Berkeley yacc, Berkeley/GNU Flex, GNU Bison, MKS lex andyacc, and Abraxas PCYACC

Publisher resources

View/Submit Errata

Table of contents

  1. lex & yacc, 2nd Edition
  2. A Note Regarding Supplemental Files
  3. Preface
    1. What’s New in the Second Edition
    2. Scope of This Book
    3. Availability of Lex and Yacc
    4. Sample Programs
    5. Conventions Used in This Handbook
    6. Acknowledgments
  4. 1. Lex and Yacc
    1. The Simplest Lex Program
    2. Recognizing Words with Lex
      1. Symbol Tables
    3. Grammars
      1. Parser-Lexer Communication
    4. The Parts of Speech Lexer
      1. A Yacc Parser
      2. The Rules Section
    5. Running Lex and Yacc
    6. Lex vs. Hand-written Lexers
    7. Exercises
  5. 2. Using Lex
    1. Regular Expressions
      1. Examples of Regular Expressions
    2. A Word Counting Program
    3. Parsing a Command Line
      1. Start States
    4. A C Source Code Analyzer
    5. Summary
    6. Exercises
  6. 3. Using Yacc
    1. Grammars
      1. Recursive Rules
    2. Shift/Reduce Parsing
      1. What Yacc Cannot Parse
    3. A Yacc Parser
      1. The Definition Section
      2. The Rules Section
      3. Symbol Values and Actions
    4. The Lexer
      1. Compiling and Running a Simple Parser
    5. Arithmetic Expressions and Ambiguity
      1. When Not to Use Precedence Rules
    6. Variables and Typed Tokens
      1. Symbol Values and %union
    7. Symbol Tables
    8. Functions and Reserved Words
      1. Reserved Words in the Symbol Table
      2. Interchangeable Function and Variable Names
    9. Building Parsers with Make
    10. Summary
    11. Exercises
  7. 4. A Menu Generation Language
    1. Overview of the MGL
    2. Developing the MGL
    3. Building the MGL
      1. Initialization
    4. Screen Processing
    5. Termination
    6. Sample MGL Code
    7. Exercises
  8. 5. Parsing SQL
    1. A Quick Overview of SQL
      1. Relational Data Bases
      2. Manipulating Relations
    2. Three Ways to Use SQL
    3. The Syntax Checker
      1. The Lexer
      2. Error and Main Routines
    4. The Parser
      1. Definitions
      2. Top Level Rules
      3. The Schema Sublanguage
        1. Base Tables
        2. View Definition
        3. Privilege Definitions
      4. The Module Sublanguage
        1. Cursor Definitions
      5. The Manipulation Sublanguage
        1. Simple Statements
        2. FETCH Statements
        3. INSERT Statements
        4. DELETE Statements
        5. UPDATE Statements
        6. Scalar Expressions
        7. SELECT Statements
        8. Table Expressions
        9. Search Conditions
      6. Odds and Ends
      7. Using the Syntax Checker
      8. Embedded SQL
        1. Changes to the Lexer
        2. Changes to the Parser
        3. Auxiliary Routines
        4. Using the Preprocessor
      9. Exercises
  9. 6. A Reference for Lex Specifications
    1. Structure of a Lex Specification
      1. Definition Section
      2. Rules Section
      3. User Subroutines
    2. BEGIN
      1. Bugs
        1. Ambiguous Lookahead
      2. AT&T Lex
        1. Flex
      3. Character Translations
      4. Context Sensitivity
        1. Left Context
        2. Right Context
      5. Definitions (Substitutions)
    3. ECHO
      1. Include Operations (Logical Nesting of Files)
        1. File Chaining with yywrap()
        2. File Nesting
        3. AT&T Lex
        4. Flex
        5. MKS Lex
        6. Abraxas Pclex
        7. POSIX Lex
    4. Input from Strings
      1. AT&T Lex
      2. Flex
      3. Abraxas Pclex
      4. MKS Lex
      5. POSIX Lex
      6. input()
    5. Internal Tables (%N Declarations)
      1. lex Library
        1. main()
        2. Other Library Routines
    6. Line Numbers and yylineno
      1. Literal Block
    7. Multiple Lexers in One Program
      1. Combined Lexers
      2. Multiple Lexers
        1. Using the p Flag
        2. Faking It
    8. output()
    9. Portability of Lex Lexers
      1. Porting Lex Specifications
      2. Porting Generated C Lexers
        1. Libraries
        2. Buffer Sizes
        3. Character Sets
    10. Regular Expression Syntax
      1. Metacharacters
      2. POSIX Extensions
    11. REJECT
    12. Returning Values from yylex()
      1. Start States
    13. unput()
    14. yyinput(), yyoutput(), yyunput()
    15. yyleng
    16. yyless()
    17. yylex()
      1. User Code in yylex()
    18. yymore()
    19. yytext
      1. Enlarging yytext
      2. AT&T and MKS Lex
        1. Flex
        2. Pclex
    20. yywrap()
  10. 7. A Reference for Yacc Grammars
    1. Structure of a Yacc Grammar
      1. Symbols
      2. Definition Section
      3. Rules Section
      4. User Subroutines Section
    2. Actions
      1. Embedded Actions
      2. Symbol Types for Embedded Actions
      3. Obsolescent Feature
    3. Ambiguity and Conflicts
      1. Types of Conflicts
        1. Shift/Reduce Conflicts
        2. Reduce/Reduce Conflicts
    4. Bugs in Yacc
      1. Real Bugs
        1. Error Handling
        2. Declaring Literal Tokens
      2. Infinite Recursion
      3. Unreal Bugs
        1. Interchanging Precedences
        2. Embedded Actions
    5. End Marker
    6. Error Token and Error Recovery
    7. %ident Declaration
    8. Inherited Attributes ($0)
      1. Symbol Types for Inherited Attributes
    9. Lexical Feedback
    10. Literal Block
    11. Literal Tokens
    12. Portability of Yacc Parsers
      1. Porting Yacc Grammars
      2. Porting Generated C Parsers
        1. Libraries
        2. Character Codes
    13. Precedence, Associativity, and Operator Declarations
      1. Precedence and Associativity
        1. Precedence
        2. Associativity
      2. Operator Declarations
      3. Using Precedence and Associativity to Resolve Conflicts
      4. Typical Uses of Precedence
    14. Recursive Rules
      1. Left and Right Recursion
    15. Rules
    16. Special Characters
    17. Start Declaration
    18. Symbol Values
      1. Declaring Symbol Types
      2. Calculator Example
      3. Explicit Symbol Types
    19. Tokens
      1. Token Numbers
      2. Token Values
    20. %type Declaration
    21. %union Declaration
    22. Variant and Multiple Grammars
      1. Combined Parsers
      2. Multiple Parsers
        1. Using the -p Flag
        2. Faking It
      3. Recursive Parsing
      4. Lexers for Multiple Parsers
    23. y.output Files
    24. Yacc Library
      1. main()
      2. yyerror()
    25. YYABORT
    26. YYACCEPT
    27. YYBACKUP
    28. yyclearin
    29. yydebug and YYDEBUG
    30. YYDEBUG
      1. yydebug
    31. yyerrok
    32. YYERROR
    33. yyerror()
    34. yyparse()
    35. YYRECOVERING()
  11. 8. Yacc Ambiguities and Conflicts
    1. The Pointer Model and Conflicts
      1. Types of Conflicts
      2. Parser States
      3. Contents of y.output
        1. Reduce/Reduce Conflicts
        2. Shift/Reduce Conflicts
      4. Review of Conflicts in y.output
    2. Common Examples of Conflicts
      1. Expression Grammars
    3. IF—THEN—ELSE
      1. Nested List Grammer
    4. How Do I Fix the Conflict?
    5. IF—THEN—ELSE (Shift/Reduce)
      1. Loop Within a Loop (Shift/Reduce)
      2. Expression Precedence (Shift/Reduce)
      3. Limited Lookahead (Shift/Reduce or Reduce/Reduce)
      4. Overlap of Alternatives (Reduce/Reduce)
    6. Summary
    7. Exercises
  12. 9. Error Reporting and Recovery
    1. Error Reporting
      1. Better Lex Error Reports
    2. Error Recovery
      1. Yacc Error Recovery
      2. Where to Put Error Tokens
    3. Compiler Error Recovery
    4. Exercises
  13. A. AT&T Lex
    1. Error Messages
  14. B. AT&T Yacc
    1. Options
    2. Error Messages
  15. C. Berkeley Yacc
    1. Options
    2. Error Messages
      1. Fatal Errors
      2. Regular Errors
      3. Warnings
      4. Informative Messages
  16. D. GNU Bison
    1. Differences
  17. E. Flex
    1. Flex Differences
    2. Options
    3. Error Messages
    4. Flex Versions of Lexer Examples
  18. F. MKS lex and yacc
    1. Differences
    2. New Features
  19. G. Abraxas lex and yacc
    1. Differences
    2. New Features
  20. H. POSIX lex and yacc
    1. Options
    2. Differences
  21. I. MGL Compiler Code
    1. MGL Yacc Source
    2. MGL Lex Source
    3. Supporting C Code
  22. J. SQL Parser Code
    1. Yacc Parser
    2. Cross-reference
  23. K. SQL Parser Code
    1. Lex Scanner
    2. Supporting Code
  24. Glossary
  25. Bibliography
  26. Index
  27. About the Authors
  28. Copyright

Product information

  • Title: lex & yacc, 2nd Edition
  • Author(s): John Levine, Doug Brown, Tony Mason
  • Release date: October 1992
  • Publisher(s): O'Reilly Media, Inc.
  • ISBN: 9781565920002