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

  1. sentence → noun phrase · verb phrase
  2. noun phrase → article · adjective · noun, or 3. article · noun
  3. 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)

TypeRestriction on productions Language class
0No restrictionsphrase-structure
1, with , , ; or if is not on any right-hand sidecontext-sensitive
2, a single nonterminalcontext-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