Difference between revisions of "SCI Parser Programmer's Reference/Tree Matching"
| (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: | ||
| | ||
| − | -- | + | ==<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 <span class="Mono">'start,(turn<on)[/car]'</span> 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. | ||
| | ||
Latest revision as of 02:22, 22 December 2015
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
< Previous: Said Spec Trees Next: Examples >
