Difference between revisions of "SCI/Specifications/SCI in action/Parser"

Jump to navigation Jump to search

SCI/Specifications/SCI in action/Parser (view source)

Revision as of 15:00, 10 February 2010

13,678 bytes added ,  15:00, 10 February 2010
→‎Semantics
m (→‎The Parse tree: added missing ;)
 
(20 intermediate revisions by 2 users not shown)
Line 1: Line 1:
''Document conversion incomplete. Work in progress.''
=The Parser=
=The Parser=


Line 22: Line 20:
;0x080 : Relative pronoun
;0x080 : Relative pronoun
;0x100 : Noun
;0x100 : Noun
;0x200 : Indicative verb )such as "is","went" as opposed to _do_ this or that, which is imperative)
;0x200 : Indicative verb (such as "is","went" as opposed to _do_ this or that, which is imperative)
;0x400 : Adverb
;0x400 : Adverb
;0x800 : Imperative verb
;0x800 : Imperative verb
Line 54: Line 52:
|}
|}
<br>
<br>
===The suffix vocabulary (VOCAB.901)===
===The suffix vocabulary (VOCAB.901)===
For the following section, a reference to a grammar book may be advisable.
For the following section, a reference to a grammar book may be advisable.
Line 149: Line 148:


==The Parse tree==
==The Parse tree==
This and the two following sections borrow some ideas and structures from abstract language theory. Readers might want to consider related literature.
This and the two following sections borrow some ideas and structures from abstract language theory. Readers might want to consider related literature.


Line 156: Line 154:
After tokenizing, looking up, and finally aliasing the data found in the parsed input string, the interpreter proceeds to build a parse tree <!-- <math>T_\pi</math> --> <i>T</i><sub>&pi;</sub> from the input tokens
After tokenizing, looking up, and finally aliasing the data found in the parsed input string, the interpreter proceeds to build a parse tree <!-- <math>T_\pi</math> --> <i>T</i><sub>&pi;</sub> from the input tokens


<br><i>I :=</i> &omega;<sub>0</sub>, &omega;<sub>1</sub>,&omega;<sub>2</sub> &hellip; &omega;<sub>n-1</sub> <!-- Mediawiki LaTeX <math>I:=~\omega_0,\omega_1,\omega_2 \ldots \omega_{n-1}</math> --><br>
:<math>I~:=~\omega_0,\omega_1,\omega_2 \ldots \omega_{n-1}</math>


where
where


* <i>&omega;<sub>j</sub> &isin; W</i>
* <math>\omega_j \in W</math>, with <math>W</math> being the set of all words;
* <i>&gamma;<sub>j</sub> &isin; &Gamma;</i>
* <math>\gamma_j \in \Gamma</math>, with <math>\Gamma</math> being the set of all word groups;
* <i>&mu;<sub>j</sub> &isin; 2<sup>c</sup></i>
* <math>\mu_j \in 2^C</math>, with <math>C</math> being the set of all class masks <nowiki>{0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,0x100}</nowiki>, and <math>2^C</math> being the set of all subsets of <math>C</math>;
* <i>&omega;<sub>j</sub> = (&gamma;<sub>j</sub>, &mu;<sub>j</sub></i>
* <math>\omega_j = (\gamma_j, \mu_j)</math>, with <math>\gamma_j</math> being the word group <math>\omega_j</math> belongs to, and <math>\mu_j</math> being its class mask.
<!-- Math formulas
 
* <math>\omega_j \in W</math>
Note that elements of <math>2^C</math> (i.e. sets of class masks) can be identified with the ORed value of these class masks. So the set <nowiki>{0x2,0x4,0x80}</nowiki> can be identified with the value 0x86.
*<math>\gamma_j \in \Gamma</math>
*<math>\mu_j \in 2^C</math>
*<math>\omega_j = (\gamma_j, \mu_j</math> -->


With <i>W</i> being the set of all words, <i>&Gamma;</i> being the set of all word groups, <i>C</i> being the set of all class masks <nowiki>{1,2,4,8,10,20,40,80,100}</nowiki>, &gamma;<sub>j</sub> being the word group <i>&omega;<sub>j</sub></i> belongs to, and <i>&omega;<sub>j</sub></i> being its class mask, as described above.
For the following sections, we define two maps and a set:


For the following sections, we define
* <math>\operatorname{group}: W \to \Gamma  : (\gamma,\mu)  \mapsto \gamma</math>
* <math>\operatorname{classes}: W \to 2^C : (\gamma,\mu) \mapsto \mu</math>
* <math>C_x = \{ \omega \in W \mid x \in \operatorname{classes}(\omega)\}</math>


* group <i>W &rarr; &Gamma;.group : (&gamma;,&mu;) (&gamma;,&mu;) &#8614; &gamma;</i>
To do that, it uses the class masks <math>M</math> as input for a pushdown automaton (PDA) A built from a parser grammar; if <math>M</math> was accepted by <math>A</math>, the parse tree <math>T_pi</math> will be built from the matching syntax tree to represent the semantics.
* classes: <i>W &rarr; C</i>.classes: (&gamma;,&mu;) &#8614; &mu;
* <i>C<sub>x</sub> = {&omega;|&omega; &isin; class(&omega;)}</i>


To do that, it uses the class masks <i>M</i> as input for a pushdown automaton (PDA) A built from a parser grammar; if <i>M</i> was accepted by <i>A</i>, the parse tree <i>T</i><sub>&pi;</sub> will be built from the matching syntax tree to represent the semantics.  
The PDA is defined by a grammar <math>G = (V,\Sigma,P,s)</math> where
* <math>V</math> is finite set of <i>nonterminal symbols</i>,
* <math>\Sigma</math> is a finite set <i>terminal symbols</i> that is disjoint from <math>V</math>,
* <math>P</math> is a finite set of <i>production rules</i>,
* <math>s \in V</math> is the <i>start symbol</i>.


The PDA is defined by a grammar <i>G = (V,&Sigma;,P,s)</i> most of which, along with its semantics, is stored in <tt>vocab.900</tt>. This resource contains a parser rule at every 20 bytes, starting with a non-terminal symbol &upsilon; (one word) and a null-terminated list of up to five tuples <i>&sigma;<sub>i</sub>,m<sub>i</sub></i> , both of which are words. In these tuples, <i>m<sub>i</sub></i> is a terminal or non-terminal symbol (determined by <i>&sigma;<sub>i</sub></i> ), and <i>&sigma;<sub>i</sub></i> is the meaning of <i>m<sub>i</sub></i> :
Most of this grammar, along with its semantics, is stored in <tt>vocab.900</tt>. This resource contains a parser rule at every 20 bytes, starting with a non-terminal symbol <math>\upsilon</math> (one word) and a null-terminated list of up to five tuples <math>(\sigma_i, m_i)</math>, both of which are words. In these tuples, <math>m_i</math> is a terminal or non-terminal symbol (determined by <math>\sigma_i</math> ), and <math>\sigma_i</math> is the meaning of <math>m_i</math> as described in the following table:


{| border="1"  
{| border="1" style="margin: 1em auto 1em auto"
|<i>&sigma;<sub>i</sub></i>
|<math>\sigma_i</math>
|Type
|Type
|Meaning
|Meaning
Line 205: Line 204:
|0x146
|0x146
|Terminal
|Terminal
|Match on class mask: Matches if <span style="white-space:nowrap"><i>m<sub>i</sub> &isin; classes(&omega;<sub>j</sub>)</i></span>
|Match on class mask: Matches if <math>m_i\in\operatorname{classes}(\omega_j)</math>
|----
|----
|0x14d
|0x14d
|Terminal
|Terminal
|Match on word group: Matches if <span style="white-space:nowrap"><i>m<sub>i</sub> &#61; group(&omega;<sub>j</sub>)</i></span>
|Match on word group: Matches if <math>m_i=\operatorname{group}(\omega_j)</math>
|----
|----
|0x154
|0x154
Line 217: Line 216:
|}
|}


With the notable exception of the first rule, these rules constitute  <span style="white-space:nowrap"><i>P. V := {&chi;|&exist;R &isin; P.&chi; &exist; R}</i></span>; typically, <span style="white-space:nowrap"><i> V = {0&chi;12&fnof;&hellip;0&chi;13&fnof;&sdot; s = m<sub>0</sub></i></span> of the first rule encountered; in all games observed, it was set to 0x13c. &Sigma; contains all word groups and class masks. For the sake of simplicity, we will consider rules matching composite class masks to be several rules. Here is a simplified example of what such a grammar might look like (the hexadecimal prefix '0x' is omitted for brevity):
With the notable exception of the first rule, these rules constitute  the set of production rules <math>P</math>. Furthermore we have <math>V := \{x \mid \exists R \in P : x \in R\}</math>; typically, <math>V = \{ \mathrm{0x12f}, \ldots, \mathrm{0x13f}\}</math> and  <math>s = m_0</math> of the first rule encountered; in all games observed, it was set to 0x13c. <math>\Sigma</math> contains all word groups and class masks. For the sake of simplicity, we will consider rules matching composite class masks to be several rules. Here is a simplified example of what such a grammar might look like (the hexadecimal prefix '0x' is omitted for brevity):
 
In addition to this grammar, each right-hand non-terminal <math>m_i</math> carries its semantic value <math>\rho_i</math> , which is not relevant for constructing a syntax tree, but must be considered for the semantic tree <math>T_\pi</math>. These values were omitted in the example above. As in the example above, the grammar is a context-free (type 2) grammar, almost in Chomsky Normal Form (CNF) in SCI; constructing a grammar with CNF rules from it would be trivial.<ref>FreeSCI constructs a GNF (Greibach Normal Form) representation from these rules for parsing.</ref>
 
Obviously, <math>G</math> is an ambiguous grammar. In SCI, rule precedence is implied by rule order, so the resulting left derivation tree is well-defined (in the Parser example further down, it would be defined by <math>D_0</math>.<ref>In FreeSCI, you can use the ”parse” console command to retrieve all possible left derivation trees.</ref>
<br>
 
====Parser grammar example====
<math>G = \langle \{ \mathrm{12f}, \ldots, \mathrm{13e} \}, \{ C_1, C_2, C_4, \ldots, C_{100} \}, P, \mathrm{13c} \rangle</math>
{| <i>
|----
|P = {
|13c
|&rarr;
|13b 134
|----
|
|13c
|&rarr;
|13b 13d 133
|----
|
|13c
|&rarr;
|13b 13d
|----
|
|13c
|&rarr;
|13b
|----
|
|13c
|&rarr;
|13b 13d 13b 13d
|----
|
|13b
|&rarr;
|131 134
|----
|
|13b
|&rarr;
|131 13d  13d
|----
|
|13b
|&rarr;
|131
|----
|
|13d
|&rarr;
|134
|----
|
|131
|&rarr;
|C<sub>80</sub>
|----
|
|133
|&rarr;
|C<sub>20</sub>
|----
|
|134
|&rarr;
|C<sub>10</sub> }
|----
|}</i>
 
===Semantics===
This is important, since the parser does much more than just accept or discard input. Using the semantic tags applied to each non-terminal on the right-hand side of a rule, it constructs what I will call the semantic parse tree <math>T_\pi</math> , which attempts to describe what the input means. For each non-terminal rule
 
<math>r = v_0 \to v_1 v_2 \ldots v_n</math>
 
there are semantic tags <math>\sigma_{r,1}, \sigma_{r,2} \ldots \sigma_{r,n} \in S</math>, as explained above. <math>T_\pi</math> is now constructed from the resulting derivation and the semantic tags assiociated with each non-terminal of the rule used. The construction algorithm is explained below with <math>T_\pi</math> being constructed from nodes, which have the following recursive structure:
 
<math>
\newcommand{\Node}{\textrm{NODE}}
\Node = \{\diamond\} \cup S \times V \times (\Node \cup \Gamma)*;</math>
 
Where <math>S</math> is the set of possible semantic values, and <math>V</math> is the set of non-terminals as defined in the grammar. We will also use the sequence <math>\gamma_{0}, \gamma_{1}, \gamma_{2} \ldots \gamma_{k-1}</math> which will represent the word groups the input tokens belonged to (in the exact order they were accepted), and the sequence <math>r_{0}, r_{1}, r_{2} \ldots r_{l-1}</math>, which will be the list of rules used to create the left derivation tree as described in the previous section.
 
<pre>
  Helper function sci_said_recursive: S &times; V &times; (V &cup; &Sigma;)* &rarr; NODE
  Parameters: s &isin; S, Rule r &isin; V &times; (V &cup; &Sigma;): v0 &rarr; v1 v2 ... vi
  cnmr = cnr
  NODE n := s, v0
  FOR j := 1 TO i
    IF (vj &isin; &Sigma;) THEN
      n := n, &gamma;cn&gamma;
      cn&gamma; := cn&gamma; + 1
    ELSE
      cnoldr := cnr
      cnr := cnr + 1
      n := n, sci_said_recursive(&Sigma;rmr,j, rcnoldr)
    FI
  ROF
  RETURN (n)
 
  Helper function get_children: NODE &rarr; NODE*
          get_children((s, v, n0, n1 ... nm)) := n0, n1 ... nm
 
 
  Algorithm SCI-SAID-TREE
  cn&gamma; := 0;
  cnr := 1;
  ntemp := ntemp, SCI-SAID-RECURSIVE(0, r0)
  root(T&Pi;) := (141, 13f, get_children(ntemp))
</pre>
 
Here is an example, based on the previous one:
 
====Example: Parser example====
Parse is called with <i>"open door"</i>.
* <math>\textrm{"open"} \in \langle 842, \{ C_{80} \} \rangle</math> (an imperative word of the word group 0x842)
* <math>\textrm{"door"} \in \langle 917, \{ C_{10} \} \rangle</math> (a substantive of the word group 0x917)
* <math>I = \langle 842, \{C_{80} \} \rangle, \langle 917, \{C_{10} \} \rangle</math>
 
<math>I</math> is clearly accepted by automatons based on the grammar described above, There are two possible derivations:
 
{|
|colspan="2" align="center"| D<sub>0</sub> = 13c
|width="50em"|&nbsp;
|colspan="2" align="center"| D<sub>1</sub> = 13c
|----
|(13c &#8614; 13b 134)
|&#8866; 13b 134
|
|(13c &#8614; 13b)
|&#8866; 13b
|----
|(13b &#8614; 131)
|&#8866; 131 134
|
|(13b &#8614; 131 134)
|&#8866; 131 134
|----
|(131 &#8614; C<sub>80</sub>
|&#8866; C<sub>80</sub> 134
|
|(131 &#8614; C<sub>80</sub>
|&#8866; C<sub>80</sub> 134
|----
|(134 &#8614; C<sub>10</sub>
|&#8866; C<sub>80</sub> C<sub>10</sub>
|
|(134 &#8614; C<sub>10</sub>
|&#8866; C<sub>80</sub> C<sub>10</sub>
|----
|}
 
====Example: Semantic tree example====
<i>
* k = 2
* &gamma;<sub>0</sub> = 842
* &gamma;<sub>1</sub> = 917
* l = 4
* r<sub>0</sub> = 13c &#8614; 13b 134
* &sigma;<sub>r<sub>0</sub>,1</sub> = 141
* &sigma;<sub>r<sub>0</sub>,2</sub> = 142
* r<sub>1</sub> = 13b &#8614; 131
* &sigma;<sub>1<sub>1</sub>,1</sub> = 141
* r<sub>2</sub> = 131 &#8614; C<sub>80</sub>
* r<sub>3</sub> = 134 &#8614; C<sub>10</sub>
</i>
 
The resulting tree would look like this:
<pre>
(141 13f
&#09;(141 13b
&#09;&#09;(141 131 842)
&#09;)
&#09;(142 134 917)
)</pre>
 
==Said specs==
To test what the player wanted to say, SCI compares <i>T</i><sub>&pi;</sub> with a second tree, <i>T</i><sub>&Sigma;</sub> , which is built from a so-called Said spec. A Said spec is a variable-sized block in SCI memory which consists of a set of byte-sized operators and special tokens (stored in the range 0xf0 to 0xf9) and word groups (in big-endian notation, so that they don't conflict with the operators); it is terminated by the special token 0xff. The meanings of the operators and special tokens are as follows:
 
{| border="1"
|Operator
|Byte representation
|Meaning
|----
|,
|f0
|"OR". Used to specify alternatives to words, such as "take, get".
|----
|&
|f1
|Unknown. Probably used for debugging.
|----
|/
|f2
|Sentence part separator. Only two of these tokens may be used, since sentences are split into a maximum of three parts.
|----
|(
|f3
|Used together with ')' for grouping
|----
|)
|f4
|See '('
|----
|[
|f5
|Used together with ']' for optional grouping. "[a]" means "either <i>a</i> or nothing".
|----
|]
|f6
|See '['.
|----
|#
|f7
|Unknown assumed to have been used for debugging, if at all.
|----
|<
|f8
|Semantic reference operator (as in "get < up").
|----
|>
|f9
|Instructs Said() not to claim the event passed  to the previous Parse() call on a match. Used for succesive matching.
|}
 
 
This sequence of operators and word groups is now used to build the Said tree <i>T</i><sub>&Sigma;</sub> . I will describe the algorithm used to generate <i>T</i><sub>&Sigma;</sub> by providing a grammar <i>G</i><sub>&Sigma;</sub> , with <i>L(G<sub>&Sigma;</sub>) </i>containing all valid Said specs. The semantics will be provided under each rule with a double arrow:
 
<pre>
        G\Sigma = ({saidspec, optcont, leftspec, midspec, rightspec, word, cwordset, wordset, expr, cwordrefset, wordrefset, recref}, \Gamma, P, saidspec)
 
        P := {
          saidspec \to  leftspec optcont
                                \Rightarrow (141 13f leftspec optcont)
                        | leftspec midspec optcont
                                \Rightarrow (141 13f leftspec midspec optcont)
                        | leftspec midspec rightspec optcont
                                \Rightarrow (141 13f leftspec midspec rightspec optcont)
 
 
 
          optcont \to  e
                                \Rightarrow
                        | >
                                \Rightarrow (14b f900 f900)
 
 
 
          leftspec \to  e
                                \Rightarrow
                        | expr
                                \Rightarrow (141 149 expr)
 
 
 
          midspec \to    / expr
                                \Rightarrow (142 14a expr)
                        | [ / expr ]
                                \Rightarrow (152 142 (142 14a expr))
                        | /
                                \Rightarrow
 
 
 
          rightspec \to  / expr
                                \Rightarrow (143 14a expr)
                        | [ / expr ]
                                \Rightarrow (152 143 (143 14a expr))
                        | /
                                \Rightarrow
 
 
          word \to      \gamma \in \Gamma
                                \Rightarrow (141 153 \gamma)
 
 
          cwordset \to  wordset
                                \Rightarrow (141 14f wordset)
                        | [ wordset ]
                                \Rightarrow (141 14f (152 14c (141 14f wordset)))
 
 
          wordset \to    word
                                \Rightarrow word
                        | ( expr )
                                \Rightarrow (141 14c expr)
                        | wordset , wordset
                                \Rightarrow wordset wordset
                        | wordset , [ wordset ]
                                \Rightarrow wordset wordset
 
 
          expr \to              cwordset cwordrefset
                                \Rightarrow cwordset cwordrefset
                        | cwordset
                                \Rightarrow cwordset
                        | cwordrefset
                                \Rightarrow cwordrefset
       
 
          cwordrefset \to        wordrefset
                                \Rightarrow wordrefset
                        | [ wordrefset ]
                                \Rightarrow (152 144 wordrefset)
 
 
          wordrefset \to        < wordset recref
                                \Rightarrow (144 14f word) recref
                        | < wordset
                                \Rightarrow (144 14f word)
                        | < [ wordset ]
                                \Rightarrow (152 144 (144 14f wordset))
 
 
          recref \to    < wordset recref
                                \Rightarrow (141 144 (144 14f wordset) recref)
                        | < wordset
                                \Rightarrow (141 144 (144 14f wordset))
        }
</pre>
 
==Matching the trees==
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 <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).
 
<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 &isin; root(<math>T_\Sigma</math>)
    IF ((first(n) = 14b) &and; (second(n) = f900)) THEN
      claim_on_match := ff
    ELSE IF &not;verify_sentence_part_brackets(n, root(<math>T_\pi</math>)) THEN
      matched := ff
    ENDIF
  ENDFOREACH


In addition to this grammar, each right-hand non-terminal <i>m<sub>i</sub></i> carries its semantic value <i>&rho;<sub>i</sub></i> , which is not relevant for constructing a syntax tree, but must be considered for the semantic tree <i>T</i><sub>&pi;</sub>. These values were omitted in the example above. As in the example above, the grammar is a context-free (type 2) grammar, almost in Chomsky Normal Form (CNF) in SCI; constructing a grammar with CNF rules from it would be trivial.<ref>FreeSCI constructs a GNF (Greibach Normal Form) representation from these rules for parsing.</ref>
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.


Obviously, G is an ambiguous grammar. In SCI, rule precedence is implied by rule order, so the resulting left derivation tree is well-defined (in the example, it would be defined by <i>D<sub>0</sub>.<ref>In FreeSCI, you can use the ”parse” console command to retreive all possible left derivation trees.</ref>
==Notes==
<references/>
Fingolfin
1,079

edits

Retrieved from "https://wiki.scummvm.org/index.php?title=Special:MobileDiff/9876...13006"

Navigation menu