The Transition to Statistical Methods (1970s) › Core Concepts in Symbolic Language Processing

The symbolic era produced several influential frameworks for representing and analyzing language structure, each addressing different aspects of how sentences are constructed and understood.

Context-free grammars became the workhorse of symbolic language processing. A CFG consists of a set of rewrite rules where each rule has a single non-terminal on the left side and a sequence of terminals or non-terminals on the right. The term "context-free" names the grammar's defining property: these rules can be applied regardless of the surrounding context. Whether a noun phrase appears at the beginning, middle, or end of a sentence, the same rules for constructing that noun phrase apply.

Consider how a CFG might analyze the sentence "The bird eats worms." The grammar would include rules such as:

S → NP VP (A sentence consists of a noun phrase followed by a verb phrase)
NP → Det Noun (A noun phrase consists of a determiner followed by a noun)
VP → Verb NP (A verb phrase consists of a verb followed by a noun phrase)

These rules work together to build a hierarchical structure, showing how smaller constituents combine into larger ones. This hierarchical view of sentence structure proved enormously influential, both in linguistics and computer science, and it remains central to how we think about syntax today.

Parsing refers to the computational process of taking a sentence and determining its grammatical structure according to the rules of a grammar. When you parse "The quick fox jumps," you identify "The quick fox" as the subject noun phrase and "jumps" as the verb phrase. The parser builds a complete structural analysis, essentially creating a diagram that shows how each word fits into the overall sentence structure.

Early parsing algorithms faced significant computational challenges. For a given sentence, there might be multiple ways to apply the grammar rules, leading to different possible structures. Finding the correct parse often required searching through many possibilities, and as sentences grew longer and grammars more complex, this search became prohibitively expensive. Researchers developed increasingly sophisticated parsing algorithms, from top-down and bottom-up methods to more efficient chart parsing techniques that avoided redundant computation. Despite these advances, the fundamental challenge remained: without some way to choose among alternative parses, symbolic systems struggled with ambiguity.

Chomsky's transformational grammar introduced a two-level representation of sentences. The deep structure captures the underlying meaning and logical relationships, while the surface structure represents the actual form of the sentence as spoken or written. Transformation rules map between these levels, allowing the system to relate different surface forms that share the same underlying meaning.

For instance, the declarative sentence "The dog chased the cat" and the question "Did the dog chase the cat?" have different surface structures but share a common deep structure. A transformation rule captures this relationship, specifying how to convert the declarative form into the interrogative form. Similarly, active and passive constructions like "The cat chased the mouse" and "The mouse was chased by the cat" can be related through transformations. This framework provided a powerful way to capture linguistic generalizations, explaining why certain sentences feel semantically related even when they have different forms.

While constituency-based grammars like CFGs focus on how words group into phrases, dependency grammar takes a different approach, emphasizing the direct relationships between words. In a dependency analysis, each word (except the root) depends on exactly one other word, creating a tree structure of dependencies rather than a hierarchy of constituents.

Consider the sentence "She gave him a book." In a dependency analysis, the verb "gave" serves as the root, with "she" as its subject dependent, "him" as its indirect object dependent, and "book" as its direct object dependent. The determiner "a" depends on "book." This representation directly captures grammatical relations like subject, object, and modifier, making it particularly useful for languages with flexible word order where constituency structure is less reliable.