Mihai Ciocoiu, Ştefan Bruda * GULiveR: Generalized Unification Based LR Parser for Natural Languages

Fig. 3. - Unification trace.

Unification combines information contained in two compatible dags. It may fail if the two dags are incompatible. Given two dags D and D', the unification of D and D' (denoted by D o D') is the dag D" such that D" D and D" D' and there is no dag D1 such that D1 D and D1 D' and D" D1 (i.e., D" is the most general dag which is subsumed by both D and D'). Unification adds information into dags in a monotonical way. An unification example is shown in the figure above.

Finally, a production of a PATR-II grammar contains two types of information:

• the concatenation of substrings in order to form a bigger string; this is the context-free backbone of the production;
• the relations between the associated dags; this is represented by a set of constraints between some subdags of that dags contained in the production, identified by paths.

Note that a PATR-II production can be represented as a dag; for example, the production:

	X0 ->   X1 X2
		<X1 cat> 	= NP
		<X2 cat> 	= VP
		<X0 cat> 	= S
		<X0 slash>	= <X2 slash>
		<X1 slash>	= 0

Fig. 4. - Production as dag.

99