Class Notes

Introduction

• Pre-Quiz
  
• Languages Used by Students
  
• First Language
  

History of Programming Languages

• Tower of Babel, CACM cover, Jan. 1961
  
• A Roster of Programming Languages for 1976-77, J. Sammet, ACM SIGPLAN Notices, 1976, pp 56-59.
  Table 1-4, Table 1-5, Language Survey
  
• Language Pedigrees, Horowitz
  
• Levenez History of Programming Languages
  

Pascal Syntax

• ISO7185 - Pascal BNF
  
• program, block
  
• statement
  
• simple type, type, field list
  
• identifier, unsigned integer, unsigned number, unsigned constant, constant
  
• simple expression, expression, parameter list
  
• variable, factor, term
  

Recursive-Descent Parsing

• LL Grammars
  
• First & Follow Sets
  
• BNF to Syntax Graph
  
• Example 3.1 Syntax Graphs
  
• Syntax Graph to Parsing Program
  
• Recursive-Descent Calculator: calc.c
  

Table-Driven Parsing

• Parse Table Representation
  
• Syntax Graph to Linked-List
  
• Example 3.1 Linked List
  
• Example: Positive Integers
  
• Table-Driven Parsing Program Outline
  
• Table-Driven Parsing Procedure
  
• Table-Driven Parser: parsegraph.c
  
• Example: Parse Table for Positive Integers
  

ALGOL-60 for statement

• Syntax Graph
  
• Linked List
  

Dependency Graphs and Topological Sorting

Variables

• Definitions
  
• Usage, Aliasing
  
• Equivalence, Declarations
  
• Binding
  
• Scope
  
• Lifetime