1,079
edits
Difference between revisions of "SCI/Specifications/SCI in action/Parser"
SCI/Specifications/SCI in action/Parser (view source)
Revision as of 13:16, 10 February 2010
, 13:16, 10 February 2010→Matching the trees: Changed to use <math>, made SCI-AUGMENT algorithm readable.
(→The Parse tree: Started to convert things to <math>; clarified some parts of the text) |
(→Matching the trees: Changed to use <math>, made SCI-AUGMENT algorithm readable.) |
||
| Line 545: | Line 545: | ||
==Matching the trees== | ==Matching the trees== | ||
The exact algorithm used to compare < | The exact algorithm used to compare <math>T_\pi</math> to <math>T_\Sigma</math> is not known yet. The one described here is based on the approximation used in FreeSCI, which is very similar to the original SCI one. | ||
First, we need to describe a set of functions for traversing the nodes of < | First, we need to describe a set of functions for traversing the nodes of <math>T_\Sigma</math> and <math>T_\pi</math>, and doing some work. They will be operating on the sets <math>\mathbb{N}</math> (all non-negative integral numbers), <math>\mathbb{B}</math> (Booleans), and <math>\mathrm{Node}</math> (which we defined earlier). | ||
second : Node | <math> | ||
\newcommand{\tuple}[1]{\langle #1 \rangle} | |||
\newcommand{\nat}{\mathbb{N}} | |||
\newcommand{\bool}{\mathbb{B}} | |||
\newcommand{\Btt}{\textrm{tt}} | |||
\newcommand{\Bff}{\textrm{ff}} | |||
\newcommand{\Node}{\mathrm{Node}} | |||
\begin{align*} | |||
\textrm{first}: & \Node \to S \\ | |||
\textrm{first}: & \tuple{s, v, n_{0}, n_{1} \ldots n_{i}} \mapsto s \\ | |||
\\ | |||
\textrm{second}: & \Node \to V \\ | |||
\textrm{second}: & \tuple{s, v, n_{0}, n_{1} \ldots n_{i}} \mapsto v \\ | |||
\\ | |||
\textrm{word}: & \Node \to \Gamma \\ | |||
\textrm{word}: & \tuple{s, v, \gamma} \mapsto \gamma \\ | |||
\\ | |||
\textrm{children}: & \Node \to \Node* \\ | |||
\textrm{children}: & \tuple{s, v, n_{0}, n_{1} \ldots n_{i}} \mapsto \{ m\in \Node \mid m\in\{ n_{0}, n_{1} \ldots n_{i} \} \} \\ | |||
\\ | |||
\textrm{all-children}: & \Node \to \Node* \\ | |||
\textrm{all-children}: & n \mapsto \textrm{children}(n) \cup \{ m \mid \exists l \in\textrm{all-children}(n) . m\in l \} \\ | |||
\\ | |||
\textrm{is-word} : & \Node \to \bool \\ | |||
\textrm{is-word} : & \tuple{s, v, n_{0}, n_{1} \ldots n_{i}} \mapsto \Btt \iff (i = 0) \land n_{0} \in \Gamma \\ | |||
\textrm{verify-sentence-part-elements}: & \Node \times \Node \to \bool \\ | |||
\textrm{verify-sentence-part-elements}: & \tuple{n_{p}, n_{s}} \mapsto \Btt \iff (\textrm{first}(n_{s} = 152) \land \\ | |||
& ((\forall m \in \Node.\textrm{verify-sentence-part-elements}(m, n_{s}) \iff \\ | |||
& \{ w \mid \exists t \in \textrm{all-children}(m).w = \textrm{word}(t)\} = \emptyset) \lor \\ | |||
& \exists m \in \textrm{children}(n_{s}).\textrm{verify-sentence-part-elements}(m, n_{s})) ) \lor \\ | |||
& ((\textrm{second}(n_{s}) = 153) \land (\exists m.m \in \textrm{children}(n_{s}).(\exists o \in \textrm{all-children}(n_{s}).\\ | |||
& (\textrm{first}(o) = \textrm{first}(n_{p})) \land \textrm{word}(o) = \textrm{word}(m))) ) \lor \\ | |||
& ((\textrm{second}(n_{s}) \in \{144, 14c\}) \land | |||
(\exists m \in \textrm{children}(n_{s}).\textrm{verify-sentence-part}(m, n_{s}))) \\ | |||
\\ | |||
\textrm{verify-sentence-part}: & \Node \times \Node \to \bool \\ | |||
\textrm{verify-sentence-part}: & \tuple{n_{p}, n_{s}} \mapsto \Btt \iff \forall n \in \textrm{children}(n_{s}):\exists m\in\textrm{children}(n_{p}). \\ | |||
& (\textrm{first}(m) = \textrm{first}(n)) \land \textrm{verify-sentence-part-elements}(n, m) \\ | |||
\\ | |||
\textrm{verify-sentence-part-brackets}: & \Node \times \Node \to \bool \\ | |||
\textrm{verify-sentence-part-brackets}: & \tuple{n_{p}, n_{s}} \mapsto \Btt \iff | |||
(\textrm{first}(n_{p}) = 152 \land | |||
(\forall m\in \Node. (\textrm{first}(m) = \textrm{first}(n_{s})) \land\\ | |||
& (\textrm{second}(m) = \textrm{second}(n_{s})). \textrm{verify-sentence-part}(n_{p}, m) \iff\\ | |||
& \{ w \mid \exists t \in \textrm{all-children}(m).w = \textrm{word}(t)\} = \emptyset)) \lor \\ | |||
& ((\textrm{first}(n_{p}) \in \{141, 142, 143\}) \land | |||
\textrm{verify-sentence-part}(n_{p}, n_{s})) \\ | |||
\end{align*} | |||
</math> | |||
With these functions, we can now define an algorithm for augmenting <math>T_\pi</math> and <math>T_\Sigma</math>: | |||
Algorithm SCI-AUGMENT: | |||
matched := tt | |||
claim_on_match := tt | |||
FOREACH n ∈ root(<math>T_\Sigma</math>) | |||
IF ((first(n) = 14b) ∧ (second(n) = f900)) THEN | |||
claim_on_match := ff | |||
ELSE IF ¬verify_sentence_part_brackets(n, root(<math>T_\pi</math>)) THEN | |||
matched := ff | |||
ENDIF | |||
ENDFOREACH | |||
Augmenting succeeded if matched = tt; in this case, <math>T_\pi</math> is one of the trees accepted by the description provided by <math>T_\Sigma</math>. In this case, Said() will return 1. It will also claim the event previously provided to Parse(), unless claim_on_match = ff. | |||
Augmenting succeeded if matched = tt; in this case, | |||
==Notes== | ==Notes== | ||
<references/> | <references/> | ||