gamma.parsgen.lalr1.ParserGrammarBuilder source code

1 module gamma.parsgen.lalr1.ParserGrammarBuilder;
2 
3 import gamma.grammar.Alternative;
4 import gamma.grammar.Grammar;
5 import gamma.grammar.GrammarBuilder;
6 import gamma.grammar.Node;
7 import gamma.grammar.Nonterminal;
8 import gamma.grammar.Rule;
9 import gamma.grammar.Symbol;
10 import gamma.grammar.SymbolNode;
11 import gamma.grammar.Terminal;
12 import gamma.parsgen.lalr1.PredicateFilter;
13 
14 public Grammar extendedCfgFromHyperGrammar(Grammar hyperGrammar,
15     bool[Symbol] lexicalHyperNonterminals,
16     PredicateFilter predicateFilter)
17 {
18     auto grammarBuilder = GrammarBuilder();
19     Symbol originalStartSymbol = grammarBuilder.buildNonterminal(hyperGrammar.startSymbol.toString);
20     Nonterminal extStartSymbol = grammarBuilder.buildNonterminal("(start)");
21 
22     // --- Go ahead with rest of parser generation... ---
23     {
24         Terminal bottom = grammarBuilder.buildTerminal("(end)");
25         Node[] rhs = [new SymbolNode(originalStartSymbol, null), new SymbolNode(bottom, null)];
26 
27         grammarBuilder.add(
28             new Alternative(new SymbolNode(extStartSymbol, null), rhs, null));
29     }
30 
31     // Filter the pure CFG out of the hyperGrammar using
32     // - help from Analyser which nonterminal symbols are "lexical nonterminals"; and
33     // - help from PredicateFilter which RHS symbol occurrences are "predicates".
34     // Any Alternative/Rule the lhs of which is not a Nonterminal of the parser CFG is skipped.
35     // For the remaining RHS's, SymbolNode's are
36     // - not copied to the corresponding target CFG RHS if they represent a "predicate";
37     // - copied to the target CFG as a Terminal if they represent a "lexical nonterminal";
38     // - copied to the target CFG as a Nonterminal otherwise.
39     foreach (hyperRule; hyperGrammar.rules)
40     {
41         foreach (hyperAlt; hyperRule.alternatives)
42         {
43             if (hyperAlt.lhs.symbol in lexicalHyperNonterminals)
44                 break;
45             if (predicateFilter.isPredicate(hyperAlt.lhs))
46                 break;
47 
48             Nonterminal lhs = grammarBuilder.buildNonterminal(hyperAlt.lhs.symbol.toString);
49             Node[] rhs;
50 
51             foreach (rhsNode; hyperAlt.rhs)
52             {
53                 assert(cast(SymbolNode) rhsNode);
54 
55                 SymbolNode node = cast(SymbolNode) rhsNode;
56 
57                 if (predicateFilter.isPredicate(node))
58                     continue;
59 
60                 Symbol sym;
61 
62                 if (node.symbol in lexicalHyperNonterminals
63                     || cast(Terminal)(cast(SymbolNode) node).symbol)
64                     sym = grammarBuilder.buildTerminal(node.symbol.toString);
65                 else
66                     sym = grammarBuilder.buildNonterminal(node.symbol.toString);
67                 rhs ~= new SymbolNode(sym, node.position);
68             }
69             grammarBuilder
70                 .add(new Alternative(new SymbolNode(lhs, hyperAlt.lhs.position), rhs, hyperAlt.position));
71         }
72     }
73 
74     return grammarBuilder.getGrammar(extStartSymbol);
75 }