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

Jump to navigation Jump to search
Merging of the SCI documentation. Work in progress.
(Merging of the SCI documentation. Work in progress. Formatting needs improving.)
(Merging of the SCI documentation. Work in progress.)
Line 176: Line 176:
* group <i>W &rarr; &Gamma;.group : (&gamma;,&mu;) (&gamma;,&mu;) &#8614; &gamma;</i>
* group <i>W &rarr; &Gamma;.group : (&gamma;,&mu;) (&gamma;,&mu;) &#8614; &gamma;</i>
* classes: <i>W &rarr; C</i>.classes: (&gamma;,&mu;) &#8614; &mu;
* classes: <i>W &rarr; C</i>.classes: (&gamma;,&mu;) &#8614; &mu;
* <i>C<sub>x</sub> = {&omega;|&omega; &isin; class(&omega;)}
* <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.  
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.  
Line 205: Line 205:
|0x146
|0x146
|Terminal
|Terminal
|Match on class mask: Matches if {{nowrap begin}}<i>m<sub>i</sub> &isin; classes(&omega;<sub>j</sub>)</i>{{nowrap end}}
|Match on class mask: Matches if <span style="white-space:nowrap"><i>m<sub>i</sub> &isin; classes(&omega;<sub>j</sub>)</i></span>
|----
|----
|0x14d
|0x14d
|Terminal
|Terminal
|Match on word group: Matches if {{nowrap begin}}<i>m<sub>i</sub> &#61; group(&omega;<sub>j</sub>)</i>{{nowrap end}}
|Match on word group: Matches if <span style="white-space:nowrap"><i>m<sub>i</sub> &#61; group(&omega;<sub>j</sub>)</i></span>
|----
|----
|0x154
|0x154
Line 217: Line 217:
|}
|}


With the notable exception of the first rule, these rules constitute  <i>P. V := {&chi;|&exist;R &isin; P.&chi; &exist R}</i>; typically, <i> V = {0&chi;12&fnof;&hellip;0&chi;13&fnof;&sdot; s = m<sub>0</sub></i> 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  <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):


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 <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>


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>
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>
245

edits

Navigation menu