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

Jump to navigation Jump to search
Line 218: Line 218:
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):
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 <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>
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, 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></i>.<ref>In FreeSCI, you can use the ”parse” console command to retreive all possible left derivation trees.</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>
<br>


====Parser grammar example====
====Parser grammar example====
<span style="white-space:nowrap">G = &lang; { 12f, &hellip;, 13e }, { C<sub>1</sub>, C<sub>2</sub>, C<sub>4</sub>, &hellip;, C<sub>100</sub> }, P, 13c &rang;</span>
<math>G = \langle \{ \mathrm{12f}, \ldots, \mathrm{13e} \}, \{ C_1, C_2, C_4, \ldots, C_{100} \}, P, \mathrm{13c} \rangle</math>
{| <i>
{| <i>
|----
|----
1,079

edits

Navigation menu