tests/test_ll.lua

   1
   2 require "luaunit"
   3 require "ll"
   4 require "fa_algorithms"
   5 require "bootstrap/rtn"
   6 require "pp"
   7
   8 function find_state(rule, slotnum)
   9   if slotnum == 0 then
  10     return rule.start
  11   end
  12
  13   for s in each(rule:states()) do
  14     for edge_val, dest_state, properties in s:transitions() do
  15       if properties.slotnum == slotnum then
  16         return s
  17       end
  18     end
  19   end
  20
  21   error(string.format("No such slotnum (%d) for rule %s", slotnum, rule_str))
  22 end
  23
  24 function get_target_for_slotnum(state, slotnum)
  25   if slotnum == 0 then
  26     return {0, 0}
  27   else
  28     for edge_val, dest_state, properties in state:transitions() do
  29       if properties.slotnum == slotnum then
  30         return {edge_val, dest_state}
  31       end
  32     end
  33   end
  34   error(string.format("Slotnum %d not found for state %s", slotnum, serialize(state, 4, "  ")))
  35 end
  36
  37 function parse_gla(str, rtn_state)
  38   local stream = CharStream:new(str)
  39   stream:ignore("whitespace")
  40   local gla = fa.GLA:new()
  41   gla.rtn_state = rtn_state
  42   local states = {[1]=gla.start}
  43   while not stream:eof() do
  44     local statenum = tonumber(stream:consume_pattern("%d+"))
  45     local state = states[statenum]
  46     if not state then
  47       error(string.format("GLA refers to state %d before it is used as a target",
  48             statenum))
  49     end
  50     while stream:lookahead(1) ~= ";" do
  51       stream:consume("-")
  52       local term = stream:consume_pattern("%w+")
  53       stream:consume("->")
  54       local dest_state_num = tonumber(stream:consume_pattern("%d+"))
  55       states[dest_state_num] = states[dest_state_num] or fa.GLAState:new()
  56       local dest_state = states[dest_state_num]
  57       if term == "EOF" then
  58         state:add_transition(fa.eof, dest_state)
  59       else
  60         state:add_transition(term, dest_state)
  61       end
  62       if stream:lookahead(1) == "(" then
  63         stream:consume("(")
  64         local final_state_slotnum = tonumber(stream:consume_pattern("%d+"))
  65         stream:consume(")")
  66         dest_state.final = get_target_for_slotnum(rtn_state, final_state_slotnum)
  67       end
  68       state = dest_state
  69     end
  70     stream:consume(";")
  71   end
  72
  73   return gla
  74 end
  75
  76 function assert_lookahead(grammar_str, rule_str, slotnum, expected_gla_str)
  77   grammar = parse_grammar(CharStream:new(grammar_str))
  78   grammar:determinize_rtns()
  79   grammar:minimize_rtns()
  80
  81   local rule = grammar.rtns:get(rule_str)
  82   state = find_state(rule, slotnum)
  83   expected_gla = parse_gla(expected_gla_str, state)
  84
  85   compute_lookahead(grammar)
  86
  87   if not fa_isequal(expected_gla, state.gla) then
  88     local bad = io.open("bad.dot", "w")
  89     bad:write("digraph untitled {\n")
  90     bad:write(state.gla:to_dot())
  91     bad:write("}")
  92     bad:close()
  93
  94     local good = io.open("good.dot", "w")
  95     good:write("digraph untitled {\n")
  96     good:write(expected_gla:to_dot())
  97     good:write("}")
  98     good:close()
  99
 100     os.execute("dot -Tpng -o good.png good.dot")
 101     os.execute("dot -Tpng -o bad.png bad.dot")
 102
 103     error("GLAs were not equal: expected and actual are " ..
 104           "in good.png and bad.png, respectively")
 105   end
 106 end
 107
 108 TestSimple = {}
 109 function TestSimple:test1()
 110   assert_lookahead(
 111   [[
 112     s -> a | "X";
 113     a -> "Y";
 114   ]],
 115   "s", 0,
 116   [[
 117     1 -Y-> 2(1);
 118     1 -X-> 3(2);
 119   ]]
 120   )
 121 end
 122
 123 function TestSimple:test_multiple_recursions()
 124   assert_lookahead(
 125   [[
 126     s -> a | "X";
 127     a -> b;
 128     b -> "Y";
 129   ]],
 130   "s", 0,
 131   [[
 132     1 -Y-> 2(1);
 133     1 -X-> 3(2);
 134   ]]
 135   )
 136 end
 137
 138 TestEpsilon = {}
 139 function TestEpsilon:test1()
 140   assert_lookahead(
 141   [[
 142     s -> a "Z" | "X";
 143     a -> "Y"?;
 144   ]],
 145   "s", 0,
 146   [[
 147     1 -Y-> 2(1);
 148     1 -Z-> 2;
 149     1 -X-> 3(3);
 150   ]]
 151   )
 152 end
 153
 154 function TestEpsilon:test2()
 155   assert_lookahead(
 156   [[
 157     s -> a | "X";
 158     a -> "Y"? "Z" ;
 159   ]],
 160   "s", 0,
 161   [[
 162     1 -Y-> 2(1);
 163     1 -Z-> 2;
 164     1 -X-> 3(2);
 165   ]]
 166   )
 167 end
 168
 169 function TestEpsilon:test3()
 170   assert_lookahead(
 171   [[
 172     s -> a "Q" | "X";
 173     a -> "Y"? "Z"? ;
 174   ]],
 175   "s", 0,
 176   [[
 177     1 -Y-> 2(1);
 178     1 -Z-> 2;
 179     1 -Q-> 2;
 180     1 -X-> 3(3);
 181   ]]
 182   )
 183 end
 184
 185 function TestEpsilon:test4()
 186   assert_lookahead(
 187   [[
 188     s -> a "Q" | "X";
 189     a -> b "Y"?;
 190     b -> "Z"?;
 191   ]],
 192   "s", 0,
 193   [[
 194     1 -Y-> 2(1);
 195     1 -Z-> 2;
 196     1 -Q-> 2;
 197     1 -X-> 3(3);
 198   ]]
 199   )
 200 end
 201
 202 function TestEpsilon:test5()
 203   assert_lookahead(
 204   [[
 205     s -> a "Q" | "X";
 206     a -> b? "Y"?;
 207     b -> "Z";
 208   ]],
 209   "s", 0,
 210   [[
 211     1 -Y-> 2(1);
 212     1 -Z-> 2;
 213     1 -Q-> 2;
 214     1 -X-> 3(3);
 215   ]]
 216   )
 217 end
 218
 219 --[=[
 220   TODO: add this test when GLAs that tell RTNs to return are supported.
 221 function TestEpsilon:test5()
 222   assert_lookahead(
 223   [[
 224     s -> a "X";
 225     a -> "Y"* "Z";
 226   ]],
 227   "a", 1,
 228   [[
 229     1 -Y-> 2(1);
 230     1 -X-> 3(0);
 231   ]]
 232   )
 233 end
 234 ]=]
 235
 236 TestMultipleNonterms = {}
 237 function TestMultipleNonterms:test1()
 238   assert_lookahead(
 239   [[
 240     s -> a | b | c;
 241     a -> "X";
 242     b -> "Y";
 243     c -> "Z";
 244   ]],
 245   "s", 0,
 246   [[
 247     1 -X-> 2(1);
 248     1 -Y-> 3(2);
 249     1 -Z-> 4(3);
 250   ]]
 251   )
 252 end
 253
 254 function TestMultipleNonterms:test22()
 255   assert_lookahead(
 256   [[
 257     s -> (a | b | c)? d;
 258     a -> "X";
 259     b -> "Y";
 260     c -> "Z";
 261     d -> "Q";
 262   ]],
 263   "s", 0,
 264   [[
 265     1 -X-> 2(1);
 266     1 -Y-> 3(2);
 267     1 -Z-> 4(3);
 268     1 -Q-> 5(4);
 269   ]]
 270   )
 271 end
 272
 273 TestLL2 = {}
 274 function TestLL2:test1()
 275   assert_lookahead(
 276   [[
 277     s -> "X" "Y" | "X" "Z";
 278   ]],
 279   "s", 0,
 280   [[
 281     1 -X-> 2;
 282     2 -Y-> 3(1);
 283     2 -Z-> 4(3);
 284   ]]
 285   )
 286 end
 287
 288 function TestLL2:test2()
 289   assert_lookahead(
 290   [[
 291     s -> a "Y" | a "Z";
 292     a -> "X";
 293   ]],
 294   "s", 0,
 295   [[
 296     1 -X-> 2;
 297     2 -Y-> 3(1);
 298     2 -Z-> 4(3);
 299   ]]
 300   )
 301 end
 302
 303 function TestLL2:test3()
 304   assert_lookahead(
 305   [[
 306     s -> a "Y" | a "Z";
 307     a -> "X" | "Q";
 308   ]],
 309   "s", 0,
 310   [[
 311     1 -X-> 2;
 312     1 -Q-> 2;
 313     2 -Y-> 3(1);
 314     2 -Z-> 4(3);
 315   ]]
 316   )
 317 end
 318
 319 function TestLL2:test3()
 320   assert_lookahead(
 321   [[
 322     s -> "X"? "Y" | "X" "Z";
 323   ]],
 324   "s", 0,
 325   [[
 326     1 -Y-> 2(2);
 327     1 -X-> 3;
 328     3 -Y-> 4(1);
 329     3 -Z-> 5(3);
 330   ]]
 331   )
 332 end
 333
 334 TestLL3 = {}
 335 function TestLL3:test1()
 336   assert_lookahead(
 337   [[
 338     s -> a "X" | a "Y";
 339     a -> ("P" | "Q") ("P" | "Q");
 340   ]],
 341   "s", 0,
 342   [[
 343     1 -P-> 2 -P-> 3;
 344     1 -Q-> 2 -Q-> 3;
 345     2 -Q-> 3;
 346     2 -P-> 3;
 347     3 -X-> 4(1);
 348     3 -Y-> 5(3);
 349   ]]
 350   )
 351 end
 352
 353 function TestLL3:test2()
 354   assert_lookahead(
 355   [[
 356     s -> a "X" | a "Y";
 357     a -> ("P" | "Q")? ("P" | "Q")?;
 358   ]],
 359   "s", 0,
 360   [[
 361     1 -X-> 2(1);
 362     1 -Y-> 3(3);
 363     1 -P-> 4 -P-> 5;
 364     4 -Q-> 5;
 365     1 -Q-> 4 -Q-> 5;
 366     4 -P-> 5;
 367     4 -X-> 2;
 368     4 -Y-> 3;
 369     5 -X-> 2;
 370     5 -Y-> 3;
 371   ]]
 372   )
 373 end
 374
 375 -- This is equivalent to the grammar on page 271 of The Definitive ANTLR Reference.
 376 function TestLL3:test3()
 377   assert_lookahead(
 378   [[
 379     s -> "X" s "Y" | "X" "X" "Z";
 380   ]],
 381   "s", 0,
 382   [[
 383     1 -X-> 2 -X-> 3;
 384     3 -X-> 4(1);
 385     3 -Z-> 5(4);
 386   ]]
 387   )
 388 end
 389
 390 TestEOF = {}
 391 function TestEOF:test1()
 392   assert_lookahead(
 393   [[
 394     s -> "A" | "A" "B";
 395   ]],
 396   "s", 0,
 397   [[
 398     1 -A-> 2;
 399     2 -B-> 3(2);
 400     2 -EOF-> 4(1);
 401   ]]
 402   )
 403 end
 404
 405 function TestEOF:test2()
 406   -- this is the example used by Terence Parr in his discussion of ANTLR 3.0's
 407   -- lookahead analysis: http://www.antlr.org/blog/antlr3/lookahead.tml
 408   assert_lookahead(
 409   [[
 410     s -> a "A" | a "B";
 411     a -> "A"?;
 412   ]],
 413   "s", 0,
 414   [[
 415     1 -A-> 2;
 416     1 -B-> 3(3);
 417     2 -B-> 3(3);
 418     2 -A-> 4(1);
 419     2 -EOF-> 4(1);
 420   ]]
 421   )
 422 end
 423
 424 TestLLStar = {}
 425 function TestLLStar:test1()
 426   assert_lookahead(
 427   [[
 428     s -> a "X" | a "Y";
 429     a -> "Z"*;
 430   ]],
 431   "s", 0,
 432   [[
 433     1 -Z-> 1;
 434     1 -X-> 2(1);
 435     1 -Y-> 3(3);
 436   ]]
 437   )
 438 end
 439
 440 -- Test lookahead that we can only compute correctly if we apply the
 441 -- tail-recursion optimization.
 442 function TestLLStar:test2()
 443   assert_lookahead(
 444   [[
 445     s -> a "X" | a "Y";
 446     a -> ("Z" a)?;
 447   ]],
 448   "s", 0,
 449   [[
 450     1 -Z-> 1;
 451     1 -X-> 2(1);
 452     1 -Y-> 3(3);
 453   ]]
 454   )
 455 end
 456
 457 TestFollow = {}
 458 function TestFollow:test1()
 459   assert_lookahead(
 460   [[
 461     s -> a "X";
 462     a -> "Y" "Y" | "Y";
 463   ]],
 464   "a", 0,
 465   [[
 466     1 -Y-> 2;
 467     2 -Y-> 3(1);
 468     2 -X-> 4(3);
 469   ]]
 470   )
 471 end
 472
 473 function TestFollow:test2()
 474   assert_lookahead(
 475   [[
 476     s -> a "X";
 477     a -> "Y"?;
 478   ]],
 479   "a", 0,
 480   [[
 481     1 -Y-> 2(1);
 482     1 -X-> 3(0);
 483   ]]
 484   )
 485 end
 486
 487 function assert_fails_with_error(grammar_str, error_string)
 488   grammar = parse_grammar(CharStream:new(grammar_str))
 489   grammar:determinize_rtns()
 490   grammar:minimize_rtns()
 491
 492   local success, message = pcall(compute_lookahead, grammar)
 493   if success then
 494     error("Failed to fail!")
 495   elseif not message:find(error_string) then
 496     error("Failed with wrong message!  Message was supposed to start with "
 497           .. error_string .. ", instead it was: " .. message)
 498   end
 499 end
 500
 501 function assert_left_recursive(grammar_str)
 502   assert_fails_with_error(grammar_str, "Grammar is not LL%(%*%): it is left%-recursive!")
 503 end
 504
 505 TestDetectNonLLStar = {}
 506 function TestDetectNonLLStar:test_left_recursive()
 507   assert_left_recursive(
 508   [[
 509     s -> s? "X";
 510   ]]
 511   )
 512 end
 513
 514 function TestDetectNonLLStar:test_left_recursive2()
 515   assert_left_recursive(
 516   [[
 517     s -> a | "X";
 518     a -> s | "Y";
 519   ]]
 520   )
 521 end
 522
 523 LuaUnit:run(unpack(arg))
 524