Java Reference
In-Depth Information
The following grammars are relevant to programming language translation:
•
Regular grammars, which are less powerful than CFGs
•
Context-sensitive and unrestricted grammars, which are more powerful
Regular Grammars
A CFG that is limited to productions of the form A
→
aBor C
→
d is a
regular
grammar
. Each rule's RHS consists of either a symbol from
Σ∪{λ}
followed
by a nonterminal symbol or just a symbol from
. As the name sug-
gests, a regular grammar defines a regular set (see Exercise 15.) We observed
in Chapter 3 that the language
Σ∪{λ}
[
i
]
i
{
|
i
≥
1
}
is not regular. This language is
generated by the following CFG:
1 S
→
T
2 T
→
[T]
3
| λ
This grammar establishes that the languages definable by regular grammars
(regular sets) are a
proper
subset of the context-free languages.
Beyond Context-Free Grammars
CFGs can be generalized to create richer notational mechanisms. A
context-
sensitive grammar
requires that nonterminals be rewritten only when they
appear in a particular context (for example,
), provided the rule
never causes the sentential form to contract in length. An
unrestricted
or
type-
0 grammar
is the most general. It allows arbitrary patterns to be rewritten.
Although context-sensitive and unrestricted grammars are more powerful
than CFGs, they also are far less useful for the following reasons:
α
A
β→αδβ
•
E
cient parsers for such grammars do not exist. Without a parser, a
grammar definition cannot participate in the automatic construction of
compiler components.
•
It is di
cult to prove properties about such grammars. For example, it
would be daunting to prove that a given type-0 grammar generates the
C programming language.
E
cient parsers for many classes of CFGs do exist. Hence, CFGs present a
nice balance between generality and practicality.
