1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 36
Текст из файла (страница 36)
For our grammar, the correctaction is always to choose the longest prefix of the stack contents that matchesthe reverse of the right-hand side of a rule and reduce it to the left-hand side ofthat rule. Thus in the case above we should take the second option and reduceF * T to T.With these two rules (reduce when the top of the stack and the next input symbol are related by P, otherwise shift; and, when reducing, reduce thelongest possible string from the top of the stack) the operation of the pushdown automaton M becomes completely deterministic. In fact, we could designa deterministic pushdown automaton that "implements" these two rules (seeProblem 3.7.9).Once again, bear in mind that the two heuristic rules we have described-namely, (1) use a precedence relation to decide whether to shift or reduce,and (2) when in doubt, reduce the longest possible string- do not work in allsituations.
The grammars for which they do work are called weak precedencegrammars; in practice, many grammars related to programming languages areor can readily be converted into weak precedence grammars. And there are many,even more sophisticated methods for constructing top-down parsers, which workfor larger classes of grammars.Problems for Section 3.73.7.1. Show that the following languages are deterministic context-free.(a) {amb n : m =1= n}(b) {wcw R : wE {a, b}*}Chapter 3: CONTEXT-FREE LANGUAGES174(c) {camb n : m i=- n} U {da mb2m : m 2: O}(d) {amcb n : m i=- n} U {a mdb 2m : m 2: O}3.7.2. Show that the class of deterministic context-free languages is not closedunder homomorphism.3.7.3.
Show that if L is a deterministic context-free language, then L is not inherently ambiguous.3.7.4. Show that the pushdown automaton M' constructed in Section 3.7.1 acceptsthe language L, given that M accepts L$.3.7.5. Consider the following context-free grammar: G = (V, I;, R, S), where V ={C),.,a,S,A}, I; = {(,),.,}, and R = {S --+ D,S --+ a,S --+ (A),A--+S, A --+ A.S} (For the reader familiar with the programming language LISP,L(G) contains all atoms and lists, where the symbol a stands for any nonnull atom.)(a) Apply Heuristic Rules 1 and 2 to G. Let G' be the resulting grammar.Argue that G' is LL(l). Construct a deterministic pushdown automaton Maccepting L(G)$.
Study the computation of M on the string ((()).a).(b) Repeat Part (a) for the grammar resulting from G if one replaces thefirst rule by A --+ e.(c) Repeat Part (a) for the grammar resulting from G if one replaces thelast rule by A --+ S.A in G.3.7.6. Consider again the grammar G of Problem 3.7.5. Argue that G is a weakprecedence grammar, with the precedence relation shown below. Constructa deterministic pushdown automaton that accepts L(G)$.laa((..;)$..;..;..;)..;..;AS..;..;3.7.7.
Let G' = (V,I;,R',S) be the grammar with rules S --+ (A),S --+ a,A --+S.A, A --+ e. Is G' weak precedence? If so, give an appropriate precedencerelation; otherwise, explain why not.3.7.8. Acceptance by final state is defined in Problem 3.3.3. Show that L is deterministic context-free if and only if L is accepted by final state by somedeterministic pushdown automaton.References1753.7.9. Give explicitly a deterministic pushdown automaton that accepts the language of arithmetic expressions, based on the nondeterministic pushdownautomaton M and the precedence table P of the last subsection.
Your automaton should look ahead in the input by absorbing the next input symbol,very much like the pushdown automaton M4 of the previous section.3.7.10. Consider the following classes of languages:(a) Regular(b) Context-free(c) The class of the complements of context-free languages(d) Deterministic context-freeGive a Venn diagram of these classes; that is, represent each class by a "bubble," so that inclusions, intersections, etc.
of classes are reflected accurately.Can you supply a language for each non-empty region of your diagram?REFERENCESContext-free grammars are a creation of Noam Chomsky; seea N. Chomsky "Three models for the description of languages," IRE Transactionson Information Theory, 2,3, pp. 113-124, 1956, and also"On certain formal properties of grammars," Information and Control, 2,137167, 1959.In the last paper, Chomsky normal form was also introduced.
A closely r-elated notationfor the syntax of programming languages, called BNF (for Backus Normal Form orBackus-Naur Form), was also invented in the late 1950s; seea N. Chomsky"Revised report on the algorithmic language Algol 60," Communications of the ACM, 6, 1, pp. 1-17, 1963, reprinted in S. Rosen, ed., ProgrammingSystems and Languages New York: McGraw-Hill, pp. 79-118, 1967.Problem 3.1.9 on the equivalence of regular grammars and finite automata is froma P. Naur, ed."Finite-state languages," Information and Control, 1,pp.
91-112, 1958.The pushdown automaton was introduced ina N. Chomsky, G. A. Miller"Automatic syntactic analysis and the pushdown store," Proceedings of Symposia on Applied Mathematics, Vol. 12, Providence, R.L: American Mathematical Society, 1961.Theorem 3.4.1 on the equivalence of context-free languages and pushdown automatawas proved independently by Schutzenberger, Chomsky, and Evey.a A.
G. Oettinger"On context-free languages and pushdown automata," Information and Control, 6, 3, pp. 246-264, 1963.a M. P. SchutzenbergeroN. Chomsky "Context-free grammar and pushdown storage," Quarterly ProgressReport, 65, pp. 187-194, M.LT. Research Laboratory in Electronics, Cambridge,Mass., 1962176Chapter 3: CONTEXT-FREE LANGUAGESo .T. Evey "Application of pushdown store machines," Proceedings of the 1963 FallJoint Computer Conference, pp. 215-217. Montreal: AFIPS Press, 1963.The closure proper·ties presented in subsection 3.5.1, along with many others, werepointed out ino V.
Bar-Hillel, M. Perles, and E. Shamir "On formal properties of simple phrasestructure grammars," Zeitschrijt for Phonetik, Sprachwissenschajt und Kommunikationsforschung, 14, pp. 143-172, 1961.In the same paper one finds a stronger version of Theorem 3.5.3 (the Pumping Theoremfor context-free grammars; see also Problem 3.5.7). An even stronger version of thattheorem appears ino W. G. Ogden "A helpful result for proving inherent ambiguity," MathematicalSystems Theory, 2. pp. 191194, 1968.The dynamic progr'amming algorithm for context-free language recognition was discovered byo T. Kasami "An efficient recognition and syntax algorithm for context-free languages," Report AFCRL-65-758 (1965), Air Force Cambridge Research Laboratory, Cambridge, Mass., and independently byo D. H.
Younger "Recognition and parsing of context-free languages in time n 3 ,"Information and Control, 10, 2, pp. 189-208, 1967.A variant of this algorithm is faster when the underlying grammar is unambiguouso .T. Earley "An efficient context-free parsing algorithm," Communications of theACM, 13, pp. 94-102, 1970.The most efficient general context-free recognition algorithm known is due to Valiant.It runs in time proportional to the time required for multiplying two n x n matrices,currently O(n 2 . 3 ...
).o L. G. Valiant "General context-free recognition in less than cubic time," Journalof Computer and Systems Sciences, 10, 2, pp. 308-315, 1975.LL (1) parsers were introduced ino P. M. Lewis II, R. E. Stearns "Syntax-directed transduction," Journal of theACM, 15, 3, pp. 465-488, 1968, and also ino D. E. Knuth "Top-down syntax analysis," Acta Informatica, 1, 2, pp. 79-110,1971.Weak precedence parsers were proposed ino .T. D. Ichbiah and S.
P. Morse "A technique for generating almost optimal FloydEvans productions for precedence grammars," Communications of the ACM, 13,8, pp. 501-508, 1970.The following is a standard book on compilerso A. V. Aho, R. Sethi, .T. D. Ullman Pr'inciples of Compiler Design, Reading,Mass.: Addison-Wesley, 1985.Ambiguity and inherent ambiguity were first studied ino N.
Chomsky and M. P. Schutzenberger "The algebraic theory of context freelanguages," in Computer Programming and Formal Systems (pp. 118-161), ed.P. Braffort, D. Hirschberg. Amsterdam: North Holland, 1963, andReferences177o S. Ginsburg and J. S. Ullian "Preservation of unambiguity and inherent ambiguity in context-free languages," Journal of the ACM, 13, 1, pp.
62-88, 1966,respective/yo Greibach normal form (Problem 3.5) is fromo S. Greibach "A new normal form theorem for context-free phrase structure grammars," Journal of the ACM, 12, 1, pp. 42-52, 1965.Two advanced books on context-free languages areo S. Ginsburg The Mathematical Theory of Context-free Languages, New York:McGraw-Hill, 1966, ando M. A. Harrison Introduction to Formal Language Theory, Reading, Massach.:Addison-Wesley, 1978.Turing Machines4.1 THE DEFINITION OF A TURING MACHINEWe have seen in the last two chapters that neither finite automata nor pushdownautomata can be regarded as truly general models for computers, since they arenot capable of recognizing even such simple languages as {anbnc n : n ~ O}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
