BookBody
.pdfSec. 12.3] |
Parsing in polynomial time |
261 |
KnownGoalList: array [1..ArraySize] of KnownGoalType;
NKnownGoals: integer;
KnownRuleList: array [1..ArraySize] of RuleNmbType;
NKnownRules: integer;
function KnownGoalNumber(nmb: RuleNmbType; pos, len: integer):integer; var n: integer;
begin
KnownGoalNumber:= 0;
for n:= 1 to NKnownGoals do with KnownGoalList[n] do
if (nmb=NmbField) and (pos=PosField)
and (len=LenField) then KnownGoalNumber:= n;
end { KnownGoalNumber };
procedure StartNewKnownGoal(nmb: RuleNmbType; pos, len: integer); begin
NKnownGoals:= NKnownGoals+1;
with KnownGoalList[NKnownGoals] do begin
NmbField:= nmb; PosField:= pos; LenField:= len; StartParsingField:= NRulesStacked+1; NKnownParsingsField:= 0;
end;
end { StartNewKnownGoal };
procedure RecordKnownParsing; var n, i: integer;
begin
with Stack[NStackElems] do begin
n:= KnownGoalNumber(NmbField, PosField, LenField); with KnownGoalList[n] do
begin
NKnownParsingsField:= NKnownParsingsField+1; with KnownParsingField[NKnownParsingsField] do begin
StartField:= NKnownRules+1;
for i:= StartParsingField to NRulesStacked do begin
NKnownRules:= NKnownRules+1; KnownRuleList[NKnownRules]:= RuleStack[i];
end;
EndField:= NKnownRules; end;
end;
end;
end { RecordKnownParsing };
function KnownGoalSucceeds
(nmb: RuleNmbType; pos, len: integer): Boolean; var n, oldNRulesStacked, i, j: integer;
begin
n:= KnownGoalNumber(nmb, pos, len);
262 |
A simple general context-free parser |
[Ch. 12 |
if n = 0 then KnownGoalSucceeds:= false else begin
oldNRulesStacked:= NRulesStacked; with KnownGoalList[n] do
begin
for i:= 1 to NKnownParsingsField do with KnownParsingField[i] do begin
for j:= StartField to EndField do begin
NRulesStacked:= NRulesStacked+1; RuleStack[NRulesStacked]:=
KnownRuleList[j];
end;
AdvanceTOS(len);
DoTopOfStack;
RetractTOS(len);
NRulesStacked:= oldNRulesStacked; end;
end;
KnownGoalSucceeds:= true; end;
end { KnownGoalSucceeds };
NKnownGoals:= 0; NKnownRules:= 0; |
{ in procedure Parse } |
Figure 12.2 Additions for the known-parsing table
Our parser can be equipped with the known-parsing table by incorporating the declarations of Figure 12.2 in it. StartNewKnownGoal, RecordKnownParsing and
KnownGoalSucceeds replace the dummy declarations in Figure 12.1, the other declarations and the initialization statement are to be inserted in the appropriate places. The thus modified parser will no longer require exponential time (if sufficient memory is supplied; see the constant declarations).
Returning to the mechanism of the parser, we see that when a new goal is established in TryRule for which IsToBeAvoided yields false, a call is made to KnownGoalSucceeds. This function accesses the known-parsing table to find out if the goal has been pursued before. When called for the very first time, it will yield false since there are no known parsings yet and not KnownGoalSucceeds will succeed as in the unmodified parser. We enter the block that really tries the rule, preceded by a call to StartNewKnownGoal. This prepares the table for the recording of the zero or more parsings that will be found for this new goal.
Goals are recorded in a three-level data structure. The first level is the array KnownGoalList, whose elements are of type KnownGoalType. A known goal has three fields describing the rule number, position and length of the goal and a KnownParsingField, which is an array of elements of type KnownParsingType and which forms the second level; it has also a field StartParsingField, which is only meaningful while the present table entry is being constructed. Each element in KnownParsingField describes a partial parse tree for the described goal. The partial parse tree is represented as a list of rule numbers, just as the full parse tree. These lists are stored one after another in the array KnownRuleList, which is the third level; the
Sec. 12.3] |
Parsing in polynomial time |
263 |
beginning and end of each parsing are recorded in the StartField and EndField of the known parsing.
StartNewKnownGoal records the goal in a new element of KnownGoalList. It sets StartParsingField to NRulesStacked+1, since that is the position in RuleStack where the first rule number for the present goal will go. When the main mechanism of the parser has found a parsing for the goal (in DoNextOnStack) it calls RecordKnownParsing, which adds the parsing found in RuleStack between StartParsingField and NRulesStacked to the present known goal under construction. To this end, it finds the pertinent element in KnownGoalList, adds an element to the corresponding KnownParsingField and copies the parsing to the array KnownRuleList while recording the begin and end in the element in KnownParsingField. There is no need to signal the end of the construction of a known goal. Note that as long as the goal is under construction, it is also on the parse stack; this means that IsToBeAvoided will yield true which in turn guarantees that StartNewKnownGoal will not be called again while the known goal is being constructed.
The next time the goal is tried by TryRule, KnownGoalSucceeds will indeed succeed: for each of the elements in the pertinent KnownParsingField, the corresponding segment of KnownRuleList, which contains one partial parse tree, is copied to the RuleStack as if the parsing had been performed normally. The advance in length is noted and DoTopOfStack is called, again just as in the normal parsing process. Upon its return, the original situation is restored, including the value of NRulesStacked.
It will be obvious that copying a ready-made solution is much faster than reconstructing that solution. That it makes the difference between exponential and polynomial behaviour is less obvious, but true nevertheless. The unmodified parser tries 41624 rules for the built-in example, the parser with the known-parsing table only 203. The new parser can be improved considerably in many points, with a corresponding increase in efficiency; the O (n k +1 ) dependency remains, though.
13
Annotated bibliography
The purpose of this annotated bibliography is to supply the reader with more material and with more detail than was possible in the preceding chapters, rather than to just list the works referenced in the text. The annotations cover a considerable number of subjects that have not been treated in the rest of the book.
The articles and books presented here have been selected for two criteria: relevancy and accessibility. The notion of relevancy has been interpreted very widely; parsers are used in an increasing number of applications and relevancy to others is hard to judge. In practice, entries have only been rejected if they were either too theoretical or did not supply insight into or understanding of parsing. Accessibility has been taken to mean ready availability to a researcher who has access to a moderately wellequipped university or company research library. We expect such a library to hold most of the prominent computer science journals, but not all or even a major part of the proceedings of conferences on programming languages and compiler construction, let alone technical reports from various research institutes all over the world. We have often been forced to compromise this criterion, to include pertinent material not otherwise available; for instance, nothing seems to have been published on left-corner parsing in journals. Fortunately, relevant material that was first published in a technical report or as a PhD thesis was often published later in a prominent journal; in these cases a reference to the original publication can be found by consulting the journal paper referenced here. We have kept the references to technical reports to the absolute minimum. No non-English (that is, no non-English-language) material has been included. It is our intention that the present collection be complete under the above criteria, but we have no real hope that such perfection has been attained. We shall be grateful to be pointed to additional references.
The bibliography contains about 400 entries, almost all of them from the Western world. Some papers from the Soviet Union and Eastern Europe have been included, if available in translation. Much work on parsing has been done and is still being done in Japan; it has been sorely underrepresented in this collection, for reasons of accessibility. Only readily available full material in translation has been included, although much more is available in the form of abstracts in English.
This annotated bibliography differs in several respects from the habitual literature
list.
The entries have been grouped into fourteen categories:
Ch. 13] |
Annotated bibliography |
265 |
13.1miscellaneous literature (Misc);
13.2unrestricted PS and CS grammars (PSCS);
13.3van Wijngaarden grammars and affix grammars (VW);
13.4general context-free parsers (CF);
13.5LL parsing (LL);
13.6LR parsing (LR);
13.7left-corner parsing (LC);
13.8precedence and bounded-context parsing (Precedence);
13.9finite-state automata (FS);
13.10natural language handling (NatLang);
13.11error handling (ErrHandl);
13.12transformations on grammars (Transform);
13.13general books on parsing (Books);
13.14some books on computer science (CSBooks).
The nature of publications in parsing is so that the large majority of them can easily be assigned a single category. Some that span two categories have been placed in one, with a reference in the other. Publications of a more general nature have found a place in “Miscellaneous Literature”.
The entries are annotated. This annotation is not a copy of the abstract provided with the paper (which generally said something about the results obtained) but is rather the result of an attempt to summarize the technical content in terms of what has been explained elsewhere in this book.
The entries are ordered chronologically rather than alphabetically.
This arrangement has the advantage that it is much more meaningful than a single alphabetic list, ordered on author names. Each section can be read as the history of research on that particular aspect of parsing, related material is found closely together and recent material is easily separated from older publications. A disadvantage is that it is now difficult to locate entries by author; to remedy this, an author index has been supplied. Only a tiny fraction of the entries is referred to in the previous chapters; these occurrences are also included in the author index.
Terms from computer science have been used more freely in the annotations than in the rest of the book (an example is “transitive closure”). See, for instance, Sedgewick [CSBooks 1988] or Smith [CSBooks 1989] for an explanation.
Note that there is a journal called Computer Languages (Elmsford, NY) and one called Computer Language (San Francisco, CA); both abbreviate to Comput. Lang.; the place name is essential to distinguish between them (although the first originates from Exeter, Devon, England).
13.1 MISCELLANEOUS LITERATURE
Noam Chomsky, “Three models for the description of language”, IEEE Trans.
Inform. Theory, vol. 2, no. 3, p. 113-124, 1956. In an attempt to delineate the set of correct English sentences, the author considers three mechanisms. Finite-state automata are rejected on the grounds that they cannot cope with arbitrary nesting. Phrase structure grammars are considered probably applicable but declared impractical due to their problems in expressing context conditions. Most of these problems can be solved if we augment PS grammars with transformation rules, which specify the rearrangement of parts of the derivation tree.
Noam Chomsky, “On certain formal properties of grammars”, Inform. Control,
266 |
Annotated bibliography |
[Ch. 13 |
vol. 2, p. 137-167, 1959. This article discusses what later became known as the Chomsky hierarchy. Chomsky defines type 1 grammars in the “context-sensitive” way. His motivation for this is that it permits the construction of a tree as a structural description. Type 2 grammars exclude e-rules, so in Chomsky’s system, type 2 grammars are a subset of type 1 grammars.
Next, the so called counter languages are discussed. A counter language is a language recognized by a finite automaton, extended with a finite number of counters, each of which can assume infinitely many values. L 1 ={a n b n | n>0} is a counter language, L 2 ={xy | x,yÎ{a,b}* , y is the mirror image of x} is not, so there are type 2 languages that are not counter languages. The reverse is not investigated.
The Chomsky Normal Form is introduced, but not under that name, and a bit different: Chomsky calls a type 2 grammar regular if production rules have the form A ®a or A ®BC, with B ¹C, and if A ®aA b and A ®gA h then a=g and b=h. A grammar is self-embedding if there is a derivation A ®* aA b with a¹e and b¹e. The bulk of the paper is dedicated to the theorem that the extra power of type 2 grammars over type 3 grammars lies in this self-embedding property.
J.W. Backus, F.L. Bauer, J. Green, C. Katz, J. McCarthy, P. Naur (Ed.), A.J.
Perlis, H. Rutishauser, K. Samelson, B. Vauquois, J.H. Wegstein, A. van Wijngaarden, M. Woodger, “Report on the algorithmic language ALGOL 60”, Commun. ACM, vol. 3, no. 5, p. 299-314, May 1960. First application of a BNF grammar (for the definition of a programming language). Revised report by the same authors: Commun.
ACM, vol. 6, no. 1, p. 1-17, Jan 1963.
R.A. Brooker, I.R. MacCallum, D. Morris, J.S. Rohl, “The compiler-compiler”,
Annual Review in Automatic Programming, vol. 3, p. 229-275, 1960 ????. One of the first extensive descriptions of a compiler-compiler. Parsing is done by a backtracking non-exhaustive top-down parser using a transduction-like grammar. This grammar is kept in an integrated form and modifications can be made to it while parsing.
Robert W. Floyd, “A descriptive language for symbol manipulation”, J. ACM,
vol. 8, p. 579-584, Oct 1961. Original paper describing Floyd productions. See Section 9.3.1.
Robert S. Ledley, James B. Wilson, “Automatic-programming-language translation through syntactical analysis”, Commun. ACM, vol. 5, no. 3, p. 145-155,
March 1962. An English-to-Korean (!) translation system is described in detail, in which parts of the Korean translation are stored in attributes in the parse tree, to be reordered and interspersed with Korean syntactic markers on output. The parser is Irons’ [CF 1961].
Melvin E. Conway, “Design of a separable transition-diagram compiler”, Com-
mun. ACM, vol. 6, no. 7, p. 396-408, July 1963. The first to introduce coroutines and to apply them to structure a compiler. The parser is Irons’ [CF 1961], made deterministic by a No-Loop Condition and a No-Backup Condition. It follows transition diagrams rather than grammar rules.
Robert W. Floyd, “The syntax of programming languages - a survey”, IEEE
Trans. Electronic Comput., vol. EC-13, p. 346-353, 1964. Early analysis of the advantages of and problems with the use of grammars for the specification of programming languages. Contains a bibliography of almost 100 entries.
Jerome Feldman, David Gries, “Translator writing systems”, Commun. ACM,
vol. 11, no. 2, p. 77-113, Feb. 1968. Grand summary of the work done on parsers (with semantic actions) before 1968.
D.J. Cohen, C.C. Gotlieb, “A list structure form of grammars for syntactic
analysis”, Computing Surveys, vol. 2, no. 1, p. 65-82, 1970. CF rules are represented as linked lists of alternatives, which themselves are linked lists of members. The trick is that both lists end in different null pointers. This representation is very amenable to various backtracking and nonbacktracking top-down and bottom-up parsing methods (by interpreting the grammar). Several practical parsers are given in flowchart form. An algorithm is given to “invert” a grammar, i.e. the linked lists, to
Sec. 13.1] |
Miscellaneous literature |
267 |
create a data structure that will efficiently guide a bottom-up parser.
A. Birman, J.D. Ullman, “Parsing algorithms with backtrack”, Inform. Control,
vol. 23, no. 1, p. 1-34, 1973. Models classes of recursive descent parsers, capable of recognizing all deterministic context-free languages and also some non-context-free languages.
B.W. Kernighan, L.L. Cherry, “A system for typesetting mathematics”, Commun.
ACM, vol. 18, no. 3, p. 151-157, March 1975. A good example of the use of an ambiguous grammar to specify the preferred analysis of special cases.
A.V. Aho, S.C. Johnson, J.D. Ullman, “Deterministic parsing of ambiguous gram-
mars”, Commun. ACM, vol. 18, no. 8, p. 441-452, 1975. Demonstrates how LL and LR parsers can be constructed for certain classes of ambiguous grammars, using simple disambiguating rules, such as operator-precedence.
Jacques Cohen, “Experience with a conversational parser generation system”,
Softw. Pract. Exper., vol. 5, p. 169-180, 1975. Realistic description of the construction of a professional interactive parser generator.
Jay Earley, “Ambiguity and precedence in syntax description”, Acta Inform., vol.
4, p. 183-192, 1975. Informal description of how to use precedence information for disambiguation.
Michael Marcotty, Henry F. Ledgard, Gregor V. Bochmann, “A sampler of for-
mal definitions”, Computing Surveys, vol. 8, no. 2, p. 191-276, June 1976.
Describes and compares four semantic definition methods: VW grammars, production systems and the axiomatic approach, Vienna Definition Language, and attribute grammars. No clear winner emerges.
R.M. Wharton, “Resolution of ambiguity in parsing”, Acta Inform., vol. 6, no. 4,
p. 387-395, 1976. It is proposed that ambiguity be resolved in a bottom-up parser by 1) reducing upon a shift/reduce conflict, 2) reducing the shorter right-hand side upon a reduce/reduce conflict and 3) reducing the textual first right-hand side upon a reduce/reduce conflict with equal lengths. In a top-down parser, criteria similar to 2) and 3) are applied to each LL(1) conflict.
R.B. Hunter, A.D. McGettrick, R. Patel, “LL versus LR parsing with illustrations
from Algol 68”, ACM SIGPLAN Notices, vol. 12, no. 6, p. 49-53, June 1977.
Syntax-improved LL(1) (Foster [Transform 1968]) and LR(1) are equally unsuccessful in handling a CF version of the grammar of Algol 68. After hand adaptation LL(1) has the advantage.
Niklaus Wirth, “What can we do about the unnecessary diversity of notation for
syntactic definitions?”, Commun. ACM, vol. 20, no. 11, p. 822-823, Nov 1977.
Introduces Wirth’s notation for extended CF grammars, using {...} for repetition, [...] for optionality, (...) for grouping and "..." for quoting.
Jacques Cohen, Martin S. Roth, “Analyses of deterministic parsing algorithms”,
Commun. ACM, vol. 21, no. 6, p. 448-458, June 1978. Gives methods to calculate the average parsing times and their standard deviations from the input grammar, for several parsers. The resulting formulae are finite series, and are sometimes given in closed form.
Kuo-Chung Tai, “On the implementation of parsing tables”, ACM SIGPLAN
Notices, vol. 14, no. 1, p. 100-101, Jan 1979. How to implement parsing tables using hashing.
Peter Deussen, “One abstract accepting algorithm for all kinds of parsers”. In
Automata, languages and programming, Hermann A. Maurer (eds.), Lecture Notes in Computer Science #71, Springer-Verlag, Berlin, p. 203-217, 1979. Parsing
268 |
Annotated bibliography |
[Ch. 13 |
is viewed as an abstract search problem, for which a high-level algorithm is given. The selection predicate involved is narrowed down to give known linear parsing methods.
Robert Endre Tarjan, Andrew Chi-Chih Yao, “Storing a sparse table”, Commun.
ACM, vol. 22, no. 11, p. 606-611, Nov. 1979. Two methods of storing sparse tables are presented and analysed: trie structure and double displacement.
Hanan Samet, “A coroutine approach to parsing”, ACM Trans. Prog. Lang. Syst.,
vol. 2, no. 3, p. 290-306, July 1980. Some inputs consist of interleaved chunks of text conforming to different grammars. An example is programming text interrupted at unpredictable points by macro-processor directives. This situation can be handled by having separate parsers for each grammar, cooperating in coroutine fashion.
Anton Nijholt, “Parsing strategies: A concise survey”. In Mathematical Foundations of Computer Science, J. Gruska & M. Chytil (eds.), Lecture Notes in Com-
puter Science #118, Springer-Verlag, Berlin, p. 103-120, 1981. The context-free parser and language field is surveyed in terse prose. Highly informative to the connoisseur.
Esko Ukkonen, “Lower bounds on the size of deterministic parsers”, J. Comput.
Syst. Sci., vol. 26, p. 153-170, 1983. Worst-case lower bounds for the parser sizes are given for the various classes of LL(k) and LR(k) parsers for k=0,1 and k³2. All LL(k) lower bounds are polynomial, except the one for full LL(k >1), which is exponential; all LR(k) bounds are exponential.
Fernando C.N. Pereira, David H.D. Warren, “Parsing as deduction”. In Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics,
Cambridge, Mass., p. 137-144, 1983. The Prolog deduction mechanism is top-down depthfirst. It can be exploited to do parsing, using Definite Clause grammars. Parsing can be done more efficiently with Earley’s technique. The corresponding Earley deduction mechanism is derived and analysed.
Anton Nijholt, Deterministic top-down and bottom-up parsing: historical notes
and bibliographies, Mathematisch Centrum, Amsterdam, p. 118, 1983. Over a 1000 references about LL(k), LR(k) and precedence parsing, with short histories and surveys of the three methods.
Peter Dencker, Karl Durre, Johannes Heuft, “Optimization of parser tables for portable compilers”, ACM Trans. Prog. Lang. Syst., vol. 6, no. 4, p. 546-572, Oct
1984. Given an n´m parser table, an n´m bit table is used to indicate which entries are error entries; this table is significantly smaller than the original table and the remaining table is now sparse (typically 90-98% don’t-care entries). The remaining table is compressed row-wise (column-wise) by setting up an interference graph in which each node corresponds to a row (column) and in which there is an edge between any two nodes the rows (columns) of which occupy an element in the same position. A (pseudo-)optimal partitioning is found by a minimal graph-colouring heuristic.
W.M. Waite, L.R. Carter, “The cost of a generated parser”, Softw. Pract. Exper.,
vol. 15, no. 3, p. 221-237, 1985. Supports with measurements the common belief that compilers employing generated parsers suffer significant performance degradation with respect to recursive descent compilers. Reasons: interpretation of parse tables versus direct execution, attribute storage allocation and the mechanism to determine which action(s) to perform. Then, a parser interface is proposed that simplifies integration of the parser; implementation of this interface in assembly language results in generated parsers that cost the same as recursive descent ones. The paper does not consider generated recursive descent parsers.
Gerard D. Finn, “Extended use of null productions in LR(1) parser applications”,
Commun. ACM, vol. 28, no. 9, p. 961-972, Sept 1985. Extensive account of how to use an LR parser for conversion purposes. Makes a strong case for the use of parsers for conversion.
270 |
Annotated bibliography |
[Ch. 13 |
Jacques Loeckx, “The parsing for general phrase-structure grammars”, Inform.
Control, vol. 16, p. 443-464, 1970. The paper sketches two non-deterministic parsers for PS grammars, one top-down, which tries to mimic the production process and one bottom-up, which tries to find a handle. The instructions of the parsers are derived by listing all possible transitions in the grammar and weeding out by hand those that cannot occur. Trial-and-error methods are discussed to resolve the non-determinism, but no instruction selection mechanisms are given. Very readable, nice pictures.
Daniel A. Walters, “Deterministic context-sensitive languages, Parts I & II”,
Inform. Control, vol. 17, no. 1, p. 14-61, 1970. The definition of LR(k) grammars is extended to context-sensitive grammars. Emphasis is more on theoretical properties than on obtaining a parser.
Z.J. Ghandour, “Formal systems and analysis of context-sensitive languages”,
Computer J., vol. 15, no. 3, p. 229-237, 1972. Ghandour describes a formal production system that is in some ways similar to but far from identical to a two-level grammar. A hierarchy of 4 classes is defined on these systems, with Class 1 Ê Class 2 É Class 3 É Class 4, Class 1 Ê CS and Class 4 = CF. A parsing algorithm for Class 1 systems is given in fairly great detail.
N.A. Khabbaz, “Multipass precedence analysis”, Acta Inform., vol. 4, p. 77-85,
1974. A hierarchy of CS grammars is given that can be parsed using multipass precedence parsing. The parser and the table construction algorithm are given explicitly.
Eberhard Bertsch, “Two thoughts on fast recognition of indexed languages”,
Inform. Control, vol. 29, p. 381-384, 1975. Proves that parsing with (tree-)unambiguous indexed grammars is possible in O (n 2 ) steps.
Robert W. Sebesta, Neil D. Jones, “Parsers for indexed grammars”, Intern. J.
Comput. Inform. Sci., vol. 7, no. 4, p. 344-359, Dec 1978. Very good explanation of indexed grammars. Three classes of indexed grammars are defined, corresponding to strong-LL, LL and LR, respectively. It is shown that the flag sets generated by indexed grammars are regular sets.
C.J.M. Turnbull, E.S. Lee, “Generalized deterministic left to right parsing”, Acta
Inform., vol. 12, p. 187-207, 1979. The LR(k) parsing machine is modified so that the reduce instruction removes the reduced right-hand side from the stack and pushes an arbitrary number of symbols back into the input stream. (The traditional LR(k) reduce is a special case of this: it pushes the recognized non-terminal back into the input and immediately shifts it. The technique is similar to that put forward by Domolki [CF 1968].) The new machine is capable of parsing efficiently a subset of the Type 0 grammars, DRP grammars (for Deterministic Regular Parsable). Membership of this subset is undecidable, but an approximate algorithm can be constructed by extending the LR(k) parse table algorithm. Details are not given, but can be found in a technical report by the first author.
Kurt Mehlhorn, “Parsing macro grammars top down”, Inform. Control, vol. 40,
no. 2, p. 123-143, 1979. Macro grammars are defined as follows. The non-terminals in a CF grammar are given parameters, as if they were routines in a programming language. The values of these parameters are strings of terminals and non-terminals (the latter with the proper number of parameters). A parameter can be passed on, possibly concatenated with some terminals and non-terminals, or can be made part of the sentential form. An algorithm to construct a recursive-descent parser for a macro grammar (if possible) is given.
G. Barth, “Fast recognition of context-sensitive structures”, Computing, vol. 22,
p. 243-256, 1979. A recording grammar (an RG) is a CF grammar in which each (numbered) production rule belongs to one of three classes: normal, recording and directed. During production, normal rules behave normally and a recording rule records its own occurrence by appending its number to a string called the p-element. When production leaves a “recording” stage, the entire p-element is added to a set called the W-component, which collects all contexts created so far. When production enters a “directed” stage, an element (a context) is retrieved from the W-component, transferred through a