The Simplest Lex Program

Recognizing Words with Lex

1. Symbol Tables

Grammars

1. Parser-Lexer Communication

The Parts of Speech Lexer

1. A Yacc Parser
2. The Rules Section

Running Lex and Yacc

Lex vs. Hand-written Lexers

Exercises

Regular Expressions

1. Examples of Regular Expressions

A Word Counting Program

Parsing a Command Line

1. Start States

A C Source Code Analyzer

Summary

Exercises

Grammars

1. Recursive Rules

Shift/Reduce Parsing

1. What Yacc Cannot Parse

A Yacc Parser

1. The Definition Section
2. The Rules Section
3. Symbol Values and Actions

The Lexer

1. Compiling and Running a Simple Parser

Arithmetic Expressions and Ambiguity

1. When Not to Use Precedence Rules

Variables and Typed Tokens

1. Symbol Values and %union

Symbol Tables

Functions and Reserved Words

1. Reserved Words in the Symbol Table
2. Interchangeable Function and Variable Names

Building Parsers with Make

Summary

Exercises

Overview of the MGL

Developing the MGL

Building the MGL

1. Initialization

Screen Processing

Termination

Sample MGL Code

Exercises

A Quick Overview of SQL

1. Relational Data Bases
2. Manipulating Relations

Three Ways to Use SQL

The Syntax Checker

1. The Lexer
2. Error and Main Routines

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

Structure of a Lex Specification

1. Definition Section
2. Rules Section
3. User Subroutines

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)

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

Input from Strings

1. AT&T Lex
2. Flex
3. Abraxas Pclex
4. MKS Lex
5. POSIX Lex
6. input()

Internal Tables (%N Declarations)

1. lex Library
   1. main()
   2. Other Library Routines

Line Numbers and yylineno

1. Literal Block

Multiple Lexers in One Program

1. Combined Lexers
2. Multiple Lexers
   1. Using the p Flag
   2. Faking It

output()

Portability of Lex Lexers

1. Porting Lex Specifications
2. Porting Generated C Lexers
   1. Libraries
   2. Buffer Sizes
   3. Character Sets

Regular Expression Syntax

1. Metacharacters
2. POSIX Extensions

REJECT

Returning Values from yylex()

1. Start States

unput()

yyinput(), yyoutput(), yyunput()

yyleng

yyless()

yylex()

1. User Code in yylex()

yymore()

yytext

1. Enlarging yytext
2. AT&T and MKS Lex
   1. Flex
   2. Pclex

yywrap()

Structure of a Yacc Grammar

1. Symbols
2. Definition Section
3. Rules Section
4. User Subroutines Section

Actions

1. Embedded Actions
2. Symbol Types for Embedded Actions
3. Obsolescent Feature

Ambiguity and Conflicts

1. Types of Conflicts
   1. Shift/Reduce Conflicts
   2. Reduce/Reduce Conflicts

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

End Marker

Error Token and Error Recovery

%ident Declaration

Inherited Attributes ($0)

1. Symbol Types for Inherited Attributes

Lexical Feedback

Literal Block

Literal Tokens

Portability of Yacc Parsers

1. Porting Yacc Grammars
2. Porting Generated C Parsers
   1. Libraries
   2. Character Codes

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

Recursive Rules

1. Left and Right Recursion

Rules

Special Characters

Start Declaration

Symbol Values

1. Declaring Symbol Types
2. Calculator Example
3. Explicit Symbol Types

Tokens

1. Token Numbers
2. Token Values

%type Declaration

%union Declaration

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

y.output Files

Yacc Library

1. main()
2. yyerror()

YYABORT

YYACCEPT

YYBACKUP

yyclearin

yydebug and YYDEBUG

YYDEBUG

1. yydebug

yyerrok

YYERROR

yyerror()

yyparse()

YYRECOVERING()

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

Common Examples of Conflicts

1. Expression Grammars

IF—THEN—ELSE

1. Nested List Grammer

How Do I Fix the Conflict?

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)

Summary

Exercises

Error Reporting

1. Better Lex Error Reports

Error Recovery

1. Yacc Error Recovery
2. Where to Put Error Tokens

Compiler Error Recovery

Exercises