245
edits
Difference between revisions of "SCI/Specifications/SCI in action/Parser"
SCI/Specifications/SCI in action/Parser (view source)
Revision as of 20:43, 18 January 2009
, 20:43, 18 January 2009Merging of the SCI documentation. Work in progress.
(Merging of the SCI documentation. Work in progress.) |
(Merging of the SCI documentation. Work in progress.) |
||
| Line 216: | Line 216: | ||
|} | |} | ||
With the notable exception of the first rule, these rules constitute <span style="white-space:nowrap"><i>P. V := {χ|∃R ∈ P.χ &exist R}</i></span>; typically, <span style="white-space:nowrap"><i> V = {0χ12ƒ…0χ13ƒ⋅ s = m<sub>0</sub></i></span> of the first rule encountered; in all games observed, it was set to 0x13c. Σ 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 <span style="white-space:nowrap"><i>P. V := {χ|∃R ∈ P.χ &exist R}</i></span>; typically, <span style="white-space:nowrap"><i> V = {0χ12ƒ…0χ13ƒ}⋅ s = m<sub>0</sub></i></span> of the first rule encountered; in all games observed, it was set to 0x13c. Σ 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 <i>m<sub>i</sub></i> carries its semantic value <i>ρ<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>π</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> | In addition to this grammar, each right-hand non-terminal <i>m<sub>i</sub></i> carries its semantic value <i>ρ<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>π</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> | ||
| Line 330: | Line 330: | ||
Here is an example, based on the previous one: | Here is an example, based on the previous one: | ||
====Example: Parser example==== | |||
Parse is called with <i>"open door"</i>. | |||
* <i>"open" ∈ ⟨842,{C<sub>8</sub>0}⟩</i> (an imperative word of the word group 0x842) | |||
* <i>"door" ∈ ⟨917,{C<sub>1</sub>0}⟩ (a substantive of the word group 0x917)</i> | |||
* <i>I = ⟨842,{C<sub>8</sub>0}⟩,⟨917,{C<sub>1</sub>0}⟩</i> | |||
<i>I</i> is clearly accepted by automatons based on the grammar described above, There are two possible derivations: | |||
{| | |||
|D<sub>0</sub> = 13c | |||
|---- | |||
|(13c ↦ 13b134) | |||
|⊢ 13b 134 | |||
|---- | |||
|(13b ↦ 131) | |||
|⊢ 131 134 | |||
|---- | |||
|(131 ↦ C<sub>80</sub> | |||
|⊢ C<sub>80</sub> 134 | |||
|---- | |||
|(134 ↦ C<sub>10</sub> | |||
|⊢ C<sub>80</sub> C<sub>10</sub> | |||
|---- | |||
|} | |||
<br> | |||
{| | |||
|D<sub>1</sub> = 13c | |||
|---- | |||
|(13c ↦ 13b) | |||
|⊢ 13b | |||
|---- | |||
|(13b ↦ 131134) | |||
|⊢ 131 134 | |||
|---- | |||
|(131 ↦ C<sub>80</sub> | |||
|⊢ C<sub>80</sub> 134 | |||
|---- | |||
|(134 ↦ C<sub>10</sub> | |||
|⊢ C<sub>80</sub> C<sub>10</sub> | |||
|---- | |||
|} | |||
====Example: Semantic tree example==== | ====Example: Semantic tree example==== | ||
| Line 347: | Line 392: | ||
The resulting tree would look like this: | The resulting tree would look like this: | ||
<pre> | |||
(141 13f | (141 13f | ||
	(141 13b | 	(141 13b | ||
| Line 353: | Line 398: | ||
	) | 	) | ||
	(142 134 917) | 	(142 134 917) | ||
)</pre | )</pre> | ||
==Said specs== | |||
To test what the player wanted to say, SCI compares <i>T</i><sub>π</sub> with a second tree, <i>T</i><sub>Σ</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: | |||
==Notes== | ==Notes== | ||
<references/> | <references/> | ||