Programming Language Syntax and Semantics
undefined
CSSE 304 Day 7
Simple Solution: Minimize-interval-list
Syntax and Semantics
Grammars and Derivations
s-lists
Follow the Grammar
Minimize-interval-list solution
B
i
g
-
O
r
u
n
n
i
n
g
t
i
m
e
f
o
r
t
h
i
s
p
r
o
c
e
d
u
r
e
?
Interlude
Always code as if the guy who ends up
maintaining your code will be a violent
psychopath who knows where you live.
Martin Golding
Two major parts of a programming language’s
definition
Syntax
Syntax
– what does a program in the given language look
– what does a program in the given language look
like?
like?
Semantics
Semantics
- what does that program mean?
- what does that program mean?
There should be an unambiguous translation from syntax
There should be an unambiguous translation from syntax
to semantics
to semantics
H
H
o
o
w
w
t
t
o
o
s
s
p
p
e
e
c
c
i
i
f
f
y
y
a
a
l
l
a
a
n
n
g
g
u
u
a
a
g
g
e
e
’
’
s
s
s
s
y
y
n
n
t
t
a
a
x
x
?
?
B
B
N
N
F
F
Semantics are harder to specify
Semantics are harder to specify
denotational, operational
denotational, operational
BNF: recursive syntax specification
Backus-Naur Form.
Backus-Naur Form.
Specify the syntax of a
Specify the syntax of a
language. a.k.a. context-free grammar (CFG)
language. a.k.a. context-free grammar (CFG)
E
E
x
x
a
a
m
m
p
p
l
l
e
e
:
:
N
N
o
o
n
n
t
t
e
e
r
r
m
m
i
i
n
n
a
a
l
l
s
s
:
:
<
<
e
e
x
x
p
p
>
>
<
<
t
t
e
e
r
r
m
m
>
>
<
<
f
f
a
a
c
c
t
t
o
o
r
r
>
>
<
<
n
n
u
u
m
m
b
b
e
e
r
r
>
>
<
<
d
d
i
i
g
g
i
i
t
t
>
>
T
T
e
e
r
r
m
m
i
i
n
n
a
a
l
l
s
s
:
:
+
+
*
*
)
)
(
(
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
P
P
r
r
o
o
d
d
u
u
c
c
t
t
i
i
o
o
n
n
s
s
:
:
<exp> ::= <exp> + <term> | <term>
<exp> ::= <exp> + <term> | <term>
<term> ::= <term> * <factor> | <factor>
<term> ::= <term> * <factor> | <factor>
<factor> ::= ( <exp> ) | <number>
<factor> ::= ( <exp> ) | <number>
<number> ::= <number> <digit> | <digit>
<number> ::= <number> <digit> | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Derive
Derive
1 * (2 + 34)
1 * (2 + 34)
by showing a derivation tree.
by showing a derivation tree.
G
r
a
m
m
a
r
T
h
e
l
a
n
g
u
a
g
e
o
f
t
h
i
s
g
r
a
m
m
a
r
i
s
t
h
e
s
e
t
o
f
a
l
l
s
t
r
i
n
g
s
o
f
t
e
r
m
i
n
a
l
s
t
h
a
t
c
a
n
b
e
d
e
r
i
v
e
d
f
r
o
m
t
h
e
s
t
a
r
t
s
y
m
b
o
l
.
3
+
2
i
s
i
n
t
h
e
l
a
n
g
u
a
g
e
;
2
*
+
7
i
s
n
o
t
<exp> ::= <exp> + <term> | <term>
<term> ::= <term> * <factor> | <factor>
<factor> ::= ( <exp> ) | <number>
<number> ::= <number> <digit> | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Derive
1 * (2 + 34)
by showing a derivation tree.
BNF: recursive syntax specification
Backus-Naur Form.
Backus-Naur Form.
Specify the syntax of a
Specify the syntax of a
language. a.k.a. context-free grammar (CFG)
language. a.k.a. context-free grammar (CFG)
E
E
x
x
a
a
m
m
p
p
l
l
e
e
:
:
N
N
o
o
n
n
t
t
e
e
r
r
m
m
i
i
n
n
a
a
l
l
s
s
:
:
<
<
e
e
x
x
p
p
>
>
<
<
t
t
e
e
r
r
m
m
>
>
<
<
f
f
a
a
c
c
t
t
o
o
r
r
>
>
<
<
n
n
u
u
m
m
b
b
e
e
r
r
>
>
<
<
d
d
i
i
g
g
i
i
t
t
>
>
T
T
e
e
r
r
m
m
i
i
n
n
a
a
l
l
s
s
:
:
+
+
*
*
)
)
(
(
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
P
P
r
r
o
o
d
d
u
u
c
c
t
t
i
i
o
o
n
n
s
s
:
:
<exp> ::= <exp> + <term> | <term>
<exp> ::= <exp> + <term> | <term>
<term> ::= <term> * <factor> | <factor>
<term> ::= <term> * <factor> | <factor>
<factor> ::= ( <exp> ) | <number>
<factor> ::= ( <exp> ) | <number>
<number> ::= <number> <digit> | <digit>
<number> ::= <number> <digit> | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Derive
Derive
1 * (2 + 34)
1 * (2 + 34)
by showing a derivation tree.
by showing a derivation tree.
G
r
a
m
m
a
r
T
h
e
l
a
n
g
u
a
g
e
o
f
t
h
i
s
g
r
a
m
m
a
r
i
s
t
h
e
s
e
t
o
f
a
l
l
s
t
r
i
n
g
s
o
f
t
e
r
m
i
n
a
l
s
t
h
a
t
c
a
n
b
e
d
e
r
i
v
e
d
f
r
o
m
t
h
e
s
t
a
r
t
s
y
m
b
o
l
.
3
+
2
i
s
i
n
t
h
e
l
a
n
g
u
a
g
e
;
2
*
+
7
i
s
n
o
t
Abbreviations: Extended BNF:
Often it is helpful to add features to the BNF notation. Both of
Often it is helpful to add features to the BNF notation. Both of
these features could be expressed in terms of “pure BNF”, so
these features could be expressed in terms of “pure BNF”, so
nothing new is added to what we can derive.
nothing new is added to what we can derive.
{ string }*{ string }*(a.k.a. Kleene *) stands for 0 or more occurrences of
(a.k.a. Kleene *) stands for 0 or more occurrences of
things derivable from
things derivable from
string
string
{ string }{ string }+
+
(a.k.a. Kleene +) stands for 1 or more occurrences of
(a.k.a. Kleene +) stands for 1 or more occurrences of
things derivable from
things derivable from
string
string
Example:
Example:
{<digit>}{<digit>}+
+
. {<digit>}* E{<digit>}. {<digit>}* E{<digit>}+
+
Language:
Language:
certain numbers in scientific notation
certain numbers in scientific notation
Grammars for some languages
used in EoPL and/or HW 7-9
<list-of-numbers> ::= ( {<number>}* )
<s-list> ::= ( {<symbol-exp>}* )<symbol-exp> ::= <symbol> | <s-list>
<bintree> ::= <number> |
( <symbol> <bintree> <bintree> )
<BST> ::= ( ) |
(<number> <BST> <BST> )
Grammars for some languages
used in EoPL (continued)
<datum> ::= <number> | <symbol> |
<string> | <boolean> |
<dotted-datum> | <list> |
<vector>
<list> ::= ( {<datum>}* )<dotted-datum> ::= ( {<datum>}+
. <datum> )
<vector> ::= # <list>
<LcExp> ::= Identifier |
(lambda (Identifier) <LcExp>) |
(<LcExp> <LcExp>)
One grammar from the list
<s-list> ::= ( {<symbol-exp>}* )<s-list> ::= ( {<symbol-exp>}* )<symbol-exp> ::= <symbol> | <s-list>
<symbol-exp> ::= <symbol> | <s-list>
What are some examples of s-lists?
What are some examples of s-lists?
Rewrite without the *
Rewrite without the *
<s-list> ::= ( ) | (<s-exp> . <s-list>)
<s-list> ::= ( ) | (<s-exp> . <s-list>)
<s-exp> ::= <symbol> | <s-list>
<s-exp> ::= <symbol> | <s-list>
Next Slide:
Derive
((a ()) b)
From the second
grammar.
Derive
((a ()) b)
From the this grammar.
s-list programming examples
contains?
contains?
count-occurrences
count-occurrences
notate-depth
notate-depth
flatten
flatten
subst
subst
I will do these on my computer (with your
I will do these on my computer (with your
help) to make sure that they are correct.
help) to make sure that they are correct.
You can do them on your computer or on
You can do them on your computer or on
paper; the latter may be preferable for some
paper; the latter may be preferable for some
students.
students.
W
e
w
i
l
l
p
r
o
b
a
b
l
y
d
o
m
o
s
t
o
f
t
h
e
s
e
(
m
a
y
b
e
a
l
l
o
f
t
h
e
m
)
i
n
l
i
v
e
c
o
d
i
n
g
.
M
o
s
t
o
f
i
t
w
i
l
l
h
a
p
p
e
n
o
n
d
a
y
8
.
File needed: largest-in-list-2007.ss
Programming languages consist of syntax and semantics that define how a program looks and what it means, ensuring unambiguous translation. Backus-Naur Form (BNF) is used to specify syntax, while semantics can be denotational or operational. Explore the syntax specification through a context-free grammar example.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSSE 304 Day 7 Simple Solution: Minimize-interval-list Syntax and Semantics Grammars and Derivations s-lists Follow the Grammar
Minimize-interval-list solution Big-O running time for this procedure?
Interlude Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. Martin Golding
Two major parts of a programming languages definition Syntax what does a program in the given language look like? Semantics- what does that program mean? There should be an unambiguous translation from syntax to semantics How to specify a language s syntax? BNF Semantics are harder to specify denotational, operational
BNF: recursive syntax specification Backus-Naur Form. Specify the syntax of a language. a.k.a. context-free grammar (CFG) Example: Start Symbol Nonterminals: <exp> <term> <factor> <number> <digit> Terminals: + * ) ( 0 1 2 3 4 5 6 7 8 9 Productions: <exp> ::= <exp> + <term> | <term> <term> ::= <term> * <factor> | <factor> <factor> ::= ( <exp> ) | <number> <number> ::= <number> <digit> | <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Derive 1 * (2 + 34)by showing a derivation tree. The language of this grammar is the set of all strings of terminals that can be derived from the start symbol. 3 + 2 is in the language; 2 * + 7 is not Grammar
<exp> ::= <exp> + <term> | <term> <term> ::= <term> * <factor> | <factor> <factor> ::= ( <exp> ) | <number> <number> ::= <number> <digit> | <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Derive 1 * (2 + 34)by showing a derivation tree.
BNF: recursive syntax specification Backus-Naur Form. Specify the syntax of a language. a.k.a. context-free grammar (CFG) Example: Start Symbol Nonterminals: <exp> <term> <factor> <number> <digit> Terminals: + * ) ( 0 1 2 3 4 5 6 7 8 9 Productions: <exp> ::= <exp> + <term> | <term> <term> ::= <term> * <factor> | <factor> <factor> ::= ( <exp> ) | <number> <number> ::= <number> <digit> | <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Derive 1 * (2 + 34)by showing a derivation tree. The language of this grammar is the set of all strings of terminals that can be derived from the start symbol. 3 + 2 is in the language; 2 * + 7 is not Grammar
Abbreviations: Extended BNF: Often it is helpful to add features to the BNF notation. Both of these features could be expressed in terms of pure BNF , so nothing new is added to what we can derive. { string }* (a.k.a. Kleene *) stands for 0 or more occurrences of things derivable from string { string }+ (a.k.a. Kleene +) stands for 1 or more occurrences of things derivable from string Example: {<digit>}+ . {<digit>}* E{<digit>}+ Language: certain numbers in scientific notation
Grammars for some languages used in EoPL and/or HW 7-9 <list-of-numbers> ::= ( {<number>}* ) <s-list> ::= ( {<symbol-exp>}* ) <symbol-exp> ::= <symbol> | <s-list> <bintree> ::= <number> | ( <symbol> <bintree> <bintree> ) <BST> ::= ( ) | (<number> <BST> <BST> )
Grammars for some languages used in EoPL (continued) <datum> ::= <number> | <symbol> | <string> | <boolean> | <dotted-datum> | <list> | <vector> <list> ::= ( {<datum>}* ) <dotted-datum> ::= ( {<datum>}+ . <datum> ) <vector> ::= # <list> <LcExp> ::= Identifier | (lambda (Identifier) <LcExp>) | (<LcExp> <LcExp>)
Next Slide: Derive ((a ()) b) From the second grammar. One grammar from the list <s-list> ::= ( {<symbol-exp>}* ) <symbol-exp> ::= <symbol> | <s-list> What are some examples of s-lists? Rewrite without the * <s-list> ::= ( ) | (<s-exp> . <s-list>) <s-exp> ::= <symbol> | <s-list>
Derive ((a ()) b) From the this grammar.
s-list programming examples contains? count-occurrences notate-depth flatten subst We will probably do most of these (maybe all of them) in live coding. Most of it will happen on day 8. I will do these on my computer (with your help) to make sure that they are correct. You can do them on your computer or on paper; the latter may be preferable for some students.
