Syntax
CMPSC 461
Programming Language Concepts Penn State University
Fall 2020
Imperative Language Functional Language OO Language
1+2
3
How does the Magic Box work?
2
Source Code to Target Code
(1.0+2)+x
Token
( 1.0 + 2 ) + x
+ + id
Num Num 1.0 2
+ only take numbers x is in scope (visible)
Cmpsc461
x
Abstract Syntax Tree
Cmpsc471
3
Formal Languages
Language: a set of (legal) strings
Goal: a concise & precise notation for specifying a language
Four levels of languages [Chomsky]:
1. Regular
2. Context-Free
3. Context-Sensitive 4. Unrestricted
programming languages
4
Lexical Syntax
Rules for basic symbols, such as
identifier, literals (e.g., numbers), operators, keywords, punctuation
C language:
Identifier: letters, digits and underscore ‘_’ only. The first character must be an underscore or a letter
literals: digits, decimal point, suffix such as “l”, “u” operators: + – * / …
keywords : if, while, for, int, … punctuation:{ } [ ] ; …
5
(1.0+2)+x
Token
( 1.0 + 2 ) + x
6
Language of tokens (C)
Identifier: letters, digits and underscore ‘_’ only. The first character must be an underscore or a letter
literals: digits, decimal point, suffix such as “l”, “u” operators: + – * / …
keywords : if, while, for, int, …
punctuation:{ } [ ] ; …
How can we specify these tokens (sets of strings)?
7
Regular Expression
Definition:
• A character
• Empty string (𝜀)
• Concatenation of two RE (e.g., (ab))
• Alternation of two RE, separated by “|” (e.g., (a|b)) • Closure (Kleene star) (e.g.(a*))
8
Examples
RE Meaning
a “a”
ac “ac”
a|c “a” or “c”
a* “” or “a” or “aa” or … (a|b)(c|d) “ac” or “ad” or “bc” or “bd” (ab)|(cd) “ab” or “cd”
((a|b)c)* “” or “ac” or “bc” or “acac” or “bcbc” or …
9
More Formally…
Regular expression defines a set of strings (aka. a language)
𝐿(𝑅): the language defined by RE 𝑅
• A character 𝑥: 𝐿(𝑥) = {“𝑥”}
• Empty string 𝜀: 𝐿(𝜀) = {“”}
String concatenation
• Concatenation: 𝐿(𝑅𝑆) = {𝑟. 𝑠|𝑟 ∈ 𝐿(𝑅), 𝑠 ∈ 𝐿(𝑆)}
•Alternation:𝐿𝑅𝑆 =𝐿𝑅 ∪𝐿(𝑆)
•Kleenestar:𝐿 𝑅∗ = “” ∪𝐿 𝑅 ∪𝐿 𝑅𝑅 ∪⋯
10
Examples
• Acharacter𝑥:𝐿 𝑥 = ”x”
• Emptystring𝜀:𝐿 𝜀 =
• Concatenation:𝐿 𝑅𝑆 = 𝑟.𝑠𝑟∈𝐿 𝑅 ,𝑠∈𝐿 𝑆 • Alternation:𝐿𝑅𝑆 =𝐿𝑅 ∪𝐿𝑆 •Kleenestar:𝐿𝑅∗ =””∪𝐿𝑅∪𝐿𝑅𝑅∪⋯
RE a ac a|c a*
𝐿(RE)
{“a”}
{“ac”}
{“a”, “c”}
{“”, “a”, “aa”, …}
11
Examples
• Acharacter𝑥:𝐿 𝑥 = ”x”
• Emptystring𝜀:𝐿 𝜀 =
• Concatenation:𝐿 𝑅𝑆 = 𝑟.𝑠𝑟∈𝐿 𝑅 ,𝑠∈𝐿 𝑆 • Alternation:𝐿𝑅𝑆 =𝐿𝑅 ∪𝐿𝑆 •Kleenestar:𝐿𝑅∗ =””∪𝐿𝑅∪𝐿𝑅𝑅∪⋯
RE (a|b)(c|d) (ab)|(cd) ((a|b)c)*
𝐿(RE)
{“ac”, “ad”, “bc”, “bd”} {“ab”, “cd”}
{“”, “ac”, “bc”, “acac”, “bcbc”, …}
12