gamma.parsgen.lalr1.ParserGrammarProperties source code

1 module gamma.parsgen.lalr1.ParserGrammarProperties;
2 
3 import gamma.grammar.Grammar;
4 import gamma.grammar.GrammarProperties;
5 import gamma.grammar.Node;
6 import gamma.grammar.Nonterminal;
7 import gamma.grammar.Symbol;
8 import gamma.grammar.SymbolNode;
9 import gamma.parsgen.lalr1.SCCSetComputation;
10 import gamma.util.Indexed;
11 import log;
12 
13 version (unittest) import gamma.grammar.GrammarBuilder;
14 
15 /**
16  * Extended grammar properties for LR parser generation.
17  */
18 public class ParserGrammarProperties : GrammarProperties
19 {
20     private bool[Indexed][] rightDeriv;
21 
22 	/**
23 	 * Constructor for ParserGramarProperties.
24 	 * @param grammar The grammar of which to present the properties.
25 	 */
26 	public this(Grammar grammar)
27 	{
28 		super(grammar);
29         computeRightDerivationLeaders;
30 	}
31 
32     /**
33      * Computes which nonterminals may appear as the leading symbol in a
34      * right-derivation from any given nonterminal.
35      */
36     private void computeRightDerivationLeaders()
37     {
38         import std.algorithm : map;
39         import std.array : array;
40 
41         Indexed[] nodes = this.grammar.nonterminals
42             .map!(nonterminal => cast(Indexed) nonterminal)
43             .array;
44 
45         rightDeriv = new bool[Indexed][this.grammar.nonterminals.length];
46         SCCSetComputation.computeSets(
47             nodes,
48             new class SCCSetComputation.TransitionEnumerator
49             {
50                 public void visitNeighborsOf( Indexed x, SCCSetComputation.TransitionWalker edge)
51                 {
52                 	assert(cast(Nonterminal) x);
53 
54                     foreach (alt; this.outer.grammar.ruleOf(cast(Nonterminal) x).alternatives)
55                     {
56                         Node[] rhs = alt.rhs;
57 
58                         if (rhs.length > 0)
59                         {
60                             Symbol y = (cast(SymbolNode) rhs[0]).symbol;
61 
62                             if (cast(Nonterminal) y)
63                                 edge.walk(x, cast(Nonterminal) y);
64                         }
65                     }
66                 }
67             },
68             new class SCCSetComputation.SetOperator
69             {
70                 public void initSet(Indexed x)
71                 {
72                     rightDeriv[x.index] = null;
73                     rightDeriv[x.index][x] = true;
74                 }
75 
76                 public void includeSet(Indexed x, Indexed y)
77                 {
78                     foreach (indexed; rightDeriv[y.index].byKey)
79                         rightDeriv[x.index][indexed] = true;
80                 }
81             });
82 
83         // Debug output
84         foreach (nont1; this.grammar.nonterminals)
85         {
86             Nonterminal[] nonterminals;
87 
88             foreach (indexedNont; rightDeriv[nont1.index].byKey)
89             {
90             	assert(cast(Nonterminal) indexedNont);
91 
92                 nonterminals ~= cast(Nonterminal) indexedNont;
93             }
94             trace!"%s right derives %-(%s, %)"(nont1, nonterminals);
95         }
96     }
97 
98     /**
99      * Yields an iterator that iterates the nonterminals which may appear
100      * as the leading symbol in a right-derivation from the given nonterminal
101      * <code>symbol</code>.
102      */
103     auto rightDerivationLeadersOf(Nonterminal nont)
104     {
105         return rightDeriv[nont.index].byKey;
106     }
107 }
108 
109 @("compute right-derivation leaders of grammar from Tremblay and Sorenson")
110 unittest
111 {
112     with (TestGrammarBuilder())
113     {
114         rule("G: E = E | f");
115         rule("E: T | E + T");
116         rule("T: f | T * f");
117 
118         with (new ParserGrammarProperties(grammar))
119         {
120             auto rightDerivationLeaders(string representation)
121             {
122                 import std.algorithm : map, sort;
123                 import std.array : array;
124 
125                 return rightDerivationLeadersOf(buildNonterminal(representation))
126                     .map!(indexed => cast(Symbol) indexed)
127                     .map!"a.toString"
128                     .array
129                     .sort
130                     .array;
131             }
132 
133             assert(rightDerivationLeaders("G") == ["E", "G", "T"]);
134             assert(rightDerivationLeaders("E") == ["E", "T"]);
135             assert(rightDerivationLeaders("T") == ["T"]);
136         }
137     }
138 }