[Overview] [Previous] [Next]
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.
- 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.
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