[Overview] [Previous] [Next]

Parsing

There are two ways to use a grammar: 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.


Copyright © 1996 by David Matuszek
Last modified Mar 2, 1996