[Overview] [Previous] [Next]

Parsing

There are two ways to use a grammar:

Use the grammar to generate strings of the language. This is easy -- start with the start symbol, and apply derivation steps until you get a string composed entirely of terminals.
Use the grammar to recognize strings; that is, test whether they belong to the language. For CFGs, this is usually much harder.

A language is a set of strings, and any well-defined set must have a membership criterion. A context-free grammar can be used as a membership criterion -- if we can find a general algorithm for using the grammar to recognize strings.

Parsing a string is finding a derivation (or a derivation tree) for that string.

Parsing a string is like recognizing a string. An algorithm to recognize a string will give us only a yes/no answer; an algorithm to parse a string will give us additional information about how the string can be formed from the grammar.

Generally speaking, the only realistic way to recognize a string of a context-free grammar is to parse it.