1,079
edits
Difference between revisions of "SCI/Specifications/SCI in action/Parser"
SCI/Specifications/SCI in action/Parser (view source)
Revision as of 17:51, 18 January 2009
, 17:51, 18 January 2009→The Parse tree: added missing ;
(Merging of the SCI documentation. Work in progress.) |
m (→The Parse tree: added missing ;) |
||
| Line 217: | Line 217: | ||
|} | |} | ||
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.χ ∃ 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> | ||
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> | ||