lec3.key
CS 314 Principles of Programming Languages
Prof. Zheng Zhang
Rutgers University
Lecture 3: Syntax Analysis (Scanning)
September 12, 2018
Class Information
Homework 1
• Due 9/18 11:55pm EST.
• Only accepted in pdf format.
• No late submission will be accepted.
2
TA office hours announced
• See Sakai course page
Review: Formalisms for Lexical and Syntactic Analysis
3
Two issues in Formal Languages:
• Language Specification → formalism to describe what a valid
program (word/sentence) looks like.
• Language Recognition → formalism to describe a machine and an
algorithm that can verify that a program is valid or not.
We use regular expression to specify tokens (words)
A Formal Definition
Regular Expressions (RE) over an Alphabet Σ
If x = a ∈ Σ, then x is an RE denoting the set { a }
or, the language L = { a }
Assuming x and y are both REs then
1. xy is an RE denoting L(x)L(y) = { pq | p ∈ L(x) and q ∈ L(y) }
2. x | y is an RE denoting L(x) ∪ L(y)
3. x* is an RE denoting
L(x)* = ∪0 ≤ k < ∞ L(x)k (Kleene Closure)
Set of all strings that are zero or more concatenations of x
4. x+ is an RE denoting
L(x)+ = ∪1 ≤ k < ∞ L(x)k (Positive Closure)
Set of all strings that are one or more concatenations of x
4
ε is an RE denoting the empty set
Review: Regular Expressions
5
RE p Language L(p)
x | y L(x) ∪ L(y)
xy {RS | R ∈ L(x), S ∈ L(y)}
x+ L(x) ∪ L(xx) ∪ L(xxx) ∪…
x* (x* = x+ | ϵ) {ϵ} ∪ L(x) ∪ L(xx) ∪...
(s) L(s)
a {a}
ϵ {ϵ}
A syntax (notation) to specify regular languages.
The symbols underlined
denotes a regular
expression, i.e., x
The symbols in bold-
face denotes a letter
from the alphabet, i.e., a
Review: Formalisms for Lexical and Syntactic Analysis
6
Two issues in Formal Languages:
• Language Specification → formalism to describe what a valid
program (word/sentence) looks like.
• Language Recognition → formalism to describe a machine and an
algorithm that can verify that a program is valid or not.
We use finite state automata to recognize regular language
Finite State Automata
7
A Finite-State Automaton is a quadruple: < S, s, F, T >
• S is a set of states, e.g., {S0, S1, S2, S3}
• s is the start state, e.g., S0
• F is a set of final states, e.g., {S3}
• T is a set of labeled transitions, of the form (state, input) → state
[i.e., S × Σ → S]
S2
S1
S3
0
1
0
1
S0
Recognizers for Regular Expressions
8
Integer Constant
S1FSA: S0
digit
digit
Let letter stand for A | B | C | . . . | Z
Let digit stand for 0 | 1 | 2 | . . . | 9
Regular Expression: digit+
From RE to Scanner
9
Classic approach is a three-step method:
1. Build automata for each piece of the RE using a template.
Multiple automata can be pasted using ε-transition.
This construction is called “Thompson’s construction”
2. Convert the newly built automaton into a deterministic automaton.
This construction is called the “subset construction”
3. Given the deterministic automaton, minimize the number of states.
Minimization is a space optimization.
Non-deterministic Finite Automaton (NFA)
10
• NFA might have transitions on ε
• Non-deterministic choice: multiple transition from the same sate
on the same symbol
Deterministic finite automaton (DFA) has no
ε-transitions and all choices are single-valued.
S2
Thompson’s Construction
11
• From each RE symbol and operator, we have a template
• Build them, in precedence order, and join them with ε-transition
S1
a
NFA for a
S2
Thompson’s Construction
12
• From each RE symbol and operator, we have a template
• Build them, in precedence order, and join them with ε-transition
S1 S0 S1 S2 S3
a x y
NFA for a NFA for xy
S2
Thompson’s Construction
13
• From each RE symbol and operator, we have a template
• Build them, in precedence order, and join them with ε-transition
S1 S0 S1 S2 S3
a x yϵ
NFA for a NFA for xy
S2
Thompson’s Construction
14
• From each RE symbol and operator, we have a template
• Build them, in precedence order, and join them with ε-transition
S1 S0 S1 S2
S1 S2
S3 S4
S3
a x y
x
y
ϵ
NFA for a NFA for xy
NFA for x|y
S2
Thompson’s Construction
15
• From each RE symbol and operator, we have a template
• Build them, in precedence order, and join them with ε-transition
S1 S0 S1 S2
S1 S2
S3 S4
S5
S3
S0
a x y
x
y
ϵ
ϵϵ
ϵ ϵ
NFA for a NFA for xy
NFA for x|y
S2
Thompson’s Construction
16
• From each RE symbol and operator, we have a template
• Build them, in precedence order, and join them with ε-transition
S1 S0 S1 S2
S1 S2
S3 S4
S5
S3
S0 S1 S2
a x y
x
y x
ϵ
ϵϵ
ϵ ϵ
NFA for a NFA for xy
NFA for x|y NFA for x*
S2
Thompson’s Construction
17
• From each RE symbol and operator, we have a template
• Build them, in precedence order, and join them with ε-transition
S1 S0 S1 S2
S1 S2
S3 S4
S5
S3
S0 S1 S2
a x y
x
y x
ϵ
ϵϵ
ϵ ϵ
NFA for a NFA for xy
NFA for x|y NFA for x*
ϵ
S2
Thompson’s Construction
18
• From each RE symbol and operator, we have a template
• Build them, in precedence order, and join them with ε-transition
S1 S0 S1 S2
S1 S2
S3 S4
S5
S3
S3S0 S0 S1 S2
a x y
x
y x
ϵ
ϵϵ
ϵ ϵ
ϵ ϵ
NFA for a NFA for xy
NFA for x|y NFA for x*
ϵ
ϵ
Thompson’s Construction
19
• Let’s build an NFA for a (b|c)*
1. a, b, & c
2. b | c
3. ( b| c )*
4. a ( b| c )*
Thompson’s Construction
20
• Let’s build an NFA for a (b|c)*
a
b
c
1. a, b, & c
2. b | c
3. ( b| c )*
4. a ( b| c )*
Thompson’s Construction
21
• Let’s build an NFA for a (b|c)*
a
b
c
ϵ
ϵ
ϵ
ϵ
1. a, b, & c
2. b | c
3. ( b| c )*
4. a ( b| c )*
Thompson’s Construction
22
• Let’s build an NFA for a (b|c)*
a
b
c
ϵ ϵ
ϵ
ϵ
ϵ
1. a, b, & c
2. b | c
3. ( b| c )*
4. a ( b| c )*
Thompson’s Construction
23
• Let’s build an NFA for a (b|c)*
a
b
c
ϵ ϵ
ϵ
ϵ
ϵ
1. a, b, & c
2. b | c
3. ( b| c )*
4. a ( b| c )* ϵ
Thompson’s Construction
24
• Let’s build an NFA for a (b|c)*
a
b
c
ϵ ϵ
ϵ
ϵ
ϵ
ϵ
1. a, b, & c
2. b | c
3. ( b| c )*
4. a ( b| c )* ϵ
ϵ
Thompson’s Construction
25
• Let’s build an NFA for a (b|c)*
a
b
c
ϵ ϵ
ϵ
ϵ
ϵ
ϵ
1. a, b, & c
2. b | c
3. ( b| c )*
4. a ( b| c )* ϵ
ϵ
Thompson’s Construction
26
• Let’s build an NFA for a (b|c)*
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
1. a, b, & c
2. b | c
3. ( b| c )*
4. a ( b| c )* ϵ
ϵ
Thompson’s Construction
27
• Let’s build an NFA for a (b|c)*
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
ϵ
ϵ
Thompson’s Construction
28
• Let’s build an NFA for a (b|c)*
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
ϵ
ϵ
Final states are double circled
From RE to Scanner
29
Classic approach is a three-step method:
1. Build automata for each piece of the RE using a template.
Multiple automata can be pasted using ε-transition.
This construction is called “Thompson’s construction”
2. Convert the newly built automaton into a deterministic automaton.
This construction is called the “subset construction”
3. Given the deterministic automaton, minimize the number of states.
Minimization is a space optimization.
?
Subset Construction
30
• Build a deterministic automaton that simulates the non-deterministic one
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
ϵ
ϵ
D0 D1
D2
D3
a
b
b
bc
c
NFA DFA
Subset Construction
31
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
ϵ
ϵ
D0
Original Automaton
New Automaton
Subset Construction
32
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
ϵ
ϵ
D0 D1
a
Original Automaton
New Automaton
Subset Construction
33
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
ϵ
ϵ
D0 D1
a
Original Automaton
New Automaton
Subset Construction
34
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2
ϵ
ϵ
D0 D1
D2
a
b
Original Automaton
New Automaton
Subset Construction
35
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2
ϵ
ϵ
D0 D1
D2
a
b
Original Automaton
New Automaton
Subset Construction
36
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
ϵ
ϵ
D0 D1
D2
a
b
Original Automaton
New Automaton
Subset Construction
37
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
ϵ
ϵ
D0 D1
D2
a
b
b
Original Automaton
New Automaton
Subset Construction
38
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
D3
ϵ
ϵ
D0 D1
D2
D3
a
b
b
Original Automaton
New Automaton
c
Subset Construction
39
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
D3
ϵ
ϵ
D0 D1
D2
D3
a
b
b
Original Automaton
New Automaton
c
Subset Construction
40
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
D3 S7, S8, S3, S9, S4, S6
ϵ
ϵ
D0 D1
D2
D3
a
b
b
Original Automaton
New Automaton
c
Subset Construction
41
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
D3 S7, S8, S3, S9, S4, S6
ϵ
ϵ
D0 D1
D2
D3
a
b
b
c
Original Automaton
New Automaton
c
Subset Construction
42
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
D3 S7, S8, S3, S9, S4, S6
ϵ
ϵ
D0 D1
D2
D3
a
b
b
c
c
Original Automaton
New Automaton
D0 D1
D2
D3
a
b
b
bc
c
Subset Construction
43
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
D3 S7, S8, S3, S9, S4, S6
ϵ
ϵ
Original Automaton
New Automaton
Subset Construction
44
• Each state in the new one represents a set of states in the original one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
DFA NFA
D0 S0
D1 S1, S2, S3, S9, S4, S6
D2 S5, S8, S3, S9, S4, S6
D3 S7, S8, S3, S9, S4, S6
ϵ
ϵ
D0 D1
D2
D3
a
b
b
bc
c
Original Automaton
New Automaton
From RE to Scanner
45
Classic approach is a three-step method:
1. Build automata for each piece of the RE using a template.
Multiple automata can be pasted using ε-transition.
This construction is called “Thompson’s construction”
2. Convert the newly built automaton into a deterministic automaton.
This construction is called the “subset construction”
3. Given the deterministic automaton, minimize the number of states.
Minimization is a space optimization.
DFA Minimization
46
• Discover states that are equivalent in their contexts and replace
multiple states with a single one
S1 S2 S3
S4 S5
S6 S7
S8 S9S0
a
b
c
ϵ ϵ ϵ
ϵ
ϵ
ϵ
ϵ
ϵ
ϵ
D0 D1
D2
D3
a
b
b
bc
c
Original Automaton
New Automaton Minimal Automaton
M0 M1
a
b | c
Read Textbook: Scott,
Chapter 2.2.1 for the DFA
minimization algorithm.
Minimal DFA Original DFA
M0 D0
M1 D1, D2, D3
Review: Scanner Implementation
47
An FSA accepts/recognizes an input string iff there is some path from
start state to a final state such that the labels on the path are that string.
Lack of entry in the table (or no arc for a given character) indicates an
error—reject.
Transitions can be represented using a transition table:
0 1
S0 S1 S2
S1 S3 –
S2 – S3
State Input
S2
S1
S3
0
1
0
1
S0
Error
Review: Code for the scanner
48
char ← next_char();
state ← S0;
done ← false;
while( not done ) {
class ← char_class[char];
state ← next_state[class,state];
switch(state) {
case S1:
/* building an id */
token_value ← token_value + char;
char ← next_char();
if (char == DELIMITER)
done = true;
break;
case S2: /* error state */
case S3: /* error state */
token type = error;
done = true;
break;
}
}
return token_type;
class S0 S1 S2 S3
letter S1 S1 — —
digit S3 S1 — —
other S3 S2 — —
S0 S1 S2
S3 error
digit
other letter/digit
letter other
error
Implementation:
Compiler Front End
49
Source
Code
Tokens
Scanner Parser IR
Compiler Front End
Errors
Syntax & semantic analyzer, IR code generator
Front End Responsibilities:
• Recognize legal programs
• Report errors
• Produce intermediate representation
Compiler Front End
50
Source
Code
Tokens
Scanner Parser IR
Compiler Front End
Errors
Syntax & semantic analyzer, IR code generator
Front End Responsibilities:
• Recognize legal programs
• Report errors
• Produce intermediate representation
Syntax Analysis ( Scott, Chapter 2.1, 2.3)
51
if id <= id then
:=id
parser
Token Sequence:
if then
Parse Tree:
Context Free Grammars (CFGs)
• Another formalism to for describing languages
• A CFG G = < T, N, P, S >:
1. A set T of terminal symbols (tokens).
2. A set N of nonterminal symbols.
3. A set P production (rewrite) rules.
4. A special start symbol S.
• The language L(G) is the set of sentences of terminal symbols in T* that
can be derived from the start symbol S:
L(G) = {w ∈ T* | S ⇒* w}
52
An Example of a Partial Context Free Grammar
53
if
Context Free Grammars (CFGs)
• A formalism to for describing languages
• A CFG G = < T, N, P, S >:
1. A set T of terminal symbols (tokens).
2. A set N of nonterminal symbols.
3. A set P production (rewrite) rules.
4. A special start symbol S.
• The language L(G) is the set of sentences of terminal symbols in T* that
can be derived from the start symbol S:
L(G) = {w ∈ T* | S ⇒* w}
54
CFGs are rewrite systems with restrictions on the form of rewrite
(production) rules that can be used.
A Partial Context Free Grammar
55
…
…
CFGs are rewrite systems with restrictions on the form of
rewrite (production) rules that can be used. The left hand side
of a production rule can only be one non-terminal symbol.
Rule 1 $1 ⇒ 1&
Rule 2 $0 ⇒ 0$
Rule 3 &1 ⇒ 1$
Rule 4 &0 ⇒ 0&
Rule 5 $# ⇒ →A
Rule 6 &# ⇒ →B
Context free grammar Not a context free grammar
56
Terminal Symbol: Symbol-in-Boldface
Non-Terminal Symbol: Symbol-in-Angle-Brackets
Production Rule: Non-Terminal ::= Sequence of Symbols
or
Non-Terminal ::= Sequence | Sequence |
…
Elements of BNF Syntax
Example:
…
How a BNF Grammar Describes a Language
A sentence is a sequence of terminal symbols (tokens).
The language L(G) of a BNF grammar G is the set of sentences
generated using the grammar:
• Begin with start symbol.
• Iteratively replace non-terminals with terminals according to
the rules (rewrite system).
This replacing process is called a derivation (⇒).
Zero or multiple derivation steps are written as ⇒*.
Formally, L(G) = {w ∈ T* | S ⇒* w}
57
58
Is X2 := 0 ∈ L(G), in another word, can X2 := 0 be derived in G?
Derivation in a Grammar (G)
Start Symbol :
In which order to apply the rules?
Typically, there are three options:
leftmost (⇒L), rightmost (⇒R), any (⇒)
X2 := 0
?
Grammar G:
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
…
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
59
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
60
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
61
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
62
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
63
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
64
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
65
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
66
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
67
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
68
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
rightmost derivation rule
applied
X2 := 0
69
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
leftmost derivation rule
applied
X
X2 := 0
70
Derivation in a Grammar (G)
Is X2 := 0 ∈ L(G), i.e., can X2 := 0 be derived in G?
rightmost derivation rule
applied
X2 := 0
1. < letter > ::= A | B | C | … | Z
2. < digit > ::= 0 | 1 | 2 | … | 9
3. < identifier > ::= < letter > |
4. < identifier > < letter > |
5. < identifier > < digit >
6. < stmt > ::= < identifier > := 0
Next Lecture
71
• Read Scott, Chapter 2.2 – 2.5 (skip 2.3.3 bottom-up Parsing)
Things to do: