Difference between revisions of "SCI Parser Programmer's Reference/Tree Matching"

From SCI Wiki
Jump to navigationJump to search
 
(6 intermediate revisions by the same user not shown)
Line 6: Line 6:
 
[[SCI Parser Programmer's Reference/User Parse Trees|2]] |  
 
[[SCI Parser Programmer's Reference/User Parse Trees|2]] |  
 
[[SCI Parser Programmer's Reference/Said Specs|3]] |  
 
[[SCI Parser Programmer's Reference/Said Specs|3]] |  
[[SCI Parser Programmer's Reference/Syntax|4]] |  
+
[[SCI Parser Programmer's Reference/Said Syntax|4]] |  
[[SCI Parser Programmer's Reference/Spec Trees|5]] |  
+
[[SCI Parser Programmer's Reference/Said Spec Trees|5]] |  
 
[[SCI Parser Programmer's Reference/Tree Matching|6]] |  
 
[[SCI Parser Programmer's Reference/Tree Matching|6]] |  
 
[[SCI Parser Programmer's Reference/Examples|7]] |  
 
[[SCI Parser Programmer's Reference/Examples|7]] |  
Line 19: Line 19:
 
 
 
 
  
-- content here --
+
==<br /> 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.
 +
 
 +
===<br /> Example ===
 +
 
 +
"start the radio" will fail to unify with &nbsp;<span class="Mono">'start,(turn<on)[/car]'</span>&nbsp; as follows:
 +
 
 +
====<br /> User tree ====
 +
 
 +
<blockquote>
 +
<div class="CodeBlockHeader">Code:</div>
 +
<syntaxhighlight lang="sci">
 +
(root vp
 +
  (root verb . 'start')
 +
  (dobj np
 +
      (ignore art . 'the')
 +
      (root noun . 'radio')
 +
  )
 +
)
 +
</syntaxhighlight>
 +
</blockquote>
 +
 
 +
===<br /> Procedure ===
 +
 
 +
====<br /> match spec root ====
 +
 
 +
<blockquote>match spec OR-node try first OR-option (root verb .'start') -> OK</blockquote>
 +
 +
====<br /> match spec optional dobj ====
 +
 
 +
<blockquote>
 +
{| class="Mono"
 +
|look for a dobj in user tree ||-> found
 +
|-
 +
|if found, compare            ||-> FAILED
 +
|}</blockquote>
 +
 
 +
Thus the tree comparison fails in this example.
  
 
&nbsp;
 
&nbsp;

Latest revision as of 02:22, 22 December 2015

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 >