245
edits
Difference between revisions of "SCI/Specifications/SCI in action/Parser"
SCI/Specifications/SCI in action/Parser (view source)
Revision as of 17:16, 18 January 2009
, 17:16, 18 January 2009Merging 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 → Γ.group : (γ,μ) (γ,μ) ↦ γ</i> | * group <i>W → Γ.group : (γ,μ) (γ,μ) ↦ γ</i> | ||
* classes: <i>W → C</i>.classes: (γ,μ) ↦ μ | * classes: <i>W → C</i>.classes: (γ,μ) ↦ μ | ||
* <i>C<sub>x</sub> = {ω|ω ∈ class(ω)} | * <i>C<sub>x</sub> = {ω|ω ∈ class(ω)}</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>π</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>π</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 | |Match on class mask: Matches if <span style="white-space:nowrap"><i>m<sub>i</sub> ∈ classes(ω<sub>j</sub>)</i></span> | ||
|---- | |---- | ||
|0x14d | |0x14d | ||
|Terminal | |Terminal | ||
|Match on word group: Matches if | |Match on word group: Matches if <span style="white-space:nowrap"><i>m<sub>i</sub> = group(ω<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 := {χ|∃R ∈ P.χ &exist R}</i>; typically, <i> V = {0χ12ƒ…0χ13ƒ⋅ s = m<sub>0</sub></i> 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> | ||
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> | ||