Lex & Yacc · 2nd Edition by Doug Brown, John Levine -- Read -- Imperial Library of Trantor

Index

lex & yacc, 2nd Edition A Note Regarding Supplemental Files Preface

What’s New in the Second Edition Scope of This Book Availability of Lex and Yacc Sample Programs Conventions Used in This Handbook Acknowledgments

1. Lex and Yacc

The Simplest Lex Program Recognizing Words with Lex

Symbol Tables

Grammars

Parser-Lexer Communication

The Parts of Speech Lexer

A Yacc Parser The Rules Section

Running Lex and Yacc Lex vs. Hand-written Lexers Exercises

2. Using Lex

Regular Expressions

Examples of Regular Expressions

A Word Counting Program Parsing a Command Line

Start States

A C Source Code Analyzer Summary Exercises

3. Using Yacc

Grammars

Recursive Rules

Shift/Reduce Parsing

What Yacc Cannot Parse

A Yacc Parser

The Definition Section The Rules Section Symbol Values and Actions

The Lexer

Compiling and Running a Simple Parser

Arithmetic Expressions and Ambiguity

When Not to Use Precedence Rules

Variables and Typed Tokens

Symbol Values and %union

Symbol Tables Functions and Reserved Words

Reserved Words in the Symbol Table Interchangeable Function and Variable Names

Building Parsers with Make Summary Exercises

4. A Menu Generation Language

Overview of the MGL Developing the MGL Building the MGL

Initialization

Screen Processing Termination Sample MGL Code Exercises

5. Parsing SQL

A Quick Overview of SQL

Relational Data Bases Manipulating Relations

Three Ways to Use SQL The Syntax Checker

The Lexer Error and Main Routines

The Parser

Definitions Top Level Rules The Schema Sublanguage

Base Tables View Definition Privilege Definitions

The Module Sublanguage

Cursor Definitions

The Manipulation Sublanguage

Simple Statements FETCH Statements INSERT Statements DELETE Statements UPDATE Statements Scalar Expressions SELECT Statements Table Expressions Search Conditions

Odds and Ends Using the Syntax Checker Embedded SQL

Changes to the Lexer Changes to the Parser Auxiliary Routines Using the Preprocessor

Exercises

6. A Reference for Lex Specifications

Structure of a Lex Specification

Definition Section Rules Section User Subroutines

BEGIN

Bugs

Ambiguous Lookahead

AT&T Lex

Flex

Character Translations Context Sensitivity

Left Context Right Context

Definitions (Substitutions)

ECHO

Include Operations (Logical Nesting of Files)

File Chaining with yywrap() File Nesting AT&T Lex Flex MKS Lex Abraxas Pclex POSIX Lex

Input from Strings

AT&T Lex Flex Abraxas Pclex MKS Lex POSIX Lex input()

Internal Tables (%N Declarations)

lex Library

main() Other Library Routines

Line Numbers and yylineno

Literal Block

Multiple Lexers in One Program

Combined Lexers Multiple Lexers

Using the p Flag Faking It

output() Portability of Lex Lexers

Porting Lex Specifications Porting Generated C Lexers

Libraries Buffer Sizes Character Sets

Regular Expression Syntax

Metacharacters POSIX Extensions

REJECT Returning Values from yylex()

Start States

unput() yyinput(), yyoutput(), yyunput() yyleng yyless() yylex()

User Code in yylex()

yymore() yytext

Enlarging yytext AT&T and MKS Lex

Flex Pclex

yywrap()

7. A Reference for Yacc Grammars

Structure of a Yacc Grammar

Symbols Definition Section Rules Section User Subroutines Section

Actions

Embedded Actions Symbol Types for Embedded Actions Obsolescent Feature

Ambiguity and Conflicts

Types of Conflicts

Shift/Reduce Conflicts Reduce/Reduce Conflicts

Bugs in Yacc

Real Bugs

Error Handling Declaring Literal Tokens

Infinite Recursion Unreal Bugs

Interchanging Precedences Embedded Actions

End Marker Error Token and Error Recovery %ident Declaration Inherited Attributes ($0)

Symbol Types for Inherited Attributes

Lexical Feedback Literal Block Literal Tokens Portability of Yacc Parsers

Porting Yacc Grammars Porting Generated C Parsers

Libraries Character Codes

Precedence, Associativity, and Operator Declarations

Precedence and Associativity

Precedence Associativity

Operator Declarations Using Precedence and Associativity to Resolve Conflicts Typical Uses of Precedence

Recursive Rules

Left and Right Recursion

Rules Special Characters Start Declaration Symbol Values

Declaring Symbol Types Calculator Example Explicit Symbol Types

Tokens

Token Numbers Token Values

%type Declaration %union Declaration Variant and Multiple Grammars

Combined Parsers Multiple Parsers

Using the -p Flag Faking It

Recursive Parsing Lexers for Multiple Parsers

y.output Files Yacc Library

main() yyerror()

YYABORT YYACCEPT YYBACKUP yyclearin yydebug and YYDEBUG YYDEBUG

yydebug

yyerrok YYERROR yyerror() yyparse() YYRECOVERING()

8. Yacc Ambiguities and Conflicts

The Pointer Model and Conflicts

Types of Conflicts Parser States Contents of y.output

Reduce/Reduce Conflicts Shift/Reduce Conflicts

Review of Conflicts in y.output

Common Examples of Conflicts

Expression Grammars

IF—THEN—ELSE

Nested List Grammer

How Do I Fix the Conflict? IF—THEN—ELSE (Shift/Reduce)

Loop Within a Loop (Shift/Reduce) Expression Precedence (Shift/Reduce) Limited Lookahead (Shift/Reduce or Reduce/Reduce) Overlap of Alternatives (Reduce/Reduce)

Summary Exercises

9. Error Reporting and Recovery

Error Reporting

Better Lex Error Reports

Error Recovery

Yacc Error Recovery Where to Put Error Tokens

Compiler Error Recovery Exercises

A. AT&T Lex

Error Messages

B. AT&T Yacc

Options Error Messages

C. Berkeley Yacc

Options Error Messages

Fatal Errors Regular Errors Warnings Informative Messages

D. GNU Bison

Differences

E. Flex

Flex Differences Options Error Messages Flex Versions of Lexer Examples

F. MKS lex and yacc

Differences New Features

G. Abraxas lex and yacc

Differences New Features

H. POSIX lex and yacc

Options Differences

I. MGL Compiler Code

MGL Yacc Source MGL Lex Source Supporting C Code

J. SQL Parser Code

Yacc Parser Cross-reference

K. SQL Parser Code

Lex Scanner Supporting Code

Glossary Bibliography

Index About the Authors Copyright

← Prev
Back
Next →

← Prev
Back
Next →