Grammars, Parsing, and Morphological Processing #

Natural-language sentences are more than sequences of words. Their words form phrases, and the way those phrases are grouped determines the sentence’s structure and meaning.

A grammar describes the structures that a language permits. A parser uses that grammar to discover the hidden structure of a particular sentence.

Course Content #

Grammars and sentence structure
What makes a good grammar
A bottom-up chart parser
Probabilistic Context-Free Grammars
Probabilistic CKY parsing of PCFGs
Ways to learn PCFG rule probabilities
Problems with PCFGs
Improving PCFGs by splitting non-terminals and using lexicalised CFGs

Learning Objectives #

Explain why sentence structure is necessary for resolving ambiguity.
Represent a grammar using terminals, non-terminals, productions, and a start symbol.
Recognise the defining restriction of a Context-Free Grammar.
Construct and interpret a simple parse tree.
Compare top-down and bottom-up parsing.
Explain how a chart prevents repeated parsing work.
Distinguish active arcs, completed constituents, the agenda, and the chart.
Explain morphological analysis and generation using finite-state models.

Big Picture #

flowchart TD
    A["Sentence"] --> B["Grammar: allowed structures"]
    B --> C["Parser: search for structure"]
    C --> D["Parse tree"]
    D --> E["Interpretation"]

    style A fill:#E1F5FE
    style B fill:#C8E6C9
    style C fill:#FFF9C4
    style D fill:#EDE7F6
    style E fill:#E1F5FE

1. Why Sentence Structure Matters ☆ #

Knowing the meanings of individual words is not enough to determine the meaning of a complete sentence. We must also know which words belong together.