GENERALIZED B?TTON-UP PARSING Thomas Gregory Szyruanski TR 73--H168 A Thesis Presented to the Faculty of the Graduate School of Cornell University for the Degree of Doctor of Philosophy May, 1973 research was supported by the Grant GJ-28176 and GJ-3)l7lX:? National Science Foundation This unaer GLNEFj?tIZED BOTTOM-UP PARSING Thomas Cregory Szymanski, Ph.D. Cornell University, 1972 ABST?CT In this thesis we present a decision procedure for testing the correctness of a broad class of bottom-up pars- ing machines. Motivated by the work of Col?erauer and Willi?T.s, we allod our parsers to find any simple phrase (not necessarily the leftnost) in the input string. Such a parser can be implemented on an autornaton using two pushdown stores and can in fact produce a complete parse for an input string in linear tie with respect to the length of the input. Certain restrictions are necessary in order for the method to work, but nevertheless it is sufficiently general to handle most existing classes of parsers. Moreover, the adjus??.ent of certain parameters to this decision procedure gives rise in a natural way to such classes of gramears as the LP.(k) class of Knuth, the BRC class of Floyd and the BCP class of Williams. Further adjustment of these parameters suggests other, more general, classes of parsable gramears which we investigate here for the first time. Anong these new classes of gramnars is one first sug- gested by Knuth and given the name LR(k,t) This class is a generalization of the tR(k) method and intuitively is that class of gr??:umars for which it is possible, n any sentential for'n, to find one of the t leftnost simple phrases gi?en only that portion of the string to the left of the phrase end the first k characters to its right. We give an c?zart onstruc- tion for parsers of this class and present the s?rprs1ng fact that these gr??ars can be parsed us?ng a deternin?stic pushdown automaton. We also investigate a class herein called LP.(k,?) in which we completely relax the condition that the selected phrase be in any certain location. This latter class, ?ich represents the ultimate left to right botton-up parser, is shown to be too general to have "nice decidability proper- ties. A final class of gxamm?rs investigated is designated FPFAP(k), that is, the class of grar%?nars which are parsable in a left to right fashion by a finite state automaton using k characters of lookahead. This class is shoT. to lie strictly between the tR(k,t) end tR(:-,?) classes. We conclude by demonstrating the relationships between these and other classes of grarroars, not only from the point of view of the gremmars themselves but also with regard to the classes of languages induced by the granT?rs. BIOGRAPHICAL SKETCH Thomas Gregory Szymanski was born in Cleveland, Ohio, on December 13, 1946, the son of Mr. and Mrs. Walter Anthony Szvmanski. He was graduated from Case Western Reserve University in June, 1968, with the degree of Bache- lor of Science, magna cum laude, having ma3ored in Engin- eering. He then spent two years at the University of Wis- consin, obtaining a Master of Science degree in Computer Science. In September of 1970 he entered the graduate school at Cornell University to further his education in Computer Science. Mr. Szymanski is a member of Tau Beta Pi and the Asso- ciation for Computing Machinery. He is married to the former Karen White. ii to my Grandmother iii ACKNOWLEDGEMENTS I would first of all like to express my gratitude to Professor John H. Williams, my thesis advisor, for his continued guidance and encouragement not only during the preparation of this dissertation, but also during those arduous nonths spent searching for a topic. I am also in- debted to Professors Juris Hartmanis and Robert Walker who served on my special committee. The National Science Foundation partially supported this work through grant GJ-33l7l. Gayle Mykita did a fine ?ob of preparing the final manuscript. Finally, and most importantly, I thank my wife, Karen', whose love and confidence constituted the real driving force behind this thesis. iv TABLE OF CONTENTS BIOGRAPHICAL SKETCH ACKNOWLEDGEMENTS TABLE OF CONTENTS PAGE REFERENCES Terms Grammars Figures Notation Chapter 0 PRELIMINARIES 0.1 Introduction and Background 0.2 Grammars, Languages and Phrases 0.3 Parsing 0.4 Description Languages 0.5 Miscellaneous Notation Chapter 1 PARSING WITH PATTERNS 1.1 Finding Phrases Using Patterns 1.2 Parsing with Patterns 1.3 A General Model of Bottom-up Parsing 1.4 Implementation of Pattern Parsing 1.5 Limitations of the Model Chapter 2 EXACT CONTEXT METHODS 2.1 Non-canonical Parsing ii iv v vii viii `:iii ix 10 15 18 18 26 31 36 46 51 51 2.2 Informal Development of LR(k,?) Parsers 2.3 Fonnal Development of LR(k,?) Parsers 2.4 properties of LR(k,?) Grammars 2.5 Development of LR(k,t) Parsers 2.6 Properties of LR(k,t) Grammars Chapter 3 INEXACT CONTEXT METhODS 3.1 DeRemer?s Simplification of the LR(k) Technique 3.2 The SLR(k,t) and SLR(k,?) Methods 3.3 The REDNEXT Method 2.4 The FPFAP(k) Technique. Chapter 4 RELATIONSHIPS BETWEEN ThE CLASSES 4.1 Relations in Grainmar Space 4.2 Relations in Language Space 4.3 Decidability Properties Chapter 5 CONCLUSIONS 5.1 Future Work 5.2 Summary 56 66 77 85 loo 109 109 116 124 135 147 147 155 165 167 167 170 BIBLIOGRAPH? 172 vi PAGE REFERENCES TERMS bounded context grammar 2 non-canonical parsing 2 phrase 5 handle 6 (generalized) bottom-up parse 7 reduction 7 reduction sequence 7 complete reduction sequence 8 description language 11 bracketed sentential form 11 phrase language 13 reduction pattern .18 bounded pattern 19 spanning pattern 19 parsing pattern 19 parsing scheme 26 leftmost pattern 31 bounded right context 33 bounded context parsable grammar 34 phrase finding automaton 40 unambiguous bracket 66 itor:? 66 valid item 66 LR(k,t) Item 91 valid LR(k,t) item 91 right context string 93 equivalent items 93 count 95 inexact context method 114 regular separable 142 vii GP??MARS 20 41 48 51 53 54 75 83 84 85 107 110 115 117 125 135 139 152 152 152 153 157 167 FIGURES G1 G2 G3 G4 G5 G6 G7 G8 G9 G10 G11 G12 G13 G14 G15 G16 G17 G18 G19 G20 G21 G22 G.23 G24 1.1 42 1.2 47 2.1 55 2.2 64 2.3 65 2.4 88 2.5 89 3.1 112 3.2 129 3.3 130 3.4 137 3.5 138 3.6 141 4.1 148 4.2 149 4.3 154 viii Notation v 93 k,t SLR(k) 113 SLR(k,t) 116 SLR(k,?) 116 RNP(k) 128 UCFL 156 BC 2 SF(G) 5 t(C) 5 B 10 DL(G) 11 m 12 13 15 TRUNCk 15 NEXTk 15 REDNEXTk 16 16 h 16 BRC 33 LR(k) 33 LRR 33 BCP 34 LR(k,t) 51 LR(k,?) 53 FPFAP(k) 35,139 RPP 35 2PDA 37 PFA 40 Vk 67 ix Cha ter 0 PRELIMINARIES u.lintroauctionandBac?qrounu The subject matter of this dissertation is the parsing of sentences generated by context free grarnr???ars. A suitable formalism and adequate solutions already exist for this gen- eral problem; see, for instance, Hopcroft and Ullnan [HU 69] and Earley rEa 701. However, since the main motivation for studying this problem is to facilitate the design of com- puter languages and, above all, to develop techniques for the quick, and automatic, "understanding" of such lancuages, we feel that continued attention to this problem is in order. Historically, the parsing problem has beem attacked from two different directions, which we will call "low level" and "high level" approaches. The "low levol" approach has resulted in a large collection of special case techniques which work for various restricted subclasses of the context free grammars. These methocs are always intended to be ef- ficient, practical and applicable to most "garden variety" programming languages. As a consequence, these approaches usually are applicable only to subcases of the deterministic context free grammars. The reader is referred to Aho and Ullman (AU 721 for a detailed description of many of these techniques. The "high level" approach on the other hand attempts to devise algorithms for the general case, namely the parsing --H2--H of arbitrary context free grammars. These approaches tend to lose efficiency because of their ability to handle those pathological conditions (such as ambiguity) which cannot be alloved to occur in programming languages In this thesis we have tried to attain a sort of "middle ground" in which we develop techniques for classes of gram- mars which are much broader than the deterministic grammars and yet sufficiently restricted to avoid those pathologies referred to above Our ideas are drawn from essentially four sources. Floyd iFl 641 in his paper on bounded context (5C) grammars, proved the correctness of his methods by doing a formal anal- ysis of all the ways in which his method could err, and them showing that none of these errors could actually arise. We will extend this idea in Chapter 1 to produce a general model of bottom-up parsing which turns out to be sufficiently powerful to model almost all existing "low level" parsing techniques. Furthermore, the model suggests new parsing techniques which will be investigated at various points throughout the dissertation. Another wellspring of ideas was furnished by Knuth [Km 651 when he showed that it was possible to develop pars- ing methods (viz. the tR(k) method) which use an unbounded amount of context and yet still could be implemented in am ?fficient manner. In this same paper he foreshadowed the concept of "non-canonical parsing" or parsing in which --H3--H reductions can be made at any place in the input string in- stead of at the leftmost place where a reduction is possible. This idea of non-canonical parsing was developed by both Colmerauer [Co 70] and Williams [Wi ?9] ap.d shovn to be a useful addition to the bag of tricks used to construct parsers. In Chapter 2 we will extend the LR(k) rne??od to incor- porate non-canonical parsing. The technique so developed (the tR(k,?) method) will still be within the frar?work of the model of Chapter 1 and will provide us with a forrnaliza- tion which will aid us throughout the rest of this work. In the rest of Chapter 2 and all of Chapter 3, we will produce several new parsing techniques which are suggested by both the parsing model of Chapter 1 and by the study of the draw- backs of the LR(k,?) method. Finally in Chapter 4?we will investigate several dif- ferent kinds of relationships between the parsing techniques which we have developed. --H4--H 0.2(3r?Th.?nars,?anguagesandPhra?ee In this section we review basic terminology and exhibit our notation We assume that the reader is familiar with such concepts as strings, formal grammars, formal languages, finite state autornata (fsa), push down automata (pda), reg- ular expressions, decidability and undecidability. We denote a context free grammar (cfg) by a quadruple (V,VT,P?S) where v is the vocabulary of the grammar VT? V is the terminalvocabulary P C (V?VT)XV is a finite set of productions S E V?VT is the startsymbol Individual productions of a grammar are written Aj x? where Ai designates whatever non-terminal is the left side of the ith production and x? designates that strinq of v* which is th. the right side of the 1--H production. We allow ernpty right sides and refer to such productions as ?-rules. We also use the symbol (or when we wish to indicate which grammar is G being used) to denote the application of a production to a string. Thus if o+?wA?y and ?w?x?y we will write o+ ?. An asterisk (*) written above a relation denotes the reflexive and transitive completion of that relation and a plus sign (+) the transitive completion. The special endmarkers ? and ? are used to delimit the ends of strings. In certain places we will assume multiple copies of the endmarkers, but such --H5--H usage will always be clear from the context in which it is necessary. Both ? and ? are considered elements of VT We designate by SF(G) tne set or sententialforr,s de--H rivable according to the grammar G, that Is, sF(G) fw E V* s ? The language of G, written L(G), is the set of terminal strings derivable by G, that is, V* L(G) = SF(G) ? We will occasionally have need to discuss certain re- stricted forms of derivations. A derivation S w1 w2 ... + Wn is said to be a rightmostderivation if at each step the production being applied is applied to the rightmost non-terminal in the current sentential form w?. We symbolize a rightmost derivation step by rm+ Similarly, leftmost deri- vations are denoted by l+m Let us introduce here an example grammar. G1: 5 tSR S+b t+a a + aa Thus L(G1) = (a?ba2? n > 0) We say that x. is a phrase of a sentential form wx.y if 1 1 there is a derivation 5 ? wA?y wx?y. Other authors have used the more cumbersome term "simple phrase" to denote this --H6--H s?'ne concept. Clearly, if G is unambiguous, then there is a unique set of phrases corresponding to any sentential form of a. Thus for G1, the sentential form "abaa" has three phrases, namely (from left to right) "a", "b" and "aa". Phrases can be visualized in terms of the derivation tree corresponding to each sentantial form. Phrases then correspond to the sons of a node A such that all sons of A are leaves. Thus for example, the following Cl tree cor- responds to "abaa". The phrases corresponding to this tree are now clearly defined. The leftmost phrase of a sentential form is called a handle. --H7--H 0.3Parsing The problem to which this thesis is directed is the problem of determining the structure of strings generated by context free granhmars. Suppose that C is a CFG and that s w0 ? w1 w2 -. ? Wn is a derivation according to G. This derivation can be represented by n pairs of integers (p0,?0), (p1,i1)??n--Hl'?n--Hl? where eacTh pair tells us that Wj+1 can be produced fro? v. by applying production Pj to the non-terminal in location ? of w. - The reverse of this sequence is called a generalizedbottoo-up parse [Au 72]. We distinguish this concept fro? the term "bottom-up parse" which has cone to imply a parse corres- ponding to a rightmost derivation. From now on vs will simply refer to bottom-up parsing when in fact we actually mean generalized bottom-up parsing. A reduction is the process of taking a grarrtrnar G and a sentential form ?=X1???Xn and performing the following operations: 1) find two integers p end L such that Xp Xt?k+l...Xt?lX? ?here k = Ix p 2) output the pair (p,t). 3) replace the characters Xt?k+l. . .Xi in ? with A p and renumber the characters of ? accordingly. A reductionsequence is a sequence of pairs (p1,t1), (p2,t2)(Pm?tm) obtained by iterating the process of --H8--H making reductions on ? and concatenating the output. Suc- cessive instances of o+ are designated Wl?W2wm+l. A cor.?olete reduction sequence is a reduction sequence which reduces a string to the point where no further reductions can be made. Lemma0.1 Let ? = (p1,i1)... (pm?tm) be a complete reduction sequence for some string w0. Then Tt is a bottom-up parse if and only if wm+1 = 5. Proof: ? Since II is a bottom-up parse, the reversal of II is a derivation which he definition, starts with the distinguished sentential form 5. eance wm+l = 5 ? Clearly the reversal of a reduction sequence is a derivation. Since Wm+l = 5, the reversal of fl corres- ponds to a derivation according to G. But now the reversal of this derivation (i.e. It) i= by definition a bottom-up parse. q.e.d. The crucial step in parsing a sentence of some grammar is step 1 of the reduction algorithm, namely finding a "cor- rect" instance of Xi For example, consider the string o+ = aabaaaa EL(G1). Applying the reduction algorithm in- discriminantly to ? can yield such outputs as (3,A), (4,2) or (4.6) which would reduce o+ respectively to aabLaaa, ??aaaa or eabaRa. Obviously, none of these strings is what we had intended to produce. --H9--H Accordingly, the essential challenge of bottom-up parsing is to select a good "choice function" for use in the reduc- tion algorithm. Traditionally this choice function is imple- mented through examination of the context of a suspected phrase, that is, the characters immediately adjacent to it. We shall see that the amount and format of the context so used characterize most persing strategies. --H10--H 0.4Descriptiontanguages Although the derivation tree is probably the clearest description of a sentential forn, it frequently turns out that the fornal rianipulation of such trees is a cunbersome process. Accordingly, we will introduce an alternative no- tation for describing string structure. Suppose we are dealing with a grammar r = (V?VT?P?S) with p productions. We picY. a set B of p new terninal characters and denote the me=bers of B by ]? for 1 < i < p. We then define a new grammar G1 (V U B, VT U B, ?I 5) where now P' also has p productions and for every production A. x. occuring in p, 1 1 p1 contains the production Ai For example, we now have G11: 5 tSR]1 5 bJ2 L al3 R aa)4 The important point is that every application of a pro- duction in a derivation according to G1 leaves its mark" in the?string produced. Thus by examining the brackets appear- ing in any sentential form of G1, we can determine exactly its structure. What we have actually done here is to define a linear representation of a derivation tree. Thus corres- --H11--H ponding to the G1 tree appearing below s we have the following string which appears in t(G1) a]3a]3b]2aaJ4]1aa14]1 Lemma0.2 If G is an arbitrary context free grammar and G' is formed as described above, then G' is an unam- biguous context free gr?mmar. Proof: G is clearly BC(0,0) and hence unambiguous q.e.d. We will call SF(G') the descriptionlan?uage for G and abbreviate it DL(G). Notice that DL(G) includes bracketed representations not only for every terminal string of G but also for every sentential form of G. Hence we call the ele- ments of DL(G) the bracketedsententialforms of G. In this dissertation, we will have frequent need to --H12--H convert back and forth between sentential forms and bracketed sentential forms. We will do this by an erasing napping n: V ti B V defined by m(X) x if xt v - c if x E B Notice that m is a hononorphism with respect to concatena- tion. Accordingly we will henceforth treat m as being de- fined on (V U 3)* We will also need to consider the inage 9f sets of strings under m and will write m(S) to denote such an image. It will always be clear from the context whether the argument to n is a string or set of strings. In bottorn-up parsing, we are actually concerned only with those places in a string where a phrase occurs and care not about the structure of the derivation tree on higher levels. Thus, in parsing the string ? = aabaaaa of G1 we are not concerned about the completestructure of o+ which is the string o+` = a]3a]3b]2aa]4]1aa14]1 E DL(G), but rather with the ?h=,,=structure of o+ which is simply the string ?" = a] 3a] 3b]2ae]4ea]4. Notice that o+" can be easily produced from ?` by erasing those brackets which do not indi- cate phrases (i.e. the right hand side of the production is not fully reduced, or in tree terms, the sons of the node in question are not all leaves) To facilitate this sort of construction we will define a new context free language in which brackets will designate --H13--H exactly those places where phrases occur in the sentential forms of sane grarninar G. This language will be called the phraselanguageofG and written PL(G). It in a sinple mat- ter to define Pt(G) in terms of a genoralize scr??e?t?al machine g applied to r)L(G). In particular, g erases all brackets in its input string except for thoso which i:e?edi- ately follow the characters of the right hand side of the corresponding production. We can also define DL(C) grar?at- ically, which we do below: Suppose G = (V?VT?P?S) has p productions. Let V = (A A E v) and B = fj. I < i 4< p) be sets of new symbols. We define G = (V U V U a, v u ?, p, ?) where P includes all productions of the form Ai Xiii and of the form A. ? where x. is the same as x. except at least one character has been given a "hat" whenever A. x. was a produc- 1 I tion in p. Then we define PL(G) = L(G) u (510) Note carefully that we have included the distinguished sen- tential form in a special way. For example, G1: 5 LSR]1 --H14- S tSR tSR tSR s ? tSR SR tSR s ?+ tss b]2 g t a13 a 5 aa ?a aa PL(G1) thus contains, for exarnple, the desired string a]3aJ3bJ2aal4aa]4 where now each bracket designates a phrase. The reader should verify that the "bracket eraser m has the following effect. sF(G) = ni(Dt(G)) = It is also true that G is ambiguous if and only if rn applied to PL(G) is not a one-to-one napping. --H15--H 0.5MiscellaneousNotation In this section we present a smorgasboard of notational devices which will be of use to us in various parts of this dissertation- We record here our conventions (which are sli?htly non- standard) for naming strings: are tarminal character A,C,D,E,F,S are non-terminal char?cters U,VZ are either terminal or non-tera?nal characters are elements of (VU B) * u,vz are elements of V* B will never be used to denote a character or string because its use is reserved for denoting the set of brackets corres- ponding to some grammar. In addition to the above, we will frequently use o+ and ? to be either sentential forms or bracketed sentential forms. The notation a denotes the number of characters im the string a whereas the function TRUNCk(a) yields the first k characters of a, that is, TRUNC?(a) = a if a < k - S if sS,y such that a = Sy and Ia = The function NEXTk(A) yields a set of k letter strings each of which 3-fl follow the non-terminal A in some sentential --H16--H form. More specifically, NEXTk(A) = fy E ? ?w,z St. S ? wAyz? Frequently we will want those elements of NEXTk(A) which occur in derivation trees which are fully "pruned" to the right of A, that is, those k letter strings which repre- sent fully reduced right contexts for the non-terminal A. Accordingly, we offer as our next definition: REDNEXTk(A) = fy E vk I 5w,z st. S wAyz). l's In places we will need to introduce a special marker in- to strings. This marker is written 4, and is always taken to be disjoint from the vocabulary or brackets for any grammar under consideration. The nap h: V U B U f*) V U B defined by h(X) = x if x E V U 13 = ? if x = * is a honomorphism with respect to concatenation and will be used to insert or delete the special marker. Finally, let us warn the reader of a possible source of confusion in our notation. We frequently will use expres- sions such as LR(k) and BRC(m,n) which involve parameters. We will almost always intend these parameters to be free in the sense of standing for all possible applicable values. Thus when we refer to "the class of LR(k) gram'nars", we ac- tually mean the class of all grammars which are LR(k) for --H17--H some value of k, or symbolically, (G ?k St. G is Ls(k)). When we intend the parameters to be bourd to a specific value, we will state explicitly that the parameters in question are fixed Chapter1PARSINGWITHPATTERNS 1.1Finding?h?a???with?a??rn? In this section we will develop sufficient groundwork for the presentation of a decision procedure for the correct- ness of bottom-up parsers. Such parsers can be characterized by the set of strings, or contexts, surrounding those occur- ences of phrases which are reduced by the parser. For exam- pie, a Bounded Context parsing machine as envisioned by Floyd [Fl 64] can be viewed as a collection of pairs of finite strings, each pair of which corresponds to an acceptable con- text for the reduction of some phrase. Similarly, an LR(k) parsing machine can be viewed as a collection of pairs of regular sets and finite strings, each pair again specifying an acceptable context for the reduction of the leftmost phrase of a right sentential form. We now state a few definitions to make this concept more precise. A reductionpattern for the ith production of some gram- mar G is a pair (Ri) such that RC v x.?V* Such a pattern is said to apply to a string o+ if o+ is of the form .. and wx?#y t R. Any such application induces a reduction on o+ which is a new string o+` of the form . where the indicated occurences of w and y in o+` are the same occurences as indicated in o+. Certain formats of patterns occurs frequently enough to warrant special names. Many existing parsing methods for --His--H --H19--H example, restrict themselves to some fixed amount of look- ahead (or lookbehind) whereas others allo? ccr?lete kno?ledge of whatever amount of the input string has already been read. We say that a reduction pattern (R,i) is kboundedon theleft (for some integer k) if ? R ir?iIas < k. (R,i) is said to be ?F??????theleft f ? irrplies w E ?v* We similarly define right bounded and right spanning patterns. In order to be able to utilize a reduction pattern for parsing, we must observe the following condition. In any application of a pattern to sentential form, it must always be the case that in every possible brackating of that senten- tial form, the instance of x. discovered by the pattern must actually be an immediate A. derivative. In other words, the reduction pattern should avoid making reductions cf things which might not be phrases. We formalize this reguirar?ent as follows. A parsi????attt:i? is a reduction pattern (x,i) such that if o+ = vwx?yz E SF(G) and wxi#Y E R then t m?1(?) fl Pl(C) , ? can be written ?P1V2XiJit3tP4 where m(?1) = v = v = y tet us pa'?-??% for a moment and consider some examples Let G2 be defined by --H20--H 5 LSR M N R aa M?b N?b Consider the reduction pattern (?a4b),4). This pattern is a parsing pattern because the center of any sentential form of G2 is "marked" by an occurence of either S,M,N or b. Since anv occurence of an a to the left of center is an i"nodiate derivative, the reduction pattern always func- tions correctly. Similarly, the pattern ((a#L),4) is a parsing pattern because an L can occur only in the left portion of a senten- tial for? and therefore any instance of an a still further to the left inust also be an immediate L derivative. Consider now the pattern (faa*J,5). Here we are at- tempting to reduce the production R aa without the benefit of any context. As expected, many things can go wrong. This pattern can apply to the left side of a sentential form as well as to the right side. We would certainly not want to reduce aabaaaa to Rbaaaa. We could even misapply the pat- tern to the right side to produce aabaRa. This last pattern failed because it could be applied in the wrong place. A pattern can also fail even if it is applied in the correct --H21--H place! For instance, the pattern ((b?),6) always locates a character which is a phrase but this phrase coul'! be e?ther an M derivative or an N derivative, Far instance the atring abaa has two possible phrase bracketings `?ich reflect this difficulty, namely?a]4b]6aa]5 and a]4b]7aa]5. It is through detection of this sort of trouble that we ill be able ta guarantee the unambiguity of the gr?--Hsar for any parser which we decide is correct. In order to transform the definition of parsing pat- terns into a more tractable form, it is necessary to eY.a:t?ne the ways in which a reduction pattern can oil to be a pars- ing pattern. In Floyd [Fl 64] and Willi?Ts [Wi 69] this was done in a somewhat more restricted setting by exanining a series of 16 relations on strings. We will taJe an alternate approach. Observe from the definition that a reduction pattern can fail to be a parsing pattern only if sons application of the pattern to a sentential form locates an occurence of Xi such that in some phrase bracketing of that sentential form, that instance of x. is not immediately followed by a ]? In the case of ?-rules, which have a null x? a mistake has been made if no instance of ?i occurs an?here between the rightmost character of left context and the leftmost charac- ter of right context. We will illustrate these ideas by showing that (fa?a),4) is not a parsing pattern for G2. Our starting point will be --H22--H the set pL(C2) which of course tells us where the phrases occur in any sentential form. Next we insert a * in each string of Pt(G2) to which the pattern in question applies. We do this hy coTnputing the set 5 = h?1(pL(G2)) fl m?1(V*a*aV*). This intersection provides us with a set of bracketed strings, each of which contains exactly one *. Furthermore, the o+ is always located at a place where the pattern applies. Since the above process is performed in all possible ways, we are left with a representation of every way in which the pattern could he applied to any sentential form. In partic- ular, 5 contains such strings as a*]4a]4b]6aa]5aa]? a]4a]4b16a*a]5aa]? a]4a]4b]6aa#]5aa]? The first string listed above certainly corresponds to a valid reduction (i.e. reducing aabaaaa to tabaaaa) but the other two do not. If we now compute the set 5' = 5 - (V U B)*V#]4(V U B) * we will discard all instances of correct reductions. 5. thus tells us exactly how the pattern ((a*a),4) can make errors. More specifically, 5' tells us that the pattern should not be applied at either position 4 or 5 of the string aabaaaa. --H23--H We can recast these ideas to produce a test for whether an arbitrary reduction pattern is a parsing pattern. Theoren1.1 (R,i) is a parsing pattern for G if and only if (*) [h?l(Pt(G)))?fl [(v U B)*m?1 (R) (V U n [(V u B)*V#(B - ?i?*V(V u 3)*1 is empty. proof: Assume that no pattern begins or ends with a * we always use at least one character of context). We will prove the contrapositives, ref?rring infornally to (t) as the "set of mistakes". 1) Assume that (R,i) is not a parsing pattern. Then there exists a se?tential forrn ? and a phrase bracket- ing a which cannot be written in the desired fornat. Since ? uniquely determines a we can foroet about a and concentrate on the structure of a tat V, and V2 be the characters immediately adjacent to the ? in the matching pattern string. Hence there exist a1,a2,y1,y2 E (V U B) V1, V2 EV a EB such that a = a1a2V1?V2Y1Y2 E PL(G) and m(u2V11V2y1) t R. By hypothesis, a cannot be written in the desired way. If Xj is non-empty then ] cannot be the initial --H24--H character of ? since we could then take ?l = V2Xi = a2V1, u? = S?V2y1 and = y2 (where ?` is the rest of ?) to produce the desired format. Similarly, if production i is an ?-rule, we can conclude that ii occurs nowhere in ?. In either case we have st (B?1i)* But clearly then a1a2V1?SV2y1y2 t h?1(pL((3)) E (V U B) *m?1(R) (V U B) E (V U H)*Vt(B?]i)*(V u Hence a1a2V1?5V2y1v2 E (*) and the set of mistakes is non-empty. 2) Ass?T? that (*) is non-empty. Let ? be any string in (*) u' can then be written as a1a2V1?5V2y1y2 where a1, a2 Yl, y2?t (V U B) * v1, v2 tv 5 E (B --H ?i?* and m(a2v1#5v2y1) t R. Clearly then, ? = a1a2v15v2y1?2 t pt(G) because ?` t (*) However since R obviously applies to m(?) and a contains no ] we cannot partition ? as required. Hence R is not a parsing pattern. q.e.d. 11 It is decidable whether a regular reduction pattern is a parsing pattern for (3. ?orc al.L --H25- Proof: The set (*) is context free if R is regular and tne emptiness problem for context free languages is well known to be decidable. g.e.d. Although we can decide the correctness 0 a regular pattern used for finding phrases, we shall see in Chapter 2 that this problem is undecidable for :nera gar?rai s?ts of patterns. --H26--H 1.2ParsingwithPatterns A sincle parsing pattern allows us to reduce only one production of the gra?ar in question. Accordingly, we need a collection of parsing patterns, one for each production, before we can start parsing. Another requirement is even fl3re irnportant. It nust be the case that if we are given any sententiel forn which arises during parsing, we must have some pattern available which applies to it. Since the set of sentential forms which arise during parsing is not necessarily a cleanly structured set, we will simply require that our parsing methods be powerful enough to find a phrase in any sentential form. A parsingscheme for a grammar G is a finite collection of reduction patterns such that 1) each reduction pattern is a parsing pattern, 2) for every sentential form of G other than ?S?, there exists some pattern in the collection which applies to it. A parsing scheme is potentially a very powerful device as de.T?nstrated by Theorem1.3 There exists a parsing scheme for G?if and only if G is unambiguous Proof: ? Suppose G is ambiguous and 5 is a parsing scheme for G. Let A f(?,?) ?,`?, ?, ? t ?L(G) and 5(a)). Thus A is simply the set of pairs of --H27--H different bracketings for the same sententlal forn. Let (? ,uf') be a pair in A such that the nt?ier of brackets in o+`tp is a rilnlmurn over A. Clearly ? and u?' have no common phrase. But now some pattern will apply to m(??) and whatever phrase it p?rports te find in ?` ?i?l be wrong in a'. Hence the pattern used cannot be a para?ng pattern ? Suppose that G is unambiguous. Then every sentential forn has a unique phrase bracketing an? the entire string on either side of any phrase will forn a parein pattern for that phrase. Thus is v. is the indicated phrase of wx.y?t SF(G) then wx.?y is certainly a parsing pattern 1 I for the ith production of G. All possible parsing pat- terns so generated form a context free language hich can easily be derived from C. Simply take the grL--H.r?r for SF(G), add the production A. x.# and intersect I 1 the resulting language with v*?v*. q.e.d. Corollary1.4 It is undecidable whether a parsing schere for G exists. proof: Such a test is equivalent (by Theorem 1.3) to testing G for ambiguity, a problem well known to be unsolvable. Lemma1.5 Let G be a context free grammar with p productions. Let P = f(R,?l)(R ,p)) be a collection of reduction - p patterns -??n is a parsing scheme for G if and only --H28--H if 1) each (Rj ?) is a parsing pattern for G. 2) SF(G) - (?S? ? h( U V*R.V*) l0Xn$?Vl? - -SkVkYEV') Q3[close] set V"' V" U?f?1V1. - -?kXi]iT?fY) I ?1V1 - kV: 1) ti (ancb2fl n > 1) This language is easily shown to not b? deterministic. However, the following parsing patterns suffice to show that G10 is LR(k,=) ((?A#?), 1) (f?B#?), 2) ((aM??4), 3) (?acA#), 4) ((aBWB#), 5) (fac7B#), 6) (fAb?, Ab?, b?A), 7) (?Bh#, Bb#, b#B), 8) (?ancb?# n > lJ, 7) ((ancb2?# n > 1), 6) q.e.d. --H85--H 2.5DevelopmentofLR(k,t)Parsers Let us now return to LR(k,t) grarrL?nars and their parsers. We recall from section 2.1, that a grammar is LR(k,t) if in any sentential form one of the leftnost t phro?es can be iden- tified solely by its left context and first k chtractors cf right context. The LR(k,?) parsing algorithm will provide us with a basis for constructing an LR(k,t) parsing algorithrn. Once again, we will be concerned with an a?tonaton wno-e states will be itens. This tirne however, an ndivjc?al item will consist not only of a bracketed string which gives?a possible local' structure of the sentential form, but a?so of a counter, which specifies how many p?rares have bean by- passed in the bracketing corresponding to t?e particular iter' being considered. Furthermore, we will truncate the right context information in such a way that it will have a bounded length. We will illustrate these ideas with a few simple ex- amples. Let G11 be 5 AAA BB A?c B cc A?eAJ a 8 eB b We will construct an automaton for finding phrases in SF(G11). Since no non-terminal is self-embedding, our right context information will always be of bounded length. Let us compute --H86--H the successive sets of items which describe the structure of the string cceea. If we have not yet examined the first character of the sentential form, we must include the item s]0?O as a possible description of the form (the trailing zero indicates that no phrases have been bypassed so far, or more specifically, no brac?ets have been shifted off the left end of the item) Furthermore we must include also the items AA??]l?0 and BB]2O. Notice we are simply taking the "closure" of the item set by applying productions to the k=lst character of each item. Finally we produce the items c]3A??O and cc',43?0 Our initial item set then is 0 S]0?O AAAJ BB]2?O c]3A??O cc]4B?O These items describe any and all sentential forms which have no complete phrase beyond the first character. Furthermore, any other sentential form can be derived from one of the above forms by applying one or more productions to characters other than the first. We now look at the initial input character and discover that it is a c. Accordingly, we shift to the following set of items --H87--H 13A??C c]4B?O which after closing becomes 0 c] 3c] 3??O The second input character is also a c which :reans we cannot decide whether or not to reduce production 3. Accordingly, we shift to the item set ]4B?O 3A?l Notice that in the second item, we have increased the count of bypassed phrases to reflect the fact that we have discarded a possible bracket. These items indicate clearly that in any sentential form beginning with two c?s, the first c is a phrase only in those sentential forms which lie in the "A- half" of the grammar. We can continue this process as before. If we look at all possible input strings, we find that only a finite number of states is generated. In Figures 2.4 and 2.5 we display the completed PFA for G11 along with the sets of items cor- responding to each state. --H88--H ______ - ? 2 -- 3 4 6 Lff# A,a??.3 b - O8 B,b A 8 ?MAtThM a 12 O6 5 ____ Figure 2.4 A PFA for G11 s?o AA??]i? BBJ 0 cl 3AA?O cc]4B?O 13AA?O c]4B-O 3ci 3A?O 0 --H89--H Qo 4B?0 13ATh1 14eB]7?0 ]?eA?]??1 14b]8?0 ]3a]6?1 Qi A] eB] ?1 7 eA] 2 b] a]6?2 0 ]8?1 0 1E?2 0 ]7?1 0 1??2 0 ??1i?0 a] 3T?11?0 3A]1?0 1 3eT?1 ??O ] 3a] 6?0 A]i?0 eA1 a]6?0 Q2 ?6? e a] Q 1??0 0 1i?0 0 B12?0 et ?o 7 bis?0 Q 1g?0 0 317?0 e?1 ?0 bJs?? 0 12A0 Qo 17?0 Figure 2?5 Item sets corresponding to the states of the PFA in Figure 2.4, --H90--H Examination of this machine reveals that we need never bypass more than two phrases while parsing. Since we used only one looka?ead character in building the automaton we conclude that G11 is LR(l,2) It is our intention to use the above process as a basis for the construction of LR(k,t) parsers. Obviously, if we ever cenerate an item in which more than t phrases have been bypassed, we can conclude that the grammar in question is not LP(k,t). By looking at the sequence of states passed through while accessing the forbidden state, we will be able to produce a series of different bracketings for the initial seg- ment of the input string, which demonstrates why no phrase can ever be reduced based solely on its left context end first k characters of right context. Furthermore, one of these bracketings will contain t "irnparsable" phrases and thus serve as a counterexample to any claim that the given grammar is tR(k,t) for those values of k and t under consideration. One difficulty remains. If the grammar in question con- tains productions which are self-embedding or left-recursive, then the size of the right context strings can grow without bounds. However, we can show that it is never necessary to retain more than kt characters of right context if the gram- mar in question is to be LR(k,t) . This in turn implies that not only will the size of each item be bounded but also the number of items in a state will be bounded. Thus the gener- ated parsing automaton will have a finite number of states. --H91,92--H Let us define an LR(k,t) item as being an ordered pair (y, h) such that v is a string E (B t) V)* containing at least k occurences of characters in V and h is an integer such that O < h < An item (?1Y1. . S?Y?v h) is a validLR(k,t)item for the string X1. o+XnYl? o+?k iff av' E v*, clcin E B* ? 1) e1X1.. .anXn?1v1.. ?kYkYW t PL(G) 2) Ici. 0n = h 3) y'? contains no complete phrases 4) v contains at most kt characters to the right of the rightmost bracket. Le??na2.14 The set of all valid LR(k,t) items for a given grammar C and fixed values of k and t is a finite set. Proof Let m equal the length of the longest rhs of a produc- tion in G. Since v can contain no complete phrases, v can have at most m-l characters to the left of its one and only bracket (if it has a bracket at all). Thus the total number of characters of V occurring in an item is at most k+m-l+kt. ?urthermore, in the absence of t-rules, we can have at most k+l brackets occuring in an item. Thus an item is a string of at most 2k+m+kt characters over B U v and an integer between 0 and t. Clearly there are but a finite number of such items. q.e.d. --H93--H Suppose that I = (?]i? h) is an tR(k,t) item and that t contains no brackets (i.e. ?i is the rightnost bracket in the item). Then ? is called the right contoxt strinc of I. Two LR(k,t) items I = (y, h) and I = (y', h') are called equivalent if h = h' and y is a proper prefix of y' - By concentrating on equivalence classc-s 0 LR(k,t) iters we will avoid the difficulty of havinq to c?rry aro-?nd sim?lar items differing only in amount of right conte?t. We will next present an algorithn for c0rp?tinc the set of equivalence classes of valid LR(k,t) iters far the string X1 ??XnYl ???k The output of this algcrithn ?ill be called v k,t AlgoritlimL.l5 [Computation of Vk,t(Xl XnYl? ?k?1 Q if n = 0 set V' = ((?k+l5]0?k 0)) otherwise set V' = Vk,t(X1.. .XnYl? set v" = ((?lVl????kVkYh+j=j)1?=+(?Xn?lVl .?kVkY,h)EV'3 Q set V." V" U (?1V1????kxi]iZh)JZ E TRUNC?t(m(Y)) (?1V1. . .?kVkY?h) E v' Vk = Ai Q4 set Vk,t(Xl? XnYl = [(?1V1?????V?Y?h) t V"' V V1 =Y1k = ?k3 Q if any item ends in a but has fewer than kt characters of right context, append ?`s to the item until there are either k ?`= or kt right context characters. --H94--H Given this algorithm, we proceed directly to the LR(k,t) parsing algorithm before proving the correctness of our cur- rent work. Aloorithm2.16 [Phrase finding for LR(k,t) grammars) Let the input string be ? = x1...x E ?kv??k Set n =0. q) Compute 5 = Vk,t(Xl...Xn+k) If 5 = ?, than halt because o+ ? SF(G). If all items in 5 share ] as a common initial bracket then halt, indicating that reduction i should be applied at position n of ? If some item in 5 contains no brackets, then halt, G is not LR(k,t). If some item (`s,h) in 5 has h > t then halt, G is not LR(k,t). If n + k = m, then halt, G is not LR(k,t). Set n = n + 1 and go to step 2. The above algorithms are correct for much the same reasons as Algorithms 2.1 and 2.3. We must however verify that the shift operation never "gobbles up" so many characters that in- sufficient context is left for parsing. In other words, we must show that at least k characters are always maintained in an item. First a definition. --H95--H Let (?] ?? h) be an item. Then the count of the indi- cated bracket is the number of brackets to its left in any bracketing of a sentential form corresponding to this iter,. This value is simply h+fti-Im(?)I. (h tolls bow r?ny brook- eta have been shifted off, and I?I-Jm(?)i tol?s bow many brackets are in ?. Lemma2.17 If G is LR(k,t), then any and all Its blob occur during parsing according to Algorlthm 2.16 contain at least one bracket. Proof ?irectly from step 5 of the parsing aloorit?. Lemma2.18 Let (?].W, h) be an item in V (X Xv y). I k,t l?? l?? Then ? either 1) contains one or mere ??s 2) is of length > k(t - count(]?)). --H k(t --H h --H + Proof We will show that the above property is true of the k k item (? s10? 0) and that it is preserved by both the shift operation and the closure operation. k Consider the item sJ0? 0). The lemma holds true of this item since ] is the only bracket in the item and it is immediately followed by k ?`s. Assume the lemma is true of some item I = Shifting produces a new item I --H (?]iW h+i8?). Suppose ? in I contained one or more --H96--H 5. Then obviously u? in I. contains one or more ?`s and the lemma holds true. On the other hand, suppose > k(t - h --H + Im(?x?)I) = k(t --H h --H 16 --H i?I + lm(?) I) = k(t - (h + :61) - !?l + lm(?)J). Thus ? in I is of the correct length and the lemma holds. Thus the shift oper- ation preserves the lemma. For the closure operation we must show 1) the property is preserved for existing brackets in the item, and 2) the property holds true for any new brackets in- troduced into the item 1) So assume the lesma is true of I = Case1 fm(?)j < k. This means that the closure opera- tion is performed to the right of ]? to produce a new item I. --H (?] If truncation occured in the production of ?`, then we clearly have at least kt characters of context for ] and the lemma is true. If truncation did not occur, and ? contains one or more ?`s, then certainly tP contains these same ? a. Finally if truncation did not occur and ? contains no ?`s, then we must have f?J > k(t - count(1?)). But in the absence of ?-rules and truncation j?'J > Hence 1?P?I > k(t - count(]?)). --H97--H Case2 Im(?) > k. Then ] is rernoved frorn the item as it no longer designates a phrase. nence nothing further need be proven. 2) Suppose I' = (?x?l?a h) is produced frorn I = (?Aiy? h). We will show the property holds for Case1 a contains a bracket. Then = (?Ai??]j?2 h) where a' = TRUNCkt(?1a2) and neither a1 ncr c2 contain any brackets. If u'j = kt then the lemma certainly holds for in I' because the right context string u is sufficiently long. If a' < kt then no truncation t?c: place and a' = a1a2 If a2 contains any ?`s then so does y' and we are done. If a2 contains no ?`s than a2 > k(t --H h --H 1?Ai?1J + In(?Ai?1) ) = k(t --H h --H + Im(a) ). But since Ia' > Ia2j we have a' > k(t - h - + Im(a) I) which is exactly what we needed. Case2 a contains no brackets. Since I rnust contain a bracket somewhere, we conclude that it must be hidden in ?. Accordingly we will concentrate on the rightmost such bracket. So I = (?1]j?2Ai? h) where a11??2 = a --H98--H and neither ?2 nor ? contain any brackets. No truncation can occur in this case since I?2Ai? < kt ? < kt. Thus ?` If yt contains any ?`s then we are done. Otherwise, I?2AiI + I?I = I?2Ai?I > k(t - h --H I?1I + s?nce k > IY2Ai! ? > k(t --H h --H ?l + im(??)I) - k = I?1I --H In(??) I + I]jI Im(]?) I + I?2I --H Jm(??) = I?lI --H )m(??) + 1, > k(t - h - i?I + Im(?)I which is exactly what was needed. q.e.d. Theorem2.19 Let (y,h) be an item generated when Algorithm 2.15 is applied to some string. If h < t then y contains at least k occurences of characters from V. Proof Follows directly from step 6 of the algorithm and lemma 2.18. q.e.d. Theorem2.20 Let G be an Ls(k,t) grammar. Then Vk,t(x1. XnYl? -?k? as computed by Algorithm 2.15 con- tains one item for each equivalence class of the valid I:R(k,t) items for X1.. XnYl ?k Furthermore, for each item valid for X1...X Y . . . there is an equivalent n 1 ? 1 n 1? item in Vk,t(X . .X Y Proof Follows the sane lines as Theorem 2.2 but also uses --H99--H Theorem 2.19 to show that truncated right context is sufficient for generating the representatives of each equivalence class. Theurew2.21 Let C be a CFG and k and t be fixed. T?en Al- gorithm 2.16 terminates when applied to any str?ng. Furthermore, any reduction made by tha Alcoritbjn is correct. Proof Immediate from the algorithm and the pre?:ious theore:t?. q.e.d. --Hloo--H 2.b?ropert1esorLt 0 such that G is LR(k,t) Proof In [Kn 65], Knuth shows that it is undecidable of an arbitrary linear grammar G', whether or not there exists so?e k such that G' is LR(k). Since a linear grammar is one in which there is at most one phrase in any senten- tial form, we conclude that a linear grammar is LR(k) iff it is LR(k,t) iff it is LR(k,'"). The theorem fol- lows immediately. q.e.d. Theorem2.26 Let k be some fixed integer and 0 be a CFG. Then it iS undecidable whether at such that 0 is LR(k,t). Proof Consider the Partial Correspondence Problem tKn 65] That is, given a finite set of ordered pairs of non- empty strings ??5i'6i? 1 < i ? n), do there exist for all p > 0, ordered p tuples of integers (i1,i2i p such that the first p characters of a a. - - .5. match 11 12 1p --H103--H the first p characters of e. a. . - a. - Knuth has shown 1 1 I 12 p this problem to be undecidable. Accordingly, let ((a????) 1 < i < ?) be an in- stance of the partial correspondence preb?ern over some elphabet Z. Let ? = o1,o20m Let a,b,c1,... `0n be new s?T?ols Let el?02? `0m a . ,e?,A,B,S be no s??rnbols. Construct G = S Aa Bb A c.Ae. ..?e. c.0 ? ?l 3k. ? ?I ?k. 3 3 where a. = 0' . .0. 3 3? 3k. B ?+ o.Bo. .. a. 0.0... .0 ? ?l 3k. ? ? 3k. 3 3 where = 0?l? 0. ? 0. 3 3 0. 0. 3 3 Clearly G is unambiguous. We will show that G is LR(k,t) for some t iff the partial correspondence problem has a negative answer. The theorem will then follow immedi- ately. Accordingly, suppose the answer is affirmative; that is --H104--H 1 1 .? (Vp > O)(??1????p)>TRUNCp(a. ...a. ) = TRUNCp1 1 p 1 p Nov suppose that C is LR(k,t) for some particular t. Let q = k + t. T?us there are particular ii> TRUNC (a. .?.a. ) = TRUNC (S. ..? ). 1 q q 11 1q q 11 1q Examine the tvo sentential forms W - c??. .c. a ...a. a and 1 1 1 1 q 11 q .c. ?. -. ? = 1q 11 11 I q Since G is unambiguous we can talk about phrases of sentential forms without danger of confusion Notice that the ith phrase of w1 is exactly the jth character of a. - - a. and that the jth character of 11 1q 1 is exactly the jth phrase of w2. Furthermore 1 _ 1 q for 1 < j < t these phrases belong either to the class or (o o? depending on which half" of the grammar the sentential form belongs to It should be equally clear that for l < < t, the ith phrase of w1 has the same left context and first k char- acters of right context as the jth phrase of w2. Nence the ith phrase cannot be reduced and G is not LR(k,t). Since the above argument can be used for any value of t, we co?clude that G is not in the class of LR(k,t) --H105--H grasenars (for this value of k) Let us now suppose that the partial corresponoenca prob- lern has a nagatfve answer. That is thara exists sor\a p * Vi1.. TRUNC (o....o. ) # T?UNC (?. pi1 1 p p P 11 1 Than the following reouction patterns aro paraino pat- terns for G. ctc. .. .c. w4 for a a if w = 7j?C (?. ..?a. 1 1 I p 1 3 3 1 p and o is t?-.e pt char- acter of c*c. ...c. w# for a. a. if w = TRUNC0(?. . . 1 1 1 1 p 1 ? 3 I p and a. is the pth char- 3 --H actar of w. 0j*0k for a? a. 0j*0k for a. a. 3 3 a. a. ... a. * for A c.o... --H Cj ?l ?2 3k. 3 3 etc. ?urthereore, these patterns always reduce one of the first p phrases and hence G is LR(k,p). q.e.d. Theorern2.2? For any fixed k and t, --H106--H 1) d' a grarn??ar which is LR(k+l,t) but not LR(k,t). 2) a a granmar which is LR(Y,t+1) but not LR(k,t). Proof 1) Suppose k is a fixed integer. Let G be 5 Aeka Bekb A?c B?c G is linear and therefore LR(k,t) iff it is LR(k). G however is certainly not LR(?) because the two senten- tial forrs ceka and cekb both have c as their handle. This handle has the sa?e k characters of right context and hence can't be reduced. It is equally clear however, that G is LR(k+l) and hence LR(k+l,t) for all t. 2) Suppose t is a fixed integer. Let G be t t S?AA BB A?c B?c A eAs A aBe b We first show that G is LR(k,t) for no value of k. To do this, we need simply consider the sentential k tk k forms tekee and c e be . Each of the c's is a phrase and should be reduced to either an A or a B depending on whether the embedded character is an a or b. How- ever, this embedded character car?. be surrcunded by arbi- -107- trarily many e's and is thus effectively shielded from the questionable phrases. Put more simply, the first t phrases of both sentential forms look the same from the viewpoint of a bounded lookahead parsor. On the other hand, G is cert?in17 LP(1,t+l) beca'?se the t+l phrase of any suntential form o? G is "solf iden- tifying" and can be reduced until it is adjacent to the series of c's. q.o.d. Theorem2.28 There exist bR(k,") gramnars which are not LR(k,t) for any finite k or t. Proof Two proofs can be given, each of which lends a differ- ent insight into the tR process. DirectProof Consider the grarninar G12: S Aa Bb A?AA A B BB 8 A?c Suppose that G12 were LR(k,t) for some finite values k+t of k and t. Let us examine the sentential forms c a k+t and c b. Each of the initial c's is a phrase but none of the first t such phrases can be reduced based on its k rightmost reighoors (they're all c's!). !!ence G is -108- not tR(k,t) for any ? and t. G12 is however LR(l,?) and in fact is also FPFAP(l). The parsing process steps over all handles until it reaches the righL?ost phrase (i.e. c), which it reduces to either A or B as appropriate. The rernaining c's can then be reduced (fron right to left). After this pars- ing proceeds trivially. Indirectproof In Theorem 2.13 we gave an example of an L?(k,?) grar?n?r C10 which generated a language which was not a detorninistic lang'?age. Clearly then by Theo- ran 2.24 c10 could not be LR(k,t) for any finite values of k or t. q.e.d. We point out here that the above proof also shows that the LR(k,?) languages strictly include the tR(k,t) languages. Chapter3INEXACTCONTEXTNETFODS The biggest drawback of the parsing tec:?igues d?scussed so far is that they tend to produce PFA's vith large n??r?ers of states. This is essentially due to the a?t that they at all times maintain exact "knowledge' of tho str'cturc of the string they are processing. It freguently is the case, how- ever, that not all this information is necessary. Many existing parsing schemes are quite "myopic" and yet produce successful parsers. The simple pre'od?nce ???tjod t'.? 661, for example, basos all decisions on the re?aticnship between successive pairs of characters and retains 0 other kncwledga of the string being parsed. Accordir'?ij, d?':rtc thLs chapter to the investigation of certein sirrii?Ticatio:'s whir can be made to our methods while still retainirc sirrificant parsing power. 3.1DeRemer'sSimplificationoftheLR(k)Technique Attempts to apply the LR(k) method in its original form to "practical" grammars are usually doomed to failure unless a value of k 0 is used. This is because the upper bound on the number of states in an LR(k) parsing machine varies exponentially with k. Thus, for example, atter?ts to gen- erate LR(l) parsers for AtGOL 60 usually are aborted after many thousands of states have been generated (An 72]. LR(O) parsers for practical grammars on the other hand, tend to have a reasonable number of states (usually a number of the --H109--H --H110--H same order as the nurber of productions). Unfortunately very few grammars are LR(O) or even can be modified to fit into the LP(O) rnold. This realization led to the work of Deemer [De 69] which can be viewed as a technique which "beefa up" the power of the LR(O) parsing algorithm in such a way as to make it applicable to a wide class of practical graPt?ars. The rnethod enjoys the same advantage as the tR(O) technique, namely it employs a small set of states. The essential idea of the SLR(k) construction is as fol- lows. ?o start by building the LR(O) machine for the grammar in question Certain 0 the states of this machine will be ir.a?equate, that is, the machine will not be able to tell whether or not to rr.ake a certain reduction based only on the string seen so far. (Remember, k 0 means that no right context is used.) We now try to resolve the difficulty by peeking at the right context and cornparing it with those characters which can legitimately follow (according to the NEXT relation) the left hand side of the "questionable'. reduction. To illustrate this point, consider G13: S aAa s bAb s acc A?c The LR(O) machine for G13 has the following states (using Earley's notation): -ill- o ? 5 .aAa 5 .bAb 5 -acc Q 5 a.Aa 5 a.cc A .c 5 b.Ab A -c 5 ac.c A 5 acc. 5 aA.a The transition diagrarn for this nachine is a 2 4 c A 6 a b 3 A _____________ 5 11 8 5 aAa. A?c. 5 bA.b s bAb. Qi 5. 5. State 4 is an inadequate state, because in a santential fora o+ = a?..., we cannot tell whether to reduce the c to an A. However, the NEXT relation can help us. A necessary condi- tion for the reduction A c being correct in o+ is that the next character of o+ be an elernent of NEXT1 (A). Further=ore, this condition is sufficient to resolve the inadecuacy of --H112 state 4, because the only other transition out of state 4 is made on reading the character c which is not an element of NEXT1 (A) (a,b). We present the final form of the SLR(l) PFA for G13 in Figure 3.1. 1 a 2 c 4 (a b) c #3 A a 6 #1 b A b cQ#4 \-b%SQo Figure 3.1 The SLR(l) PFA for G13. We, have changed the names of the terminal states to reflect the reduction to be applied at that point. Further- more, a set appearing on a transition arrow indicates a so- called "lookahead transition", that is, in state 4, if the next character of input is either an a or `a b we do not ad- Vance the scanner but instead simply go to the reduce state --H113- for production 4. It is appropriate at this point to introduce a fonnal definition of SLR(k) graminars. Unfortunately, no clean gram- matical definition seems to exist because S?F(k) ora?Tars are defined operationally, that is, an SL?(k) crarjnar is one for which a certain construction yields a parser. For our purposes, an intuitive definition is really all that we need. The reader should, however, be aware of our laxnoss hen we say A grammar C; is SLP(k) if in any right sentential form we can uniquely determine the handle by a) exa,?ining its left context to produce a list of productions which could possibly be reduced at the present point b) choosing between these alternatives by comparing the next k characters of Input with the ae?s of strings NEXTk(AiJ for each i on our list of sus- pected handles. Notice that in some sense, the left and right contexts are used independently here. NEXTic(Ai) can only provide us with an appi???,?tion to the set of characters which can actually occur in the sentential form being parsed. The in- exactness of this approximation is the main reason why the SLR(k) parsing technique is less general than the LR(k) technique. Let us examine the complete set of parsino pat- terns induced by the machine of Figure 3.1. These patterns -114--H are: (?ac#a,4) (?ac4b,4) (?acc# 3) (--HaAa#,l) (?bab#,2) Notice in particular that the second pattern (?ac#b,4) cannever apply to a sentential form of G13. This phenomenon occurs because of the independence of the left and right con- texts for state 4. Keep in mind that this does not make this pattern incorrect in the sense of Theorem 1.1. Since the pat- tern Is never applicable to a sentential form, it can never ma?e an error on a santential form. The SLR(k) technique then, is our first example of a class of parsing methods which we call inexact context methods because they "lose track" of the exact structure of their input strings. Such a "forgetfulness" is sirnultaneously to their advantage and to their disadvantage. Fewer states are used by these methods because of their inexactness. On the other hand, we occasion- ally throw away so much information about the string being parsed that we no longer know whether or not to make a reduc- tion As an exa:nple of these ideas consider the grammar --H115--H G14: 5 ? aEa 5 bEb 5 aDb 5?? bDa D?c E?c This grammar is LR(l) but not SLR(l) beca?na in the sentential form acb the context characters a on the right side and b on the left are used independently to detcrrniro vhsthar to re- duce the c to a ? or E. In effect, the S?R(l) inachine has `forgotten" the initial a because the strings ac and bc?both take the machine into the same state (the r?ader should veri- fy that this does not occur in the LR(l) inachine). Let us record here, a well knovn fact. Theorem3.0 Every 5LR(k) grammar is an LR(k) graT.?mar but not conversely. In the next few sections, we will apply the sinplifying ideas of the SLR(k) technique to the parsing algorithrns developed in Chapter 2. --H116--H 3.2TheSLR(k,t)andSLR(k,?)Methods Let us attempt to extend the SLR technique to allow non- canonical parsing, that is, the reduction of phrases which rnight not be handles. Accordingly, we compare the defini- tions of LP(k), SLP(k) and LR(k,t) grammars to derive the following crute definition. A gra.Th??ar is SLR(k,t) if in any sentential form one of the leftinost t phrases is uniquely distinguished by 1) exam?ning its left context to determine which phrases might occur at the current point. 2) choosing between these alternatives by coin- paring the first k characters of right con- text with the sets of string which stand in the NEXTk relation to the left hand sides of those productions selected in part one. As always, if any uncertainty arises we postpone the reduction decision and continue scanning in the hope of being able to make a reduction elsewhere. We can, of course, continue the analogy by defining sLR(k,") grammars in which we require only that some phrase somewhere in the string be uniquely identifiable. The above definitions seem to be the `natural" extension of the SLR(k) concept. Unfortunately as we will soon see, this generalization yields rather dis- appointing results Let us consider --H117--H G15: 5 a3A 5 bEB 5 aDB 5 bDA D?c E?c A?a A?a B?b Notice that L(G15) L(G14) and as a netter of fact G15 covers G14. Suppose that we wish to parse the strino acb using the SLR(l,2) technique. Reading the string frcr left to right, we first scan an a and then a c. At this point, the left context (i.e. the string we have alreaoy scanned) is ac. This tells us irninediately that either production 5 or 6 should be reduced here (i.e, the c should beccrna either a D or an E) - However, the SbR frart?owork re?jires us to choose between these alternatives by comparing the next input character (viz. b) with NEXT1(D) and Nt?T1 (E). Since b is an element of both these sets, we cannot r?ke a reduc- tion now and must instead scan on. Accordingly, we step over the b and our left context becomes acb which i?nrediately tells us that the b should be reduced to a B. Accordingly, we make this reduction and the sentential form becomes acB. Now that the right context of the c has changed, we can --H118- resolve the difficulty of which way to reduce it, because B E NEXT (D) but B ? NEXT1(E). So we reduce the string to ADB and then to 5 and we are done parsing. Thus G15 is SL?(l,2) and everything seems rosy. Unfortunately, a formal implementation of this method will reveal a glaring flaw. We have seen that it is always necessary to hava exact knowledge or control over the left context string. In order to cor??pute this information we must maintain almost as much information in our item sets as do the LR(k,t) or LR(k,?) methods. This is because whenever a reduction is postponed, the inexact right context information provided by the NEXTk relation must be discarded and replaced instead with exact context information. This exact informa- tion can only be provided by using "complete" item sets. Thus it is that for the most part, our parser must maintain exact right context information in its item sets, even though the general philosophy of the method forbids full utilization of this knowledge. This criticism does not, of course, apply to the SLR(k) family of parsers because the difficulty only arises when the reduction of a suspected phrase is postponed. Since we never make postponements in the SLR(k) method, the difficulty simply never arises. We illustrate these ideas by presenting Algorithm3.1 (The SLR(k,?) Parsing Algorithm] k*k Assume the input is a string ? Xl? o+Xm E v ? --H119- (Initialize] [Shift] [Close] [Intersect] (Error?] ? Q [lookahead] [Continue?] [Reduce] set n = 0, w = (?k+l5]0?k) set n = n + 1. if n + k > n then halt, G is not SflR(k,=) set W' = fyJ?a ? B*, y E v, ?Yy E set W" = w' U (?1v1.. ?kXiJirP(Y) I ?lVl. ?kVkY ? V" an Vk = AiJ set W = (?1v1. -. ?kVkY E w" V1 =X?+1Vk =xn&?; if w = ?, halt, ? ? SF(G) if Wfl v* # ?, halt, G is not StR(k,?). set Zi = NEXTk(Ai) if V fl ] (V U 3) r = ? otherwise set Z = TRUNCk(w fl V(V U B)*) if Xn+1? Xn+k E z, go to if Xn+l Xn+k E z. n z. for i # j, go 1 3 to since Xn+l Xn+k E z for a unique i, halt indicating production i should be reduced at position n. This algorithrn is essentially a coinbinod version of --H120- algorithms 2.1 and 2.3 modified to utilize the SLR(k) strat- egy. The sets W, W, and W' represent sets of items describing the local structure of the string. As parsing proceeds, these sets can actjally become infinite. This is of little concern to us as these sets will in fact be regular and the necessary computations upon them can be performed in a finite amount of time. In step 6, we test for the presence of an item which con- tains no further brackets, indicating we have bypassed all parsing opportunities in ?. This test was, of course, used in the same way in the LR(k,?) and LR(k,t) parsing algorithms In step 1, WC are applying the essential SLR(k) idea, namely using our left context to predict which productions might have phrases at the position n in o+. Thus Z. is non- empty if and only if production i rnight so generate a phrase. In step 8, we compare the first k characters of right context with the appropriate sets of strings. Notice how the NEXTk relation has been used here. Note further that this test can never be as "sharp" as the test used by the LR(k,"") method, namely, direct comparisons with the items in W. As always, conflicting results cause us to postpone these reductions and continue scanning. Several routine theorems concerning this algorithm are evident Theorem3.2 Algorithm 3.1 always terainates and is correct. -121--H Proof By correct" we mean here that the algorithm never makes an incorrect reduction in the sense of Theorem 1.1. We also mean that the algorithm halts in step 5 only ??? SF(G). The formal proof of the theorem follows the lines of Theorems 2.4 and 2.5. Theorem3.3 Every SLR(k,?) grarr?ar is Lp(k,?). h?ever, there are LR(k,?) grammars which are not SLR(k,?). Proof The inclusion of SLk(k,?) in LR(k,?) is obvious from Algorithm 3.1. To see that the IncIuslon 15 proper, one need only consider grammar G14 Whic is LR(l,?) but not SLR(k,'") for any value of k. q.e.d. It should be obvious that tbe SLR(k,?) algorith can be "trimmed down" to produce an SLR(k,t) parsing slcorlthm. This process essentially is the same as was used to produce the LR(k,t) algorithm from the LR(k,") algorithm. Nowever, a few minor points merit discussion. In particular, we need never maint?in any characters to the right of the tth bracket in any item. (Since we will never step over this bracket, we will never need exact context information to its right. It might well be the case t?at we will need approximate con- text information, but this will, as always, be provided by the NEXTk relation.) Using the above strategy, it may hap- pen that some items will be generated having a length less than k. Such items will always end in a bracket (which will --H122--H be the tth bracket). For purposes of making the necessary right context tests, we can recover (approximately) the missing characters by using the NEXTk relation for the left hand side of whatever production corresponds to this final bracket. We point out here that the SLR(k,t) algorithm produced above becomes e>:actly the SLR(k) method of DeRemer [De 691 when a value of t = 1 is chosen. We will not bother to even list any theorems about the SLR(k,?) and SLR(k,t) classes because for the most part they and their proofs just carry over from Sections 2.4 and 2.6. Fowever, it is appropriate to comment upon the fundamental unsouneness of generalizing the SLR(k) method in the manner done in this section. In the case of the SLR(k,?) algorithm, the generated PFA w?ll have a set of states which will, in general, prop- erly include the state set of the LR(k,") PFA for the same grar%?ar and value of k. However, as Theorem 3.3 shows the StR(k,?) method is actually weaker in power than the tR(k,?) method. Accordingly, we must include the SLR method in our collection of nice ideas which do not generalize nicely. Thinos are not quite so bad in the case of `SLR(k,t) parsers. Here we can in fact save a few states over the corresponding LR(k,t) parser simply because we do not need to carry around the right context for the tth phrase. How- ever, whenever t > 1, the same general criticism can be made -123--H as was made of the SLR(k,") method. That is, the StR(k,t) item sets actually contain more accurate information than is provided by the NaXTk relation. To ignore thiS infertion simply to stay within the "Spirit" of the SLR(k) method Is foolhardy. Accordingly, we must continue e?r search for a clean" application of DeRemer's ideas to nen-oanenical parsing. --H124- 3.3TheREDN?XTMethod In this section we will present another parsing method motivated by the SLR technique. The intuitive idea is to construct sets of states similar to LR(O) state sets as we scan the input from left to right. Upon reaching an inade- quate state, we attempt to resolve the local ambiguity by using the NEXT? relation. So far, our method is just the SLR(k) rr?ethod. However, if it now turns out that the state is still inadequate, then we postpone the reduction and move on to phrases further to the right. The crucial problem is deciding what characters can follow the "ambiguous" phrase. In the LR('s.,?) and LR(k,t)?methods (as well as the SLR(k,") and SLR(k,t) methods) this problem was solved by examining the "reduced right context" string associated with each item in the state and thereby determining all possible continua- tio?s of the sentential form being parsed. In the method a- bout to be presented, we will approximate these reduced right context strings by using the REDNEXT relation. We will thus achieve a saving with respect to the amount of information stored in each state and consequently be able to generate parsers which have the ability to postpone an unbounded num- ber of reductions while still using a bounded number of states. The price paid for this privilege will as always, be a loss of parsing generality. The closure process used to produce item sets will pro- ceed as follows. Suppose, that ?Ai? is an item to be "closed". -125--H We generate new items ?x.].y where y E REDNEXT. (A.). Notice 11 that we have completely thrown away the right context string a It will always be true however, that m(?) E U REDNEXT.(A.). Thus we have aproximated the l<3 l)?U (a?b2?h a > 1) Let us use a lookahead factor of k = I and list the relations we will need. s A NEXTk SEDNEXTk g,C,b g,G --H126--H NEXTk REDNEXTk 3 h,H,b G g,G,b g,G H h,H,b The first item set for our parser will contain the item Proceeding with the closure, we generate AgJ1?4 and Bb)2? (because PEDNEXTk(5) = a singleton set). Closing the item Ag]1? yields acG]3g and aAG]3G as well as aG]4g and aGi4G because both G and g are in REDNEXT1(A). Notice how a have already introduced "spurious" items into the item set, narely AG]3G and aGi4G which describe the initial characters of no sentential form. Such is the danger of ap- proximation. We present below the complete first item set. 0 5] Ag)1 Bh12? aAG]3g aBHH] h aAG)3G aBHH]5H aci4g aHui6b aG]4G aH?]6H If our input character is an a then we shift and pro- duce the basis set for item set 2 (shown above the line in the figure below). The complete item set for state 2 is: --H127--H 0 AG]3g BHHJ5? AG]3G BHH]5?I G]4g iiHJ6h Gi4G willEH bI7g b]2h bJ7G bJ? aAG]3g aB?H]5h eAGi3G aohH]5h aG]4g ahH]6h aGi4G ailH)6h Once again, spurious items ha?e crept into the iton set For example, ? contains the item b]8h but no sentential form of G16 begins with abh. Scanning a b in state 0 results in item set whose basis set is describoil above the line in the figure below. 0 7g ] ]7G ]8H 17b17g ]8b]8h ]7b]7G ]8b]8H If the next input character were a g we would of course reduce production 7 since all items in 0 whose first real character is a g agree that this reduction should be made. On the other b? %f our next input character ?9re a b we --H128--H would have to postpone our decision to reduce because we do not know whether to reduce production 7 or 8. Continuing the scan, the next basis set would then be i7g ]8h ]7G which is exactly the basis set for item set 3 . Hence the parsing machine enters a loop, stepping over successive b's until finally a g,G,h or H is encountered. The complete parsing automaton induced by this technique is displayed in Figure 3.2. The corresponding sets of items are shown in Figure 3.3. a will call the grammars parsable by this technique the RNP(k) grammars (i.e. REDNEXT ?arsable using k characters of lookahead). A gr??ar will fail to be RNP(k) if in some generated inadequate item set, there is an item whose first k real characters are fully reduced. This is the same failure criterion used for the LR(k,?) grammars and corresponds to the case in which bypassing a reduction will do us no good because the right context information for the suspected phrase is already fully reduced and hence will never change as a result of a reduction performed still further to?its right. Intuitively, it is easier for a grammar to be LR(k,?) than RNo(k) because the spurious?items introduced into the RNP item sets can cause conflicts to occur and postpone those reductions which the tR(k,?) method is in fact "smart" enough --H129--H I-#-c4J?ii#GQ;4 H b,h,H b 10 B H 12 H b ________ 7 D16 h _ s ?halt Figure 3?2 A PFA for G16 0 0 0 slo--H Ag)1? Bhi2 aAGi39 aH?Ni5b aAGi3G aHUHi5H a?14q a?.?]6b a?1 G aH?i6H AG139 B?Fi5h Aci3c HHNi5H Gi4g HHl6h Gi4G flfli6H bi7g biBb bi7G bi8n aAGi3g annni5b aAGi3G aBH4i5H aGi4g anHi6b aGi4G anHi6n 179 18b i7G lOli 17bi79 i8bi8b i7bi7G i0bi8n --H130--H i6b 16H i6bi8b i6bi8n 0 i8b i8bi8b i8bi8n 0 Gi3g Gi3G bi7g bi7G 0 139 i3G i3bi7g i3bi7G ? 179 i7G i7bi7g 17b17G 011 nni5h nni5n bi0b bi0n 012 ni5h Hi5H bi8h bioH 013 15b i5n i5bi8h i5bi8n 014 gli Ois ii 016 hi2 017 12 0 149 i4G i4bi79 i4bi7G -0 ni6h ni6n bi8b bi8n Figure 3.3 Item sets corresponding to tbe states of the machine sho?n in Fl9ute 3.2. --H131--H to make. Let us reiterate the point that this phenomenon oc- curs because the RNP(k) technique is an loexactuu?e? ethod and accordingly is "less sure" of the structure o its input string. This "uncertainty" results in more reduction post- ponements being made and in the extreme, gives rise to the parser postponing all reduction decisIons. Th?s be parser fails to work. Let us now define an slgorithm for parsing ?Np(k) cram- mars. Individual items in the item set for this eloorithn will be written ?1V1? ?pVp where each t ?* and V. E v. 1 1 Algorithm3.4 [The RNp(k) parsing alcorithmi k*k Suppose the input string is ? Xl? Xm E v set n = 0 and W = (?k+l5]0?k) set n = n + 1. if n + k > m, the halt (G is not RNP(k)). set W' = Q3 set W" = 0 0 (?2V2.. %Vp 1 ??1?v1 * ?1V1 ??pVp E w). W' U ?1v1. . ???1X?J?? Sp,?? q?,Vk.+l such that ?1V1.. -?k?lAi?kVk?l... E w" y E REDNEXTk(A1) set W = (131v1.. . ? v E w" = Xn+l V = X ) p p ?l k n+k if W = ?, then halt (? ? SF(G)). if every item in W contains the common initial brac'?et ] * * (i.e. for each item, ?1 E B JiB ) then ha2t indicating --H132--H that production i should be reduced at position n of o+. if S?1v1.. . E w such that ?l = = ?p = ? then halt (G is not RNP(k)). Q8 go to step 2. Le?r.a3.5 suppose G is RNP(k) and W is an item set which arises during the execution of Algorithn 3.4. Let I = ?1V1 . ?pVp E W. Then p < 2k + q - I where q is the length of the longest right hand side of a production in G. Proof By induction on the number of steps used to produce I. The only place in the algorithm where a longer item can be produced is step 3 where the closure is being taken. ?owever, the closure operation by its very definition always produces exactly 2k + q - 1 characters where g is now the length of the right hand side of the production being applied. g.e.d. We can now proceed to bound the size of each which occurs. In the absence of c- rules, clearly each is of length 0 or 1. In the presence of c-rules however, the S's can in fact grow unboundedly in?length. We point out here that we never need include more than 1 instance of any ] in a ? because we are only interested in whether or not can occur between two particular characters of the input string. --H133--H Thus if we have p productions in G, none of the 8?s need ever grow larger than p characters in length. Thus we have Lemma3.6 The total number of PNP(k) ite:?s for a gra??r G is bounded by (2P(v+l) 12k+q--Hl where p the number of productions in G v the number of vocabulary symbols in G q the length of the longest right side of a pro- duction in G Theorem3.7 The RNP(k) parsing algorithm can be implomented on a 2PDA which parses in linear time. Furthermore, it is decidable whether an arbitrary grar?r G is F?p(k) for a given value of k Proof Since the number of?RNP(k) items 5 bounded (see prev- ious lemma), so too is the number of possible R?W(k) item sets. Hence, we can construct all transitions be- tween. these item sets, reduce the resulting finite state automaton, and test if a non-RNP(k) item set (as de- fined by steps 7 and 8) is accessible from the start state. This gives us the desired decision procedure. The first part of the theorem (dealing vith implementa- tion issues) follows from Theorem 1.10. q.e.d. Theorem3.8 The RNP(k) parsing algorithm is correct. -134- proof The proof essentially mirrors Theorem 2.5. The crucial observation is that the RNP(k) item sets contain all valid items (plus some invalid items) describing the local structure of the input string. Hence the RNP(k) algorith o+?ill ne?er make a reduction prohibited by the prosence 0 conflicting valid items. Thus any parse produced by?the algorithm is correct. For the same reason, if the algorithm ever generates an empty set of items and halts in stop 5, then the input string is not a sentential form. If it were, there would be a repre- sentative of some phrase bracketing for the string present in the item set. g.e.d. --H135--H ?.qTheFpFAP(k)Technique Although the RNP(k) technique is rather simple concep- tually, it frequently fails to yield parsers for some rather simple grammars. Consider for example, grar:r?ar G17: S?A B A EEA EE B 0013 0 E=a n?a L(G11) = (aa)*?U (aa)*a Let us attempt to construct a RNP(l) parser for We list the pertinent relations for refererce. NEXT1 KEDNEXT1 s A 13 E E,A,a,? 0 0,B,a,? Item set construction proceeds as follows S]0? A]1? EEA]3(E,A,?) 00B1?(0?B??) EE]4(E,A,? 0]6(0,B,?) aJs(O,B,?) --H136--H Scanning an a, we proceed to state whose basis is: 18(O?B??) Clearly this state will be inadeguate if the next character is ?. Furthermore, the reader may easily verify that using larger values of k will not help either. Thus G17 is not PNp(k) for any finite k. This failure is disappointing be- cause it can be remedied by the simple expediency of counting module 2, tne number of a's already scanned. Unfortunately, the RNP(k) nethod coos not do this, its right context is completely independent of its left context. On the other hand, the LR(k,") method, when applied to G17 generates only a finite number of item sets as illustrated in FigNire 3.4. These item sets correspond to the states of the pFA shown in Figure 3.5. The crucial point here is that although the RNP(k) construction has failed, there does in fact exist a simple parser for G17. What we would like to do next is to characterize the class of grammars for which there are "simple' parsers. More specifically, we wish to devise a parsing scheT?e which corr?ines the good points and avoids the faults of some of the previous parsing methods examined. In particular, a left to right scan using some bounded arnount of lookahead should be employed as this will guarantee linear parsing time. Decision postponement (i.e. non-canonical parsing) seems to be advantageous although"it does necess2tate the use of two stacks for parsing. Finally and most impor- ]7EA? 17E? 7a]7A? 7a] ?? --H137--H 0 S]0? A]1--H EEA] EE] a]7EA a]7E? 0 B] OOB] a]8OB? B] OOB] 0] a]8OB? a] 0] a] ]8OB? 8ajsB? 0 ]5? o ?]3? a]7A G ]7A? 8OB? ]8a]?B? o ]8B? ]3OOB]5? ]8O]6? ]8a]8OB? ]8a]8? Figure 3.4 The LR(1,?) item sets for C17. E] .? a -? Q ]7A? 8B? ]7EEA]3? ]8OOB]6?' ]7EE]4--H ]8O]6? ]7a]7EA? ]8a]8oB? ]7a]7E? ]8a]8? A]3? EEA]3? 14 a]?EA? ]7EA? 7a]7A--H J7a]7? ? ? Q OB]5? a]8B? --H138--H 0 a 5 a O,B 6 a AQ4? 16 halt Figure 3?5 The LR(l,?) PFA for C17. --H139--H tantly, we wish our parser to utilize a finite n?T?er of states, or expressed differently, the parsing patterns in- duced by the method should be regular sets. We define the class formally by A grammar G is finite hrase finding automaton 2arsable using k characters of lookahead(FPFAP(k)) if and only if there exists a parsir? scheme for G which uses a finite collection of regular k right ba??ed patterns. Grammar G17 is an FPFAP(k) grammar as is any grarinar for which the LR(k,?) algorithm happens to yield a PFA witli a finite number of states. However ths FprA?(k) cl?ss is much broader than this as will be shown by the next earple. Consider Gis: S aAa bAb S ? aDb bDa A cA? cA D cDD cD A?d D?d L(G18) ((a u b)c?d?(aU b) n > 1). The reader can easily verify that G is LR(k,?) and 18 furthermore that the PFA induced by the LR(k,?) algorithm has infinitely many states. Furthermore, the RNP(k) method and the SLR(k,?) method both fail on G18 because of the --H140- necessity to utilize interdependent context, that is, the parser must know whether the first and last characters of its input string are alike or different. There does how- ever, exist a right bounded regular parsing scheme for G18. The appropriate reduction patterns are: (aAa4', 1) (bAb#, 2) (aDb#, 3) (bDa), 4) (cAA4, 5) (cA#, 6) (c0D#, 7) (cD#, 8) (ac+d+?(aU A), 9) (bc+d+#(bU W), 9) (ac+d+#(bU 0), 10) (bc+d+#(aU 0), 10) A PrA corresponding to these patterns is displayed in Fig- ure 3.6. Loosely speaking, the FPFAP(k) technique is the ultimate "practical" bottom-up parsing method. Unfortunately we can not at this point give a terminating construction for gener- ating FpFAP(k) parsers. We can however show Theorem3.9 Let G be a context-free grarnrr(ar and k be a fixed integer. Then there is a procedure which emits an --H141--H Th?# AD?;ya,aAy;; `? CA:aa--H 10 b ir? Th c a ffia b 21 a,dfflD?4??? Th2 ?aD%)2.? 27 ad?D #1 A D 30 a 31 Figure 3.6 A PFA for G18. -142--H FPFA?(k) parser for G if one exists, and runs forever otherwise. Proof The procedure simply enumerates all regular k-bounded reductIon schenes using Theorem 1.6 to test each one for beIng a parsing scheme. In order to guarantee termination of the above process, we need to answer the allowing OpenQuestion3.10 [The FPFAP(k) decision problem] Is it decidable for fixed integer k and arbitrary context- free gramrrar G whether G is FpFAP(k)? Let us make a tangential approach to the FPFAP decidabil- ity problem. Two sets S1 and S2 are said to be regularlyseparable if there exists a regular set R such that S1 ? R and S2 fl R ?. Pictorially, the situation is R St If S1 and S2 are taken to be context-free languages, then it is easy to discover instances of pairs of sets which either are or are not regularly separable. A problem which -143- is not so readily cracked is openQuestion3.11 [The Regular Separability Problem] Is it decidable of two arbitrary context-free languages (two arbitrary deterein stic context-free la?guages) whether they are regularly separable? This question has arisen in other places [cc ?O] and bears a strong relationship to the problern at hand as shown beicw. Theorem3.12 If the Regular Separability Problem for deter- ministic context-free languages is unsolvable, then the FPFAP(k) decision problem is unsolwo-ble Proof Suppose G1 and C2 are LR(k) graIr?ars or the languaces in question. We apply exactly the sar?e constructIon as in Theorem 2.11 to produce a new grammar G. We next demonstrate that G is FPFAP(k) if and only if 1(G1) and 1(G2) are regularly separeble by some set R. Accordingly, suppose G is FpFAp(?) using so:T?e set of reduction patterns fR 1 < i < p). Consider now the regular set R = U h(R.)I* where the j?s are chosen j 3 only for those productions in class Clearly, 1. 1(c1) ? R. It is also clear that 1(c2) fl = ,? because then a wrong" reduction would be implied by son pat- tern Ri nence, R separates 1(c1) and 1(G2). Conversely, suppose R separates 1(c1) and 1(G2). This time we can use the patterns --H144--H and (Rfl S*o.#? for a. a. 1 1 1 (Rfl z*o.#? for a. a. 1 I I in conjunction with the other patterns listed in the proof of Wneorern 2.11 to parse G. But these patterns are all regular k-bounded patterns and hence G is FPFA?Ck) g.e.d. Although the FPFAP(k) decision problen renains open for fixed k, if we allow k to be a free variable, we can prove a routine result. The?ron3.13 Let G be a context-free grainnar. Then it is uncocidable whether there exists a k such that G is FPFAP(k). Proof Simply observe that in the space.of linear granUnars, the notions of LR(k) and FPFAP(k) are identical. ?ow- ever, it is well known [Xn 65] that it is undecidable whether a linear context free grammar is LB(k) for free k. q.e.d. Finally, let us put the FPFAP(k) grammars in perspec- tive by stating several theorems related to their utility and linitations. --H145- Theoram3.14 If G is FPFAP(k), then G can ha parsed in lin- ear time on a 2PDA with a finite nunber of states. Proof Direct from the definition of EpFAP(k) and Theo- rem 1.10. Theorem3.15 If G is LR(k,t) or RNP(k), then G is FPFAP(k). Proof The parsing patterns which correspond to the PFA for either an LR(k,t) grammar or an PNP(k) crar--Har are k right-bounded regular sets as as 3r.e&n n the proa5s of Theorerns 2.23 and 3.?. But then y definitien, such a grammar is FpFAP(k) c.e.d. ?heoramj.16 Every FPFAP(k) grarear 5 an LR(Th,?) rarer. However, there exist LR(k,?) grartars vr?ah are not FPFAP(k) for any value of k. Proof If G is FPFAP(k), G is pattern parsable by using a finite collection of regular k bounded patterns. 5ut then, by Lemma 2.? , G is also LR(%,?). To see that this inclusion is proper, consider the gramrar G10. G10 was shown to be LR(k,") in Theorern 2.13. On the other hand, we can demonstrate that G10 is not FPrAP(k) for any finite value of k. ?e could prove this directly using the idea of regular separability. Instead, we will wait until Lamma 4.13 in which we will prove that L(G10) is generated by no FPFAP(k) grammar. This fact --H146--H will, of course, coinpiete the present theoren. q.e.d. Chapter4RELATIONSH PSBETWEENTHECLASSES In this chapter we will compare the properties of the various parsino techniruos defined in this thesiS. Tr par- ticular, we will discuss incluslons between classes of gru?- mars and classes of languages. We will also elaborate upon certain decidability and censtructability pror-ortles wnich apply to some of the classes. 4.1?ela?i?iri?i????w?Spac The power or generality of the various classes of gr?T.- mars can be explained most easily in terirs of a lattice. A class of grammars A is "greater' in the lattice sense than a class B if A ? B and the inclusion is proper. The relation of all the grammar classes mentioned in this dissertation is summarized in Figure 4.1. Notice that we restrict our atten- tion to grammars which contain no ?-rules. The reason for this will be explained in Section 5.1. The lattice of Figure 4.1 summarizes a myriad of rela- tionships. Pather than prove every one of them, we instead present Figure 4.2 which provides the reader with sufficient "hints" to construct his own proofs. One siinply looKs up the table entry corresponding to the classes a in?erest. This table entry refers to the necessary theorems and example grammars for proving either strict containment or incompar- ability. If one class is an upper bound but not a least upper bound of the other (i.e. there is a chain of one or --H147--H --H148--H FPFAP(k) RNP(k) sLR(k,t) LR(k) BCP(m,n) Figure 4.1 Inclusion lattice for classes of grainmars with- out ?-rules. --H149--H LsL-j??(-?? -? - - d I I ? u ? .--H --H A --H150--H more classes between them) then the corresponding table an- try is a dash. We conclude this section by listing those example gram- mars, facts and theorems referenced in Figure 4.2. At the end of the section o+?e present Figure 4.3 which specifies for each relevant grar?ar exactly which classes it is a member of. Theorem4.1 Not all unambiguous context-free grammars are parsable using regular patterns. Proof If every unambiguous context-free grammar were RpP (regular pattern parsable), then we could recursively enumerate the set of unambiguous context-free grammars by using Theorem 1.6. However, since this set is known to be non-R.E., we arrive at a contradiction which proves our theorem. q.e.d. Theorem4.2 Every RNp(k) grammar is SLR(k,?) for the same value of k. Proof Compare Algorithms 3.1 and 3.4. Cuite clearly, the RNP(k) metnod will never make a reduction which would be bypassed by the SLR(k,") method. Thus, if w E SF(G) and the RNP(k) method performs a reduction on w, then the SLR(k,?) method will also perform a reduction on w although it may in fact be a different reduction (i.e. performed further to the left). Since both --Hf 51--H algorithrns are correct in the sense of never making wrong reductions, we reason that if c is RNP(k), then Algorithm 3.4 will make a correct reduction on every element of SF(C). Therefore, Algorith? 3.1 also ill make a correct reduction on every sentential forT. of G which means that G is SLR(k,?). q.e.d. Theoren4.3 Every LR(k) grammar is an LrR (;rar:nar. Every LRR grammar is parsable using a finite set of regular patterns Proof See Cohen and Culik [CC ?l]. Theorem4.4 Every BCP grammar is an FPFAP grammar. Proof Suppose G is BCP(m,n) for some fixed values of m end n. Therefore, G is parsable using a collection of n left hounded, n right bounded patterns. These sare pat- terns are obviously regular, n right bounded patterns and so G is FPFAp(n). q.e.d. Fact4.5 Every BC grammar is an LR(k) grammar. Every BC grammar is a BCP grammar. Proof The first statement was shown in Enuth [Kn 651. The second fact was proven by Williams [Wi 69]. Fact4.6 Every SLR(k,t) grammar is an LR(k,t) grarmar for --H152--H the same values of k and t. Proof Obvious from definitions. For?al proof parallels Theorems 3.0 and 3.3 Theorar.4.7 ?ver7 SLP(k) grammar is an RNP(k) grammar for tr?e same value of k. Proof As we commented in Section 3, the RNP(k) and SLR(k) methods function identically until the first postpone- rent is made. F?wever, if G is SLR(k) and we apply the ?NP(k) algorithm to it, then no postponements will ever have to be made. Hence, the RNP(k) algorith's will also parse the string. G19= G20 S Aa Bb A cAc d B cBc d 5 an A?d B?d A aA I aB aBa b 5 aA bB A cA d B cB d q.e.d. G21: --H153--H S ? aBG aAD bAL A?c D dD f E dE f G dC g G22: --H154--H 0 ? z ? z z z z ? Ca z z z ? z ? z ? 4J z ? 0 ? ? 0 H ? H ? H H ? x 0 0 0 0 0 --H155--H 4.2RelationsinLanguageSpace Suppose we are given some subset 5 of the context-free grammars. Corresponding to 5 will be a subset 5' of the con- text-free languages. 5' will be defined as ?L(G) G E 5). We will call 5' the set of languages inducad by 5. In this section we will investigate the relationships between the classes of languages induced by the classes of crartosrs de- fined eorlier in this dissertation. One fact quickly becornes apparent ?hen workina in ion- guage space, namely proving the appropriate relations is much more difficult than was the case in qrar?ar Dan reason for this is essentially that there are inf?ninelv many grammars which generate any one lanquano. Thus, n order to prove that a certain language is not indured by a given parsing technique, one must show that none of the cor- responding grammars is parsable by the method in question. Similarly, in order to prove inclusion of one class by another, we must show that for every language in class A, there exists a grammar generating it which is a merr?er of class B. We will restrict ourselves in this section to the classes of languages which correspond to the parsino schemes which we find most interesting, namely the LR(k), LR(k,t), FPFAP(k), BCP and LR(k,") methods. Accordingly, we present their relationship in Figure 4.4. --H156- UCFL LR(k,?) FPFAP(k) BCP LR(k) LR(k,t) Figure 4.4 The inclusion lattice for classes of languages. The class UCFL is the class of unambiguous context-free languages or as it is more commonly called, the class of languages which are not inherently ambiguous. The relation between this class and the class of languages for which there exists an LR(k,") grammar is shown as a dotted line because we have been unable to show that this inclusion is proper. Let us prove the facts summarized by this lattice. The first few proofs are quite easy. It is well known [Km 651 that the class of LR(k) languages is exactly the class of deterministic context-free languages, that is, the set of languages accepted by deterministic push down automate. hcwever, we ha'/e already shown in Theorem 2.24 that the --H15?--H LR(k,,t) languages are all deterministic context-free lan- guages. Hence, in language space LR(k,t) G tR(k). On the other hand, since every LR(k) grammar is an LR(k,t) grammar (simply take t = 1) we also have the converse rela- tion and can conclude that Theorem4.8 The classes of deterainistic context-free lan- guages, LR(k) languages and L?(k,t) lano'?aees are iden- tical Turning our attention to the FPFAP languaces, we first note that every tR(k) grammar is an FPFAP(k) erarJnar and hence the LR(k) languages are all FPFAP lena'j??as. To see that this inclusion is proper, we conejeer G23: S Aa Bb A cAA d cBB d A c cc t(G23) = (c?dc?a n > 0) U (c?dc2?b n > 0) The reader can easily verify both thatG is ?pFAP(l) 23 and that t(G23) is not a deterministic context-free len- guage. Hence, we have Theorem4.9 The class of FPFAP(k) languages strictly in- cludes the class of LR(k) languages. --H158--H To produce our next result, we must first present?a series of lew:nas Ler?a4.10 Every FpFAP(k) language is an LR(k,=) language. prcof l?ediete from Theorem 3.16. Len?4.11 The sets fa?cb? n > 1) and (ancb2? > 1) are not separable by any regular set. proof Suppose some finite state autornaton M accepted the former set and rejected the latter. Consider the set of congruence classes induced on a* by M. Pick any n n m- and m such that n > 2m and a = a . such n and m exist because there certainly rnust be an infinite congruence class. If we now apply Nerode's Theorem [HU 69] we conclude successively that n m a a n n--H2m aa 2 (n-m) a rn n--H2m saa n-m a 2(n-m) However, since a cb2(n?m) E T(N), we also have afl??cb2(n-m) e T(M) in contradiction to our assumption. q.e.d. Lenra4.12 !Hennie] If a one-tape off line Thring machine M performs all of its computations within the time Kn where K is a constant and n is the length of its input string, then the set accepted by M is gular --H159- Proof This lemma was proved in (He 65] Lemma4.13 There exist LR(k,?) languages for which no gram- mar is FpFAP(k). (Both instances of k are free.) n n n 2n Proof Consider L = fa cb n > 1) U fa ch n _ 1). L is generated by G10 which we have alrooc?y shown to be an LR(k,?) grammar (see Theoram 2.13 for the details). Hence, L is certainly an LR(?,=) language. Suppose that some grammar G for L wore ffiPffiAP(k) for some k. Let us analyze the prorortios of this grammar. Assume without loss of generality, that G is reduced. 1) If Aisa nonterminal of 3 whrch can generate infinitely many strings, then it must be the case that any terminal string produced by A contains a c. If this were not the case, SF(3) would contain a string such as wAy where w and y are strings of terminals and y (say) contains a c. By letting A derive a string of length 2 x yJ we produce a string which certainly is not in L. 2) If ? E SF(3) then there can be at most one mon- terminal in ? which generates am infinite set because otherwise we could produce a string with multiple c's. 3) Suppose that A is a non-terminal and that + 5 n A ? a Ab for some values of m and n. Then either m = 5 or n = 2m. Using 1 above and the fact that 3 is reduced, --H160--H + + r, 5, t such that 5 ??? and A a?cbS- There- + km kn fore, since A a Ab for all k, we conclude that ???kTn????sbknbt E L(G) V k. Examine the ratio of num- ber of b's to number of a's in such a form. This ratio is ((cS+tr))+kn and must for any value of k be either 1 or 2. The only ?ay that this can happen is for n = m or for n = 2n. + n 2m 4a) Let A a?Ab for some m. Then A never can occur in a sentential form o+ which derives a string in fa?cb0 n > 1). ? n n Suppose otherwise. Thus ? = ?1A?2 and o+ ? a cb for some n. Then ?q, r, 5, t, such that ?q and r 5 * t A a -cb and b . Furthermore, q + r = 5 + t. Since W1A?2 is a sentential form, so are ???kTh?2km?t a0akmarcbsb2kmbt examing the ratio of b's to a's in this latter sentence, we have = 5+t+2km q + r + km In particular, letting k = q + r and recalling that s + t = q + r, - (g+r)+2(g+r)m - 1+2m + (q+r)= but then 2 > f > 1 and the string could not have been in t(G). -161- + m m 4b) Similarly, if A a Ab for some in, then no sentential form containing an A car ever Gerive a string n 2n of the form a cb 5) We can now partition the vocabulary of c into four subsets. `71 = (A E v L(GA) is finite) `72 = (A E v 1(GA) is infinite but A is n6t recursive) + `73 = (A E v A is recursive arc A a??bin frr some In) + r `74 = (A E v A is recursive and A e?Ab for some in) 6) ?q such that any sentential form whose length is greater than q can ?nly be derived using recursive non- terminals. Pictorially then, a tree for a long string looks like /4 where only elements of `72 ? `73 occur along the cere?' or else elements of `72 Uv? occur along the `core". All characters on the side branches are elements of `71 --H162--H 7) Suppose 0 is FPFAP(k) with machine M (a 2pDA) as its parser. We will generate a two stack acceptor M' which will simulate M on any input whose length is greater t?an q. ?ovever, the first time that M pro- duces an ele?nent of V3 or V4, M' will halt. Further- more, M will indicate acceptance of its input if and only if the nonterminal which caused the termination is in V3. On the other hand, if the input string has lencth < q, then N' accepts it if and only if it is of n n the form (a cb 1 n < q/2). Notice now that the n n set accepted by M separates (a cb n > 1) from (a?cb2? n > 1). Furthermore, M' does this in limear time on a 2pDA. 8) M can be simulated by a Turing machine M" which also runs in linear time. When M" makes a reduc- tion such as A BCD on its tape it will actually change the instance of BCD to Aro. Thus M" does not attempt to shrink its tape as the two stack device M' does. Since the side trees occurring on a derivation tree belonging to 0 are bounded in size (i.e. width) by some value p, we cam never produce more than 2p blanks in a row before producing one of the nonterminals in V3 or V4. Thus, M" runs slower than M' by at most a con- stant factor, namely 2p. 9) T(M") is a regular set by Lemma 4.12. However, since T(M") = T(M'), we conclude that T(M") is a regular set which separates (a?cb? n ? 1) from ano2n n > II; -163--H This in turn contradicts Lera?a 4.11 so we conclude that M could not have existed in the first place. Thus no grammar for L can be parsed by a finite state a?tonaton or, rnore sirrply, L is not a meipoer of t? cbs of FPFAP(k) languages for any k. q.e.d. Combining Lemmas 4.10 and 4.13 vs nave Theorern4.14 The class of LR(k,?) languages properly in- cludes the FPFAP(k) languages. ?? relationships remain to be investigat5 clear that every L?(k,?) language is uranbiguous era that every BCP language is FpFAP. On the other hand, we cannot prove whether or not these inclusions are proper. We offer our opinions however in Conjecture4.15 The classes of BCP and FPFAP languages are identical. Conjectuis?.l6 Not all unambiguous context free languages are LR(k,?) languages. Supporting (but not conclusive) evidence for the former theorem is a proof due to Williams twi 691 that the BCP lan- guages include all deterministic languages. Two languages which we feel are strong candidates for establishing the latter conjecture are --H164--H fwwreversed w E (a,u b)*1 and faflcb? n < m < 2n?. --H165--H ?.?DecidabilityPr????tie When the classes of grammars presented in this disser- tation are viewed from the standpoint of decidability, three categories quickly distinguish thenselves. t? will define these categories as Category 1: Pattern Parsable (pp) grn?rnars LR(k,?) grammar sLR(k,?) grammars Category 2: Regular Pattern Parsable (r?PP) grartnars FpFAP(k) grarJnarr LR-Regular (tRR) grawnars Category 3: LR(k,t) grammars LR(k) grammars SLR(k,t) gra??ars SLR(k) grammars RNP(k) grammars Bounded Context Parsable (BCP(m,n)) grarnflars Bounded Right Context (BRC(m,n)) grammars Bounded Context (BC(m,n)) grammars If we take an arbitrary grammar G and pick any class from category 3 with fixed parameters (i.e. pick definite, fixed integer values for k, t, m or n) then it is decidable whether G is a member of the class in question. Furthermore, constructions can be given for building parsers for each of --H166- tho category 3 classes. On the other hand, even for fixed parameter values in the classes of category I, it is undecidable whether an arbi- trary grammar is in that class. Although algorithms can be given for parsing these grammars, no construction can be given for building parsers (in the sense of a 2PDA) for those grammars. The reason for this is that such a parser might very ?ll have infinitely many states. An additional corr??on property of this category is that it is undecidable whether a given set of reduction patterns is a parsing schar?a fcr a grammar of this class. Category 2 is somewhat of a hybrid. Parsers for gram- mars in these classes always have a finite number of states although it seems as if there is no a priori bound on how large thiS number can get (notice the similarity here to the Regular separability Problem). We can certainly use Theo- rem 1.6 to test a set of patterns for correctness with re- spect to category 2 classes, but it is not presently known whether we can decide (for fixed parameters) whether a gram- mar is in one of these classes. We can summarize the differences of these categories in a succinct way as follows. Let all parameters be fixed. Then category 1 classes are not recursively enumerable, category 2 classes are recursively enumerable (but probably not recursive) and category 3 classes are racursive sets. ChapterSCONCLUSIONS ?.i Futu?e No? There are essentially three areas in which the wor:? of this thesis is incomplete. First, we have yet to establish a decision procedure (or prove the non-existence thereof) for w?ather a prar?ar is FPFAP(k) for fixed k. As was mentioned in Chapter 3, this problem seems intimately related to the unsolved Regular Separability problem. The decidability q'?cstion as rerains open for the LRR and RPP grammars. Second, our diagram of the lattice for language spaca (Figure 4.4) is incomplete, probably because of our inability to choose the right counter-examples. Finally, our parsing model of Chapter 1 has rnns?csrabla room for further development. Although our theorems eke provision for handling grammars with ?-rules, and are still correct in their presence, a certain anomaly does occur In grammar space. Consider the example, G24: 5 Aa Bb A dAE dE B dBE dE L(G24) = d+a U d+b C24 is an LR(k) grammar and even an SLR(k) grammar, but it is not, according to our definitions, an LR(k,t) gram:iar! --H16"--H --H168--H The reason for this is that we have required our parsers to be able to handle any sentential form. In particular, our LR(k,t) parser cannot handle fdnEna n > 1; ? SF(G24) or (dnEnb n > 1) ? SF(G24). The LR(k) parser, on the other hand, needs only to concern itself with right sentential forms, which eliminates from its scope of action the trouble- sam cases described above. We now make an important obser- vation. If we apply our LR(k,t) parser to a string in L(G24), the string will be parsed correctly. This is because our parser, which always makes the leftmost possible reduction, will only generate right sentential forms while parsing. Hence our parsers will handle G24 even though G24 is not technically an LR(k,t) grammar. This anomaly can never occur in the absence of -rules because then any k letter lookahead string always contains as much information as k characters of terminals. With -rules present however, a right context string can "shrink away" to nothing, giving us absolutely no additional infor- nation for making parsing decisions. In G24 for example, in the string "ddddEEE?a", the series of E's shield us from the piece of information which we really need to know, namely the presence of the final "a". Thus in the absence of ?-rules, if we are given a parser M which works on the set of right sentential forms, then we can easily produce a new parser ?` which works on all sentential forms. Further- more, M' will have the same number of states as M and can --H169--H be easily constructed from the transition table for M. The c-rule anomaly mentioned above is merely one aspect of a problem which we have already discussed extensively in sections 1.4 and l.?, namely the fact that we need to re- strict our parsers to certaIn domalns whIch arc actually proper subsots of the set of all sontential forms. T?csa proper subsets arise because every parser makcs roductions in a specific order. Our present model, however, prevents a parser from deriving any useful infureatlon cc _t_ c'?er in which it perforrns reductions. Said another way, all parsing information which arises from the richt end of the input string must be transmitted back by making recuctions and thereby changing the context of other phrases. Our model can not use seguencing in any way, shape or form to aid it in parsing. What we would like to suenost for fur- ther study is an investigation of the ways in which this sort of sequencing can be used profitably by a parser. -170--H 5.2Summary We feel that there are essentially four main contribu- tions which we have made in this dissertation. The parsing model of Chapter 1 provides a "global view of the parsing process in that it reveals that the differ- ences bet'?ean methods can usually be characterized in terms of differences in either their parsing patterns or in the mode of application (leftnost, rightmost, etc.) of these patterns. proving the correctness o, arbitrary parsers by searching for their mistakes is a novel approach which marits future study in the directions indicated in the pre- vious section. In particular this sane approach can be used to ustify optimizations and transformations performed on practical parsers for the purpose of increasing their ef- ficiency or range of applicability. The LR(k,?) technique developed in Chapter 2 serves as the basis for all left to right non-canonical parsers. In particular, other parsers of this style can be viewed as operating with a set of states which is a homomorphic image of the state set of the LR(k,"') PFA. Thus, the operation of the less general methods can be explained in terms of the structure of the item sets which are merged together by this homomorphism. The distinction between exact and in- exact context methods is important because it reveals how the process of context approximation affects the trade off between parsing power and state set size. --H171--H The concept of FPFAP parsing, introduced in Chapter 3, is possibly the most general existing model of "practical" parsing within the traditional framework of utorsta. "?cb work is needed here to bound the applicability of this technique. Finally, our investigations of lanruage space in Chap- ter 4 have revealed that many facts can soretires be ascer- tained about the structure of all erarnrers generating a particular language. These facts can then pro?ide a basis for proving facts concerning the application of arioss - parsing techniques to this language. --H172--H BIBLIOGRAPHY [An 72] Anderson, T. "Syntactic Analysis of LR(k) tan- guages". Ph.D. Thesis, University of Newcastle upon Tyne, Nevcastle upon Tyne, England. 1972. [CC 71] Cohen, R.S. anc E. Culik II. "LR-Regular Gram- mars - an Extension of LR(k) Grammars". IEEE Conference Record of 12th Symposium on Switching and Automate Theory, pp7l53-165. 1971. [Co 70] Colmerauer, A. "Total precedence Relations". JAC, 17:1, pp. 14-30. January 1970. [De 691 DeRer?er, F.L. "practical Translators for LR(k) Languages". ph.D. Thesis, Massachusetts Insti- tute of Technology, Cambridge, Mass. October 1969. [De 71] DeRerer, F.L. "Simple LR(k) Gratrmars". CACH, 14:7, pp. 453--H460 July 1971. [Ea 70] Earley, J. "An Efficient Context-free Parsing Aloorithm". CACH, 13:2, pp. 94-102. February 1970. (Fl 641 Floyd, R.W. "Bounded Context Syntactic Analysis". CACH, 7:2, pp. 62-67. February 1964. [He 65] Hennie, F.C. "One-tape, Off-line Turing Machine Conputations". Inf. and Control, 8=6, pp. 553- 578. 1965. [HU 69] Hopcroft, J.E. and J.D. Ullman. Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Mass. 1969. (En 65] Knuth, D.E. "On the Translation of Languages from La?t to Right". Inf. and Control, 8:6, pp. 607- 639. 1965. [Wi 69) Williams, J.M. "Bounded Context Parsable Grammars". Technical Report 458, Computer Science Department, University of Wisconsin, Madison, Wisconsin. 1969 Wirth, N. and H. Weber. "Euler - A Generalization of Algol and its Formal Definition, parts 1 and 2" CACI, 9:1, pp. 13--H23. CACM, 9:2 pp. 89--H99. January and February 1966. [wW 66]