# 0x442 Syntax

## Constituent Tree Parsing

### CFG

#### Ambiguities

• coordination ambiguity: CFG cannot enforce agreement in the context. (e.g: koalas eat leaves and (barks))
• prepositional phrase attachment ambiguity (e.g: I saw a girl (with a telescope))

Solution is to use PCFG to score all the derivations to encode how plausible they are

### PCFG

#### Estimation

ML Estimation

$$P(X \to \alpha) = \frac{C(X \to \alpha)}{C(X)}$$

#### Parsing

CKY

complexity is $O(n^3 |R|)$ where $n$ is the number of words and $|R|$ is the number of rules in the grammar

Horizontal Expansion

Vertical Expansion

### Discriminative Rerankings

generate top-k candidates from the previous parser and rerank them with discriminative reranking might be helpful