Syntactic Parsing Algorithms

Parsing is the process of analyzing a sentence according to a grammar and producing its parse tree(s). Given a CFG (Unit 2, previous lesson), there are several algorithmic strategies to search for a valid parse.

1. Top-Down Parsing

Starts from the start symbol (S) and repeatedly expands non-terminals using grammar rules, trying to match the input sentence left to right.

Start: S
Try:   S -> NP VP
Try:   NP -> 'Riya'  ✓ matches first word
Try:   VP -> V NP
Try:   V -> 'reads'  ✓ matches next word
Try:   NP -> Det N -> ... matches remaining words

• Pros: Never explores trees inconsistent with the grammar's start symbol.
• Cons: Can waste time on rules that will never match the actual input (no lookahead at the words); struggles with left-recursive rules (e.g. NP -> NP PP) which can loop forever.

2. Bottom-Up Parsing

Starts from the input words (terminals) and works upward, combining them into larger constituents until the start symbol S is reached.

Input:  Riya   reads   a   book
Step1:  NNP    V       Det  N
Step2:  NP     V       NP        (combine 'Riya'->NP, 'a book'->NP)
Step3:  NP     VP                 (combine V NP -> VP)
Step4:  S                          (combine NP VP -> S)

• Pros: Always works directly from the actual input words, so it never explores a rule irrelevant to the sentence.
• Cons: Can build constituents that never end up part of a full valid parse (wasted work); doesn't know the "target" is S until the very end.

Using NLTK's Chart Parser (Top-Down Strategy)

import nltk
from nltk import CFG, ChartParser

grammar = CFG.fromstring("""
S -> NP VP
NP -> 'Riya' | Det N
VP -> V NP
Det -> 'a'
N -> 'book'
V -> 'reads'
""")

parser = ChartParser(grammar)
sentence = ['Riya', 'reads', 'a', 'book']
for tree in parser.parse(sentence):
    print(tree)
    tree.pretty_print()
# (S (NP Riya) (VP (V reads) (NP (Det a) (N book))))

3. The CYK (Cocke-Younger-Kasami) Algorithm

CYK is a dynamic programming bottom-up algorithm that parses in guaranteed O(n³) time — much more efficient than naive backtracking parsers for longer sentences. It requires the grammar to be in Chomsky Normal Form (CNF), where every rule is either A -> B C (two non-terminals) or A -> a (one terminal).

CYK builds a triangular table: cell [i, j] holds the set of non-terminals that can generate the substring from word i to word j.

Sentence: "the dog barked"  (CNF grammar assumed)

        the        dog          barked
the    {Det}     {NP}         {S}         <- combines whole sentence
dog       -      {N}          {VP}? no -> combine dog+barked
barked    -        -          {V}

# CYK core idea in pseudocode
def cyk_parse(words, grammar_cnf):
    n = len(words)
    table = [[set() for _ in range(n)] for _ in range(n)]
    # Fill diagonal: single-word constituents
    for i, w in enumerate(words):
        table[i][i] = grammar_cnf.tags_for_word(w)
    # Fill table for increasing substring lengths
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                for B in table[i][k]:
                    for C in table[k+1][j]:
                        table[i][j] |= grammar_cnf.rules_producing(B, C)
    return 'S' in table[0][n-1]   # sentence is valid if S spans the whole table

Dependency Parsing (Alternative to Constituency Parsing)

Instead of nested phrases (NP, VP), dependency parsing represents a sentence as directed grammatical relations between word pairs (e.g. subject, object).

import spacy

nlp = spacy.load("en_core_web_sm")
doc = nlp("Riya reads a book")
for token in doc:
    print(f"{token.text:10} --{token.dep_:10}--> {token.head.text}")
# Riya       --nsubj    --> reads
# reads      --ROOT     --> reads
# a          --det      --> book
# book       --dobj     --> reads

Comparing Parsing Strategies