SCI Parser Programmer's Reference/Tree Matching

Official SCI Documentation

Chapter: 1 | 2 | 3 | 4 | 5 | 6 | 7 | Index

Tree Matching

Author: Pablo Ghenis

Date: 21 July 1988 9:56:56 am

 

Tree Matching

The Tree Matching algorithm is quite simple: for each part of the spec tree, find a corresponding branch in the user parse tree. For example if one is looking for a modifier match, one may search both among the modifiers at the current tree depth and also among the modifiers of the roots, the modifiers of the root's roots and so on...

Special handling is required for OR and OPT nodes. An OR-node match will only be declared a failure if all the options fail, and it will succeed as soon as one of the options does, not bother to check the rest. An OPT-node match will succeed if a true match is found but also if no matching slot exists in the user tree. However if there is a matching slot with a different word in it the OPT-node match will fail.

Example

"start the radio" will fail to unify with 'start,(turn<on)[/car]' as follows:

User tree

Code:

(root vp
   (root verb . 'start')
   (dobj np
      (ignore art . 'the')
      (root noun . 'radio')
   )
)

Procedure

match spec root

match spec OR-node try first OR-option (root verb .'start') -> OK

match spec optional dobj

look for a dobj in user tree	-> found
if found, compare	-> FAILED

Thus the tree comparison fails in this example.

 

Notes

 

Table of Contents

 

< Previous: Said Spec Trees Next: Examples >