ID/LP grammar

ID/LP Grammars are a subset of Phrase Structure Grammars, differentiated from other formal grammars by distinguishing between immediate dominance (ID) and linear precedence (LP) constraints. Whereas traditional phrase structure rules incorporate dominance and precedence into a single rule, ID/LP Grammars maintains separate rule sets which need not be processed simultaneously. ID/LP Grammars are used in Computational Linguistics. For example, a typical phrase structure rule such as S > NP \; VP, indicating that an S node dominates an NP node and a VP node, and that the NP precedes the VP in the surface string. In ID/LP Grammars, this rule would only indicate dominance, and a linear precedence statement, such as , would also be given. The idea first came to prominence as part of Generalized Phrase Structure Grammar; the ID/LP Grammar approach is also used in head driven phrase structure grammar, lexical functional grammar, and other unification grammars. Current work in the Minimalist Program also attempts to distinguish between dominance and ordering. For instance, recent papers by Noam Chomsky have proposed that, while hierarchical structure is the result of the syntactic structure building operation Merge, linear order is not determined by this operation, and is simply the result of externalization (oral pronunciation, or, in the case of sign language, manual signing).

Immediate dominance is the asymmetrical relationship between the mother node of a parse tree and its daughters, where the mother node (to the left of the arrow) is said to immediately dominate the daughter nodes (those to the right of the arrow), but the daughters do not immediately dominate the mother. The daughter nodes are also dominated by any node that immediately dominates the mother node, however this is not an immediate dominance relation. For example, the context free rule , shows that the node labelled A (mother node) immediately dominates nodes labelled B, C, and D, (daughter nodes) and nodes labelled B, C, and D can be immediately dominated by a node labelled A.

Linear precedence is the order relationship of sister nodes. LP constraints specify in what order sister nodes under the same mother can appear. Nodes that surface earlier in strings precede their sisters. The principle of transitivity can be applied to LP relations which means that if and , then as well. LP relationships are asymmetric: if B precedes C, C can never precede B. An LP relationship where there can be no intervening nodes is called immediate precedence, while an LP where there can be intervening nodes (those derived from the principle of transitivity) are said to have weak precedence.

For a string to be grammatical in an ID/LP Grammar, it must belong to a local subtree that follows at least one ID rule and all LP statements of the grammar. If every possible string generated by the grammar fits this criterion, than it is an ID/LP Grammar. Additionally, for a grammar to be able to be written in ID/LP format, it must have the property of Exhaustive Constant Partial Ordering (ECPO): namely that at least part of the ID/LP relations in one rule is observed in all other rules.

ID and LP rules impose constraints on sentence strings; the format of an ID/LP Grammar into a Context Free Grammar (CFG), dividing the ID/LP Grammar into an Ordered Context Free Grammar (CFG) and Unordered Context Free Grammar (UCFG). This allows the two algorithms to parse strings more efficiently; in particular, the Earley Parser uses a point tracking method that follows a linear path established by the LP rules. In a CFG, LP rules do not allow repeated constituents in the parsed string, but an UCFG allows repeated constituents within the parsed strings. If the ID/LP Grammar is converted to a UCFG then the LP rules do not dominate during the parsing process, however, it still follows the point tracking method.

The foundation of Shieber's Algorithm is based on the Earley Parser for CFG, however, it does not require the ID/LP Grammar to be converted into a different grammar in order to be parsed. ID rules can be parsed in a separate form, S →ID {V, NP, S}, from the LP rules, V < S. Shieber compared parsing of a CFG to an ordered ID/LP Grammar string and Barton compared the parsing of a UCFG to an unordered ID/LP Grammar string.

Parsing an ID/LP Grammar, directly, generates a set list that will determine whether the production of the string will be accepted or fail. The algorithm follows 6 Steps (the symbols used can also represents the Syntactic Categories):

For all of the ID rules, add to the initial item in the parse list,
If all of the elements in , , and the elements, , of does not allow Z to be preceded by ,, and Z is not an element of , ; then the following string, can be added to If all items, , are elements of , then , and and all of then the next item can be added to this list, This step will build the set list, , more. Every item, , that is an element of and where , and then the following item is added, , to If items, , are elements of and items, , are elements of where , and ; the string, , is added to If the items, , is an element of where , and ; the string, , is added to
Steps 2 3 are repeated exhaustively until no more new items can be added and then continue on to Step 4. Steps 5 6 are also exhaustively repeated until no further new items can be added to the set list. The string will be accepted if a string behaves or resembles the production, is an element of For example:

+ Table 1.0 Set Lists Items
The complete production of is accepted and produces the following production string: .