2 Syntax
For snoring?!
Hell, that’s nothin’.
I once shot a man for ending a sentence in a preposition.
CS 381 • Syntax
1
Sharing Thoughts
doggy
dog
Wauwau
chien
Hund
CS 381 • Syntax
2
Syntax:Agreed-upon representation for semantic concepts
2 Syntax
CS 381 • Syntax
3
Grammars & Derivation
Syntax Tree
Abstract vs. Concrete Syntax
Representing Grammars by Haskell Data Types
Well-Structured Sentences
The syntax of a language defines the set of all sentences. How can syntax be defined?
CS 381 • Syntax
4
Enumerate all sentences
Define rules to construct
valid sentences
Grammar
Grammar
A grammar is given by a set of productions (or rules).
A ::= BC… LHS
RHS
A, B, C … are symbols (= strings)
CS 381 • Syntax
5
How are sentences generated by rules?
Start with one symbol and repeatedly expand symbols by RHSs of rules.
A grammar is called context free if all LHSs contain only 1 symbol.
Example Grammar
sentence ::= noun verb noun (R1) noun ::= dogs (R2) noun ::= teeth (R3) verb ::= have (R4)
CS 381 • Syntax
6
nonterminal symbols
(do appear on the LHS of some rule, i.e.,
can be expanded)
terminal symbols
(do not appear on the LHS of any rule, i.e.
cannot be expanded)
Derivation sentence ::= noun verb noun (R1)
noun ::= dogs noun ::= teeth verb ::= have
sentence
noun verb noun dogs verb noun dogs have noun dogs have teeth
(R2) (R3) (R4)
apply rule (R1) apply rule (R2) apply rule (R4) apply rule (R3)
Repeated rule application (i.e. replacing nonterminal by RHS) yields sentences.
CS 381 • Syntax
7
CS 381 • Syntax
8
The order of rule application is not fixed.
sentence
noun verb noun (R1) noun have noun (R4) noun have teeth (R3) dogs have teeth (R2)
sentence ::= noun verb
noun (R1) (R2) (R3) (R4)
(R1) (R3) (R2) (R4)
Derivation Order
noun noun verb
::= dogs ::= teeth ::= have
sentence
noun verb noun noun verb teeth dogs verb teeth dogs have teeth
(1) Extend the “sentence” grammar to allow the creation of “and” sentences
sentence ::= noun verb noun noun ::= dogs
noun ::= teeth
verb ::= have
Exercises
CS 381 • Syntax
9
(2) Write a grammar for binary numbers
(3) Derive the sentence 101
(4) Write a grammar for boolean expression built from the constants T and F and the operation not
(5) Derive the sentence not not F
Exercises
(1) Extend the “sentence” grammar to allow the creation of “and”
sentences
sentence ::= noun verb noun noun ::= dogs
noun ::= teeth
verb ::= have
(2) Write a grammar for binary numbers
digit ::= 0 (R1) digit ::= 1 (R2) bin ::= digit (R3) bin ::= digit bin (R4)
bin ::= 0 bin (R1) bin ::= 1 bin (R2) bin ::=ε (R3)
sentence ::= noun verb noun sentence ::= sentence and sentence …
CS 381 • Syntax
“empty RHS”
10
Exercises (3) Derive the sentence 101
CS 381 • Syntax
11
digit ::= 0
digit ::= 1
bin ::= digit (R3) bin ::= digit bin (R4)
bin
digit bin
digit digit bin
digit digit digit
digit digit 1
digit 0 1
101 (R2)
(R1) bin ::= 0 bin (R1) (R2) bin ::= 1 bin (R2) bin ::=ε (R3)
(R4) bin
(R4) 1 bin (R2) (R3) 1 0 bin (R1) (R2) 101bin (R2)
(R1)
101 (R3)
(4) Write a grammar for boolean expression built from the constants T and F and the operation not
(5) Derive the sentence not not F
bool
not bool (R3) not not bool (R3) not not F (R2)
bool ::= T (R1) bool ::= F (R2) bool ::= not bool (R3)
Exercises
CS 381 • Syntax
12
CS 381 • Syntax
13
Why Grammar Matters …
Video clip
WARNING: The video contains R-rated language!
2 Syntax
CS 381 • Syntax
14
Grammars & Derivation
Syntax Tree
Abstract vs. Concrete Syntax
Representing Grammars by Haskell Data Types
Syntax Tree
A syntax tree is a structure to represent derivations.
Derivation is a process of producing a sentence according to the rules of a grammar.
sentence
noun verb noun dogs verb noun dogs have noun dogs have teeth
noun
dogs
sentence
verb noun
have teeth
CS 381 • Syntax
15
Observations About Syntax Trees
(1) Leaves contain terminal symbols
(2) Internal nodes contain nonterminal symbols
(3) Nonterminal in the root node indicates the type of the syntax tree
sentence noun verb noun
dogs
(4) Derivation order is not represented, which is a Good Thing, because the order is not important
CS 381 • Syntax
16
have teeth
Alternative Representation
(1) Leaves contain terminal symbols (2) Internal nodes contain
nonterminal symbols
sentence noun verb noun
dogs
sentence ::= noun verb noun (R1) sentence ::= sentence and sentence (R2) noun ::= dogs (R3) noun ::= teeth (R4) verb ::= have (R5)
(1) Leaves contain terminal symbols (2) Internal nodes contain rule names
R1
R3 R5 R4
CS 381 • Syntax
have teeth
dogs
have teeth
17
Exercises
(1) Draw the syntax tree for the sentence 101
(2) Draw the syntax tree for the sentence not not F
(3) Draw all syntax trees of type noun
(4) How many sentences/trees of type stmt can be constructed with the following grammar?
cond ::= T
stmt ::= while cond do stmt
(5) How many with the following grammar?
cond ::= T
stmt ::= while cond do stmt stmt ::= noop
bin ::= 0 bin bin ::= 1 bin bin ::=ε
bool ::= T
bool ::= F
bool ::= not bool
(R1) (R2) (R3)
(R1) (R2) (R3)
CS 381 • Syntax
18
Exercises (1) Draw the syntax tree for the sentence 101
digit digit bin bin
::= 0 (R1) ::= 1 (R2) ::= digit (R3) ::= digit bin (R4)
R4
R2
bin 1 R1 R3
11
bin
bin
0
1
(R1) (R2) (R3)
R2
R1
bin 1 digit
R4
bin ::= 0 bin bin ::= 1 bin bin ::=ε
1
bin
0 R2
bin
1
digit
bin
0 digit 0 R2
ε
1
R3
CS 381 • Syntax
ε
19
Exercises
(2) Draw the syntax tree for the sentence not not F
not
bool bool
R3
not
not
R3
R2
F
bool ::= T (R1) bool ::= F (R2) bool ::= not bool (R3)
not
F
bool
CS 381 • Syntax
20
(3) Draw all syntax trees of type noun
Exercises sentence ::= noun verb noun
noun ::= dogs noun ::= teeth verb ::= have
noun noun
teeth dogs
(4) How many sentences/trees of type stmt can be constructed with the following grammar?
cond ::= T
stmt ::= while cond do stmt
zero
(since stmt has no base case)
(5) How many with the following grammar?
CS 381 • Syntax
21
cond ::= T
stmt ::= while cond do stmt stmt ::= noop
infinitely many
(since stmt can be expanded arbitrarily often)
Group Rules by LHS
sentence ::= noun verb noun (R1) | sentence and sentence (R2)
noun ::= dogs|teeth (R3,R4) verb ::= have (R5)
⇒ Grammar lists for each nonterminal all possible ways to construct a sentence of that kind.
Grammars can be defined in a modular fashion.
CS 381 • Syntax
22
2 Syntax
Grammars & Derivation
Syntax Tree
Abstract vs. Concrete Syntax
Representing Grammars by Haskell Data Types
CS 381 • Syntax
23
Concrete vs. Abstract Syntax
Grammar
Set of sentences/strings
{dogs have teeth, dogs have dogs, …}
CS 381 • Syntax
Set of syntax trees
R1
R1
R3 R5 R4
dogs have teeth
R3 R5 R3 … dogs have dogs
24
Abstract syntax
Concrete syntax
Grammar
sentence ::= noun verb noun (R1) | sentence and sentence (R2)
noun ::= dogs|teeth (R3,R4)
Set of syntax trees
Abstract Syntax
verb
::= have (R5) terminal symbols uniquely identify rules
(in this grammar)
R1
R3 R5 R4
dogs have teeth
R1
dogs have teeth
…
R1
R3 R5 R3
dogs have dogs
R1
dogs have dogs
CS 381 • Syntax
25
Abstract syntax
Denoting Syntax Trees
sentence ::= noun verb noun (R1) | sentence and sentence (R2)
noun ::= dogs|teeth (R3,R4) verb ::= have (R5)
Use rule names as constructors: R1 dogs have teeth
Simple linear/textual representation: Apply rule names to argument trees
R Tree-1 … Tree-k
R2 (R1 dogs have teeth) (R1 dogs have dogs)
CS 381 • Syntax
Note: Parentheses are only used for linear notation of trees; they are not part of the abstract syntax
26
2 Syntax
Grammars & Derivation
Syntax Tree
Abstract vs. Concrete Syntax
Representing Grammars by Haskell Data Types
CS 381 • Syntax
27
Why Grammars in Haskell?
CS 381 • Syntax
28
“What I cannot create, I do not understand.”
Richard Feynman
Haskell Representation of Syntax Trees
Define a data type for each nonterminal Define a constructor for each rule
data Sentence = Phrase Noun Verb Noun
| And Sentence Sentence
data Noun = Dogs | Teeth data Verb = Have
sentence ::= noun verb noun
| sentence and sentence
noun ::= dogs | teeth verb ::= have
A syntax tree is represented by a Haskell value (built by data constructors)
To construct a syntax tree, apply a constructor to subtrees
CS 381 • Syntax
29
noun verb
| sentence and sentence (R2)
::= dogs|teeth (R3,R4)
Haskell Representation of Syntax Trees
sentence ::= noun verb noun (R1)
data Sentence = R1 Noun Verb Noun
| R2 Sentence Sentence
data Noun = Dogs | Teeth data Verb = Have
::= have
dogs have teeth
R2
R1 R1
(R5)
R1
R1 Dogs Have Teeth
dogs have teeth dogs have dogs
CS 381 • Syntax
30
R2 (R1 Dogs Have Teeth)
(R1 Dogs Have Dogs)
noun verb
| sentence and sentence (R2)
::= dogs|teeth (R3,R4)
Haskell Representation of Syntax Trees
sentence ::= noun verb noun (R1)
data Sentence = Phrase Noun Verb Noun
| And Sentence Sentence
data Noun = Dogs | Teeth data Verb = Have
::= have
dogs have teeth
R2
R1 R1
(R5)
R1
Phrase Dogs Have Teeth
dogs have teeth dogs have dogs
CS 381 • Syntax
31
And (Phrase Dogs Have Teeth)
(Phrase Dogs Have Dogs)
CS 381 • Syntax
32
Haskell Demo … SentSyn.hs
Exercises
(1) Define a Haskell data type for binary numbers
(2) Represent the sentence 101 using constructors
(3) Define a Haskell data type for boolean expression including constants T and F and the operation not
(4) Represent the sentence not (not F)
(5) What is the type of T ?
What is the type of Not T ? What is the type of Not ? What is the type of Not Not ?
digit ::= 0 (R1) digit ::= 1 (R2) bin ::= digit (R3) bin ::= digit bin (R4)
CS 381 • Syntax
33
More Exercises
(1) Define a Haskell data type for Peano-style natural numbers
(constructed by 0 and successor)
(Note: numbers cannot be constructors; you must use names such as Zero.)
(2) Represent the sentence 3 using constructors
(3) Extend the number data type by constructors for representing addition
and multiplication
(4) Represent the sentence 2*(3+1) using constructors
(5) Explain how the construction of syntactically incorrect sentences is
prevented by Haskell’s type system
(Hint:Try to build incorrect sentences)
CS 381 • Syntax
34
Abstract Grammar
Abstract grammar contains:
(1) exactly one unique terminal symbol in each rule (2) no redundant rules
Concrete grammar
cond ::= T | not cond | (cond) stmt ::= while cond { stmt }
| noop CS 381 • Syntax
Haskell Data Type =
Abstract grammar
data Cond = T | Not Cond data Stmt = While Cond Stmt
| Noop
35
Abstract Syntax Tree
Concrete grammar
cond ::= T | not cond | (cond) stmt ::= while cond { stmt }
| noop
while not(not(T)) {
while T { noop }
}
Haskell Data Type =
Abstract grammar
data Cond = T | Not Cond data Stmt = While Cond Stmt
| Noop
CS 381 • Syntax
36
Sentence
Abstract Syntax Tree
=
Value of Haskell Data Type
While (Not (Not T))
(While T Noop)
(1) Draw the syntax tree for the following sentence
while not(not(T)) {
while T { noop } }
cond ::= T | not (cond)
stmt ::= while cond { stmt }
| noop CS 381 • Syntax
37
Exercises
(1) Draw the syntax tree for the following sentence
while not(not(T)) {
whileT { noop }
cond ::= T | not (cond)
stmt ::= while cond { stmt }
| noop CS 381 • Syntax
Exercises
stmt
}
while
not ( not
cond { stmt } cond ) while cond { stmt }
(cond) T noop T
while not(not( T )){while T { noop} }
38
Exercises (2) Draw the following
abstract syntax tree
While (Not (Not T))
(While T Noop)
data Cond = T | Not Cond data Stmt = While Cond Stmt
| Noop
CS 381 • Syntax
39
Exercises (2) Draw the following
abstract syntax tree
While
Not
Not T
While
T Noop
data Cond = T | Not Cond data Stmt = While Cond Stmt
| Noop
CS 381 • Syntax
40
While (Not (Not T))
(While T Noop)
CS 381 • Syntax
41
From Concrete To Abstract Syntax stmt
X X condX
X X X
while
not ( ) while cond { stmt }
not
cond { stmt }
X
X
Not
Not T
While
T Noop
(cond)
T noop
while not(not( T )){while T { noop} }
T
While
While (Not (Not T))
(While T Noop)
Why Two Kinds of Syntaxes?
Abstract syntax: • more concise
• represents essential language structure • basis for analyses and transformations
Concrete syntax:
• more verbose and often better readable • extra keywords and symbols help parser
cond ::= T | not cond | (cond) stmt ::= while cond { stmt }
| noop
data Cond = T | Not Cond data Stmt = While Cond Stmt
| Noop
CS 381 • Syntax
42
Acceptable (Data) Types for Abstract Syntax
Acceptable (data) type:
• must represent all sentences of language,
(not more), not less
Names and order of arguments of constructors don’t matter
dataCond=Y|ZCond ✓ data Stmt = Loop Cond Stmt
|A
data Cond = T | Not Cond data Stmt = While Cond Stmt
| Noop
CS 381 • Syntax
43
CS 381 • Syntax
44
Acceptable (Data) Types for Abstract Syntax
Acceptable (data) type:
• may represent multiple productions with one constructor
data BExpr = T | F | Not BExpr
data BExpr = Const Bool | Not BExpr
✓
Acceptable (data) type: • may be able to
represent one sentence in different ways
data Ints = One Int | Add Int Ints Add 2 (Add 4 (One 5))
data Ints = One Int | Join Ints Ints Join (One 2) (Join (One 4) (One 5))
Join (Join (One 2) (One 4)) (One 5)
type Ints = [Int] can represent empty list ✗
Acceptable (Data) Types for Abstract Syntax
✓
[2,4,5]
CS 381 • Syntax
45
Exercises
(1) Define abstract syntax for the following grammar
con ::= 0|1
reg ::=A|B|C
op ::= MOV con TO reg
| MOV reg TO reg | INC reg BY con | INC reg BY reg
(2) Refactor grammar and abstract syntax by introducing a nonterminal to represent a con or a reg
(3) What are the elements of a Haskell data type definition? CS 381 • Syntax
46
Pretty Printing A pretty printer creates a string from a syntax tree.
A parser extracts a syntax tree from a string. CS 480
data Cond = T | Not Cond data Stmt = While Cond Stmt
| Noop
cond ::= T | not cond | (cond) stmt ::= while cond { stmt }
| noop
while not(not(T)) { while T { noop }
}
pretty printer parser
While (Not (Not T))
(While T Noop)
CS 381 • Syntax
47
CS 381 • Syntax
48
Haskell Demo …
SentSyn.hs SentPP.hs BoolSyn.hs BoolPP.hs
Exercise
(1) Define a pretty printer for the following abstract syntax
that produces output according to the following grammar
cond ::= T | not cond | (cond) stmt ::= while cond { stmt }
| noop
data Cond = T | Not Cond data Stmt = While Cond Stmt
| Noop
CS 381 • Syntax
49
CS 381 • Syntax
50
Haskell Demo … Stmt.hs
Grammar Rules for Lists A string is a sequence of zero or more characters
Concrete syntax
string ::= char string | ε char ::= a|b|c|…
aac
Using built-in Char and list types data Str = Seq [Char]
Abstract syntax
data Str = Seq Chr Str | Empty data Chr = A | B | C | …
Seq A (Seq A (Seq C Empty))
Using built-in String type type String = [Char]
CS 381 • Syntax
51
Seq [‘a’,’a’,’c’]
“aac”
[‘a’,’a’,’c’]
Grammar Rules for Lists (2) A number is a sequence of one or more digits
Concrete syntax
num ::= digit num | digit digit ::= 1|2|3|…
211
Using built-in Int and list types
Abstract syntax
data Num = S Digit Num | D Digit data Digit = One | Two | …
S Two (S One (D One))
CS 381 • Syntax
data Num = S [Int] S [2,1,1]
Strictly speaking, incorrect
Using built-in Int type type Num = Int
211
52
Grammar Rules for Lists (3)
A qualified adjective is a list of adverbs followed by an adjective
adv* ::= adv adv* | ε Concrete syntax
qadj ::= adv* adj
adv ::= really | frigging adj ::= awesome | …
really really frigging awesome
Abstract syntax
Q [“really”,”really”,”frigging”] “awesome”
data QAdj = Q [Adv] Adj type Adv = String
type Adj = String
CS 381 • Syntax
53
abbreviation
Representing Lists in Abstract Grammars
Zero or more A’s
As ::= AAs|ε B ::= … As …
As ::= AAs|A B ::= … As …
abbreviation
B ::= … A* …
abbreviation
One or more A’s
B ::= … A+ …
Abstract syntax
data B = Con … [A] … ✗
data B = Con … (A,[A]) …
54
CS 381 • Syntax
CS 381 • Syntax
55
Zoom Poll
Alternative abstract syntax
Data Types vs.Types
Type definitions just give names to type expressions, while Data definitions introduce constructors that build new objects
type Point = (Int,Int)
(3,5) :: Point
(3,5) :: (Int,Int)
data Point = Pt Int Int
Pt 3 5 :: Point
Pt 3 5 :: (Int,Int)
CS 381 • Syntax
more than one constructor is needed pretty printing is required representation might be hidden (ADT)
56
Design rule. Data definitions are used when:
• • •
Translating Grammars Into Data Types
(1) Represent each basic nonterminal by a built-in type (names, symbols, etc. by String, numbers by Int)
(2) For each other nonterminal, define a data type
(3) For each production, define a constructor
(4) Argument types of constructors are given by the production’s nonterminals
➋➊ ➋➊
exp ::= num | exp+exp | (exp) data Exp = N Int | Plus Exp Exp
CS 381 • Syntax
57
➌➌
stmt ::= while exp { stmt }
data Stmt = While Exp Stmt
| Noop ➍
| noop
➍
exp ::= num | exp+exp | (exp) stmt ::= while exp { stmt }
| noop
➡Each case of a data type must have a constructor! (Even if no terminal symbol exists in the concrete syntax.)
➡Argument types of constructors may be grouped into pairs
(or other type constructors).
Constructor is indispensable!
Note Carefully!
data Exp = N Int | Plus Exp Exp data Stmt = …
A perfectly valid alternative!
Plus (Exp,Exp)
type EPair = (Exp,Exp)
data Exp = …
| Plus EPair
| Times EPair
CS 381 • Syntax
58