Context-Free Grammars
In abstract mathematical terms, a language is a set of alphanumeric strings of finite length over some fixed, finite alphabet. A grammar is a set of production rules that specify how valid strings in the language may be got--every formal language has a formal grammar implicitly or explicitly associated with it, and vice versa.
Context-free grammars constitute members of a certain class that is described as containing generators of computer languages. Computer languages have rules about how strings must be generated in order to be syntactically correct and meaningful. Grammars are thus needed that generate precisely the correct strings and no others. Two major approaches are possible in respect of the specification of the relationship between grammars and languages--either the language must be specified formally and then a grammar constructed that generates it; or else, a grammar must be specified formally and the language that it generates must be derived analytically.
Although each approach has its own advantages, it is common for theoretical analyses to start by defining a grammar first and then examining the strings it generates. In practical uses of languages, however, there is rarely an effort to define a formal grammar that would generate the language (for example, there is no well-studied formal grammar to generate valid statements in Java)--the principles of such languages are well understood, and it is accepted that a formal grammar could be derived if enough effort were expended for it.
A context-free grammar formally is specified by the following: a finite set of variables (intermediate symbols), an alphabet, a finite set of production rules, and a distinguished start symbol. The production rules specify how strings are generated, and thus impose structure on the language. Such structure may consist of ensuring the presence--or absence--of specific combinations of elements of the alphabet.
To take an example, let us study a simple grammar with the alphabet {a, b, c}, with the restriction that the language consists of any and all strings, except for the string abc itself and any strings that contain abc as a substring.
Such a grammar is given by:
- S bS | cS | aB |
- B aB | cS | bC |
- C aB | bS |
Each production rule specifies a certain way that an existing variable can be replaced by another variable, symbol, or some combination of these. S is the distinguished start symbol. It can be replaced by a b and itself; by successive application of this very rule, we can generate indefinitely long finite strings of the form bbb..., for example. Two other such production rules are given, separated by column bars, and there is also the possibility of replacing S by the null terminal , which cannot be replaced with anything else.
Only one variable (S, B, or C) may be present in a string at any time. If an S is present, then an abc has not been introduced into the derivation yet, hence no abc substring is yet present. Now, the variable B can only be seen with a previous instantiation of the terminal a. In order to generate a substring abc, it is therefore necessary to replace the aB derived from the start symbol A, with a bC. However, because C cannot be replaced with an initialc using any production rule, the total substring abc can never be obtained.
A little further reasoning along these lines should convince you that any other strings can be generated as long as they do not contain the forbidden substring abc--specifically, note that all pairwise combinations of the three elements of the alphabet can be generated.
Context-free grammars are sufficient to describe computer languages, but are inadequate tools to model and describe human language generation and parsing. Meanings in human language are dependent upon a rich context, and it is not possible to specify context-free rules to derive them. For instance, the sentence, "Visiting relatives can be boring" has two meanings--either that relatives who visit inflict boredom, or else that one suffers from boredom when one visits relatives. However, a similar sentence, "Visiting hospitals can be boring" has only one meaning. Yet, the fact that it has only one valid meaning is known to us solely from real-life contextual knowledge--viz., that hospitals do not come to visit--rather than from the syntax rules of grammar themselves.
This is the complete article, containing 710 words
(approx. 2 pages at 300 words per page).
