1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 33
Текст из файла (страница 33)
Nevertheless, all is not lost. Itturns out that for most programming languages one can construct deterministicpushdown automata that accept all syntactically correct programs. Later in thissection we shall give some heuristic rules ~rules of thumb~ that are useful forconstructing deterministic pushdown automata from suitable context-free grammars. These rules will not invariably produce a useful pushdown automatonfrom any context-free grammar; we have already said that that would be impossible. But they are typical of the methods actually used in the construction ofcompilers for programming languages.Deterministic Context-free LanguagesA pushdown automaton Al is deterministic if for each configuration there isat most one configuration that can succeed it in a computation by M. This condition can be rephrased in an equivalent way.
Call two strings consistent if thefirst is a prefix of the second, or vice versa. Call two transitions ((p, a, 13), (q, ,))and ((p, a', 13'), (q', ,')) compatible if a and a' are consistent, and 13 and 13' arealso consistent-in other words, if there is a situation in which both transitions1593.7: Determinism and Parsingare applicable. Then M is deterministic if it has no two distinct compatibletransitions.For example, the machine we constructed in Example 3.3.1 to accept thelanguage {wcw R : w E {a, b} *} is deterministic: For each choice of state ahdinput symbol, there is only one possible transition.
On the other hand, themachine we constructed in Example 3.3.2 to accept {ww R : w E {a, b} *} is notdeterministic: Transition 3 is compatible with both Transitions 1 and 2; noticethat these are the transitions that "guess" the middle of the string -an actionwhich is intuitively nondeterministic.Deterministic context-free languages are essentially those that are acceptedby deterministic pushdown automata. However, for reasons that will becomeclear very soon, we have to modify the acceptance convention slightly.
A language is said to be deterministic context-free if it is recognized by a deterministicpushdown automaton that also has the extra capability of sensing the end of theinput string. Formally, we call a language L ~ ~* deterministic context-freeif L$ = L(M) for some deterministic pushdown automaton M.
Here $ is a newsymbol, not in ~, which is appended to each input string for the purpose ofmarking its end.Every deterministic context-free language, as just defined, is a context-freelanguage. To see this, suppose a deterministic pushdown automaton M acceptsL$. Then a (nondeterministic) pushdown automaton M' that accepts L can beconstructed. At any point, M' may "imagine" a $ in the input and jump to anew set of states from which it reads no further input.If, on the other hand, we had not adopted this special acceptance convention, then many context-free languages that are deterministic intuitively wouldnot be deterministic by our definition. One example is L = a* U {anb n : n ~ I}.A deterministic pushdown automaton cannot both remember how many a's ithas seen, in order to check the string of b's that may follow, and at the sametime be ready to accept with empty stack in case no b's follow.
However, onecan easily design a deterministic pushdown automaton accepting L$: If a $ ismet while the machine is still accumulating a's, then the input was a string ina*. If this happens, the stack is emptied and the input accepted.The natural question at this point is whether every context-free languageis deterministic -just as every regular language is accepted by a deterministicfinite automaton. It would be surprising if this were so. Consider, for example,the context-free languageL = {anbmd' : m, n,p~0, and m"I- nor m "I- pl·It would seem that a pushdown automaton could accept this language only byguessing which two blocks of symbols to compare: the a's with the b's, or theb's with the c's. Without so using nondeterminism, it would seem, the machine160Chapter 3: CONTEXT-FREE LANGUAGEScould not compare the b's with the a's, while at the same time preparing tocompare the b's with the c's.
However, to prove that L is not deterministicrequires a more indirect argument: The complement of L is not context-free.Theorem 3.7.1: The class of deterministic context-free languages is closed under complement.Proof: Let L ~ ~. be a language such that L$ is accepted by the deterministicpushdown automaton M = (K,~, r,~, s, F). It will be convenient to assume,as in the proof of Lemma 3.4.2, that M is simple, that is, no transition of Mpops more than one symbol from the stack, while an initial transition places astack bottom symbol Z on the stack that is removed just before the end of thecomputation; it is easy to see that the construction employed to this end in theproof of Lemma 3.4.2 does not affect the deterministic nature of M.Since M is deterministic, it would appear that all that is required in order toobtain a device that accepts (~.
- L)$ is to reverse accepting and non-acceptingstates -as we have done with deterministic finite automata in the proof ofTheorem 2.3.1(d), and will do again in the next chapter with more complexdeterministic devices. In the present situation, however, this simple reversal willnot work, because a deterministic pushdown automaton may reject an input notonly by reading it and finally reaching a non-accepting state, but also by neverfinishing reading its input. This intriguing possibility may arise in two ways:First, 111 may enter a configuration C at which none of the transitions in ~ isapplicable.
Second, and perhaps more intiguingly, 111 may enter a configurationfrom which M executes a never-ending sequence of e-moves (transitions of theform (q, e, a)(p, {3)).Let us call a configuration C = (q, w, a) of M a dead end if the followingis true: If C f-'M C' for some other configuration C' = (q', w', a'), then w' = wand la'i 2: lal. That is, a configuration is said to be a dead end if no progresscan be made starting from it towards either reading more input, or reducing theheight of the stack. Obviously, if AI is at a dead-end configuration, then it willindeed fail to read its input to the end.
Conversely, it is not hard to see that, ifM has no dead-end configurations, then it will definitely read all its input. Thisis because, in the absence of dead-end configurations, at all times there is a timein the future in which either the next input symbol will be read, or the height ofthe stack will be decreased -and the second option can only be taken finitelymany times, since the stack length cannot be decreased infinitely many times.\Ve shall show how to transform any simple deterministic pushdown automaton M into an equivalent deterministic pushdown automaton without dead-endconfigurations.
The point is that, since M is assumed to be simple, whether aconfiguration is or is not a dead end only depends on the current state, the nextinput symbol, and the top stack symbol. In particular, let q E K be a state, a E ~3.7: Determinism and Parsing161an input symbol, and A Era stack symbol. We say that the triple (q, a, A) is adead end if there is no state p and stack symbol string 0 such that the configuration (q, a, A.) yields either (p, e, a) or (p, a, e).
That is, a triple (q, a, A) is deadend if it is a dead end when considered as a configuration. Let D ~ K x ~ x rdenote the set of all dead-end triples. Notice that we are not claiming that wecan effectively tell by examining a triple whether it is in D or not (although itcan be done); all we are saying is that the set D is a well-defined, finite set oftriples.Our modification of M is the following: For each triple (q, a, A) E D weremove from ~ all transitions compatible with (q, a, A.), and we add to ~ thetransition ((q, a, A), (r, e)), where r is a new, non-accepting state.
Finally, weadd to ~ these transitions: ((r,a,e),(r,e)) for all a E~, ((r,$,e),(r',e)), and(r', e, A), (r' , e)) for each A E r u {Z}, where r' is another new, non-acceptingstate. These transitions enable M', when in state r, to read the whole input(without consulting the stack), and, upon reading a $, to empty the stack andreject. Call the resulting pushdown automaton M'.lt is easy to check that M' is deterministic, and accepts the same languageas M (M' simply rejects explicitly whenever M would have rejected implicitlyby failing to read the rest of the input). Furthermore, AI' was constructed sothat it has no dead end configurations -and hence, it will always end up readingits whole input. Now reversing the role of accepting and non-accepting states ofM' produces a deterministic pushdown autom&ton that accepts (~* - L )$, andthe proof is complete.
•Theorem 3.71 indeed establishes that the context-free language L = {anbmcpm "I- nor m "I- p} above is not deterministic: If L were deterministic, then itscomplement, L would also be deterministic context-free - and therefore certainlycontext-free. Hence, the intersection ofL with the regular language a*b*c* wouldbe context-free, by Theorem 3.5.2. But it is easy to see that L n a*b*c* is precisely the language {anbnc n : n 2: O}, which we know is not context-free.
Weconclude that the context-free language L is not deterministic context-free:Corollary: The class of deterministic context free languages is properly contained in the class of context-free languagesIn other words, nondeterminism is more powerful than determinism in thecon ted of pushdown automata. In contrast, we saw in the last chapter that nondeterminism adds nothing to the power of finite automata -unless the numberof states is taken into account, in which case it is exponentially more powerful.This intriguing issue of the power of nondeterminism in various computationalcontexts is perhaps the single most important thread that runs through thisbook.162Chapter 3: CONTEXT-FREE LANGUAGESTop-Down ParsingHaving established that not every context-free language can be accepted by adeterministic pushdown automaton, let us now consider some of those that can.Our ovetall goal for the remainder of this chapter is to study cases in whichcontext-free grammars can be converted into deterministic pushdown automatathat can actually be used for "industrial grade" language recognition.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
