1 module gamma.parsgen.lalr1.run.LR1ParserTablesReader; 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.OrderedLR1Tables; 13 import gamma.util.Position; 14 import std.algorithm; 15 import std.exception; 16 import std.format; 17 import std.json; 18 import std.stdio; 19 20 /** 21 * Reads an OrderedLR1Tables representation from a given input file. 22 */ 23 public class LR1ParserTablesReader 24 { 25 private OrderedLR1Tables.Action[][] parserActionRows; 26 27 private OrderedLR1Tables.Goto[][] gotoRows; 28 29 private GrammarBuilder grammarBuilder; 30 31 private Nonterminal[size_t] index2Nonterminal; 32 33 private Terminal[size_t] index2Terminal; 34 35 private Alternative[size_t] index2Alternative; 36 37 private long maxState; 38 39 static public class SimplePosition : Position 40 { 41 private string repr; 42 43 public this(string repr) 44 { 45 this.repr = repr; 46 } 47 48 public void markError(string message) 49 { 50 import log; 51 52 error!"%s: %s"(repr, message); 53 } 54 } 55 56 static private string ruleReprFor(Alternative alt) 57 { 58 return format!"%s ::=%-( %s%)"(alt.lhs.symbol, alt.rhs.map!(node => (cast(SymbolNode) node).symbol)); 59 } 60 61 private this() 62 { 63 this.maxState = -1; 64 } 65 66 public static OrderedLR1Tables read(File input) 67 { 68 import std.array : array; 69 70 auto text = cast(char[]) input.byChunk(4096).joiner.array; 71 auto value = parseJSON(text); 72 73 return new LR1ParserTablesReader().parseLR1Parser(value); 74 } 75 76 private OrderedLR1Tables parseLR1Parser(JSONValue value) 77 { 78 import gamma.parsgen.lalr1.run.OrderedLR1TablesImpl : OrderedLR1TablesImpl; 79 80 JSONValue[string] object = value.object; 81 Grammar grammar = parseGrammar(object["grammar"]); 82 83 parseActions(object["states"]); 84 return new OrderedLR1TablesImpl(grammar, this.parserActionRows, this.gotoRows); 85 } 86 87 private Grammar parseGrammar(JSONValue value) 88 { 89 JSONValue[string] object = value.object; 90 91 parseNonterminals(object["nonterminals"]); 92 parseTerminals(object["terminals"]); 93 parseRules(object["rules"]); 94 95 Nonterminal startSymbol = parseStartSymbol(object["startSymbol"]); 96 97 Grammar grammar = grammarBuilder.getGrammar(startSymbol); 98 99 enforce(startSymbol == grammar.startSymbol, 100 "sorry, not able to build a grammar with the required start symbol"); 101 102 checkGrammar(grammar); 103 return grammar; 104 } 105 106 private void parseNonterminals(JSONValue value) 107 { 108 foreach (nonterminalValue; value.array) 109 { 110 JSONValue[string] object = nonterminalValue.object; 111 const index = object["index"].integer; 112 const repr = object["repr"].str; 113 Nonterminal nonterminal = grammarBuilder.buildNonterminal(repr); 114 115 enforce(nonterminal.index == index, 116 "bad nonterminal index..."); 117 118 119 index2Nonterminal[index] = nonterminal; 120 } 121 } 122 123 private void parseTerminals(JSONValue value) 124 { 125 foreach (terminalValue; value.array) 126 { 127 JSONValue[string] object = terminalValue.object; 128 const index = object["index"].integer; 129 const repr = object["repr"].str; 130 Terminal terminal = grammarBuilder.buildTerminal(repr); 131 132 enforce(terminal.index == index, 133 "bad terminal index..."); 134 135 136 index2Terminal[index] = terminal; 137 } 138 } 139 140 private void parseRules(JSONValue value) 141 { 142 foreach (ruleValue; value.array) 143 parseRule(ruleValue); 144 } 145 146 private void parseRule(JSONValue value) 147 { 148 JSONValue[string] object = value.object; 149 const index = object["lhs"].integer; 150 Nonterminal lhs = index2Nonterminal[index]; 151 152 foreach (alternativeValue; object["alternatives"].array) 153 parseAlternative(lhs, alternativeValue); 154 } 155 156 private void parseAlternative(Nonterminal lhs, JSONValue value) 157 { 158 JSONValue[string] object = value.object; 159 const index = object["index"].integer; 160 161 Node[] rhs; 162 163 foreach (nodeValue; object["rhs"].array) 164 { 165 Symbol symbol; 166 167 if (nodeValue.object["type"].str == "nonterminal") 168 symbol = parseNonterminal(nodeValue); 169 else if (nodeValue.object["type"].str == "terminal") 170 symbol = parseTerminal(nodeValue); 171 else 172 break; 173 rhs ~= new SymbolNode(symbol, new SimplePosition(symbol.toString)); 174 } 175 176 auto alternative = new Alternative( 177 new SymbolNode(lhs, new SimplePosition(lhs.toString)), 178 rhs, 179 new SimplePosition(format!"alternative #%s"(index))); 180 181 this.index2Alternative[index] = alternative; 182 grammarBuilder.add(alternative); 183 } 184 185 private Nonterminal parseNonterminal(JSONValue value) 186 { 187 JSONValue[string] object = value.object; 188 const index = object["index"].integer; 189 Nonterminal nonterminal = index2Nonterminal[index]; 190 191 return nonterminal; 192 } 193 194 private Terminal parseTerminal(JSONValue value) 195 { 196 JSONValue[string] object = value.object; 197 const index = object["index"].integer; 198 Terminal terminal = index2Terminal[index]; 199 200 return terminal; 201 } 202 203 private Nonterminal parseStartSymbol(JSONValue value) 204 { 205 JSONValue[string] object = value.object; 206 const index = object["index"].integer; 207 Nonterminal nonterminal = index2Nonterminal[index]; 208 209 return nonterminal; 210 } 211 212 private void parseActions(JSONValue value) 213 { 214 foreach (stateValue; value.array) 215 { 216 JSONValue[string] object = stateValue.object; 217 const index = object["index"].integer; 218 219 enforce(index == parserActionRows.length, 220 format!"illegal state %s"(index)); 221 222 OrderedLR1Tables.Action[] parserActionRow; 223 224 foreach (actionValue; object["actions"].array) 225 if (actionValue.object["type"].str == "shift") 226 parserActionRow ~= parseShift(actionValue); 227 else if (actionValue.object["type"].str == "reduce") 228 parserActionRow ~= parseReduce(actionValue); 229 else if (actionValue.object["type"].str == "halt") 230 parserActionRow ~= parseHalt(actionValue); 231 parserActionRows ~= parserActionRow; 232 233 OrderedLR1Tables.Goto[] gotoRow; 234 235 foreach (transitionValue; object["transitions"].array) 236 gotoRow ~= parseGoto(transitionValue); 237 gotoRows ~= gotoRow; 238 } 239 240 enforce(this.maxState < parserActionRows.length, 241 "something went wrong..."); 242 } 243 244 private OrderedLR1Tables.Shift parseShift(JSONValue value) 245 { 246 Terminal lookahead = parseOnTerminal(value); 247 const toState = parseTo(value); 248 const continues = parseContinues(value); 249 OrderedLR1Tables.Shift shift = new OrderedLR1Tables.Shift(lookahead, toState); 250 251 shift.isContinuationAction = continues; 252 return shift; 253 } 254 255 private OrderedLR1Tables.Reduce parseReduce(JSONValue value) 256 { 257 Terminal lookahead = parseOnTerminal(value); 258 Alternative alternative = parseRuleAlt(value); 259 const continues = parseContinues(value); 260 OrderedLR1Tables.Reduce reduce = new OrderedLR1Tables.Reduce(lookahead, alternative); 261 262 reduce.isContinuationAction = continues; 263 return reduce; 264 } 265 266 private OrderedLR1Tables.Halt parseHalt(JSONValue value) 267 { 268 Terminal lookahead = parseOnTerminal(value); 269 const continues = parseContinues(value); 270 OrderedLR1Tables.Halt halt = new OrderedLR1Tables.Halt(lookahead); 271 272 halt.isContinuationAction = continues; 273 return halt; 274 } 275 276 private OrderedLR1Tables.Goto parseGoto(JSONValue value) 277 { 278 Nonterminal lhs = parseOnNonterminal(value); 279 const to = parseTo(value); 280 OrderedLR1Tables.Goto goTo = new OrderedLR1Tables.Goto(lhs, to); 281 282 return goTo; 283 } 284 285 private Terminal parseOnTerminal(JSONValue value) 286 { 287 JSONValue[string] object = value.object; 288 const on = object["on"].integer; 289 Terminal terminal = index2Terminal[on]; 290 291 return terminal; 292 } 293 294 private Nonterminal parseOnNonterminal(JSONValue value) 295 { 296 JSONValue[string] object = value.object; 297 const on = object["on"].integer; 298 Nonterminal lhs = index2Nonterminal[on]; 299 300 return lhs; 301 } 302 303 private long parseTo(JSONValue value) 304 { 305 JSONValue[string] object = value.object; 306 const to = object["to"].integer; 307 308 maxState = max(maxState, to); // for final check if all referred stated have been seen 309 310 return to; 311 } 312 313 private Alternative parseRuleAlt(JSONValue value) 314 { 315 JSONValue[string] object = value.object; 316 const ruleAlt = object["ruleAlt"].integer; 317 Alternative alternative = index2Alternative[ruleAlt]; 318 319 return alternative; 320 } 321 322 private bool parseContinues(JSONValue value) 323 { 324 JSONValue[string] object = value.object; 325 326 if ("continues" in object) 327 return object["continues"].boolean; 328 return false; 329 } 330 331 /** 332 * Checks whether this.grammar is acceptable for the parser generator. 333 * <p> 334 * The following checks are performed:<br> 335 * (1) that this.grammar is a pure context-free grammar and <br> 336 * (2) that this.grammar is an "extended" context-free grammar, 337 * i.e. its start symbol <ExtendedStartSymbol> has only one alternative 338 * <ExtendedStartSymbol> ::= <StartSymbol> <eofSymbol> such that 339 * <StartSymbol> and <ExtendedStartSymbol> are Nonterminals, <eofSymbol> is a Terminal, 340 * and both <ExtendedStartSymbol> and <eofSymbol> occur only in this grammar rule. 341 * <p> 342 * If this.grammar is not acceptable, the method throws an IllegalArgumentException. 343 */ 344 private void checkGrammar(Grammar grammar) 345 { 346 Rule startRule = grammar.ruleOf(grammar.startSymbol); 347 348 enforce(startRule.alternatives.length == 1, 349 "not an extended grammar"); 350 351 auto startAlternative = cast(Alternative) startRule.alternatives[0]; 352 353 enforce(startAlternative.rhs.length == 2, 354 "not an extended grammar"); 355 enforce(cast(Nonterminal)((cast(SymbolNode) startAlternative.rhs[0]).symbol), 356 "not an extended grammar"); 357 358 Symbol extendedStartSymbol = grammar.startSymbol; 359 Symbol eofSymbol = (cast(SymbolNode) startAlternative.rhs[1]).symbol; 360 361 enforce(cast(Terminal) eofSymbol, 362 "not an extended grammar"); 363 364 foreach (oldRule; grammar.rules) 365 { 366 foreach (alternative; oldRule.alternatives) 367 { 368 if (alternative == startAlternative) 369 continue; 370 371 foreach (node; alternative.rhs) 372 { 373 enforce(cast(SymbolNode) node, 374 "not a pure context-free grammar"); 375 376 auto symbolNode = cast(SymbolNode) node; 377 378 enforce(symbolNode.symbol != extendedStartSymbol && symbolNode.symbol != eofSymbol, 379 "not an extended grammar"); 380 } 381 } 382 } 383 } 384 }