Notes on Specification Languages and Grammars

Introduction to Grammar

  • Grammar determines the validity of sentences in a language.
    • Examples:
    • Valid: "The large rabbit hops quickly."
    • Valid: "The frog writes neatly."
    • Not Valid: "Swims quickly mathematician."
  • Grammar focuses on syntax (form) rather than semantics (meaning).

English Grammar Structure

  • Sentence Structure: Noun phrase + Verb phrase
  • Components:
    • Noun Phrase: Article + Adjective + Noun (e.g., "the large rabbit")
    • Verb Phrase: Verb + Adverb (e.g., "hops quickly")
    • Examples of elements:
    • Article: a, the
    • Adjective: large, hungry
    • Noun: rabbit, mathematician
    • Verb: eats, hops, writes, swims
    • Adverb: quickly, wildly, neatly

Use of Grammars in Computation

  • Model computation:
    • Generate words in a language
    • Determine if a word belongs to a language

Phrase-Structure Grammar

Definition
  • Grammar G = (V, T, S, P) includes:
    • Vocabulary V (set of symbols)
    • Terminal set T (subset of V)
    • Start symbol S from V
    • Set P of production rules
    • Nonterminals: N = V - T
Derivation
  • Derivation indicates transformation from one string to another using production rules.
  • Direct derivation represented by:
    • w0 ➞ w1,
    • Entire derivation can be visualized in a derivation tree.

Types of Grammars

  • Type 0: No restrictions on productions
  • Type 1: Length of production outputs is longer or equal to inputs
  • Type 2: Productions are in the form A ➞ w2 (A is nonterminal)
  • Type 3: Productions of the form A ➞ aB or A ➞ a (regular grammars)
  • Each type is a subset of the previous type (Type 3 ⊆ Type 2 ⊆ Type 1 ⊆ Type 0).

Parsing Techniques

  • Top-Down Parsing: Start from S and apply productions to derive a word.
  • Bottom-Up Parsing: Analyze a word and work backwards using productions.

Backus-Naur Form (BNF)

  • Used for specifying syntax of languages (e.g., programming languages).
  • Syntax:
    • Nonterminals are enclosed in < >
    • Production form: ::=
    • Grouping with | for alternatives

Key Examples and Exercises

  • Construct phrase-structure grammars and derivation trees for various sets of strings.
  • Practice identification of grammar types from given production rules.