Programming Language Syntax

Principles of Programming Languages

Nguyễn Thị Minh Huyền

Faculty of Mathematics, Mechanics and Informatics

VNU University of Science, Hanoi
Contents

1. Introduction

2. Language specifications
Formal language
Regular expressions
Context-free grammars

3. Syntax Analysis
Scanning
Deterministic finite automaton
Generating a finite automaton
Scanner code
Parsing

Programming Language Syntax 2 / 48

 Introduction

Contents

1. Introduction

2. Language specifications
Formal language
Regular expressions
Context-free grammars

3. Syntax Analysis
Scanning
Deterministic finite automaton
Generating a finite automaton
Scanner code
Parsing

Programming Language Syntax 1 / 48

 Introduction

Language syntaxe

Programming languages must have a clearly specified

syntax.
Compilers of a programming language only understand
programs conforming to its syntax specifications.
Language specifications: formal languages
Regular expression (lexical analysis)
Context-free grammar (syntax analysis)

Programming Language Syntax 2 / 48

 Introduction

Language syntaxe

Programming languages must have a clearly specified

syntax.
Compilers of a programming language only understand
programs conforming to its syntax specifications.
Language specifications: formal languages
Regular expression (lexical analysis)
Context-free grammar (syntax analysis)

Programming Language Syntax 2 / 48

 Introduction

Language syntaxe

Programming languages must have a clearly specified

syntax.
Compilers of a programming language only understand
programs conforming to its syntax specifications.
Language specifications: formal languages
Regular expression (lexical analysis)
Context-free grammar (syntax analysis)

Programming Language Syntax 2 / 48

 Introduction

Language syntaxe

Programming languages must have a clearly specified

syntax.
Compilers of a programming language only understand
programs conforming to its syntax specifications.
Language specifications: formal languages
Regular expression (lexical analysis)
Context-free grammar (syntax analysis)

Programming Language Syntax 2 / 48

 Introduction

Language syntaxe

Programming languages must have a clearly specified

syntax.
Compilers of a programming language only understand
programs conforming to its syntax specifications.
Language specifications: formal languages
Regular expression (lexical analysis)
Context-free grammar (syntax analysis)

Programming Language Syntax 2 / 48

 Introduction

Language syntax (1)

In a natural language:
Alphabet
Word: string of characters in the alphabet
Defined in a dictionary
Categorized in accordance with its syntactic functions
(noun, verb, adjective ...)
Sentence: string of words in the dictionary, in accordance
with the grammar
Constituents: noun phrase, verb phrase, adjective phrase
Paragraph, document...

Programming Language Syntax 3 / 48

 Introduction

Language syntax (1)

In a natural language:
Alphabet
Word: string of characters in the alphabet
Defined in a dictionary
Categorized in accordance with its syntactic functions
(noun, verb, adjective ...)
Sentence: string of words in the dictionary, in accordance
with the grammar
Constituents: noun phrase, verb phrase, adjective phrase
Paragraph, document...

Programming Language Syntax 3 / 48

 Introduction

Language syntax (1)

In a natural language:
Alphabet
Word: string of characters in the alphabet
Defined in a dictionary
Categorized in accordance with its syntactic functions
(noun, verb, adjective ...)
Sentence: string of words in the dictionary, in accordance
with the grammar
Constituents: noun phrase, verb phrase, adjective phrase
Paragraph, document...

Programming Language Syntax 3 / 48

 Introduction

Language syntax (1)

In a natural language:
Alphabet
Word: string of characters in the alphabet
Defined in a dictionary
Categorized in accordance with its syntactic functions
(noun, verb, adjective ...)
Sentence: string of words in the dictionary, in accordance
with the grammar
Constituents: noun phrase, verb phrase, adjective phrase
Paragraph, document...

Programming Language Syntax 3 / 48

 Introduction

Language syntax (1)

In a natural language:
Alphabet
Word: string of characters in the alphabet
Defined in a dictionary
Categorized in accordance with its syntactic functions
(noun, verb, adjective ...)
Sentence: string of words in the dictionary, in accordance
with the grammar
Constituents: noun phrase, verb phrase, adjective phrase
Paragraph, document...

Programming Language Syntax 3 / 48

 Introduction

Language syntax (2)

In a programing language:
Alphabet: a, ..., z, , ?, <, >, ; (, ), {, }, ...
Token: if, while, =, ==, <= ...
Tokens are specified using string patterns
Statement in accordance with the syntax
Syntax is specified by a formal grammar
Program

Programming Language Syntax 4 / 48

 Introduction

Language syntax (2)

In a programing language:
Alphabet: a, ..., z, , ?, <, >, ; (, ), {, }, ...
Token: if, while, =, ==, <= ...
Tokens are specified using string patterns
Statement in accordance with the syntax
Syntax is specified by a formal grammar
Program

Programming Language Syntax 4 / 48

 Introduction

Language syntax (2)

In a programing language:
Alphabet: a, ..., z, , ?, <, >, ; (, ), {, }, ...
Token: if, while, =, ==, <= ...
Tokens are specified using string patterns
Statement in accordance with the syntax
Syntax is specified by a formal grammar
Program

Programming Language Syntax 4 / 48

 Introduction

Language syntax (2)

In a programing language:
Alphabet: a, ..., z, , ?, <, >, ; (, ), {, }, ...
Token: if, while, =, ==, <= ...
Tokens are specified using string patterns
Statement in accordance with the syntax
Syntax is specified by a formal grammar
Program

Programming Language Syntax 4 / 48

 Introduction

Language syntax (2)

In a programing language:
Alphabet: a, ..., z, , ?, <, >, ; (, ), {, }, ...
Token: if, while, =, ==, <= ...
Tokens are specified using string patterns
Statement in accordance with the syntax
Syntax is specified by a formal grammar
Program

Programming Language Syntax 4 / 48

 Language specifications

Contents

1. Introduction

2. Language specifications
Formal language
Regular expressions
Context-free grammars

3. Syntax Analysis
Scanning
Deterministic finite automaton
Generating a finite automaton
Scanner code
Parsing

Programming Language Syntax 5 / 48

 Language specifications Formal language

Formal language

Alphabet: a finite, nonempty set of symbols

Conventional notation: Σ
A string over an alphabet Σ: a finite sequence of symbols
from Σ
 - empty string: empty sequence of symbols
Σ∗ (the Kleene star of Σ) - set of all strings over Σ, including

A language L over an alphabet Σ: a set of strings over Σ
L is a subset of Σ∗

Programming Language Syntax 6 / 48

 Language specifications Formal language

Formal language

Alphabet: a finite, nonempty set of symbols

Conventional notation: Σ
A string over an alphabet Σ: a finite sequence of symbols
from Σ
 - empty string: empty sequence of symbols
Σ∗ (the Kleene star of Σ) - set of all strings over Σ, including

A language L over an alphabet Σ: a set of strings over Σ
L is a subset of Σ∗

Programming Language Syntax 6 / 48

 Language specifications Formal language

Formal language

Alphabet: a finite, nonempty set of symbols

Conventional notation: Σ
A string over an alphabet Σ: a finite sequence of symbols
from Σ
 - empty string: empty sequence of symbols
Σ∗ (the Kleene star of Σ) - set of all strings over Σ, including

A language L over an alphabet Σ: a set of strings over Σ
L is a subset of Σ∗

Programming Language Syntax 6 / 48

 Language specifications Formal language

Formal language

Alphabet: a finite, nonempty set of symbols

Conventional notation: Σ
A string over an alphabet Σ: a finite sequence of symbols
from Σ
 - empty string: empty sequence of symbols
Σ∗ (the Kleene star of Σ) - set of all strings over Σ, including

A language L over an alphabet Σ: a set of strings over Σ
L is a subset of Σ∗

Programming Language Syntax 6 / 48

 Language specifications Formal language

Formal language

Alphabet: a finite, nonempty set of symbols

Conventional notation: Σ
A string over an alphabet Σ: a finite sequence of symbols
from Σ
 - empty string: empty sequence of symbols
Σ∗ (the Kleene star of Σ) - set of all strings over Σ, including

A language L over an alphabet Σ: a set of strings over Σ
L is a subset of Σ∗

Programming Language Syntax 6 / 48

 Language specifications Formal language

Formal language

Alphabet: a finite, nonempty set of symbols

Conventional notation: Σ
A string over an alphabet Σ: a finite sequence of symbols
from Σ
 - empty string: empty sequence of symbols
Σ∗ (the Kleene star of Σ) - set of all strings over Σ, including

A language L over an alphabet Σ: a set of strings over Σ
L is a subset of Σ∗

Programming Language Syntax 6 / 48

 Language specifications Formal language

String concatenation

Concatenation of two strings u = u1 · · · um and v = v1 · · · vn

(with n, m ≥ 0) over Σ is

w = u · v = uv = u1 · · · um v1 · · · vn

The empty string is the neutral element:

w = w = w ∀w ∈ Σ∗

Powers (exponents):
Denote u 0 = , u 1 = u, u n = u n−1 · u
with n being any natural number > 1

Programming Language Syntax 7 / 48

 Language specifications Formal language

String concatenation

Concatenation of two strings u = u1 · · · um and v = v1 · · · vn

(with n, m ≥ 0) over Σ is

w = u · v = uv = u1 · · · um v1 · · · vn

The empty string is the neutral element:

w = w = w ∀w ∈ Σ∗

Powers (exponents):
Denote u 0 = , u 1 = u, u n = u n−1 · u
with n being any natural number > 1

Programming Language Syntax 7 / 48

 Language specifications Formal language

String concatenation

Concatenation of two strings u = u1 · · · um and v = v1 · · · vn

(with n, m ≥ 0) over Σ is

w = u · v = uv = u1 · · · um v1 · · · vn

The empty string is the neutral element:

w = w = w ∀w ∈ Σ∗

Powers (exponents):
Denote u 0 = , u 1 = u, u n = u n−1 · u
with n being any natural number > 1

Programming Language Syntax 7 / 48

 Language specifications Formal language

Language concatenation

Given L1 , L2 ⊆ Σ∗ , the concatenation of L1 and L2 is

L = L1 · L2 = L1 L2 = {w ∈ Σ∗ |∃u ∈ L1 , v ∈ L2 : w = u · v}

L{} = {}L = L
L∅ = ∅L = ∅
Powers: Given L ⊆ Σ∗
L0 = {}
L1 = L
Ln = Ln−1 L
with n being any natural number > 1

Programming Language Syntax 8 / 48

 Language specifications Formal language

Language concatenation

Given L1 , L2 ⊆ Σ∗ , the concatenation of L1 and L2 is

L = L1 · L2 = L1 L2 = {w ∈ Σ∗ |∃u ∈ L1 , v ∈ L2 : w = u · v}

L{} = {}L = L
L∅ = ∅L = ∅
Powers: Given L ⊆ Σ∗
L0 = {}
L1 = L
Ln = Ln−1 L
with n being any natural number > 1

Programming Language Syntax 8 / 48

 Language specifications Formal language

Language concatenation

Given L1 , L2 ⊆ Σ∗ , the concatenation of L1 and L2 is

L = L1 · L2 = L1 L2 = {w ∈ Σ∗ |∃u ∈ L1 , v ∈ L2 : w = u · v}

L{} = {}L = L
L∅ = ∅L = ∅
Powers: Given L ⊆ Σ∗
L0 = {}
L1 = L
Ln = Ln−1 L
with n being any natural number > 1

Programming Language Syntax 8 / 48

 Language specifications Formal language

Language concatenation

Given L1 , L2 ⊆ Σ∗ , the concatenation of L1 and L2 is

L = L1 · L2 = L1 L2 = {w ∈ Σ∗ |∃u ∈ L1 , v ∈ L2 : w = u · v}

L{} = {}L = L
L∅ = ∅L = ∅
Powers: Given L ⊆ Σ∗
L0 = {}
L1 = L
Ln = Ln−1 L
with n being any natural number > 1

Programming Language Syntax 8 / 48

 Language specifications Formal language

Set operations on languages

Union, intersection, difference, complement

Union: L1 , L2 ⊆ Σ∗

L = L1 ∪ L2 = L1 ∨ L2 = {w ∈ Σ∗ |w ∈ L1 ∨ w ∈ L2 }

Programming Language Syntax 9 / 48

 Language specifications Formal language

Set operations on languages

Union, intersection, difference, complement

Union: L1 , L2 ⊆ Σ∗

L = L1 ∪ L2 = L1 ∨ L2 = {w ∈ Σ∗ |w ∈ L1 ∨ w ∈ L2 }

Programming Language Syntax 9 / 48

 Language specifications Formal language

Kleene star, Kleene plus

Given L ⊆ Σ∗
The Kleene star (or concatenation closure) of L
∞
[
∗
L = Ln
n=0

The Kleene plus of L

∞
[
L+ = Ln
n=1

Example: Σ = {0, 1}
(Σ2 )∗ =?

Programming Language Syntax 10 / 48

 Language specifications Formal language

Kleene star, Kleene plus

Given L ⊆ Σ∗
The Kleene star (or concatenation closure) of L
∞
[
∗
L = Ln
n=0

The Kleene plus of L

∞
[
L+ = Ln
n=1

Example: Σ = {0, 1}
(Σ2 )∗ =?

Programming Language Syntax 10 / 48

 Language specifications Formal language

Kleene star, Kleene plus

Given L ⊆ Σ∗
The Kleene star (or concatenation closure) of L
∞
[
∗
L = Ln
n=0

The Kleene plus of L

∞
[
L+ = Ln
n=1

Example: Σ = {0, 1}
(Σ2 )∗ =?

Programming Language Syntax 10 / 48

 Language specifications Formal language

Kleene star, Kleene plus

Given L ⊆ Σ∗
The Kleene star (or concatenation closure) of L
∞
[
∗
L = Ln
n=0

The Kleene plus of L

∞
[
L+ = Ln
n=1

Example: Σ = {0, 1}
(Σ2 )∗ =?

Programming Language Syntax 10 / 48

 Language specifications Formal language

Operator precedence

Unary operators: Kleene star *

Binary operators:
Concatenation
Union

Programming Language Syntax 11 / 48

 Language specifications Formal language

Operator precedence

Unary operators: Kleene star *

Binary operators:
Concatenation
Union

Programming Language Syntax 11 / 48

 Language specifications Regular expressions

Regular expression

Let Σ be an alphabet. A regular expression (regex) R

defines a language L(R)
Inductive definition:
Basis: a (a ∈ Σ) is a regex representing the language {a}, 
representing {}, ∅ representing the empty language
Inductive step: If R1 , R2 are regular expressions, then
R1 |R2 is a regex defining the language L(R1 ) ∪ L(R2 )
R1 .R2 (or R1 R2 ) is a regex defining the language L(R1 ).L(R2 )
R1∗ defining the language L(R1 )∗
Closure: Nothing else is a regex.
Parentheses: We use parentheses to define the order of
operations, but we often omit them following standard
precedence rules: Star (∗ ) > Concatenation > Union (+)

Programming Language Syntax 12 / 48

 Language specifications Regular expressions

Regular expression

Let Σ be an alphabet. A regular expression (regex) R

defines a language L(R)
Inductive definition:
Basis: a (a ∈ Σ) is a regex representing the language {a}, 
representing {}, ∅ representing the empty language
Inductive step: If R1 , R2 are regular expressions, then
R1 |R2 is a regex defining the language L(R1 ) ∪ L(R2 )
R1 .R2 (or R1 R2 ) is a regex defining the language L(R1 ).L(R2 )
R1∗ defining the language L(R1 )∗
Closure: Nothing else is a regex.
Parentheses: We use parentheses to define the order of
operations, but we often omit them following standard
precedence rules: Star (∗ ) > Concatenation > Union (+)

Programming Language Syntax 12 / 48

 Language specifications Regular expressions

Tokens: Example

letter = a | b | c | ... | A | B | C | ...

digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
pdigit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
id = (letter | _)(letter | digit | _)*
num = 0 | pdigit(digit)*

Programming Language Syntax 13 / 48

 Language specifications Regular expressions

Tokens: Example

letter = a | b | c | ... | A | B | C | ...

digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
pdigit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
id = (letter | _)(letter | digit | _)*
num = 0 | pdigit(digit)*

Programming Language Syntax 13 / 48

 Language specifications Regular expressions

Tokens: Example

letter = a | b | c | ... | A | B | C | ...

digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
pdigit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
id = (letter | _)(letter | digit | _)*
num = 0 | pdigit(digit)*

Programming Language Syntax 13 / 48

 Language specifications Regular expressions

Tokens: Example

letter = a | b | c | ... | A | B | C | ...

digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
pdigit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
id = (letter | _)(letter | digit | _)*
num = 0 | pdigit(digit)*

Programming Language Syntax 13 / 48

 Language specifications Regular expressions

Tokens: Example

letter = a | b | c | ... | A | B | C | ...

digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
pdigit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
id = (letter | _)(letter | digit | _)*
num = 0 | pdigit(digit)*

Programming Language Syntax 13 / 48

 Language specifications Context-free grammars

Regular expressions for syntax?

Regular expressions are not sufficient to capture all

programming constructs
Regular expressions have no concept of counting, therefore
impossible to create a regular expression R for matching
L(R) = {, (), (()), ((())), · · · }

Programming Language Syntax 14 / 48

 Language specifications Context-free grammars

Context-free grammars (CFG)

Formal definition: A CFG is quadruple (4-tuple)

G = (T , N, S, P), in which:
T is an alphabet of terminals
N is an alphabet of nonterminals or variables, N ∩ T = ∅
S ∈ N is a start symbol
P is a finite set of rules/productions A → α
A ∈ N, →∈ / T ∪ N, α ∈ (T ∪ N)∗

Programming Language Syntax 15 / 48

 Language specifications Context-free grammars

Context-free grammars (CFG)

Formal definition: A CFG is quadruple (4-tuple)

G = (T , N, S, P), in which:
T is an alphabet of terminals
N is an alphabet of nonterminals or variables, N ∩ T = ∅
S ∈ N is a start symbol
P is a finite set of rules/productions A → α
A ∈ N, →∈ / T ∪ N, α ∈ (T ∪ N)∗

Programming Language Syntax 15 / 48

 Language specifications Context-free grammars

Context-free grammars (CFG)

Formal definition: A CFG is quadruple (4-tuple)

G = (T , N, S, P), in which:
T is an alphabet of terminals
N is an alphabet of nonterminals or variables, N ∩ T = ∅
S ∈ N is a start symbol
P is a finite set of rules/productions A → α
A ∈ N, →∈ / T ∪ N, α ∈ (T ∪ N)∗

Programming Language Syntax 15 / 48

 Language specifications Context-free grammars

Context-free grammars (CFG)

Formal definition: A CFG is quadruple (4-tuple)

G = (T , N, S, P), in which:
T is an alphabet of terminals
N is an alphabet of nonterminals or variables, N ∩ T = ∅
S ∈ N is a start symbol
P is a finite set of rules/productions A → α
A ∈ N, →∈ / T ∪ N, α ∈ (T ∪ N)∗

Programming Language Syntax 15 / 48

 Language specifications Context-free grammars

Context-free grammars (CFG)

Formal definition: A CFG is quadruple (4-tuple)

G = (T , N, S, P), in which:
T is an alphabet of terminals
N is an alphabet of nonterminals or variables, N ∩ T = ∅
S ∈ N is a start symbol
P is a finite set of rules/productions A → α
A ∈ N, →∈ / T ∪ N, α ∈ (T ∪ N)∗

Programming Language Syntax 15 / 48

 Language specifications Context-free grammars

Derivation

Direct derivation: α ∈ (T ∪ N)∗ directly generates

β ∈ (T ∪ N)∗ (or β is directly derived from α), denoted
α ⇒ β, iff there exists a rule A → γ ∈ P s.t. α = uAv and
β = uγv.
In other words, the right-hand side is obtained by using a
production to replace some nonterminal in the left-hand side.
The relation ⇒∗ denotes the reflexive transitive closure of
the derivation relation ⇒.
α ⇒∗ β: derives after zero or more replacements
[w0 , w1 , · · · , wn ] - Derivation of n steps w0 ⇒ w1 ⇒ ... ⇒ wn
w0 ⇒ ∗ wn

Programming Language Syntax 16 / 48

 Language specifications Context-free grammars

Derivation

Direct derivation: α ∈ (T ∪ N)∗ directly generates

β ∈ (T ∪ N)∗ (or β is directly derived from α), denoted
α ⇒ β, iff there exists a rule A → γ ∈ P s.t. α = uAv and
β = uγv.
In other words, the right-hand side is obtained by using a
production to replace some nonterminal in the left-hand side.
The relation ⇒∗ denotes the reflexive transitive closure of
the derivation relation ⇒.
α ⇒∗ β: derives after zero or more replacements
[w0 , w1 , · · · , wn ] - Derivation of n steps w0 ⇒ w1 ⇒ ... ⇒ wn
w0 ⇒ ∗ wn

Programming Language Syntax 16 / 48

 Language specifications Context-free grammars

Derivation

Direct derivation: α ∈ (T ∪ N)∗ directly generates

β ∈ (T ∪ N)∗ (or β is directly derived from α), denoted
α ⇒ β, iff there exists a rule A → γ ∈ P s.t. α = uAv and
β = uγv.
In other words, the right-hand side is obtained by using a
production to replace some nonterminal in the left-hand side.
The relation ⇒∗ denotes the reflexive transitive closure of
the derivation relation ⇒.
α ⇒∗ β: derives after zero or more replacements
[w0 , w1 , · · · , wn ] - Derivation of n steps w0 ⇒ w1 ⇒ ... ⇒ wn
w0 ⇒ ∗ wn

Programming Language Syntax 16 / 48

 Language specifications Context-free grammars

Language generated by a grammar

Let G = (T , N, S, P) be a grammar. The formal language L

generated by the grammar G is the set of all strings over
the alphabet T derived from the start symbol S:
L(G) = {w ∈ T ∗ |S ⇒∗ w}
Two formal grammars G1 and G2 are equivalent iff
L(G1 ) = L(G2 ).

Programming Language Syntax 17 / 48

 Language specifications Context-free grammars

Language generated by a grammar

Let G = (T , N, S, P) be a grammar. The formal language L

generated by the grammar G is the set of all strings over
the alphabet T derived from the start symbol S:
L(G) = {w ∈ T ∗ |S ⇒∗ w}
Two formal grammars G1 and G2 are equivalent iff
L(G1 ) = L(G2 ).

Programming Language Syntax 17 / 48

 Language specifications Context-free grammars

Example

Expression grammar with precedence and associativity

expr → id | num | −expr | (expr ) | expr op expr
op → + | - | * | /
In this grammar, generate the string slope * x +
intercept

Programming Language Syntax 18 / 48

 Language specifications Context-free grammars

Example

expr ⇒ expr op expr

⇒ expr op id
⇒ expr + id
⇒ expr op expr + id
⇒ expr op id + id
⇒ expr * id + id
⇒ id * id + id
(slope) (x) (intercept)

Programming Language Syntax 19 / 48

 Language specifications Context-free grammars

Parse tree

Each derivation [w0 , w1 , · · · , wn ] s.t. w0 = A ∈ N can be

represented by a parse tree
Each symbol (terminal or nonterminal) is a node in the tree
The constituents on the right-hand side of the production
used to replace the symbol are its children
If w0 is the start symbol S, each string wi (1 ≤ i ≤ n) is
called a sentential form.
If wn is the final sentential form, i.e. it consists of only
terminals, then wn is called the yield of the derivation.
Parse tree of the above derivation?

Programming Language Syntax 20 / 48

 Language specifications Context-free grammars

Parse tree

Each derivation [w0 , w1 , · · · , wn ] s.t. w0 = A ∈ N can be

represented by a parse tree
Each symbol (terminal or nonterminal) is a node in the tree
The constituents on the right-hand side of the production
used to replace the symbol are its children
If w0 is the start symbol S, each string wi (1 ≤ i ≤ n) is
called a sentential form.
If wn is the final sentential form, i.e. it consists of only
terminals, then wn is called the yield of the derivation.
Parse tree of the above derivation?

Programming Language Syntax 20 / 48

 Language specifications Context-free grammars

Parse tree

Each derivation [w0 , w1 , · · · , wn ] s.t. w0 = A ∈ N can be

represented by a parse tree
Each symbol (terminal or nonterminal) is a node in the tree
The constituents on the right-hand side of the production
used to replace the symbol are its children
If w0 is the start symbol S, each string wi (1 ≤ i ≤ n) is
called a sentential form.
If wn is the final sentential form, i.e. it consists of only
terminals, then wn is called the yield of the derivation.
Parse tree of the above derivation?

Programming Language Syntax 20 / 48

 Language specifications Context-free grammars

Example

Parse tree for "slope * x + intercept"

Programming Language Syntax 21 / 48

 Language specifications Context-free grammars

Left-most and right-most derivations

A derivation is a series of replacements

Right-most derivation: At each step, the right-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation: At each step, the left-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation equivalent to the previous right-most
derivation?
The parse tree does not depend on the replacement
strategy

Programming Language Syntax 22 / 48

 Language specifications Context-free grammars

Left-most and right-most derivations

A derivation is a series of replacements

Right-most derivation: At each step, the right-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation: At each step, the left-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation equivalent to the previous right-most
derivation?
The parse tree does not depend on the replacement
strategy

Programming Language Syntax 22 / 48

 Language specifications Context-free grammars

Left-most and right-most derivations

A derivation is a series of replacements

Right-most derivation: At each step, the right-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation: At each step, the left-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation equivalent to the previous right-most
derivation?
The parse tree does not depend on the replacement
strategy

Programming Language Syntax 22 / 48

 Language specifications Context-free grammars

Left-most and right-most derivations

A derivation is a series of replacements

Right-most derivation: At each step, the right-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation: At each step, the left-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation equivalent to the previous right-most
derivation?
The parse tree does not depend on the replacement
strategy

Programming Language Syntax 22 / 48

 Language specifications Context-free grammars

Left-most and right-most derivations

A derivation is a series of replacements

Right-most derivation: At each step, the right-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation: At each step, the left-most
nonterminal is replaced with the right-hand side of some
production
Left-most derivation equivalent to the previous right-most
derivation?
The parse tree does not depend on the replacement
strategy

Programming Language Syntax 22 / 48

 Language specifications Context-free grammars

Example

The grammar is ambiguous: Alternate (incorrect) parse tree for

"slope * x + intercept"

Programming Language Syntax 23 / 48

 Language specifications Context-free grammars

Example

Better version: unambiguous and captures precedence

expr → term | expr add_op term
term → factor | term mult_op factor
factor → id | num | −factor | (expr )
add_op → + | -
mult_op → * | /

Programming Language Syntax 24 / 48

 Language specifications Context-free grammars

Example

Parse tree for expression grammar (with left associativity) for

3+4*5

Programming Language Syntax 25 / 48

 Language specifications Context-free grammars

Common syntax of RE
A single ordinary character represents itself, excepting
metacharacters: ? + - * . { } [ ] ( ) \ | ˆ $
To match a metacharacter, use \ before.
[03a−c] ≡ {0, 3, a, b, c}, [ˆ 15] ≡ set of all characters
excepting 1 and 5
. replaces any character, ˆ and $ match start and end of a
line string.
\< and \> match empty string at the beginning and the end
of a word, \b matches empty string at the edge of a word,
\B matches empty string not at the edge of a word.
Repetition: ?, *, +, {n}, {n, }, {n, m}
Concatenation, union |
\n substring between the n-th () from the beginning to that
position.
Programming Language Syntax 26 / 48
 Syntax Analysis

Contents

1. Introduction

2. Language specifications
Formal language
Regular expressions
Context-free grammars

3. Syntax Analysis
Scanning
Deterministic finite automaton
Generating a finite automaton
Scanner code
Parsing

Programming Language Syntax 27 / 48

 Syntax Analysis Scanning

Scanning

Scanner is responsible for

tokenizing source;
removing comments;
dealing with pragmas/directives (i.e., significant
comments);
saving text of identifiers, numbers, strings;
saving source locations (file, line, column) for error
messages.

Programming Language Syntax 28 / 48

 Syntax Analysis Scanning

Scanning: Example

Scan for id and num:

Read the characters in the source program one at a time
with look-ahead
If it is a letter or an underscore, we keep reading letters and
digits and maybe underscores until we can’t anymore
then we check to see if it is a reserved word
If it is a positive digit, we keep reading until we find a
non-digit

Programming Language Syntax 29 / 48

 Syntax Analysis Scanning

Scanning: Example

Scan for id and num:

Read the characters in the source program one at a time
with look-ahead
If it is a letter or an underscore, we keep reading letters and
digits and maybe underscores until we can’t anymore
then we check to see if it is a reserved word
If it is a positive digit, we keep reading until we find a
non-digit

Programming Language Syntax 29 / 48

 Syntax Analysis Scanning

Scanning: Example

Scan for id and num:

Read the characters in the source program one at a time
with look-ahead
If it is a letter or an underscore, we keep reading letters and
digits and maybe underscores until we can’t anymore
then we check to see if it is a reserved word
If it is a positive digit, we keep reading until we find a
non-digit

Programming Language Syntax 29 / 48

 Syntax Analysis Scanning

Scanning: Example

Scan for id and num:

Read the characters in the source program one at a time
with look-ahead
If it is a letter or an underscore, we keep reading letters and
digits and maybe underscores until we can’t anymore
then we check to see if it is a reserved word
If it is a positive digit, we keep reading until we find a
non-digit

Programming Language Syntax 29 / 48

 Syntax Analysis Scanning

Scanning: Example

Scan for id and num:

Read the characters in the source program one at a time
with look-ahead
If it is a letter or an underscore, we keep reading letters and
digits and maybe underscores until we can’t anymore
then we check to see if it is a reserved word
If it is a positive digit, we keep reading until we find a
non-digit

Programming Language Syntax 29 / 48

 Syntax Analysis Scanning

Scanning: Another example

Tokens
assign → :=
plus → +
minus → -
times → *
div → /
lparen → (
rparen → )
id → letter(letter | digit)∗
except for read and write
number → digit digit∗ | digit∗ ( . digit | digit . ) digit∗
comment → /* (non-* | * non-/)∗ *+ /
| // (non-newline)∗ newline

Programming Language Syntax 30 / 48

 Syntax Analysis Scanning

Scanner: pseudo-code

Programming Language Syntax 31 / 48

 Syntax Analysis Scanning

Scanning: finite automaton

Programming Language Syntax 32 / 48

 Syntax Analysis Scanning

Deterministic finite automaton (DFA)

A machine that accepts the language

We run the machine over and over to get one token after
another
Longest matching prefix rule (nearly universal):
Always take the longest possible token from the input
Example: 3.14159 is a real const and never 3, ., and 14159
Regular expressions "generate" a regular language; DFAs
"recognize" it

Programming Language Syntax 33 / 48

 Syntax Analysis Scanning

Deterministic finite automata : Formal definition

A DFA is a 5-tuple A = (S, Σ, δ, s0 , F ), where

S is a finite set of states, S 6= ∅
Σ 6= ∅ is a finite set of input symbols
s0 ∈ S is a start state
F ⊆ S is a set of final states
δ : S × Σ → S is a transition function that takes as
arguments a state and an input symbol and returns a state.
δ(p, a) = q : the DFA is in the state p, given the input symbol
a, it enters the state q.
δ is usually represented by a transition table.

Programming Language Syntax 34 / 48

 Syntax Analysis Scanning

Representation of DFA

Transition diagram
Each state is a node. Start state is marked by an arrow into
it, each accepting state (final state) is marked by a double
circle.
For each state p ∈ S and each input symbol a, if δ(p, a) = q
then the transition diagram has an arc from p to q, labeled
a.

1 1
0
s1 s2
0
Programming Language Syntax 35 / 48
 Syntax Analysis Scanning

Generating a finite automaton

DFAs can be generated automatically from a set of regular

expressions
Section 2.2.1, pages 56-61 (Scott textbook)
Convert a regular expression to a NFA (non-deterministic
finite automaton)
Base case: Transition diagram of {a}, {}, ∅?
Operations: union, concatenation, Kleene *
Convert a NFA to a DFA
Minimizing the DFA

Programming Language Syntax 36 / 48

 Syntax Analysis Scanning

Generating a finite automaton

DFAs can be generated automatically from a set of regular

expressions
Section 2.2.1, pages 56-61 (Scott textbook)
Convert a regular expression to a NFA (non-deterministic
finite automaton)
Base case: Transition diagram of {a}, {}, ∅?
Operations: union, concatenation, Kleene *
Convert a NFA to a DFA
Minimizing the DFA

Programming Language Syntax 36 / 48

 Syntax Analysis Scanning

Generating a finite automaton

DFAs can be generated automatically from a set of regular

expressions
Section 2.2.1, pages 56-61 (Scott textbook)
Convert a regular expression to a NFA (non-deterministic
finite automaton)
Base case: Transition diagram of {a}, {}, ∅?
Operations: union, concatenation, Kleene *
Convert a NFA to a DFA
Minimizing the DFA

Programming Language Syntax 36 / 48

 Syntax Analysis Scanning

Generating a finite automaton

DFAs can be generated automatically from a set of regular

expressions
Section 2.2.1, pages 56-61 (Scott textbook)
Convert a regular expression to a NFA (non-deterministic
finite automaton)
Base case: Transition diagram of {a}, {}, ∅?
Operations: union, concatenation, Kleene *
Convert a NFA to a DFA
Minimizing the DFA

Programming Language Syntax 36 / 48

 Syntax Analysis Scanning

From a regular expression to an NFA

Construction of NFA equivalent to an regular expression

Programming Language Syntax 37 / 48

 Syntax Analysis Scanning

From a regular expression to an NFA (cont.)

Each step of subconstruction needs to preserve 3 invariants

No transitions into the initial state
A single final state
No transitions out of the final state

Programming Language Syntax 38 / 48

 Syntax Analysis Scanning

From a regular expression to an NFA: Example

NFA equivalent to d ∗ ( . d | d . ) d ∗

Programming Language Syntax 39 / 48

 Syntax Analysis Scanning

From an NFA to a DFA

Implementation of NFA: explore all possible transitions

concurrently or via backtracking
⇒ complex and time-consuming
Transform the NFA into an equivalent DFA
Each state of the DFA is a set of states that the NFA might
reached on the same input

Programming Language Syntax 40 / 48

 Syntax Analysis Scanning

From an NFA to a DFA: Example

Programming Language Syntax 41 / 48

 Syntax Analysis Scanning

Minimizing the DFA

Reduce the space complexity

P ← {F , S\F }
repeat
done ← true
for Q ∈ P
for si , sj ∈ Q, si 6= sj
for a ∈ Σ
if δ(si , a) 6≡P δ(sj , a)
done ← false
Refine Q based on a
until done;

Programming Language Syntax 42 / 48

 Syntax Analysis Scanning

Minimizing the DFA: Example

Programming Language Syntax 43 / 48

 Syntax Analysis Scanning

Three ways to build scanners

Ad-hoc scanners: create manually code in some

implementation language (slide 31). This generally yields
the fastest, most compact code by doing lots of
special-purpose things
Writing a pure DFA as a set of nested case statements
(Section 2.2.2, pages 61-65, Scott’s textbook)
Table-driven DFA (Section 2.2.3, pages 65-67, Scott’s
textbook) - method used in the tool lex (or flex)

Programming Language Syntax 44 / 48

 Syntax Analysis Scanning

Three ways to build scanners

Ad-hoc scanners: create manually code in some

implementation language (slide 31). This generally yields
the fastest, most compact code by doing lots of
special-purpose things
Writing a pure DFA as a set of nested case statements
(Section 2.2.2, pages 61-65, Scott’s textbook)
Table-driven DFA (Section 2.2.3, pages 65-67, Scott’s
textbook) - method used in the tool lex (or flex)

Programming Language Syntax 44 / 48

 Syntax Analysis Scanning

Three ways to build scanners

Ad-hoc scanners: create manually code in some

implementation language (slide 31). This generally yields
the fastest, most compact code by doing lots of
special-purpose things
Writing a pure DFA as a set of nested case statements
(Section 2.2.2, pages 61-65, Scott’s textbook)
Table-driven DFA (Section 2.2.3, pages 65-67, Scott’s
textbook) - method used in the tool lex (or flex)

Programming Language Syntax 44 / 48

 Syntax Analysis Scanning

Nested case statements

Programming Language Syntax 45 / 48

 Syntax Analysis Scanning

Table-driven Scanning

States are numbered as in slide 32 + two states—17 and 18—to "recognize" white space and comments. The

right-hand column represents token state. Numbers in the table indicate an entry for which the corresponding action

is move. Dashes appear where there is no way to extend the current token: if the corresponding entry in token

column is nonempty, then action is recognize; otherwise, action is error.

Programming Language Syntax 46 / 48
 Syntax Analysis Scanning

Longest-possible tokens
Longest-possible tokens means you return only when the
next character can’t be used to continue the current token
the next character will generally need to be saved for the
next token
In some cases, you may need to peek at more than one
character of look-ahead in order to know whether to
proceed
For example, in Pascal, when you have a 3 and you see a
dot: do you proceed (3.14) or stop (3..5)?
In messier cases, you may not be able to get by with any
fixed amount of look-ahead
For example, in Fortran
DO 5 I = 1,25 loop
DO 5 I = 1.25 assignment
Here, we need to remember we were in a potentially final
state, and save enough information that we can back up to
it, if we get stuck later
Programming Language Syntax 47 / 48
 Syntax Analysis Parsing

Parsing

Terminology:
context-free grammar (CFG)
symbols
terminals (tokens)
non-terminals
production
derivations (left-most and right-most - canonical)
parse trees
sentential form: any string derived from the start symbol

to be continued ...

Programming Language Syntax 48 / 48