1. Motivation
- Formal language theory began with Noam Chomsky (1950s), trying to describe the syntax of natural languages with precise rules.
- Programming-language syntax is described by Chomsky’s context-free grammars; a compiler’s syntax analyzer (parser) uses the grammar to check whether code is syntactically correct.
- Grammars answer two questions: (1) is a string a valid sentence? (2) how do we generate valid sentences?
- We care about syntax (form), not semantics (meaning): “the frog writes neatly” is valid; “swims quickly mathematics” is not.
Running example: a subset of English
- sentence → noun phrase · verb phrase
- noun phrase → article · adjective · noun, or 3. article · noun
- verb phrase → verb · adverb, or 5. verb
6–7. article → a | the
8–9. adjective → large | hungry
10–11. noun → rabbit | mathematician
12–13. verb → eats | hops
14–15. adverb → quickly | wildly
Derivation of the hungry rabbit eats quickly:
sentence ⇒ noun phrase verb phrase ⇒ article adjective noun verb phrase ⇒ article adjective noun verb adverb ⇒ the adjective noun verb adverb ⇒ the hungry noun verb adverb ⇒ the hungry rabbit verb adverb ⇒ the hungry rabbit eats adverb ⇒ the hungry rabbit eats quickly
Also valid: a hungry mathematician eats wildly, a large mathematician hops. Not valid: the quickly eats mathematician.
2. Phrase-Structure Grammars
Definition 1 — vocabulary, words, languages
- Vocabulary / alphabet : finite nonempty set of symbols.
- Word / sentence over : finite string of symbols from .
- Empty string : the string with no symbols.
- = set of all words over . A language over is a subset of .
⚠️ . is a set containing one string (the empty one).
Terminology
- Terminals : symbols that cannot be replaced (a, the, rabbit, …).
- Nonterminals : symbols that can be replaced (sentence, noun phrase, …).
- Start symbol : where every derivation begins (sentence).
- Productions : rules saying may be replaced by .
Definition 2
A phrase-structure grammar : vocabulary , terminals , start symbol , finite set of productions . Every production must have at least one nonterminal on its left side.
Example 1: , , .
Definition 3 — derivations
If , and , then is directly derivable from : .
If , then is derivable from : . The sequence is a derivation.
Example 2 (grammar of Ex. 1):
- (using )
- :
Definition 4 — language of a grammar
(all strings of terminals derivable from ). is the Kleene closure of : plus all finite concatenations of elements of .
Worked examples
| Grammar (productions) | Language |
|---|---|
| : | |
| : | (same as !) |
Two different grammars can generate the same language ( and ).
3. Types of Grammars (Chomsky hierarchy)
| Type | Restriction on productions | Language class |
|---|---|---|
| 0 | No restrictions | phrase-structure |
| 1 | , with , , ; or if is not on any right-hand side | context-sensitive |
| 2 | , a single nonterminal | context-free |
| 3 | and or (, ); or | regular |
Every type 3 grammar is type 2, every type 2 is type 1 (apart from λ-rules), every type 1 is type 0.
Examples
- — context-sensitive (type 1 grammar above).
- — context-free ().
- — regular (grammar is type 3).
4. Derivation (Parse) Trees
For context-free (type 2) grammars, a derivation is drawn as an ordered rooted tree:
- root = start symbol; internal vertices = nonterminals; leaves = terminals.
- If is used, ‘s children are the symbols of , left to right.
Tree for the hungry rabbit eats quickly:
sentence
/ \
noun phrase verb phrase
/ | \ / \
article adjective noun verb adverb
| | | | |
the hungry rabbit eats quickly
5. Is a string in the language? Top-down vs bottom-up parsing
Grammar: . Is cbab in ?
Top-down (start from , apply productions):
✓
(only one rule for ; only one for ; string starts with cb so use ; finish with .)
Bottom-up (start from the string, work backwards):
i.e. ✓
6. Backus–Naur Form (BNF)
Compact notation for type 2 grammars (used for ALGOL, Java, …):
::=instead of- nonterminals in angle brackets ⟨ ⟩
- all right-hand sides for the same nonterminal in one rule, separated by
|
becomes ⟨A⟩ ::= ⟨A⟩a | a | ⟨A⟩⟨B⟩.
English subset in BNF
⟨sentence⟩ ::= ⟨noun phrase⟩⟨verb phrase⟩
⟨noun phrase⟩ ::= ⟨article⟩⟨adjective⟩⟨noun⟩ | ⟨article⟩⟨noun⟩
⟨verb phrase⟩ ::= ⟨verb⟩⟨adverb⟩ | ⟨verb⟩
⟨article⟩ ::= a | the
⟨adjective⟩ ::= large | hungry
⟨noun⟩ ::= rabbit | mathematician
⟨verb⟩ ::= eats | hops
⟨adverb⟩ ::= quickly | wildly
ALGOL 60 identifiers (letters/digits, must start with a letter)
⟨identifier⟩ ::= ⟨letter⟩ | ⟨identifier⟩⟨letter⟩ | ⟨identifier⟩⟨digit⟩
⟨letter⟩ ::= a | b | ··· | z
⟨digit⟩ ::= 0 | 1 | ··· | 9
Deriving x99a: ⟨identifier⟩ ⇒ ⟨identifier⟩⟨letter⟩ ⇒ ⟨identifier⟩a ⇒ ⟨identifier⟩⟨digit⟩a ⇒ ⟨identifier⟩⟨digit⟩⟨digit⟩a ⇒ ⟨identifier⟩99a ⇒ ⟨letter⟩99a ⇒ x99a.
Signed integers
⟨signed integer⟩ ::= ⟨sign⟩⟨integer⟩
⟨sign⟩ ::= + | −
⟨integer⟩ ::= ⟨digit⟩ | ⟨digit⟩⟨integer⟩
⟨digit⟩ ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Extended BNF (EBNF)
Metacharacters applied to the symbol (or parenthesized group) on their left:
?— zero or one time (optional)*— zero or more times+— one or more times
Angle brackets are usually dropped in EBNF.
7. Solved Exercises (from the slides)
Ex. 4 —
- (a) ✓
- (b) 11001 ∉ : no production can produce a 1 as the rightmost character.
- (c)
Ex. 9 — derive
- :
- (all 0s first, then switch to ):
Ex. 15 — grammars for:
- (a) even number of 0s, no 1s:
- (b) a 1 followed by an odd number of 0s:
- (c) even number of 0s and even number of 1s: use nonterminal stand-ins (for 0), (for 1) so they can be reordered:
Ex. 17
- (a) :
- (b) : (or )
- (c) :
Ex. 27 — derivation tree for −109 (signed-integer grammar):
⟨signed integer⟩
/ \
⟨sign⟩ ⟨integer⟩
| / \
− ⟨digit⟩ ⟨integer⟩
| / \
1 ⟨digit⟩ ⟨integer⟩
| |
0 ⟨digit⟩
|
9
Ex. 31 — BNF for identifiers
- (a) one or more lowercase letters:
⟨identifier⟩ ::= ⟨lcletter⟩ | ⟨identifier⟩⟨lcletter⟩,⟨lcletter⟩ ::= a | b | ··· | z - (b) 3 to 6 lowercase letters: list each length explicitly —
⟨identifier⟩ ::= ⟨lcletter⟩⟨lcletter⟩⟨lcletter⟩ | ⟨lcletter⟩×4 | ⟨lcletter⟩×5 | ⟨lcletter⟩×6 - (c) 1 to 6 letters, starting uppercase:
⟨identifier⟩ ::= ⟨ucletter⟩ | ⟨ucletter⟩⟨letter⟩ | … | ⟨ucletter⟩⟨letter⟩⟨letter⟩⟨letter⟩⟨letter⟩⟨letter⟩
⟨letter⟩ ::= ⟨lcletter⟩ | ⟨ucletter⟩,⟨ucletter⟩ ::= A | B | ··· | Z - (d) lowercase letter, then digit or underscore, then 3 or 4 alphanumerics:
⟨identifier⟩ ::= ⟨lcletter⟩⟨digitorus⟩⟨alphanumeric⟩⟨alphanumeric⟩⟨alphanumeric⟩ | ⟨lcletter⟩⟨digitorus⟩⟨alphanumeric⟩⟨alphanumeric⟩⟨alphanumeric⟩⟨alphanumeric⟩
⟨digitorus⟩ ::= ⟨digit⟩ | _,⟨alphanumeric⟩ ::= ⟨letter⟩ | ⟨digit⟩
Ex. 33 — C identifiers in BNF (start with letter or _, then any letters/digits/underscores; a lone _ is valid):
⟨identifier⟩ ::= ⟨letterorus⟩ | ⟨identifier⟩⟨symbol⟩
⟨symbol⟩ ::= ⟨letterorus⟩ | ⟨digit⟩
⟨letterorus⟩ ::= ⟨letter⟩ | _
⟨letter⟩ ::= ⟨lcletter⟩ | ⟨ucletter⟩
⟨lcletter⟩ ::= a | b | ··· | z
⟨ucletter⟩ ::= A | B | ··· | Z
⟨digit⟩ ::= 0 | 1 | ··· | 9
Ex. 37 — the same in EBNF:
identifier ::= letterorus symbol*
symbol ::= letterorus | digit
letterorus ::= letter | _
letter ::= lcletter | ucletter
lcletter ::= a | b | ··· | z
ucletter ::= A | B | ··· | Z
digit ::= 0 | 1 | ··· | 9