llvm-journey

commit 302c5702401c14acd757563f5e7edb685e900cbc
parent 2d54b5b80877040cf62707c3eda5ead300291ada
Author: Mohammad-Reza Nabipoor <m.nabipoor@yahoo.com>
Date:   Sun, 16 Aug 2020 09:22:57 +0430

Add basic parser (parse extern statements)

Diffstat:
A
kaleidoscope_parser.hpp
 | 
178
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
tests/kaleidoscope_parser.test.cpp
 | 
73
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 251 insertions(+), 0 deletions(-)
diff --git a/kaleidoscope_parser.hpp b/kaleidoscope_parser.hpp
@@ -0,0 +1,178 @@
+
+#pragma once
+
+#include "kaleidoscope_ast.hpp"
+#include "kaleidoscope_lexer.hpp"
+
+#include <string>
+
+namespace kal {
+
+namespace detail {
+
+template<typename FwdIt>
+struct ParseResult
+{
+  FwdIt last;
+  ASTNode node;
+  struct
+  {
+    FwdIt pos;
+    std::string msg;
+  } err;
+};
+
+template<typename FwdIt>
+ParseResult<FwdIt>
+parse_prototype(FwdIt f, FwdIt l)
+{
+  ParseResult<FwdIt> r{
+    f,
+  };
+  Prototype p;
+  auto err = [&](auto&& msg) {
+    r.err.pos = f;
+    r.err.msg = std::move(msg);
+  };
+
+  assert(f != l);
+
+  if (token_type(*f) != TkType::Id) {
+    err("expects identifier");
+    return r;
+  }
+
+  p.name = token_str(*f);
+  ++f;
+
+  if (token_str(*f) != "(") {
+    err("expects `(`");
+    return r;
+  }
+  ++f;
+
+  // args
+  while (f != l && token_str(*f) != ")") {
+    if (token_type(*f) != TkType::Id) {
+      err("early termination: expects identifier");
+      return r;
+    }
+
+    p.params.emplace_back(token_str(*f));
+    ++f;
+  }
+
+  if (f == l) {
+    err("early termination: expects `)`");
+    return r;
+  }
+  ++f;
+
+  r.last = f;
+  r.node = std::move(p);
+  return r;
+}
+
+template<typename FwdIt>
+ParseResult<FwdIt>
+parse_expr(FwdIt f, FwdIt l)
+{
+  ParseResult<FwdIt> r{
+    f,
+  };
+  auto err = [&](auto&& msg) {
+    r.err.pos = f;
+    r.err.msg = std::move(msg);
+  };
+
+  assert(f != l);
+
+  (void)err;
+
+  r.last = f;
+  err("not implemented yet");
+  return r;
+}
+
+} // namespace detail
+
+// TODO std::move err msg
+
+template<typename FwdIt, typename OutIt, typename ErrOp>
+FwdIt
+parse(FwdIt f, FwdIt l, OutIt nodes, ErrOp error)
+{
+  auto err = [&](FwdIt pos, const auto& msg) {
+    error(pos, msg);
+    return pos;
+  };
+
+  while (f != l) {
+    switch (token_type(*f)) {
+      case TkType::Extern: {
+        if (++f == l)
+          return err(f,
+                     "early termination: "
+                     "expects function prototype after `extern` keyword");
+
+        auto r = detail::parse_prototype(f, l);
+
+        if (r.last == f) // failure
+          return err(r.err.pos, r.err.msg);
+        f = r.last;
+        *nodes++ = std::move(r.node);
+      } break;
+
+      case TkType::Def: {
+        if (++f == l)
+          return err(f,
+                     "early termination: "
+                     "expects function prototype after `def` keyword");
+
+        {
+          auto r = detail::parse_prototype(f, l);
+
+          if (r.last == f) // failure
+            return err(r.err.pos, r.err.msg);
+          f = r.last;
+          *nodes++ = std::move(r.node);
+        }
+
+        if (f == l)
+          return err(f, "early termination: expects function body");
+
+        {
+          auto r = detail::parse_expr(f, l);
+
+          if (r.last == f) // failure
+            return err(r.err.pos, r.err.msg);
+          f = r.last;
+          *nodes++ = std::move(r.node);
+        }
+      } break;
+
+      case TkType::Etc:
+        if (token_str(*f) == ";") {
+          ++f;
+          break;
+        }
+        /* fallthrough */
+
+      default: { // top-level expr
+        auto r = detail::parse_expr(f, l);
+
+        if (r.last == f) // failure
+          return err(r.err.pos, r.err.msg);
+        f = r.last;
+        *nodes++ = std::move(r.node);
+      } break;
+
+      case TkType::END:
+        return f;
+    }
+  }
+
+  return f;
+}
+
+} // namespace kal
diff --git a/tests/kaleidoscope_parser.test.cpp b/tests/kaleidoscope_parser.test.cpp
@@ -0,0 +1,73 @@
+
+#include "kaleidoscope_parser.hpp"
+
+#define CATCH_CONFIG_MAIN
+#define CATCH_CONFIG_COLOUR_NONE
+#include <catch2/catch.hpp>
+
+#include <iterator>
+#include <string>
+#include <vector>
+
+#include <iostream> // FIXME
+
+#include "kaleidoscope_ast.hpp"
+#include "kaleidoscope_tokens.hpp"
+
+TEST_CASE("parse simple programs", "[simple]")
+{
+  auto p = [](const std::string& s) {
+    std::vector<kal::Token> tk;
+    std::vector<kal::ASTNode> nd;
+
+    kal::tokenize(s.cbegin(), s.cend(), std::back_inserter(tk));
+    tk.erase(std::remove_if(
+               tk.begin(),
+               tk.end(),
+               [](const auto& t) { return t.type == kal::TkType::Comment; }),
+             tk.end());
+
+    auto tkb = tk.cbegin();
+    auto tke = tk.cend();
+
+    kal::parse(
+      tkb, tke, std::back_inserter(nd), [&](const auto& it, const auto& err) {
+        auto pos = std::distance(tkb, it);
+
+        FAIL("PARSER ERROR pos:" << pos << " err:\"" << err << '"');
+      });
+
+    return nd;
+  };
+
+  SECTION("extern")
+  {
+    {
+      auto nd = p("extern sin(x)");
+
+      using kal::to_string;
+
+      REQUIRE(nd.size() == 1);
+      REQUIRE(to_string(nd[0]) == "(prototype sin x)");
+    }
+
+    {
+      auto nd = p("extern tan2 ( arg0 arg1 )");
+
+      using kal::to_string;
+
+      REQUIRE(nd.size() == 1);
+      REQUIRE(to_string(nd[0]) == "(prototype tan2 arg0 arg1)");
+    }
+
+    {
+      auto nd = p("extern cos(realInput);extern atan2(arg0 arg1);");
+
+      using kal::to_string;
+
+      REQUIRE(nd.size() == 2);
+      REQUIRE(to_string(nd[0]) == "(prototype cos realInput)");
+      REQUIRE(to_string(nd[1]) == "(prototype atan2 arg0 arg1)");
+    }
+  }
+}