xiiregexbuilder

commit ac8796a476323808a396dddd700772bcab5f504c
parent af09500cd291b011c9b2790673508cb204643dd9
Author: Pranav Prabhu Kumble <kumblepranavprabhu@gmail.com>
Date:   Sat, 28 Mar 2026 03:32:18 +0530

Week 2: Implement AST Parser (Part 1: Initial definitions)

Diffstat:
A
src/parser.cpp
 | 
42
++++++++++++++++++++++++++++++++++++++++++
A
src/parser.h
 | 
35
+++++++++++++++++++++++++++++++++++

2 files changed, 77 insertions(+), 0 deletions(-)
diff --git a/src/parser.cpp b/src/parser.cpp
@@ -0,0 +1,42 @@
+#include "parser.h"
+#include <stdexcept>
+
+std::string nodeTypeToString(ASTNodeType type) {
+    switch (type) {
+        case ASTNodeType::LITERAL:       return "LITERAL";
+        case ASTNodeType::DOT:           return "DOT";
+        case ASTNodeType::CONCATENATION: return "CONCATENATION";
+        case ASTNodeType::UNION:         return "UNION";
+        case ASTNodeType::STAR:          return "STAR";
+        case ASTNodeType::PLUS:          return "PLUS";
+        case ASTNodeType::OPTIONAL:      return "OPTIONAL";
+        default:                         return "UNKNOWN";
+    }
+}
+
+Parser::Parser(const std::vector<Token>& tokens) : tokens(tokens), pos(0) {}
+
+std::unique_ptr<ASTNode> Parser::parse() {
+    auto root = parseExpression();
+    if (!isAtEnd() && peek().type != TokenType::END_OF_INPUT) {
+        error("Unexpected token at end of expression: " + tokenTypeToString(peek().type));
+    }
+    return root;
+}
+
+// Expression -> Term ( '|' Term )*
+std::unique_ptr<ASTNode> Parser::parseExpression() {
+    if (check(TokenType::PIPE)) {
+        error("Empty alternation branch (missing left side)");
+    }
+    auto left = parseTerm();
+
+    while (match(TokenType::PIPE)) {
+        if (isAtEnd() || peek().type == TokenType::RPAREN || peek().type == TokenType::PIPE || peek().type == TokenType::END_OF_INPUT) {
+            error("Empty alternation branch");
+        }
+        auto right = parseTerm();
+        left = std::make_unique<UnionNode>(std::move(left), std::move(right));
+    }
+
+    return left;
diff --git a/src/parser.h b/src/parser.h
@@ -0,0 +1,35 @@
+#ifndef PARSER_H
+#define PARSER_H
+
+#include <memory>
+#include <vector>
+#include <set>
+#include "lexer.h"
+
+enum class ASTNodeType {
+    LITERAL,
+    DOT,
+    CONCATENATION,
+    UNION,
+    STAR,
+    PLUS,
+    OPTIONAL
+};
+
+class ASTNode {
+public:
+    ASTNodeType type;
+    virtual ~ASTNode() = default;
+
+    // The following fields are populated by the NFA builder (Stage 2), NOT the parser.
+    bool nullable = false;
+    std::set<int> firstpos;
+    std::set<int> lastpos;
+
+    explicit ASTNode(ASTNodeType t) : type(t) {}
+};
+
+std::string nodeTypeToString(ASTNodeType type);
+
+class LiteralNode : public ASTNode {
+public: