key: cord-0046345-s8xxdw9h authors: Drewes, Frank; Hoffmann, Berthold; Minas, Mark title: Graph Parsing as Graph Transformation: Correctness of Predictive Top-Down Parsers date: 2020-05-31 journal: Graph Transformation DOI: 10.1007/978-3-030-51372-6_13 sha: e5e7f683a071cdcd111007bc785d4e11f88c2311 doc_id: 46345 cord_uid: s8xxdw9h Hyperedge replacement (HR) allows to define context-free graph languages, but parsing is NP-hard in the general case. Predictive top-down (PTD) is an efficient, backtrack-free parsing algorithm for subclasses of HR and contextual HR grammars, which has been described and implemented in earlier work, based on a representation of graphs and grammar productions as strings. In this paper, we define PTD parsers for HR grammars by graph transformation rules and prove that they are correct. Hyperedge replacement (HR, [8] ) is one of the best-studied mechanisms for generating graphs. Being context-free, HR grammars inherit most of the favorable structural and computational properties of context-free string grammars. Unfortunately, simplicity of parsing is not one of these, as there are NP-complete HR languages [1, 14] . Hence, efficient parsing can only be done for suitable subclasses. The authors have devised predictive top-down (PTD, [4] ) and predictive shift-reduce (PSR, [6] ) parsing for subclasses of HR grammars and, in fact, for subclasses of contextual HR grammars (CHR grammars, [2, 3] ), which are a modest extension of HR grammars that allows to overcome some of the structural limitations of HR languages. Although the concepts and implementation of PTD parsers have been described at depth in [4] , their correctness has not yet been formally established. We show in this paper how PTD parsing can be defined by graph transformation rules and use this in order to prove the correctness of PTD parsers. Our experience with the correctness proof for PSR parsing in [6] seems to indicate that a graph-and rule-based definition of parsers can make this task easier. Related work on using graph transformation for defining parsers has dealt with LR string grammars [11] and two-level string grammars [12] . For a broader discussion of related work on parsing algorithms for graph grammars in general we refer to [6, Sect. 10.1] . The paper is structured as follows. After recalling graph transformation concepts (Sect. 2) and HR grammars (Sect. 3), we introduce threaded HR grammars (Sect. 4), which impose a total order on the edges of their derived graphs, which in turn induces a dependency relation on their nodes. In Sect. 5, we define a general top-down parser for HR grammars that respects edge order and node dependencies, and prove it correct. Since this parser is nondeterministic and hence inefficient, we introduce properties that make the parser predictive, and backtrack-free (Sect. 6 ) and show that this yields correct parsers that terminate for grammars without left recursion. 1 We conclude the paper by indicating some future work (Sect. 7). In this paper, N denotes the set of non-negative integers and [n] denotes {1, . . . , n} for all n ∈ N. A * denotes the set of all finite sequences over a set A; the empty sequence is denoted by ε, and the length of a sequence α by |α|. As usual, → + and → * denote the transitive and the transitive reflexive closure of a binary relation →. For a function f : A → B, its extension f * : A * → B * to sequences is defined by f * (a 1 · · · a n ) = f (a 1 ) · · · f (a n ), for all n ∈ N and a 1 , . . . , a n ∈ A. The composition of functions f : Definition 1 (Hypergraph). An alphabet Σ is a finite set of symbols that comes with an arity function arity : Σ → N. A hypergraph (over Σ) is a tuple G = (Ġ,Ḡ, att, lab), whereĠ andḠ are finite sets of nodes and hyperedges, respectively, the function att :Ḡ →Ġ * attaches hyperedges to sequences of nodes, and the function lab :Ḡ → Σ labels hyperedges so that |att(e)| = arity(lab(e)) for every e ∈Ḡ, i.e., the number of attached nodes of hyperedges is dictated by the arity of their labels. G Σ denotes the class of hypergraphs over Σ; denotes the empty hypergraph, with empty sets of nodes and hyperedges. A set of hyperedges E ⊆Ḡ induces the subgraph consisting of these hyperedges and their attached nodes. For brevity, we omit the prefix "hyper" in the sequel. Instead of "x ∈Ġ or x ∈Ḡ", we often write "x ∈ G". We often refer to the functions of a graph G by att G and lab G . An edge carrying a label in an alphabet Σ is also called a Σ-edge. And a node is called isolated if no edge is attached to it. Definition 2 (Graph Morphism). Given graphs G and H, a graph morphism (morphism, for short) m : G → H is a pair m = (ṁ,m) of functionsṁ :Ġ →Ḣ andm :Ḡ →H that preserve attachments and labels, i.e., att H •m =ṁ * • att G and lab H •m = lab G . The morphism is injective or surjective if bothṁ andm are, and a subgraph inclusion of G in H if m(x) = x for every x ∈ G; then we write G ⊆ H. If m is surjective and injective, it is called an isomorphism, and G and H are called isomorphic, written as G ∼ = H. For transforming graphs, we use the classical approach of [7] , with injective matching and non-injective rules [9] , but without rules that delete nodes. Definition 3 (Rule). A graph transformation rule r = (P, R, r • ) consists of a pattern graph P , a replacement graph R, and a mapping r • :Ṗ →Ṙ. 2 We briefly call r a rule and denote it as r : P •→ R. An injective morphism m : P → G into a graph G is a match of r, and r transforms G at m to a graph H as follows: -Remove all edges m(e), e ∈P , from G to obtain a graph K. -Construct H from the disjoint union of K and R by identifying m(x) with r • (x) for every x ∈Ṗ . Sometimes it is necessary to restrict the application of a rule by requiring the existence or non-existence of certain graphs in the context of its match. Our definition of application conditions is based on [10] . A conditional rule r = (r, c) consists of a rule r : P •→ R and a condition c over P , and is denoted as r : c P •→ R. We let G ⇒ m r H if m c and G ⇒ m r H. Note that each rule P •→ R without a condition can also be seen as a conditional rule ∃P P •→ R. If C is a finite set of conditional rules, ⇒ C denotes the conditional transformation relation using these rules. Examples of graphs and rules, with and without conditions, will be shown below. We recall graph grammars based on hyperedge replacement [8] . 4 Definition 5 (Hyperedge Replacement Grammar). Consider a finite alphabet Σ and a subset N ⊆ Σ of nonterminals. Edges with labels in N are accordingly nonterminal edges; those with labels in Σ \ N are terminal edges. A rule p : P •→ R is a hyperedge replacement production (production, for short) over Σ if the pattern P consists of a single edge e and its attached nodes, where lab P (e) ∈ N , and the mapping p • :Ṗ →Ṙ is injective. A hyperedge-replacement grammar (HR grammar ) Γ = Σ, N , P, Z consists of Σ and N ⊆ Σ as above, a finite set P of productions over Σ, and a start graph Z ∈ G Σ . The language generated by Γ is given by Example 1 (HR Grammars for Trees). As a running example for the constructions in this paper, we use the productions in Fig. 1 . They derive n-ary trees like the one in Fig. 2 , if the pattern of production s is the start graph. We draw nodes as circles, and nonterminal edges as boxes that contain their labels. Edges are connected to their attached nodes by lines, called tentacles. Tentacles are ordered counter-clockwise around the edge, starting in the north. For the purpose of this paper, we restrict ourselves to this simple example because illustrations would otherwise become too complex. Further examples of well-known HR languages for which PTD parsers can be built include string graph languages such as palindromes, non-context-free ones like a n b n c n , arithmetic expressions, and Nassi-Shneiderman diagrams. In our running example, edges of shape with arity( ) = 1 designate root nodes, whereas edges of shape with arity( ) = 2 connect parent nodes to their children. In productions (and later in other rules), nodes of the pattern P have the same identifier ascribed in P as their images in R under p • , like x in our example. In the following, the letters s, l, and b under the arrows in Fig. 1 are used as identifiers that refer to the corresponding production. Assumption 1. Throughout the remainder of this paper, we consider only HR grammars Γ = Σ, N , P, Z that satisfy the following conditions: 1. Z consists of a single edge e of arity 0. 2. L(Γ ) does not contain graphs with isolated nodes. These assumptions imply no loss of generality: a new initial nonterminal with a single start production according to Assumption 1 can be added easily. A grammar that violates Assumption 1 and produces isolated nodes can be transformed easily into an equivalent grammar that attaches virtual unary edges to those nodes. We now prepare HR grammars for parsing. The edges in graphs, productions and derivations will be ordered linearly with the idea that the parser is instructed to process the symbols of a grammar in this order when it attempts to construct a derivation for a given input graph. The edge order induces a dependency relation between nodes of a graph as follows: for an edge, an attached node is "known" if it is also attached to some preceeding edge, which will be processed earlier by the parser; it is "unknown" otherwise. This defines what we call the profile of an edge: a node is classified as incoming if it is known, and as outgoing otherwise. Technically, edge order and profiles are represented by extending the structure and labels of a graph: Every edge is equipped with two additional tentacles by which edges are connected to a thread, and the label of an edge is equipped with a profile ν ⊆ N indicating the positions of its incoming nodes. Unary hyperedges labeled with a fresh symbol distinguish thread nodes from kernel nodes of a graph. 3. The profiled edges and thread nodes of G can be ordered as pe We call v 0 the first and v n the last thread node of G, and define furthermore The kernel graph of G is the graph G ∈ G Σ obtained by removing the profiles of edge labels, the -edges, the thread nodes and their attached tentacles.GΣ denotes the set of threaded graphs overΣ; • denotes the empty threaded graph that consists of a single thread node with its attached -edge. Remark 1 It is important to note that the profiles of the (profiled) edges of a threaded graph G are uniquely determined by in(G) and the structure of G. To see this, let pe(G) = {e 1 , . . . , e n }, threaded in this order. For every v ∈Ġ, let Then Let the concatenation H = G • G of two threaded graphs G and G with G ∩Ḡ =G ∩G = ∅ be the threaded graph H that is constructed from the union of G and G by identifying the last thread node of G with the first thread node of G (and removing one of their attached -edges). Note that kernel nodes of G may also occur in G . Definition 7 (Threaded Production and HR grammar). A rule p : P •→ R is a threaded production if P and R are threaded and the following conditions are satisfied: 1. the rule p : P •→ R, where p • is the restriction of p • toṖ , is a production, called kernel production of p, 2. p • maps the first and last thread nodes of P onto the first and last thread nodes of R, respectively, and 3. p • (in(P )) = in(R). An application G ⇒ m p H of a threaded production p to a threaded graph G is called leftmost, written G ⇒ A HR grammarΓ = Σ ,Ñ ,P,Z over a profiled alphabetΣ is threaded if all its productions are threaded. As in the case of context-free string grammars, the context-freeness of hyperedge replacement implies that derivations can be restricted to leftmost ones: This fact will be important, as top-down parsers for HR grammars attempt to construct leftmost derivations of a graph. It follows from Remark 1 and condition 3 of Definition 7 that the profiles of edges in the replacement graph of a threaded production are uniquely determined by the profile of the pattern. Hence, given a HR grammar Γ = Σ, N , P, Z and an order onR for each of its productions p : P •→ R, a unique threaded versioñ Γ of Γ is obtained as follows: 1. The threaded start graphZ ofΓ is given byZ = Z (recall that arity(Z) = 0). 2. Every production p : P •→ R of Γ is turned into all threaded productions p :P •→R whereP = P ,R = R, and the edges ofR are threaded according to the chosen order onR (which defines the profiles of edges inR uniquely). While the procedure above creates an exponential number of profiles and thus productions, in most cases many of them will be useless. A more efficient way of constructingΓ is thus to choose the threading order and then construct the useful threaded productions inductively. The procedure would initially construct the threaded start production (in which in(P ) = ∅) and then, as long as a replacement graph of one of the constructed productions contains a hitherto unseen profiled nonterminal, continue by constructing the threaded productions for this nonterminal. This leads to the following definition: Example 2 (Threaded Tree Grammar). We consider a threaded version of the tree grammar, given by the threaded productions in Fig. 3 . In examples such as this one we draw thread nodes in gray and omit the attached -edges, and we write profiles as ascending sequences of numbers rather than as sets. The profiles of profiled terminal edges are inscribed into the label symbols, i.e., 1 for 1 and Fig. 4 . A leftmost threaded derivation of the tree in Fig. 2 ε for ε Moreover, we distinguish threaded productions with the same kernel productions by the profile of the (unique edge in the) pattern in the production name. The profiled symbols T ε , ε , 2 , 12 , and 1 do not appear as they occur only in useless productions. It is worthwhile to note that productionl 1 merges thread nodes t and n, which we indicate in the drawing by annotating the corresponding node in the replacement graph with "t=n". We arrange thread nodes from left to right and draw thread tentacles in gray so that the kernel graph can be better identified. To make it easier to distinguish incoming from outgoing attached nodes, we draw the former to the left of an edge and the latter to the right of it. In productionb 1 , left-recursion was avoided by choosing the terminal edge to be the first one on the thread. Figure 4 shows a threaded derivation of the tree in Fig. 2 , which is leftmost. Threaded productions derive threaded graphs to threaded graphs. Thus the threaded and unthreaded version of a HR grammar generate the same language of kernel graphs. Proof. Easy induction on the length of derivations, using Lemma 1. We define top-down parsers for HR grammars as stack automata, which perform transitions of configurations that represent the input graph and a stack. Configurations are graphs, and transitions are described by graph transformation rules. This definition is more precise than the original definition of PTD parsing in [4] , but avoids the technical complications occuring in the precise definition of PSR parsing for HR grammars [6] , where graphs are represented textually as sequences of literals, and transitions are defined by the transformation of literal sequences, involving substitution and renaming operations on node identifiers. The use of graph transformation and graph morphisms avoids the explicit handling of these technical issues. A configuration consists of a threaded graph as in Definition 6, which represents its stack and its read input, edges without profile that induce its unread input, and further edges that serve as flags, distinguishing different types of nodes. Definition 9 (Configuration). Given a HR grammar Γ = Σ, N , P, Z and its profiled alphabetΣ, let , ⊗, and be fresh symbols of arity 1. A graph G without isolated nodes is a configuration (of Γ ) if the following hold: We let read(G), the read input, denote the subgraph of thread(G) induced by the profiled edges between the first thread node and h (including the -edges attached to those nodes). The (threaded) subgraph of thread(G) induced by the profiled edges between h and the last node of the thread (again including theedges attached to those nodes) represents the stack stack(G), and the subgraph unread(G) induced by the Σ-edges represents the unread input. The union of unread(G) and the kernel of read(G) is the input represented by G, denoted by input (G) . A configuration G is Consider in the following a threaded versionΓ = Σ ,Ñ ,P,Z of a HR grammar Γ = Σ, N , P, Z . We define two types of general top-down parsing rules, called match and expand rules. Definition 11 (Match and Expand Rules). For every terminal symbol a ν ∈ Σ \Ñ , the match rule t a ν : P •→ R is given as follows: -The pattern P is a configuration where • read(P ) = • , • unread(P ) consists of one a-edge e with a ∈ Σ \N and att P (e) = v 1 . . . v k (where arity(a) = k), with a -edge attached to every v i with i ∈ ν and a ⊗-edge attached to every v i with i ∈ ν, and • stack(P ) consists of one a ν -edge e with att P (e) = v 1 For each of the threaded productions p :P •→R inP, the expand rule t p : P •→ R is given as follows: -read(P ) = read(R) = • , -unread(P ) = unread(R) = , -stack(P ) =P and stack(R) =R, -the mapping t • p is the same as in p; We let R M Γ denote the set of all match rules for terminal symbols, and R Ẽ Γ the set of all expand rules for productions ofΓ . In the following, we will show that RΓ = R M Γ ∪ R Ẽ Γ is in fact a top-down parser for Γ , hence we call RΓ a general top-down parser ofΓ (for Γ ). The expand rules of the general top-down parser for trees in Fig. 5 differ from the threaded productions only in the -edge marking the top of the stack. (We draw -and -edges around the nodes to which they are attached, so that they look like distinguished kinds of nodes. Nodes with an attached ⊗-edge are drawn as ⊗, omitting the attached edge in the drawing.) The match rules for the two edge patterns needed are shown in Fig. 6 . Figure 7 shows snapshots of a successful parse of the tree in Fig. 2 with these rules, where five configurations are omitted for brevity. The parse constructs the leftmost derivation in Fig. 4 . Note that match rules do not change the thread, but just "move" the matched terminal from the unread to the read subgraph of the configuration. In contrast, expand rules do not modify the unread or read subgraphs of the configuration, but just replace the first nonterminal on the thread by the replacement graph of a threaded production for this nonterminal. We can summarize these observations in the following fact: Fact 3. For a parse G ⇒ * RΓ G ⇒ r H (where r ∈ RΓ ), the following hold: if r = t a ν is a match for some a ∈ Σ \ N , then thread(G ) ∼ = thread(H); 3. if r = t p for some threaded production p ∈P, then thread(G ) lm ⇒ p thread(H). Thus RΓ constitutes a top-down parser: there is a successful parse if and only if its input graph is in the language of the grammar. IfΓ is not left-recursive, the general top-down parser terminates. Here, we say thatΓ = Σ ,Ñ ,P,Z is left-recursive if there is a threaded graph G consisting of a single nonterminal edge labeled A (for some nonterminal A) and there is a derivation G ⇒ + P H for some graph H such that the first profiled edge of H is also labeled with A. Proof Assume that there is an infinite parse G ⇒ t1 G 1 ⇒ t2 G 2 ⇒ t3 · · · with t i ∈ RΓ for i ∈ N. Since unread(G) is finite and each match operation "removes" an unread edge, there must be a k ∈ N such that t i is an expand rule for all i > k. As their number is finite, there must be numbers i and j, k < i < j, such that stack(G i ) and stack(G j ) start with edges labeled with the same nonterminal. By Fact 3, thread(G i ) ⇒ lm + P thread(G j ), which proves thatΓ is left-recursive. Inconveniently, the steps of the general top-down parser are nondeterministic: 1. The expansion of a nonterminal A ν may choose any of its productions. 2. The match of an edge a ν may choose any unread edge fitting the profile ν. We consider a parse G ⇒ * RΓ H as a blind alley if the configuration H is not accepting, but does not allow further steps (using RΓ ). This is the case if -stack(H) starts with an edge a ν , but t a ν does not apply (edge mismatch), or -stack(H) = • but unread(H) = (input too big). Due to nondeterminism, a successful parse may nevertheless exist in such a situation. Exploring the entire search space of parses to determine whether a successful one exists is very inefficient. The aim of predictive top-down parsing for threaded HR grammars is to avoid backtracking, the major source of inefficiency of a straightforward implementation of the general top-down parser. So we have to cope with the nondeterminism identified in the previous section. In every configuration of a parse, it must efficiently be possible to predict which choices of moves are wrong in the sense that they lead into a blind alley, whereas other moves could still lead to a successful parse if there is any. However, this is most likely not achievable for every threaded HR grammarΓ because Theorem 2 in combination with the known NP-completeness of some HR languages would otherwise imply that P=NP. For such a grammar, certain configurations will allow more than one expansion, and it may be the case that any of them is promising, or just some of them (or none). Thus backtrack-free parsing only seems to be possible for HR grammars that make correct moves of their top-down parsers predictable. Let us first define predictive expand rules that will prevent a parser from running into blind alleys by additionally checking so-called lookahead conditions. Henceforth, given a rule r : P •→ R and a condition c over P , we denote the conditional rule r : c P •→ R by r[c]. Definition 12 (Predictive expand rules). Let Γ be a HR grammar,Γ a threaded version of Γ , and RΓ = R M Γ ∪ R Ẽ Γ its general top-down parser. For an expand rule t p ν : P •→ R ∈ R Ẽ Γ , a condition c over P is a lookahead condition for t p ν if the following holds: For every derivation G ⇒ * RΓ H ⇒ m t p ν H where G is an initial configuration and H is promising, 5 if m c then H is promising. Γ } of conditional rules is a set of predictive expand rules forΓ if c p ν is a lookahead condition for every t p ν ∈ R Ẽ Γ . In the following, we briefly describe a simple way to check whether a set of predictive expand rules can be obtained from R Ẽ Γ . For this purpose, let G be any initial configuration and t p ν : P •→ R any expand rule so that G ⇒ * RΓ H ⇒ m t p ν H where H is promising, i.e., there is an accepting configuration F such that Inspection of expand rule tb1 shows that choosing this rule cannot produce a promising configuration if the unread part of the input does not contain a -edge starting at node x. The existence of this edge is hence requested by the graph conditionĉb1 ≡ ∃Cb1, defined by the supergraph Cb1 of the pattern of tb1 (see Fig. 8 ). No such edge can be requested for expand rule tl1 ; each match of tl1 satisfiesĉl1 ≡ ∃Cl1 since Cl1 is just the pattern of tl1. Conditionĉl1 is in particular satisfied if choosing tb1 produces a promising configuration, and therefore tb1 tl1. By Lemma 2, we can choose lookahead conditions cb1 ≡ cb1 ≡ ∃Cb1 and cl1 ≡ĉl1 ∧ ¬cb1 ≡ ¬∃Cb1. Figure 9 shows the resulting predictive expand rules for the nonterminal T of the tree parser. For brevity, lookahead conditions show only those subgraphs that must or must not exist in order to apply tb1 or tl1 . The match rules and the expand rule tsε for the start production remain the same as in Example 3. Moreover, it is easy to see that match rule t 1 produces a promising configuration for each of its matches, i.e., the threaded tree grammar has the free edge choice property. With these modified expand rules, the predictive parser can select the same parse as in Fig. 7 . As mentioned earlier, other well-known examples that allow for predictive parsing include palindromes, a n b n c n , arithmetic expressions, and Nassi-Shneiderman diagrams. In this paper, we have defined PTD parsers for HR grammars by graph transformation rules, and shown their correctness. The definition is consistent with the implementation of PTD parsers in the graph parser distiller grappa 7 described in [4] , but some features are still missing: First, productions that merge nodes of the left-hand side have been omitted. Such productions may occur when a HR grammar is "left-factorized" in order to allow for predictive expansion. (This corresponds to left-factorization of CF string grammars for LL-parsing.) Second, PTD parsing for contextual HR grammars [2, 3] has not been considered. Finally, a more sophisticated way of calculating lookahead conditions, by approximating Parikh images, has been ignored. So our next step will be to extend our definitions and proofs to cover these concepts as well. Our ultimate goal ist to use this definition to relate the power of PTD parsing to that of PSR parsing, probably by using a definition of PSR parsing that is based on graph transformation as well. On the membership problem for regular DNLC grammars Contextual hyperedge replacement Contextual hyperedge replacement Predictive top-down parsing for hyperedge replacement grammars Extending predictive shift-reduce parsing to contextual hyperedge replacement grammars Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement Implementation of typed attributed graph transformation by AGG Hyperedge Replacement: Grammars and Languages Double-pushout graph transformation revisited Correctness of high-level transformation systems relative to nested conditions A parsing automata approach to LR theory Modelling compiler generation by graph grammars Generalized predictive shift-reduce parsing for hyperedge replacement graph grammars String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing Parsing Theroy I: Languages and Parsing Acknowledgements. The authors thank Annegret Habel for her valuable suggestions in several stages of this work. (2) Consider case (1) first. There is an isomorphism iso : unread(K) → unread(H) because K is obtained from H by expand rules only. Let e be the edge of unread(K) that is read by the match operation K ⇒ R M Γ K and E the subgraph of K induced by e. Clearly, m(P ) as well as iso(E) are both subgraphs of H. Now select a graph C and an injective morphism m so that P ⊆ C, m = m | P , and m (C) = m(P ) ∪ iso (E) . By definition, m ∃C. In case (2) , unread(H) is empty and m ∃P .We can make use of this as follows. For an expand rule t p ν , performing the above analysis for all derivations of types (1) and (2) yields only finitely many distinct graphs C (up to isomorphism). These graphs C 1 , . . . , C n can be computed by procedures similar to the construction of FIRST and FOLLOW sets for LL(k) parsing [15, Sect. 5.5] . Definingĉ p ν = ∃C 1 ∨ ∃C 2 ∨ · · · ∨ ∃C n we thus obtain for all promising graphs H, H that H ⇒ m t p ν H implies m ĉ p ν . Thus, by contraposition, if H is promising and H ⇒ m t p ν H but m ĉ p ν , then H cannot be promising.Note, however, that m ĉ p ν does not necessarily imply that H is promising if H ⇒ m t p ν H and H is promising. Therefore,ĉ p ν can in general not directly serve as a lookahead condition. To solve this problem, we define a relation on expand rules. For this purpose, let us consider two different expand rules t p ν a , t p ν b ∈ R Ẽ Γ with isomorphic left-hand sides. Without loss of generality, we assume that the left-hand sides are identical. We define t p νH where H is promising and m ĉ p ν b . In fact, relation can be defined while conditionsĉ p ν i are constructed. 6 Note that is in general not an ordering and that it may even containBut if there are no such cycles, one can create (by topological sorting) a linear ordering ≺ on all expand rules with isomorphic left-hand sides (where we again assume that they have in fact identical left-hand sides) so that t p νThe following lemma states that these conditions can serve as lookahead conditions for predictive expand rules: where G is an initial configuration, and H is promising. Then there is an expand rule t p ν so that H ⇒ m t p ν K and K is promising. By construction, m ĉ p ν . If there were a smaller expand rule tpν ≺ t p ν with m ĉpν , then this would imply t p ν tpν because K is promising, and therefore, t p ν ≺ tpν , contradicting the linearity of ≺. Therefore, m ¬ĉpν for tpν ≺ t p ν and m ĉ p ν , i.e., t p ν is the only expand rule that satisfies its lookahead condition for H, i.e., m c p ν .The proof shows that these lookahead conditions always select a unique expand rule. Clearly, this cannot succeed for situations where expand rules can turn a promising configuration into two or more promising successor configurations.However, the existence of a set of predictive expand rules is not sufficient for obtaining a predictive top-down parser. The threaded HR grammar must satisfy the following property as well: Proof. Let Γ ,Γ , and R ptd be as in the theorem. Moreover, letΓ satisfy the free edge choice property, and let R be a set of predictive expand rules forΓ . Each derivation G ⇒ * R ptd H where G and H are initial and accepting configurations, resp., is also a successful parse in RΓ , i.e., unread(G) ∈ L(Γ ) by Theorem 2. Now let G be any initial configuration with unread(G) ∈ L(Γ ), i.e., G is promising. Any infinite derivation G ⇒ R ptd H 1 ⇒ R ptd H 2 ⇒ R ptd · · · would also be an infinite parse G ⇒ RΓ H 1 ⇒ RΓ H 2 ⇒ RΓ · · · , contradicting Theorem 3.Finally assume that R ptd runs into a blind alley starting at G, i.e., there is a derivation G ⇒ This theorem justifies to call a threaded HR grammarΓ predictively topdown parsable (PTD for short) ifΓ satisfies the free edge choice property and there is a set of predictive expand rules forΓ . The threaded tree grammar in Example 2 is PTD. To see this, let us construct lookahead conditions for expand rule tb1 and tl1 as described above.