xiiregexbuilder

  1#include "parser.h"
  2#include <stdexcept>
  3
  4std::string nodeTypeToString(ASTNodeType type) {
  5    switch (type) {
  6        case ASTNodeType::LITERAL:       return "LITERAL";
  7        case ASTNodeType::DOT:           return "DOT";
  8        case ASTNodeType::CONCATENATION: return "CONCATENATION";
  9        case ASTNodeType::UNION:         return "UNION";
 10        case ASTNodeType::STAR:          return "STAR";
 11        case ASTNodeType::PLUS:          return "PLUS";
 12        case ASTNodeType::OPTIONAL:      return "OPTIONAL";
 13        case ASTNodeType::CHAR_CLASS:    return "CHAR_CLASS";
 14        default:                         return "UNKNOWN";
 15    }
 16}
 17
 18Parser::Parser(const std::vector<Token>& tokens) : tokens(tokens), pos(0) {}
 19
 20std::unique_ptr<ASTNode> Parser::parse() {
 21    auto root = parseExpression();
 22    if (!isAtEnd() && peek().type != TokenType::END_OF_INPUT) {
 23        error("Unexpected token at end of expression: " + tokenTypeToString(peek().type));
 24    }
 25    return root;
 26}
 27
 28// Expression -> Term ( '|' Term )*
 29std::unique_ptr<ASTNode> Parser::parseExpression() {
 30    if (check(TokenType::PIPE)) error("Empty alternation branch");
 31    auto left = parseTerm();
 32    while (match(TokenType::PIPE)) {
 33        auto right = parseTerm();
 34        left = std::make_unique<UnionNode>(std::move(left), std::move(right));
 35    }
 36    return left;
 37}
 38
 39// Term -> Factor+
 40std::unique_ptr<ASTNode> Parser::parseTerm() {
 41    auto node = parseFactor();
 42
 43    while (!isAtEnd() && 
 44           peek().type != TokenType::PIPE && 
 45           peek().type != TokenType::RPAREN && 
 46           peek().type != TokenType::END_OF_INPUT) {
 47        auto next = parseFactor();
 48        node = std::make_unique<ConcatenationNode>(std::move(node), std::move(next));
 49    }
 50
 51    return node;
 52}
 53
 54// Factor -> Atom ( '*' | '+' | '?' )?
 55std::unique_ptr<ASTNode> Parser::parseFactor() {
 56    auto node = parseAtom();
 57
 58    if (match(TokenType::STAR)) {
 59        node = std::make_unique<StarNode>(std::move(node));
 60    } else if (match(TokenType::PLUS)) {
 61        node = std::make_unique<PlusNode>(std::move(node));
 62    } else if (match(TokenType::QUESTION)) {
 63        node = std::make_unique<OptionalNode>(std::move(node));
 64    }
 65
 66    return node;
 67}
 68
 69// Atom -> LITERAL | DOT | '(' Expression ')'
 70std::unique_ptr<ASTNode> Parser::parseAtom() {
 71    if (match(TokenType::LITERAL)) {
 72        return std::make_unique<LiteralNode>(tokens[pos - 1].value);
 73    }
 74
 75    if (match(TokenType::DOT)) {
 76        return std::make_unique<DotNode>();
 77    }
 78
 79    if (match(TokenType::LPAREN)) {
 80        auto node = parseExpression();
 81        if (!match(TokenType::RPAREN)) error("Unmatched parenthesis");
 82        return node;
 83    }
 84
 85    if (match(TokenType::LBRACKET)) {
 86        auto node = std::make_unique<CharClassNode>();
 87        while (!check(TokenType::RBRACKET) && !isAtEnd()) {
 88            if (peek().type == TokenType::END_OF_INPUT) error("Unterminated char class");
 89            char start = advance().value;
 90            if (peek().value == '-' && pos + 1 < tokens.size() && 
 91                (tokens[pos+1].type == TokenType::LITERAL || tokens[pos+1].type == TokenType::DOT)) {
 92                advance(); // consume '-'
 93                char end = advance().value;
 94                for (int c = start; c <= end; ++c) node->characters.insert(static_cast<unsigned char>(c));
 95            } else {
 96                node->characters.insert(static_cast<unsigned char>(start));
 97            }
 98        }
 99        if (!match(TokenType::RBRACKET)) error("Expected ']' after char class");
100        return node;
101    }
102
103    if (peek().type == TokenType::STAR || peek().type == TokenType::PLUS || peek().type == TokenType::QUESTION) {
104        error("Quantifier applied to nothing");
105    }
106
107    error("Unexpected token: " + tokenTypeToString(peek().type));
108    return nullptr;
109}
110
111const Token& Parser::peek() const {
112    return tokens[pos];
113}
114
115const Token& Parser::advance() {
116    if (!isAtEnd()) pos++;
117    return tokens[pos - 1];
118}
119
120bool Parser::match(TokenType type) {
121    if (check(type)) {
122        advance();
123        return true;
124    }
125    return false;
126}
127
128bool Parser::check(TokenType type) const {
129    if (isAtEnd()) return false;
130    return peek().type == type;
131}
132
133bool Parser::isAtEnd() const {
134    return pos >= tokens.size() || tokens[pos].type == TokenType::END_OF_INPUT;
135}
136
137void Parser::error(const std::string& message) const {
138    const Token& t = peek();
139    throw std::runtime_error(message + " at line " + std::to_string(t.line) + ", column " + std::to_string(t.column));
140}