parse.lua 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696
  1. local unique_name = require"bon".unique_name
  2. local function do_everything(Tokens, Skeleton)
  3. local TokensIdx = 1
  4. local IdxStack = {}
  5. local function gettoken()
  6. local r = Tokens[TokensIdx]
  7. if r then
  8. TokensIdx = TokensIdx + 1
  9. end
  10. return table.unpack(r)
  11. end
  12. local function peektoken()
  13. local r = Tokens[TokensIdx]
  14. if r then
  15. return table.unpack(Tokens[TokensIdx])
  16. end
  17. end
  18. local function maybe(t)
  19. local a, b, c, d = peektoken()
  20. if a == t then return gettoken() end
  21. return nil
  22. end
  23. local function pushlexi()
  24. table.insert(IdxStack, TokensIdx)
  25. end
  26. local function poplexi()
  27. TokensIdx = table.remove(IdxStack)
  28. end
  29. local function forgetlexi()
  30. table.remove(IdxStack)
  31. end
  32. local function expect(t)
  33. local a, b, c, d = gettoken()
  34. if t ~= a then
  35. error(string.format("%i:%i expected %s, got %s", c, d, t, a))
  36. end
  37. return a, b, c, d
  38. end
  39. local parse_chunk
  40. local function new_parse_context(parent)
  41. return setmetatable({["the parent"] = parent}, {
  42. __index = function(self, key)
  43. while true do
  44. local r = rawget(self, key)
  45. if r then
  46. return r
  47. end
  48. self = rawget(self, "the parent")
  49. if not self then
  50. return
  51. end
  52. end
  53. end,
  54. __newindex = function(self, key, value)
  55. local z = self
  56. local r = nil
  57. while true do
  58. r = rawget(z, key)
  59. if r then break end
  60. z = rawget(z, "the parent")
  61. if not z then break end
  62. end
  63. rawset(z or self, key, value)
  64. end,
  65. })
  66. end
  67. local ParseContext, ParseContextTypes
  68. local function push_parse_context()
  69. ParseContext = new_parse_context(ParseContext)
  70. ParseContextTypes = new_parse_context(ParseContextTypes)
  71. end
  72. local function pop_parse_context()
  73. ParseContext = rawget(ParseContext, "the parent")
  74. ParseContextTypes = rawget(ParseContextTypes, "the parent")
  75. end
  76. local Types = {}
  77. function Types.castable(this, to)
  78. return not to or (this and this.type == to.type)
  79. end
  80. function Types.is_number(this)
  81. return not this or this.type == 'number' or this.type == 'integer'
  82. end
  83. function Types.can_do_arith(this)
  84. return Types.is_number(this)
  85. end
  86. function Types.is_callable(this)
  87. return not this or this.type == 'function'
  88. end
  89. function Types.is_indexable(this)
  90. return not this or this.type == 'list'
  91. end
  92. function Types.has_field(this, field)
  93. if not this then
  94. return true, nil
  95. end
  96. if this.type == 'list' and field == 'pop' then
  97. return true, {type = 'function', ret = false, args = {this}}
  98. end
  99. if this.type ~= 'structure' then
  100. return false, nil
  101. end
  102. for k, v in ipairs(this.members) do
  103. if v.name == field then
  104. return true, v.et
  105. end
  106. end
  107. return false, nil
  108. end
  109. local function parse_et()
  110. local A
  111. if peektoken() == "id" then
  112. local name = select(2, gettoken())
  113. if name == "number" then
  114. A = {type = 'number'}
  115. elseif name == "integer" then
  116. A = {type = 'integer'}
  117. elseif name == "string" then
  118. A = {type = 'string'}
  119. elseif name == "boolean" then
  120. A = {type = 'boolean'}
  121. elseif name == "list" then
  122. A = {type = 'list'}
  123. elseif name == "dict" then
  124. A = {type = 'dict'}
  125. else
  126. A = ParseContextTypes[name]
  127. end
  128. end
  129. if not A then
  130. error("Invalid type description")
  131. end
  132. if maybe("[") then
  133. A.parametrization = {parse_et()}
  134. expect("]")
  135. end
  136. return A
  137. end
  138. local parse_function
  139. local function parse_function_arg()
  140. local name = select(2, expect("id"))
  141. local et
  142. if maybe(":") then
  143. et = parse_et()
  144. end
  145. return name, et
  146. end
  147. local function parse_type()
  148. expect("type")
  149. local name = select(2, expect("id"))
  150. local ret = {type = 'structure', members = {}, name = name}
  151. while true do
  152. if maybe("end") then
  153. break
  154. end
  155. if peektoken() == "constr" or peektoken() == "func" then
  156. local isConstr = gettoken() == "constr"
  157. local fname
  158. if isConstr then
  159. fname = "__call"
  160. else
  161. fname = select(2, expect("id"))
  162. end
  163. local argnames = {}
  164. local argets = {}
  165. if not isConstr then
  166. table.insert(argnames, "self")
  167. table.insert(argets, ret)
  168. end
  169. push_parse_context()
  170. rawset(ParseContext, "self", {et = ret, name = "self"})
  171. if maybe("(") then
  172. if not maybe(")") then
  173. while true do
  174. local name, et = parse_function_arg()
  175. table.insert(argnames, name)
  176. argets[#argnames] = et
  177. rawset(ParseContext, name, {et = et, name = name})
  178. if maybe(")") then
  179. break
  180. else
  181. expect(",")
  182. end
  183. end
  184. end
  185. end
  186. local fret
  187. if isConstr then
  188. fret = ret
  189. else
  190. if maybe(":") then
  191. fret = parse_et()
  192. end
  193. end
  194. local chu = parse_chunk(false)
  195. local et = {type = "function", args = argets, ret = fret}
  196. table.insert(ret.members, {
  197. type = "static",
  198. name = fname,
  199. et = et,
  200. value = {type = "function", et = et, args = argnames, chunk = chu, is_constructor = isConstr},
  201. })
  202. pop_parse_context()
  203. expect("end")
  204. else
  205. local membname = select(2, expect("id"))
  206. expect(":")
  207. local et = parse_et()
  208. table.insert(ret.members, {type = "field", name = membname, et = et})
  209. end
  210. end
  211. return name, ret
  212. end
  213. parse_function = function()
  214. expect("func")
  215. local name = select(2, maybe("id"))
  216. push_parse_context()
  217. local argnames = {}
  218. local argets = {}
  219. if maybe("(") then
  220. if not maybe(")") then
  221. while true do
  222. local name, et = parse_function_arg()
  223. table.insert(argnames, name)
  224. argets[#argnames] = et
  225. rawset(ParseContext, name, {et = et, name = name})
  226. if maybe(")") then
  227. break
  228. else
  229. expect(",")
  230. end
  231. end
  232. end
  233. end
  234. local retet
  235. if maybe(":") then
  236. retet = parse_et()
  237. end
  238. rawset(ParseContext, "the function name", name)
  239. rawset(ParseContextTypes, "the function return type", retet)
  240. local ret = {
  241. type = "function",
  242. et = {type = "function", args = argets, ret = retet},
  243. chunk = parse_chunk(false),
  244. args = argnames
  245. }
  246. pop_parse_context()
  247. expect("end")
  248. return ret, name
  249. end
  250. local active_stmt_list_stack = {}
  251. BINOP_LEVELS = {["+"] = 3, ["-"] = 3, ["=="] = 4, ["/"] = 2, ["*"] = 2, ["%"] = 2, ["**"] = 1}
  252. local function parse_expr(level)
  253. level = level or 4
  254. if level == 4 then
  255. local A = parse_expr(level - 1)
  256. if peektoken() == "==" then
  257. local op = gettoken()
  258. local B = parse_expr(level - 1)
  259. A = {type = "binop", level = level, et = {type = 'boolean'}, op = op, a = A, b = B}
  260. end
  261. return A
  262. elseif level == 3 then
  263. local A = parse_expr(level - 1)
  264. if peektoken() == "+" or peektoken() == "-" then
  265. local op = gettoken()
  266. local B = parse_expr(level - 1)
  267. if not Types.can_do_arith(A.et) or not Types.can_do_arith(B.et) then
  268. error(op .. " operator not supported for non-number types")
  269. end
  270. A = {type = "binop", level = level, et = A.et, op = op, a = A, b = B}
  271. end
  272. return A
  273. elseif level == 2 then
  274. local A = parse_expr(level - 1)
  275. if peektoken() == "*" or peektoken() == "/" or peektoken() == "%" then
  276. local op = gettoken()
  277. local B = parse_expr(level - 1)
  278. if not Types.can_do_arith(A.et) or not Types.can_do_arith(B.et) then
  279. error(op .. " operator not supported for non-number types")
  280. end
  281. A = {type = "binop", level = level, et = A.et, op = op, a = A, b = B}
  282. end
  283. return A
  284. elseif level == 1 then
  285. local A = parse_expr(level - 1)
  286. if peektoken() == "**" then
  287. local op = gettoken()
  288. local B = parse_expr(level - 1)
  289. if not Types.can_do_arith(A.et) or not Types.can_do_arith(B.et) then
  290. error(op .. " operator not supported for non-number types")
  291. end
  292. A = {type = "binop", level = level, et = A.et, op = op, a = A, b = B}
  293. end
  294. return A
  295. elseif level == 0 then
  296. local A
  297. if maybe("#") then
  298. A = {type = 'lengthof', et = {type = 'integer'}, sub = parse_expr(level)}
  299. if A.sub.et and A.sub.et.type ~= 'list' then
  300. error("# requires a list")
  301. end
  302. elseif maybe("(") then
  303. A = parse_expr()
  304. expect(")")
  305. elseif peektoken() == "func" then
  306. A = parse_function()
  307. elseif peektoken() == "num" then
  308. local lit = select(2, gettoken())
  309. A = {type = "num", et = lit:find("%.") and {type = 'number'} or {type = 'integer'}, value = tonumber(lit)}
  310. elseif peektoken() == "id" then
  311. local name = select(2, gettoken())
  312. local v = ParseContext[name]
  313. if not v then
  314. error(string.format("No value with name %s exists.", name))
  315. end
  316. A = {type = "var", which = v, et = v.et}
  317. elseif maybe("{") then
  318. A = {type = "dict", et = {type = "dict", parametrization = {}}, mappings = {}}
  319. expect("}")
  320. elseif maybe("[") then
  321. A = {type = "list", et = {type = "list", parametrization = {}}, values = {}}
  322. expect("]")
  323. elseif peektoken() == "string" then
  324. A = {type = "string", et = {type = 'string'}, value = select(2, gettoken())}
  325. elseif maybe("nil") then
  326. A = {type = 'null', et = {type = 'null'}}
  327. else
  328. error("Unexpected token " .. select(2, peektoken()))
  329. end
  330. while peektoken() == "[" or peektoken() == "(" or peektoken() == "." do
  331. if maybe("[") then
  332. if A.et and A.et.type ~= 'list' and A.et.type ~= 'dict' and A.et.type ~= 'string' then
  333. error("Indexed value is not a list nor dict.")
  334. end
  335. local newet
  336. if A.et.type == 'list' then
  337. newet = A.et.parametrization and A.et.parametrization[1]
  338. elseif A.et.type == 'dict' then
  339. newet = A.et.parametrization and A.et.parametrization[2]
  340. elseif A.et.type == 'string' then
  341. newet = A.et
  342. else
  343. error()
  344. end
  345. local idx = parse_expr()
  346. if A.et.type == 'string' then
  347. local temp = {name = unique_name(), et = nil}
  348. table.insert(active_stmt_list_stack[#active_stmt_list_stack], {
  349. type = 'let',
  350. var = temp,
  351. expr = {type = 'binop', level = BINOP_LEVELS['+'], op = '+', a = idx, b = {type = 'num', value = 1, et = {type = 'integer'}}}
  352. })
  353. A = {
  354. type = 'call',
  355. what = {type = 'dot', colon = true, a = A, b = 'sub', et = nil},
  356. args = {
  357. {type = 'var', which = temp, et = temp.et},
  358. {type = 'var', which = temp, et = temp.et}
  359. }
  360. }
  361. else
  362. if A.et.type == 'list' then
  363. -- Switch to 1-based indexing
  364. idx = {type = 'binop', level = BINOP_LEVELS['+'], op = '+', a = idx, b = {type = 'num', value = 1, et = {type = 'integer'}}}
  365. end
  366. A = {type = 'index', what = A, idx = idx, et = newet}
  367. end
  368. expect("]")
  369. elseif maybe("(") then
  370. if not Types.is_callable(A.et) then
  371. error("Called value is not a function.")
  372. end
  373. local args = {}
  374. if not maybe(")") then
  375. while true do
  376. table.insert(args, parse_expr())
  377. if maybe(")") then break end
  378. expect(",")
  379. end
  380. end
  381. A = {type = 'call', what = A, et = A.et and A.et.ret or nil, args = args}
  382. elseif maybe(".") then
  383. local B = select(2, expect("id"))
  384. local has_field, field_type = Types.has_field(A.et, B)
  385. if not has_field then
  386. error(string.format("No such field %s", B))
  387. end
  388. A = {type = 'dot', a = A, b = B, et = field_type}
  389. end
  390. end
  391. return A
  392. end
  393. error("Invalid expression")
  394. end
  395. local function parse_stmt()
  396. if maybe("let") then
  397. local name = select(2, expect("id"))
  398. local et
  399. if maybe(":") then
  400. et = parse_et()
  401. end
  402. local expr
  403. if maybe("=") then
  404. expr = parse_expr()
  405. end
  406. if not et and not expr then
  407. error(string.format("Cannot create name %s without a given type", name))
  408. end
  409. if not et then
  410. et = expr.et
  411. elseif expr and not Types.castable(expr.et, et) then
  412. error(string.format("Cannot cast expression to type %s", et.type))
  413. end
  414. local newvar = {et = et, name = name}
  415. ParseContext[name] = newvar
  416. return {type = "let", var = newvar, expr = expr}
  417. elseif maybe("if") then
  418. local ret = {type = "if"}
  419. while true do
  420. local expr = parse_expr()
  421. if not et and not Types.castable(expr.et, {type = 'boolean'}) then
  422. error("If predicate must be castable to boolean")
  423. end
  424. expect("then")
  425. local chu = parse_chunk(false)
  426. table.insert(ret, {pred = expr, chu = chu})
  427. if maybe("else") then
  428. ret.elsa = parse_chunk(false)
  429. expect("end")
  430. break
  431. end
  432. if maybe("end") then
  433. break
  434. end
  435. expect("elseif")
  436. end
  437. return ret
  438. elseif maybe("for") then
  439. local varname = select(2, expect("id"))
  440. expect("=")
  441. local from = parse_expr()
  442. expect(",")
  443. local to = parse_expr()
  444. expect("do")
  445. push_parse_context()
  446. rawset(ParseContext, varname, {et = {type = 'integer'}, name = varname})
  447. local chu = parse_chunk(false)
  448. pop_parse_context()
  449. expect("end")
  450. return {type = "fori", varname = varname, from = from, to = to, chu = chu}
  451. elseif maybe("loop") then
  452. push_parse_context()
  453. local chu = parse_chunk(false)
  454. pop_parse_context()
  455. expect("end")
  456. return {type = "loop", chu = chu}
  457. elseif maybe("break") then
  458. return {type = "break"}
  459. elseif maybe("return") then
  460. local expr = parse_expr()
  461. if expr.et and not Types.castable(expr.et, ParseContextTypes["the function return type"]) then
  462. error(string.format("Function %s returns different type.", ParseContext["the function name"]))
  463. end
  464. return {type = "return", expr = expr}
  465. else
  466. local e = parse_expr()
  467. if maybe("=") then
  468. local src = parse_expr()
  469. if not Types.castable(src.et, e.et) then
  470. error("Cannot cast for assignment")
  471. end
  472. return {type = "assign", dest = e, src = src}
  473. else
  474. if e.type ~= "call" then
  475. error("Expected statement.")
  476. end
  477. return e
  478. end
  479. end
  480. error(string.format("Unexpected token %s", (select(2, peektoken()))))
  481. end
  482. local SAFE_MODE = true
  483. parse_chunk = function(toplevel)
  484. push_parse_context()
  485. local ast = {type = "chunk", types = {}, vars = {}, stmts = {}, imports = {}, toplevel = toplevel}
  486. table.insert(active_stmt_list_stack, ast.stmts)
  487. while true do
  488. local tt, ts, tr, tc = peektoken()
  489. if tt == "end" or tt == "else" or tt == "elseif" then
  490. if toplevel then
  491. error("Unexpected end in top-level chunk")
  492. end
  493. break
  494. elseif tt == nil then
  495. if not toplevel then
  496. error("Unexpected EOF in non top-level chunk")
  497. end
  498. break
  499. end
  500. if toplevel and tt == "import" then
  501. gettoken()
  502. local path = {}
  503. while true do
  504. local part = select(2, expect("id"))
  505. table.insert(path, part)
  506. if not maybe(".") then
  507. break
  508. end
  509. end
  510. rawset(ParseContext, path[#path], {et = nil, name = path[#path]})
  511. table.insert(ast.imports, path)
  512. elseif tt == "type" then
  513. local name, t = parse_type()
  514. ast.types[name] = t
  515. rawset(ParseContextTypes, name, t)
  516. elseif tt == "func" then
  517. local expr, name = parse_function()
  518. ast.vars[name] = expr
  519. rawset(ParseContext, name, {et = expr.et, name = name})
  520. elseif not toplevel then
  521. table.insert(ast.stmts, parse_stmt())
  522. else
  523. error(string.format("Unexpected %s in top-level chunk", tt))
  524. end
  525. end
  526. table.remove(active_stmt_list_stack)
  527. pop_parse_context()
  528. return ast
  529. end
  530. return parse_chunk(true)
  531. end
  532. --local chu = parse_chunk(true)
  533. --pass_destandardify(chu)
  534. --compile(chu)
  535. --print()
  536. return do_everything