Method and Apparatus for Document Transformation Based on Attribute Grammars and Attribute Couplings

1. Field of the Invention

This invention relates to a method and apparatus for transforming an attributed tree valid under an attribute grammar to another attributed tree valid under another attribute grammar.

2. Background of the Invention

Some of the expected (but only partially realized) benefits of electronic documents over paper documents include enhanced document processing capabilities and easier manipulation of documents, such as creation, editing, updating, storage, access, and delivery of documents. A key enabler for such enhancement in known systems is their ability to represent not only the contents of documents but also various meta-information about the contents. For instance, document structures such as chapter, section, and paragraph breaks can be explicitly represented for enhanced browsing, retrieval, and component reuse.

However, one central technical problem involves how to represent such meta-information in a way computers and humans can easily manipulate. One prominent approach to this problem is to adapt formal grammars (used to describe programming languages) to represent hierarchical structures of documents (e.g., chapter, section, and paragraph breaks). The Standard Generalized Markup Languages (SGML), for instance, uses an extension of context-free grammars for this purpose.

This invention addresses two insufficiencies in the existing grammar-based approaches to representing and manipulating electronic documents. First, these approaches have only a limited capability to specifying attributes and their dependencies. For example, an attribute of "section" may depend on certain attributes of "chapter". Second, these approaches have an inadequate ability to specify and compute document transformation. That is, they are unable to fully transform document instances as derivation trees of one grammar to document instances as derivation trees of another grammar.

The first limitation leads to the second. The idea of document transformation is important for a variety of reasons. For example, while the notion of grammar-based document schema is useful in capturing structural information of documents, it also imposes some rigidity on kinds of documents one can create under a given schema. Because one often wishes to modify the given schema in order to accommodate features of document design not originally considered, this creates the need to transform documents from the given schema to the modified schema. Additionally, some institution documents are so large and complex that it is highly desirable to be able to specify and compute more customized and manageable views as a document transformation. Furthermore, it is often possible and desirable to automatically assemble documents from existing documents as a document transformation. For example, generating a draft of a technical report of a research laboratory from previously submitted project reports.

Therefore, what is needed is a method and apparatus for specifying the generic properties common to a class of documents as an extended attribute grammar, specifying the transformation from the extended attribute grammar to another extended attribute grammar as an extended attribute coupling, and computing the transformation as an attribute evaluation.

Thus, this invention provides a method and apparatus for specifying generic logical structures of documents as extended attribute grammars. This invention additionally provides for a method and an apparatus for specifying the transformation from one class of logical structures to another class of logical structures as another extended attribute grammar.

This invention further provides for a method and apparatus for transforming one class of documents to a second class documents by a transformation from a first extended attribute grammar to a second extended attribute grammar, the transformation specified as an extended attribute coupling.

This invention further provides for computing the transformation from the first document to the second document as an attribute evaluation.

In order to realize these and other objectives and overcome the disadvantages in known approaches, the method and apparatus for transforming a first document to a second document comprises: specifying the class of a first document as an extended attribute grammar and the class of a second document as a second extended attribute grammar where the first and second documents are represented by trees generated from the first and second extended attribute grammars, and where the extended attribute grammars comprising logical and non-logical attributes, the non-logical attributes comprising imported, inherited and synthesized attributes; transforming the first document to the second document by specifying an extended attribute coupling between the first extended attribute grammar and the second extended attribute grammar; and computing the transformation from the tree of the first document to the tree of the second document as an attribute evaluation of the first extended attribute grammar in terms of the second extended attribute grammar. The method and apparatus for computing the attribute evaluation comprises: copying a first source tree of the first document generated from a first extended grammar into a second source tree, keeping only those imported attributes of the extended attribute coupling; evaluating the inherited and synthesized attributes of the second source tree in terms of the extended attribute coupling to produce a partially attributed tree for the second extended attribute grammar; and evaluating the remaining attributes of the partially attributed tree with respect to the second extended attribute grammar to produce the second document.

This invention will be described in detail with reference to the following figures, in which like reference numerals refer to like elements, and wherein:

FIG. 1 is a generalized derivation tree;

FIG. 2 is a generalized flowchart of the method of this invention;

FIG. 3 is a extended attribute grammar for a first document;

FIG. 4 is a source tree generated from the extended attribute grammar for the first document;

FIG. 5 is an extended attribute grammar for the second document;

FIG. 6 is a result tree of the second extended attribute grammar for the second document;

FIG. 7 is an attribute coupling grammar for coupling the first extended attribute grammar to the second extended attribute grammar;

FIG. 8 is an initial result tree having an imported attributes of the attribute coupling grammar generated from the source tree;

FIG. 9 is the fully attributed tree generated by the attribute coupling grammar from the source tree to generate the result tree; and

FIG. 10 is a block diagram of the transformation apparatus.

An alphabet is a nonempty finite set of symbols. Thus, if A is an alphabet, a string over A is a finite sequence of symbols from A. The empty string, denoted by .epsilon., is the string consisting of zero symbols. A language over A is a possibly infinite set of strings over A. A regular expression over A is associated with a regular language over A, where L(r) is the language associated with a regular expression "r". Therefore, if ".alpha." is a string over A, then .alpha. is a regular expression over A and L(.alpha.)=.alpha., i.e., the set consisting of a single string .alpha.. In particular, .epsilon. is a regular expression, and L(.epsilon.)={.epsilon.}. In addition, if "r" and "u" are regular expressions over A, so is their concatenation "ru", and:

That is, L(ru) is the set of all strings that can be constructed by concatenating a string from the language of "r" and a string from the language of "u", in that order. Furthermore, if "r" and "u" are regular expressions over A, so is their union "r.vertline.u", and:

Further, if "r" is a regular expression over A, so is its Kleene closure "r*" and:

That is, L(r*) is the set of all strings that can be constructed by concatenating zero or more strings from the language of "r" an arbitrary but finite number of times.

In addition, r.sup.+ " is used to denote the regular expression "r(r*)". Thus, the language of "r.sup.+ " is the set of all strings that can be constructed by concatenating one or more strings from the language of "r". That is, L(r*) includes a finite number of strings each having a different multiple of "r", and the empty set .epsilon., while L(r.sup.+) includes all of L(r*) except the empty set .epsilon.. For convenience, a string of a regular expression is a string in the language associated with that regular expression.

A context-free grammar with regular extension, or simply an extended context-free grammar for short, is a tuple G=(V, .SIGMA., P, Z). V is an alphabet called the vocabulary of G, and the members of V are called (grammar) symbols of G. .SIGMA. is a subset of V, and the members of .SIGMA. are called terminal symbols of G. The symbols of V which are not terminal symbols of G are called nonterminal symbols of G. Z is a designated nonterminal symbol of G called the start symbol of G. P is a finite set of productions of G. The productions of G are in the form:

where "q" is the name of the production, X is a symbol of G and "r" is a regular expression over V-{Z}. If X is a terminal symbol, "r" is the empty string .epsilon..

The nonterminal symbols start with an upper case letter, whereas terminal symbols are all in lower case. FIG. 1 shows an example of an extended context free grammar G.sub.1.

In the extended context free grammar G.sub.1 shown in FIG. 1, the terminal symbol .SIGMA..sub.1 of G.sub.1 is the symbol "word". The start symbol Z.sub.1 of G.sub.1 if the symbol "Section". The vocabulary V.sub.1 of G.sub.1 is "Section, SectionHead, Paragraph, Summary, word". Thus, the productions "q.sub.n are:

The production "q.sub.0 " states that each Section comprises a SectionHead followed by one or more Paragraphs and possibly by a Summary. The production "q.sub.1 " states that each SectionHead is a sequence of one or more words. The production "q.sub.2 " states that each paragraph is also a sequence of one or more words. Finally, the production "q.sub.3 " states that each summary is also a sequence of one or more words. Further, for any production, "q: A.fwdarw.r", of an extended context-free grammar, an instance of the production is:

where .alpha. is a string in the language L(r) of the regular expression "r". For instance, production "q.sub.0 " above has the following possible instances, although it is not limited to these instances:

For an extended context-free grammar G, a derivation tree of G, or simply a tree of G, is an ordered, labeled tree such that every node is labeled with a symbol of G. Then every internal node (i.e., a node having one or more children) is associated with a production of G. Thus, for every internal node, if its label is "A" and if the labels of its children are "X.sub.1, X.sub.2, . . . X.sub.n " from left to right, "A.fwdarw.X.sub.1 X.sub.2 . . . X.sub.n " is an instance of the production associated with the internal node. A derivation tree is complete is its root node is labeled with the start symbol of the grammar and every leaf node (i.e., a node with no children) is labeled with a terminal symbol. FIG. 1 shows an example of complete derivation trees for the grammar in the example above.

This generic structure and attributes of the structural components of a document are given by an extension of conventional attribute grammars, as shown in FIG. 2. Document transformation is then given by a mapping from attributed trees of a source extended attribute grammar to attributed trees of a result extended attribute grammar (Step S10). A critical point is that such mappings themselves are specified by a special form of extended attribute grammars, extended attribute couplings. The document transformation is then computed as an attribute evaluation process under the attribute coupling grammars. An input to this process is an attributed tree of the result attribute grammar. Finally, the remaining attributes of this tree are evaluated under the result grammar for full attribution (STEP S20).

FIGS. 3-6 show the extended attribute grammars and resulting trees for a pair of documents. FIG. 3 shows a first extended attribute grammar for a first document. FIG. 4 shows the attributed tree generated from the first document based on the first extended attribute grammar. In contrast, FIG. 5 shows a second attribute grammar of a second document and FIG. 6 shows a second tree generated from the second document based on the second extended attribute grammar. Since, in the following example, the first document will be transformed into the second document, the first extended attribute grammar, the first tree and the first document will also be referred to as the source extended attribute grammar, the source tree and the source document. Likewise, the second extended attribute grammar, the second tree, and the second document will also be referred to as the result extended attribute grammar, the result tree and the result document.

For example, G.sub.2 =(V.sub.2, .SIGMA..sub.2, P.sub.2, Z.sub.2) is an extended context-free grammar. For each symbol X.sub.2 of G.sub.2, a number of sets of attributes exist. A first set of attributes comprises the logical attributes. These attributes are system-defined and include tree attributes. The tree attributes themselves comprise count attributes. The count attribute comprises the number of children of various nodes having the same label.

A second set of attributes comprises the non-logical attributes, which are user-defined. These attributes include imported, inherited, and synthesized attributes. Imported attributes are associated only with start and terminal symbols. In general, once the symbols are declared or defined, the attributes and their types for each of the symbols are then declared.

The types of the symbols are determined based on where they get their inputs. Synthesized attributes obtain their inputs from their children (i.e., the tree branches extending to new symbols from the current symbols). Accordingly, synthesized attributes are generally computed. However, they can also be merely copied from one child symbol.

For inherited attributes, the flow of information is opposite that of synthesized attributes. That is, inherited attributes obtain their inputs from the parent symbols on the tree. Accordingly, inherited attributes are generally merely copied from the parent symbol, although they can also be calculated.

For imported attributes, the flow of information is not within, but between, trees. Thus, imported attributes obtain their inputs from other trees. Further, while only terminal and start symbols have imported attributes, imported attributes can obtain their inputs from any symbol of the other tree. Accordingly, the imported attribute can be either computed from or merely a copy of the inputted attribute value.

These sets are pair-wise disjoint. Every logical attribute has a universal definition. One class of (tree) attributes of this category called count attributes. That is, each symbol X has a count-Y attribute for each symbol Y of the grammar, which represents the number of children labeled "Y". For an example of synthesized and inherited attributes, suppose we have the following production,

Then, the two symbols "Lab" and "Scientist" might have the following attributes. The symbol "Lab" has as its attributes "Total-Patents" which is a synthesized attribute and "Base-Salary" which is an inherited attribute. The symbol "Scientist" has as its attributes "Bonus" and "Patents" which are synthesized attributes and "Total-Salary" which is an inherited attribute.

Each production is then associated with a set of attribution sentences, or simply sentences. These sentences state, for instance, that the number of total patents of Lab is the sum of patents of individual Scientists, or that for each Scientist, his salary is the base salary of Lab together with his bonus.

For notational simplicity, no symbol in a product has multiple occurrences. This is achieved by renaming multiple occurrences via subscripts or the like and by treating each of the multiple occurrences as interchangeable symbols for the purpose of syntactic manipulation such as construction of derivation trees, as usually is done in a convention attribute grammars. However, in the setting of extended context-free grammars, a symbol in a production may occur within a scope of the repetition operators, such as * and + (e.g., Scientist+), and an instance of such a production may have multiple occurrences of a symbol. For example, one instance of the production "q.sub.0 " of Eq. (6) may be Lab.fwdarw.Scientist Scientist Scientist.

In order to distinguish such occurrences, each symbol in a production is given an array name, and is distinguished from its occurrences within an instance of the production through array indices. Given a production "q: A.fwdarw.r", its array index expression, or simply index expression, is either a positive integer, an index variable, for which we use i,j,k as the count attributes of A, or an arithmetic expression constructed from these symbols. Generally, I,J,K are used to denote index expressions. If "q" is a production of G, then an attribute meta-variable of "q" is in the form "X[I].a", where X is a symbol appearing in "q" and "a" is an attribute of X. For example, the elements of the instance, ".lambda..sub.1 " can be labeled as Scientist[a].bonus, Scientist[i].bonus, Scientist [i+1].bonus, Scientist[count].bonus, or the like. In the last example, count is an abbreviation for Lab.count-Scientist. When the occurrence of a symbol in a production is outside the scope of the iteration operators, the index is omitted in writing the attribute variables. For example, e.g., Lab.base-salary is used instead of Lab[1].base-salary.

The following points on these variables should be noted. First, the variables of a production are actually meta-variables of scheme-variables in the sense that they will be instantiated to actual variables when a production gets instantiated. Second, if an attribute variable has no occurrences of index variables, this meta-variable ranges over a singleton set consisting of itself. That is, the meta-variable Scientist[1].bonus ranges over the set of actual variables {Scientist[1].bonus}.

Furthermore, for each production, its attribute variables are divided into input and output variables. An attribute variable X[I].a is an output variable if X appears on the left side of the arrow (in which case, I=1) and a is a synthesized attribute of X, or X appears on the right side of the arrow and "a" is an inherited attribute of X. Otherwise, it is an input variable. For instance, for the production "q.sub.0 " and its example attributes given above, Lab.total-patents and Scientist[1].total-salary are output variables, while Lab.base-salary, Scientist[1].bonus and Scientist[1].patents are input variables.

A metalinguistic means of constructing lists is now introduced, which has the form of:

where X[I].a is an attribute variable, and I has a single index variable which ranges from the value of J to the value of K, inclusive. For example (Scientist[i+1].bonus.sub.1.sup.count means the list (Scientist[2].bonus, Scientist[3].bonus, . . . , Scientist [count+1].bonus). Again, count is an abbreviation for Lab.count-Scientist.

If some predefined set of functions and constants are assumed, which are referred to as external functions and constants, then "q: A.fwdarw.Ar" is a production. The attribution terms of "q: A.fwdarw.r", or simply terms of "q", are those defined as expressions that can be constructed from count attributes of A, attribute variables and list expressions of "q", and external functions. For instance, given the production of Eq.(8):

some of its attribution terms are Scientist[1].bonus, (Scientist[i+1].bonus.sub.1.sup.count, sum((Scientist[i+1].bonus.sub.1.sup.count), budget(Lab.name, current-year), and Lab.count-Scientist. In this case current-year is an external constant, and budget an external function (defined by an external database, for instance). A term of "q" is an input term of "q" if every variable appearing in it is an input variable of "q". Finally, an attribution sentence of a production "q" is an universally quantified sentence of the form,

where "x" is an index variable, "v" is an output variable of "q" and "t" is an input term of "q". For instance, for the production "q.sub.0 " above,

Given an instance ".lambda..sub.1 " of "q.sub.0 : Lab=Scientist Scientist Scientist", this attribution sentence generates the following semantic equations,

If no free index variables appears in "v=t", the universal quantifier is dropped, and the simple term, "v=t" is used for attribute sentences. For instance, the production ".lambda..sub.1 " of "q.sub.0 " may have the attribution sentence:

which, given the instance ".lambda..sub.1 : Lab=Scientist Scientist Scientist", generates the following equation,

An attribution of a production "q" is a set of attribution sentences of "q", and it is complete if it contains exactly one sentence for each output variable of "q" and nothing more.

Thus, an extended attribute grammar is an extended context-free grammar G together with the following additions. First, each symbol of G is associated with synthesized and inherited attributes, and possibly imported attributes (for the case of the start and terminal symbols). Second, each production of G has a complete attribution. Two examples of extended attribute grammars are shown in FIG. 3 and FIG. 5. These two grammars also serve as a source grammar (FIG. 3) and a result grammar (FIG. 5) for an illustration of document transformation. Furthermore, FIGS. 4 and 6 show examples of derivation trees under the source grammar and the result grammar, respectively.

The grammar G=(V,.SIGMA.,P,Z) is an extended context-free grammar. The trees T.sub.1, T.sub.2, . . . , T.sub.n are a sequence of derivation trees of G where the root label of T.sub.i is A.sub.i. The grammar G has a production "p: A.fwdarw.r" such that "r" accepts the string "A.sub.1 A.sub.2 . . . A.sub.n ". Then the tree constructed from the sequence of T.sub.i s by adding a new root labeled with "A" as the parent of the root nodes of the T.sub.i s is called a unit reduction of the sequence T.sub.i s through p.

More generally, a sequence of trees may admit multiple unit reductions simultaneously. For example, a sequence of trees of G, .sigma., has a partition into subsequences .sigma..sub.1, .sigma..sub.2 , . . . .sigma..sub.k such that each subsequence .sigma., has a unit reduction through a production p.sub.i of G. The sequence of these unit reductions is called a reduction of .sigma. through p.sub.1 p.sub.2 . . . p.sub.k. For instance, a sequence of trees T.sub.1, T.sub.2. T.sub.3, T.sub.4 has root labels A, B, C, D. An extended context-free grammar G has the productions: "p.sub.1 : K.fwdarw.AB.sup.+ " and "p.sub.2 : L.fwdarw.(C.vertline.A)D*". Then the sequence of T.sub.i s admits two unit reductions. The first unit reduction is the unit reduction of T.sub.1 T.sub.2 through p.sub.1. The second is the unit reduction of T.sub.3 T.sub.4 through p.sub.2. Thus, the tree sequence admits a reduction through p.sub.1 p.sub.2.

A G-based reduction operator is a map that takes a sequence of derivation trees of G and produces its reduction. A reduction operator has a syntactic signature, which is a regular expression over the set of production names of G. For instance, assuming G has the productions "p.sub.1 " and "p.sub.2 " above, a G-based reduction operator may have a signature p.sub.1.sup.+ (p.sub.2 .vertline..epsilon.). Intuitively, this signature indicates that any reduction operator of this signature must use "p.sub.1 " one or more times and "p.sub.2 " at most once, in this order from left to right. For instance, a tree sequence with root labels "A,B,B,A,B,C,D" can be reduced through a reduction operator having the above signature by using p.sub.1 twice and then p.sub.2 once.

If ".delta." is a reduction operator, the regular expression obtained from its signature by replacing each p.sub.i by its left-hand side is called the type of .delta., while the regular expression obtained from the signature by replacing each p.sub.i by its right-hand side is called the arity of .delta.. For instance, if .delta. has signature p.sub.1.sup.+ (p.sub.2 .vertline..epsilon.), its type of K.sup.+ (L/.epsilon.), while its arity is (AB.sup.+).sup.+ ((C.vertline.A)D*.vertline..epsilon.). Thus, a reduction operator takes a tree sequence whose root labels form a string accepted by its arity and generates its reduction whose root labels form a string accepted by its type.

Consider a production "q: H.fwdarw.r" with some synthesized and inherited attributes assigned to its symbols. The attribution sentences of "q" involves reduction operators. An attribution of "q" is then G-based if all of its reduction operators are G-based. The grammars G.sub.1 and G.sub.2 are extended attribute grammars. An extended attribute coupling from G.sub.1 to G.sub.2 is an extended attribute grammar .GAMMA. such that the extended context-free grammar of .GAMMA. is the same as that of G.sub.1. Then, every production of .GAMMA. has a complete G.sub.2 -based attribution. Further, some synthesized or inherited attributes of .GAMMA. are distinguished as syntactic attributes, and the start symbol of .GAMMA. has a special syntactic attribute result-tree which is defined through a reduction operator of type Z.sub.2, the start symbol of G.sub.2. Finally, any symbol of .GAMMA. may have imported attributes, and every imported attribute of .GAMMA. is an attribute of G.sub.1 whereas every imported attribute G.sub.2 is an attribute of .GAMMA..

Further, .GAMMA. is well-formed if for every production of .GAMMA., its syntactic input variable appears at most once as an argument. Note that if an attribute coupling is well-formed, the value of the syntactic attribute result-tree of Z.sub.1 is always a complete derivation tree of G.sub.2. FIG. 7 shows an example of attribute couplings from the source grammar shown in FIG. 3 to the result grammar shown in FIG. 5.

Once a transformation is specified in terms of a source extended attribute grammar, an extended attribute coupling and a result extended attribute grammar, the transformation of the source document to the result document consists of three main steps.

First, given source tree is copied to create an initial result tree. The initial result tree keeps only those imported attributes of the coupling grammar. Then, the remaining attributes of the copied tree are evaluated with respect to the extended attribute coupling. This produces a partially attributed result tree of the result grammar. This is produced as the value of the syntactic attribute result-tree of the coupling grammar. Finally, the remaining attributes of the partially attributed tree are evaluated with respect to the result extended attribute grammar. Well-known attribute evaluation algorithms exist that can be used for these two evaluation steps, such as "Attribute Grammars", by P. Deransart, M. Jourdan, and B. Lorho, Springer-Verlag, 1988, New York.

For an example, take the attributed tree shown in FIG. 4 of the source grammar shown in FIG. 3 as an input to the transformation given by the coupling shown in FIG. 7 and the result grammar shown in FIG. 5. FIG. 7 indicates the symbols of the nodes of the result tree of FIG. 6 by a line over those symbols in the attribution sentences of the attribute coupling of FIG. 7. FIG. 8 shows the copy of the source tree that keeps only those imported attributes of the coupling. FIG. 9 shows result of attribute evaluation with respect to the coupling grammars as set forth in step S10 of FIG. 2. The synthesized attributes of the attribute declaration of FIG. 7 are underlined in the attribute coupling of FIG. 7 and are used to couple imported attributes from the terminal symbols of the source tree to terminal symbols of the result tree. The value of the syntactic attribute result-tree of the root node in that figure is a derivation tree of the result grammar with imported attributes (i.e., name and salary). Finally, this tree is fully attributed, as set forth in step S20 of FIG. 2, with respect to the result grammar, which results in the final result tree shown in FIG. 6.

As shown in FIG. 10, the transformation apparatus 20 such as a general purpose computer comprises a first grammar determination means 22 for determining the first extended attribute grammar corresponding to the first document. The transformation apparatus 20 also comprises a second grammar determination means 24 and a third grammar determination means 26 for determining the second extended attribute grammar corresponding to the second document and the extended attribute coupling grammar for transforming the first document to the second document, respectively.

The transformation apparatus 20 also comprises a first tree generating means 30 for generating a first tree from the first extended attribute grammar and the first document. The transformation apparatus 20 also comprises a second tree generating means 32 for generating a tree from the source tree and the extended attribute coupling grammar. Finally, the transformation apparatus 20 comprises a converting means 34 for converting the result tree into the second document.

As also shown in FIG. 10, the first grammar determination means 22 itself comprises a vocabulary determining means 40 for determining the vocabulary of the first extended attribute grammar and a production determining means 60 for determining a production of the first extended attribute grammar. The second grammar determining means 24 and the third grammar determining means 26 generally comprise the same elements and subelements as the first grammar determining means 22. Thus, the following discussion, while relating only to the first grammar determining means 22, is also applicable to the second and third grammar determining means 24 and 26.

Further, the vocabulary determining means 40 comprises a terminal symbol determining means 42 for determining a terminal symbol of the extended attribute grammar. The vocabulary determining means also comprises a non-terminal symbol determining means 44 for determining one or more non-terminal symbols of the extended attribute grammar. Finally, the vocabulary determining means also comprises a start symbol determining means 46 for determining which one of the one or more non-terminal symbols is the start symbol.

Together, the terminal symbol determining means 42, the non-terminal symbol determining means 44 and the start symbol determining means 46 combine to form a generalized symbol determining means 48. The vocabulary determining means 40 further comprises a logical attribute determining means 50 for determining at least one logical attribute for the symbols determined by the symbol determining means 48 and a non-logical attribute determining means 52 for determining at least one non-logical attribute for each of the pluralities of symbols determined by the symbol determining means 48.

The non-logical attribute determining means 52 itself comprises synthesized attribute determining means 54 for determining synthesized attributes for one or more of the plurality of symbols; inherited attribute determining means 56 for determining at least one inherited attribute for one or more of the plurality of symbols; and imported attribute determining means 58 for determining at least one imported attribute for one or both of the terminal symbol and the start symbol determined by the symbol determining means 48.

While the invention has been described in connection with the preferred embodiment, it will be understood that it is not intended to limit the invention to these embodiments. On the contrary, it is intended to cover all alternatives, modifications and equivalents as may be included within the spirit and scope of the invention as defined by the appended claims.