Grammars 1

Grammars vs. Parsers and Generators

• Grammar/lexicon: knowledge about the structure and content of linguistic objects
• Parser: algorithm (program) which applies a grammar/lexicon to an input sentence (or set of sentences) yielding an analysis, typically including a representation of the content of the sentence(s)
• Generator: algorithm (program) which applies a grammar/lexicon to an input representation of some semantic/pragmatic content yielding one or more sentences

Natural Language and Computational Adequacy

• What sort of grammar (or equivalently, what sort of computational device) is necessary to generate and assign structures to natural language sentences?
• We would like the most constrained type possible because this will simplify parsing and because we don't want our theory to be too powerful.

Regular Grammars, Finite-State Automata/Transducers

• Regular grammars seem to be adequate for morphology
• Mathematical adequacy for sentences
  • Regular grammars cannot handle the language aⁿbⁿ
  • Languages seem to exhibit aⁿbⁿ, e.g., center embedding in English: the doctor (the plumber)ⁿ (likes)ⁿ
• Notational adequacy for sentences: how practical or elegant is a formalism?
  • Regular grammars cannot capture the generalization that noun phrases have the same sort of structure wherever they occur

Context-Free Grammars, Pushdown Automata/Transducers, Recursive Transition Networks

• Context-free grammars: left-hand side of rule consists of one symbol
• Recursive transition networks: permit arcs labeled with phrasal categories, as well as lexical categories and JUMP
• This allows for recursion but requires a stack
• Context-free grammars embellished with complex categories (features-value pairs) can handle nearly all of the phenomena in natural language
• Mathematical inadequacy for certain structures
  • Respectively structures: Francis, Tom, and Arlene hate Ellen, Phil, and Al respectively.
  • Cross-serial dependencies in Dutch, Swiss German: ... dat Piet Jan de kinderen zag helpen zwemmen '... that Piet saw Jan help the children swim'
• Indexed grammars, context-free grammars augmented with infinitely many categories, can handle all known phenomena in natural language

Back to the Real World

• There are no infinite sentences and no systems, human or machine, with infinite resources.
• If we are interested in modeling people and we limit the depth of recursion, we have two alternatives
  • Relying on regular grammars instead
  • Sticking with context-free (or indexed) grammars but limiting the memory somehow
    • Simple recurrent networks (Elman nets) as a way of achieving this

[L645 Syllabus]