Given a word and a context-free grammar , how do we determine if ?
There are in general two ways to proceed. Start from , and proceed backward to find such that . Keep going until a derivation is found. This procedure is known as the bottom-up parsing of . The other method the top-down approach: begin with the starting symbol , and work its way down to , so .
As with the bottom-up approach, finding a derivation of from the top-down may be time consuming, if one is lucky enough to find a derivation at all.
There is a class of grammars, known as the grammars, which make the top-down parsing of a word natural and direct. The first in means scanning the symbols of from left to right, the second stands for finding a leftmost derivation () for , and means having the allowance to look at up to symbols ahead while scanning.
Definition. Let be a context-free grammar such that is not a production of , and an integer. Suppose with a a production in a leftmost derivation of :
Let and be the prefix of of length (if , then set ).
Then is said to be if for any , with as a prefix, such that there is a production in a leftmost derivation of :
implies that .
In a leftmost derivation of a word , call a prefix of is a leftmost descendant of a production if is . Then the definition above can be restated in words as follows:
Given a leftmost derivation of a word , a production used in is uniquely determined up to symbols beyond the prefix of which is a leftmost descendant of the production. In other words, if and are leftmost derivations of and which agree on symbols beyond the common prefix , where is both a leftmost descendant of used in , and a leftmost descendant of used in , then and are the same production, i.e. .
Every is unambiguous. Furthermore, every grammar is (http://planetmath.org/LRk).
Given a context-free grammar and , there is an algorithm deciding whether is .
The grammar over , with productions , and is but not . It is not hard to see that is the set . On the other hand, the grammar over , with productions
also generates , but is instead.
The grammar over , with productions
is not for any .
Definition A language is said to be if it is generated by an grammar. The family of languages is denoted by .
It is easy to see that an contains no more than one word. Furthermore, it can be shown that
and the inclusion is strict. If denotes the family of -free languages, then
Given two grammars and , there is an algorithm that decides if .
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
|Date of creation||2013-03-22 19:00:54|
|Last modified on||2013-03-22 19:00:54|
|Last modified by||CWoo (3771)|