Grammars and Parsing

Computational Linguistics

Course 1 · Chapter 6 · Grammars and Parsing

Chapter 5's model saw only the previous word. A sentence has more structure than that: the man with the telescope is a unit, and a program that knows it can answer questions a word-by-word model cannot. This chapter writes grammar rules in a form a machine can apply, and then meets the problem that follows every attempt: the same sentence can have more than one structure.

The idea in a box

A grammar is a small set of rewriting rules; a parse is the record of which rules produced a sentence. When a sentence has more than one record, the program has to choose.

Context-Free Grammars

Wikipedia's Context-free grammar article defines a CFG as a formal grammar whose production rules "can be applied to a nonterminal symbol regardless of its context". Formally it has four parts: nonterminals, terminals, production rules and a start symbol, which "represent[s] the whole sentence (or program)". Each rule has one nonterminal on the left and a string of terminals and/or nonterminals on the right; a nonterminal may have several rules; the language it generates is "the set of all strings of terminal symbols that can be derived" from the start symbol.

Where it came from. The article says Noam Chomsky "invented" CFGs to describe natural-language sentence structure. Some linguists use "phrase structure grammar" to mean CFGs, and phrase structure grammars are also called constituency grammars, contrasted with dependency grammars. In computer science CFGs describe programming-language syntax.
Derivation. "A sequence of grammar rule applications that transform the start symbol into the string"; it imposes hierarchical structure, shown as a parse tree.
Where it fits. In Chomsky's classification, context-free is Type-2, with regular grammars as a subclass of linear grammars. This links to Chapter 4: regular expressions match regular languages, and context-free grammars are the next step up in power, because they can describe nesting, such as balanced parentheses, which a regular expression cannot. (The nesting remark is the article's grammar examples, such as S → SS | (S) | (), read with Chapter 4's regular-language point; stating the contrast is my own.)

The limits for natural language

The article says context-free rules do not capture features such as agreement and reference. Chomsky's view that natural language is not context-free has held up, but his specific counterexamples were later disproved. Gazdar and Pullum argue natural language has a few non-context-free constructions, such as cross-serial dependencies in Swiss German and reduplication in Bambara, and that "the vast majority of forms in natural language are indeed context-free". The page was read to 100,000 of 107,898 characters; the unread end is mostly navigation.

Parse Trees

The Parse tree article defines one as "an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar". There are two kinds:

	Constituency tree	Dependency tree
Follows	phrase structure grammars	dependency grammars
Nodes	interior nodes labelled by non-terminal categories; leaves are terminals	all nodes terminal
Size	more nodes	fewer nodes; omit phrasal categories such as S, VP, NP, but still show constituent structure, since any complete subtree is a constituent

The article's example is John hit the ball: S is the root, with NP (John) and VP as branches; the VP contains V (hit) and an NP containing D (the) and N (ball). "Parse tree" is mainly the computational-linguistics term; "syntax tree" is more common in theoretical syntax. (The tree itself is an image in the article; I am relying on its text description.)

A Grammar You Can Run

The grammar, words and parser below are mine. The parser tries every way of splitting a stretch of words between a rule's two parts and remembers the results; it is meant to be short and clear, not fast. I ran it and copied the output. The bracketed lines are trees: for example [NP i] means the word i was an NP by way of the rule NP → Pro.

from functools import lru_cache

rules = {
    "S":  [("NP", "VP")],
    "NP": [("Pro",), ("Det", "N"), ("NP", "PP")],
    "VP": [("V", "NP"), ("VP", "PP")],
    "PP": [("P", "NP")],
}
lexicon = {
    "Pro": {"i"}, "Det": {"the"}, "N": {"man", "telescope", "ball"},
    "V": {"saw", "hit"}, "P": {"with"},
}

def parse(words, start="S"):
    words = tuple(words)

    @lru_cache(maxsize=None)
    def trees(sym, i, j):
        out = []
        if sym in lexicon:
            if j == i + 1 and words[i] in lexicon[sym]:
                out.append((sym, words[i]))
            return tuple(out)
        for rhs in rules[sym]:
            if len(rhs) == 1:
                for t in trees(rhs[0], i, j):
                    out.append((sym, t))
            else:
                for k in range(i + 1, j):
                    for left in trees(rhs[0], i, k):
                        for right in trees(rhs[1], k, j):
                            out.append((sym, left, right))
        return tuple(out)

    return trees(start, 0, len(words))

def show(t):
    if len(t) == 2 and isinstance(t[1], str):
        return t[1]
    return "[" + t[0] + " " + " ".join(show(c) for c in t[1:]) + "]"

s = "i saw the man with the telescope".split()
for t in parse(s):
    print(show(t))
print(len(parse(s)))
print(len(parse("i hit the ball".split())), len(parse("hit the i".split())))

[S [NP i] [VP saw [NP [NP the man] [PP with [NP the telescope]]]]] [S [NP i] [VP [VP saw [NP the man]] [PP with [NP the telescope]]]] 2 1 0

Two parses for one sentence. In the first, with the telescope attaches to the man (the man has the telescope); in the second it attaches to the verb phrase (I used the telescope to see). The sentence i hit the ball has one parse and the word salad hit the i has none, so the grammar is also a test of whether a string belongs to its language.

Ambiguity

The Syntactic ambiguity article defines it as "the potential for a sentence to yield multiple interpretations due to its ambiguous syntax", arising from how words and clauses relate and not from individual word meanings. Its example: John saw the man on the mountain with a telescope, with readings in which the telescope belongs to John's seeing, to the man, or to the mountain. It distinguishes globally ambiguous sentences (The woman held the baby in the green blanket) from locally ambiguous ones that resolve by the end, and from garden-path sentences, where "a structurally correct sentence is difficult to interpret" because the reader commits to the wrong structure early. It also gives the headline Violinist linked to JAL crash blossoms. For NLP, it defines a "parse forest" as "the collection of all possible syntactic structures" for a sentence, and "syntactic disambiguation" as "the task of clarifying which meaning is actually intended". My code's list of two trees is a tiny parse forest, though the article does not use my example or my grammar.

How fast does the number of parses grow? I added more prepositional phrases with the same code:

base = "i saw the man"
for n in range(0, 5):
    sent = (base + " with the telescope" * n).split()
    print(n, len(parse(sent)))

0 1 1 2 2 5 3 14 4 42

1, 2, 5, 14, 42: each extra phrase multiplies the possibilities. Chapter 1's NLP article said a typical sentence may have thousands of potential parses; this toy grammar shows how easily they multiply. I recognise this sequence from mathematics, but neither article mentions it, so I only report the run.

Parsing in Practice

The Parsing article defines it as analyzing a string of symbols and checking that it conforms to the rules of a formal grammar. For natural language it cites "substantial ambiguity in the structure of human language" as the reason programs struggle, and says "Most modern parsers are at least partly statistical": they learn from hand-parsed corpora (Chapter 3's treebanks) using methods such as probabilistic context-free grammars, maximum entropy and neural nets; lexical statistics help but risk overfitting and need smoothing (Chapter 5). It also describes:

Idea	What the article says
Top-down	expands rules from the start symbol, leftmost, consuming tokens left to right; LL and recursive-descent parsers
Bottom-up	starts from the input and works back to the start symbol; LR (shift-reduce) parsers
CYK	a cubic-time algorithm for context-free grammars in Chomsky normal form
Earley	a cubic-time algorithm that handles any context-free grammar
Shallow parsing	finds only the boundaries of major constituents

My parser is closest in spirit to a chart approach that tries all splits of a span, but I have not implemented CYK or Earley and do not claim it is either.

Watch out: a grammar describes what you put in it

My grammar accepts the telescope saw the man (an NP can be anything, and nothing says telescopes cannot see) and has no way to parse i saw, since every verb needs an object. Both limits come from what I wrote, not from English. This is the article's point that context-free rules do not capture features such as agreement and reference.

Note on sources

This chapter uses Wikipedia's Context-free grammar (read to 100,000 of 107,898 characters), Parse tree, Syntactic ambiguity and Parsing (all read in full). The Syntactic ambiguity page does not use "I saw the man with the telescope" or the term PP-attachment, so those are mine; it gives NLP only brief coverage. The Parse tree example tree is an image, and I used the article's text description. The grammar, the parser, the sentences, all outputs and the growth sequence are mine and were run with py -X utf8. The link to Chapter 4 (regular versus context-free power) rests on the article's examples and my own reading. NLP 7's coverage of syntax-related tagging is not re-read here.

Try It Yourself

Exercise 1

Run parse on the man saw i, i saw, the telescope saw the man and the man saw the telescope. For each, say whether the result matches English, and name which limit of this grammar explains any mismatch.

📄 View solution

Exercise 2

Add ("Name",) to the NP rules and "Name": {"john"} to the lexicon, then parse john hit the ball. Compare your tree with the Parse tree article's description of the same sentence and list the differences in labels.

📄 View solution

Exercise 3

The two parses of i saw the man with the telescope give two meanings. Say which meaning goes with each tree, and what kind of extra information (not in the grammar) a program would need to prefer one.

📄 View solution

Chapter 6 Quick Reference

CFG: nonterminals, terminals, rules, start symbol; Type-2 in Chomsky's hierarchy
Parse tree: constituency (phrase categories) or dependency (words only)
Ambiguity: more than one tree for one string; a parse forest holds them all
Most modern parsers are at least partly statistical and learn from treebanks

Coming next

Computational Linguistics 7 labels each word with its part of speech, rule by rule and by statistics.