The Computer Science Relationship Between Context-Free Grammar and Syntax

A context-free grammar is a set of computer science rules governing sequences, or strings, of symbols. For example, writing a sentence in English creates a string of words according to that language's grammar rules. The main difference between human syntax and a context-free grammar is that a sentence has to have meaning, whereas a string produced by a context-free grammar only has to follow the rules; it doesn't have to mean anything. Some linguists use context-free grammars to further the study of human syntax.

Function

A context-free grammar comprises four pieces. A starting symbol that acts as a seed for future strings; recursive rules that tell you how an expression can be modified within the grammar; terminal symbols comprised of the alphabet used to generate strings; and non-terminal symbols. Non-terminal symbols are like variables in an equation; they are placeholders used to specify the grammar's recursive rules. All possible character strings can be placed into a tree, whereby each branch represents the application of each recursive rule. The starting symbol is at the top of the tree.

Significance

If a context-free grammar is coupled with a lexicon, which assigns meaning to symbols like a dictionary assigns meaning to words, then it could be said to have meaning. For example, a simple context-free grammar might tell you how to form equations by inserting symbols in between numbers. If a lexicon then told you that one of those symbols represented addition and the other represented multiplication, you would be able to perform the calculations created by the context-free grammar. There is no guarantee that a context-free grammar and a lexicon together generate meaningful statements.

Potential

Supplying a a computer with context-free grammar and a lexicon would, in principle, allow it to parse, or break down into component parts, sentences used in human communication to determine if they are grammatically correct. It might also tell which parts of a sentence are subject, verb and predicate. The syntax of real human languages does not match any known context-free grammar, so a computer parser isn't expected to be completely accurate.

Types

One of the key differences between a context-free grammar and human syntax is that a context-free grammar is always prescriptive--it dictates exactly how a strings are put together. In syntax, grammar can either be prescriptive or descriptive. For example, a prescriptive English grammar might prohibit use of the word "ain't." But a descriptive grammar would simply note that it is commonly used in place of the phrase "am not."

History

"Syntactic Structures," the work of linguist and philosopher Noam Chomsky, published in 1957, was a major influence on context-free grammar and syntax. Chomsky is considered to be the first to formalize how grammars can be based on parts of phrases. In this work, he identified four grammar types: context-free languages, type zero languages, context-sensitive languages and the natural languages we use every day.

References

• University of Rochester: Context-Free Grammars
• Natural Language Proessing Techniques in Prolog: Context Free Grammars
• "Introduction to Natural Language Processing: Context Free Grammar"; Andrew McCallum
• "The Syntax of Natural Language"; Beatrice Santorini, Anthony Kroch; 2007

Resources

• "Syntactic Structures"; Noam Chomsky; 2002