Home /Modules/sleela-terminal/parser.cpp

parser.cpp

sleela-terminal/parser.cpp · 373 line(s) · c

// SleelaTerminal(TM) shell -- L3 parser implementation.
// Original SLeeLa work (see NOTICE).

#include "parser.hpp"

#include <stdexcept>

namespace sleela::sh {

namespace {

// Thrown internally to unwind to parse(); converted to a ParseError there.
struct PErr {
    std::string message;
    int line;
    int col;
};

class Parser {
public:
    explicit Parser(const std::vector<Token>& toks) : t_(toks) {}

    NodePtr parseProgram() {
        skipSeparators();
        auto list = parseList();
        if (peek().kind != Tok::Eof) {
            throw PErr{"unexpected token '" + peek().text + "'", peek().line, peek().col};
        }
        return list;
    }

private:
    const Token& peek() const { return t_[pos_]; }
    const Token& peek2() const { return pos_ + 1 < t_.size() ? t_[pos_ + 1] : t_.back(); }
    const Token& advance() { return t_[pos_ < t_.size() - 1 ? pos_++ : pos_]; }
    bool at(Tok k) const { return peek().kind == k; }

    void expect(Tok k, const char* what) {
        if (peek().kind != k) {
            throw PErr{std::string("expected ") + what + " but found '" + peek().text + "'",
                       peek().line, peek().col};
        }
        advance();
    }

    void skipSeparators() {
        while (at(Tok::Semi) || at(Tok::Newline)) advance();
    }

    bool isListTerminator() const {
        switch (peek().kind) {
            case Tok::Eof: case Tok::Then: case Tok::Elif: case Tok::Else:
            case Tok::Fi: case Tok::Do: case Tok::Done:
            case Tok::Esac: case Tok::RBrace:
                return true;
            default:
                return false;
        }
    }

    // list := andor ( (';' | '\n') andor )*
    NodePtr parseList() {
        auto list = std::make_unique<Node>(NodeKind::List);
        list->children.push_back(parseAndOr());
        list->child_async.push_back(false);
        for (;;) {
            // A separator is ';', newline, or '&' (which marks the *previous*
            // and-or as asynchronous / background).
            bool sawSep = false;
            while (at(Tok::Semi) || at(Tok::Newline) || at(Tok::Amp)) {
                if (at(Tok::Amp)) list->child_async.back() = true;
                advance();
                sawSep = true;
            }
            if (!sawSep) break;
            if (isListTerminator()) break;
            list->children.push_back(parseAndOr());
            list->child_async.push_back(false);
        }
        return list;
    }

    // andor := pipeline ( ('&&' | '||') pipeline )*
    NodePtr parseAndOr() {
        auto first = parsePipeline();
        if (!at(Tok::AndIf) && !at(Tok::OrIf)) return first;

        auto node = std::make_unique<Node>(NodeKind::AndOr);
        node->children.push_back(std::move(first));
        while (at(Tok::AndIf) || at(Tok::OrIf)) {
            node->andor_ops.push_back(at(Tok::AndIf) ? AndOrOp::And : AndOrOp::Or);
            advance();
            // allow a newline after && / ||
            while (at(Tok::Newline)) advance();
            node->children.push_back(parsePipeline());
        }
        return node;
    }

    // pipeline := [ '!' ] command ( '|' command )*
    NodePtr parsePipeline() {
        bool negated = false;
        while (at(Tok::Bang)) { negated = !negated; advance(); }

        auto first = parseCommand();
        if (!at(Tok::Pipe)) {
            if (negated) {
                // Wrap a single command in a Pipeline node to carry the flag.
                auto node = std::make_unique<Node>(NodeKind::Pipeline);
                node->negated = true;
                node->children.push_back(std::move(first));
                return node;
            }
            return first;
        }

        auto node = std::make_unique<Node>(NodeKind::Pipeline);
        node->negated = negated;
        node->children.push_back(std::move(first));
        while (at(Tok::Pipe)) {
            advance();
            while (at(Tok::Newline)) advance();
            node->children.push_back(parseCommand());
        }
        return node;
    }

    // command := if | while | for | case | function_def | brace_group | simple
    NodePtr parseCommand() {
        if (at(Tok::If)) return parseIf();
        if (at(Tok::While)) return parseWhile();
        if (at(Tok::Until)) return parseUntil();
        if (at(Tok::For)) return parseFor();
        if (at(Tok::Case)) return parseCase();
        if (at(Tok::LBrace)) return parseBraceGroup();
        // function definition: WORD '(' ')' '{' ... '}'
        if (at(Tok::Word) && peek2().kind == Tok::LParen) return parseFunctionDef();
        return parseSimple();
    }

    // brace_group := '{' list '}'   (executed in the current shell)
    NodePtr parseBraceGroup() {
        expect(Tok::LBrace, "'{'");
        while (at(Tok::Newline)) advance();
        auto list = parseList();
        while (at(Tok::Newline) || at(Tok::Semi)) advance();
        expect(Tok::RBrace, "'}'");
        return list;
    }

    // function_def := WORD '(' ')' brace_group
    NodePtr parseFunctionDef() {
        auto node = std::make_unique<Node>(NodeKind::FunctionDef);
        node->func_name = peek().text;
        advance();                     // name
        expect(Tok::LParen, "'('");
        expect(Tok::RParen, "')'");
        while (at(Tok::Newline)) advance();
        node->func_body = parseBraceGroup();
        return node;
    }

    // for := 'for' NAME [ 'in' word* ] (';'|'\n') 'do' list 'done'
    NodePtr parseFor() {
        auto node = std::make_unique<Node>(NodeKind::For);
        expect(Tok::For, "'for'");
        if (!at(Tok::Word)) throw PErr{"expected a variable name after 'for'", peek().line, peek().col};
        node->for_var = peek().text;
        advance();
        // optional word list after 'in'
        if (at(Tok::In)) {
            advance();
            while (at(Tok::Word)) { node->for_words.push_back(peek().text); advance(); }
        } else {
            // no explicit list -> iterate the positional parameters ("$@")
            node->for_words.push_back("$@");
        }
        // separator, then do..done
        while (at(Tok::Semi) || at(Tok::Newline)) advance();
        expect(Tok::Do, "'do'");
        while (at(Tok::Newline)) advance();
        node->for_body = parseList();
        expect(Tok::Done, "'done'");
        return node;
    }

    // case := 'case' word 'in' ( [ '(' ] pattern ('|' pattern)* ')' list ';;' )* 'esac'
    NodePtr parseCase() {
        auto node = std::make_unique<Node>(NodeKind::Case);
        expect(Tok::Case, "'case'");
        if (!at(Tok::Word)) throw PErr{"expected a word after 'case'", peek().line, peek().col};
        node->case_subject = peek().text;
        advance();
        expect(Tok::In, "'in'");
        while (at(Tok::Newline) || at(Tok::Semi)) advance();

        while (!at(Tok::Esac)) {
            CaseItem item;
            if (at(Tok::LParen)) advance();  // optional leading '('
            // patterns separated by '|', terminated by ')'
            for (;;) {
                if (!at(Tok::Word)) throw PErr{"expected a case pattern", peek().line, peek().col};
                item.patterns.push_back(peek().text);
                advance();
                if (at(Tok::Pipe)) { advance(); continue; }
                break;
            }
            expect(Tok::RParen, "')'");
            while (at(Tok::Newline)) advance();
            // body: a list up to ';;' (represented as Semi Semi) or 'esac'
            item.body = parseCaseBody();
            node->case_items.push_back(std::move(item));
            while (at(Tok::Newline) || at(Tok::Semi)) advance();
        }
        expect(Tok::Esac, "'esac'");
        return node;
    }

    // Parse a case arm body: a list that ends at ';;' or 'esac'. We detect ';;'
    // as two consecutive Semi tokens.
    NodePtr parseCaseBody() {
        auto list = std::make_unique<Node>(NodeKind::List);
        // empty body (immediate ';;' or 'esac')
        if (isCaseArmEnd()) return list;
        list->children.push_back(parseAndOr());
        for (;;) {
            // ';;' ends the arm
            if (at(Tok::Semi) && peek2().kind == Tok::Semi) { advance(); advance(); break; }
            bool sawSep = false;
            while (at(Tok::Semi) || at(Tok::Newline)) {
                if (at(Tok::Semi) && peek2().kind == Tok::Semi) break;  // leave ';;'
                advance(); sawSep = true;
            }
            if (at(Tok::Semi) && peek2().kind == Tok::Semi) { advance(); advance(); break; }
            if (at(Tok::Esac)) break;
            if (!sawSep) break;
            if (at(Tok::Esac)) break;
            list->children.push_back(parseAndOr());
        }
        return list;
    }

    bool isCaseArmEnd() const {
        if (at(Tok::Esac)) return true;
        if (at(Tok::Semi) && peek2().kind == Tok::Semi) return true;
        return false;
    }

    // if := 'if' list 'then' list ('elif' list 'then' list)* ['else' list] 'fi'
    NodePtr parseIf() {
        auto node = std::make_unique<Node>(NodeKind::If);
        expect(Tok::If, "'if'");
        node->if_conds.push_back(parseList());
        expect(Tok::Then, "'then'");
        node->if_bodies.push_back(parseList());
        while (at(Tok::Elif)) {
            advance();
            node->if_conds.push_back(parseList());
            expect(Tok::Then, "'then'");
            node->if_bodies.push_back(parseList());
        }
        if (at(Tok::Else)) {
            advance();
            node->else_body = parseList();
        }
        expect(Tok::Fi, "'fi'");
        return node;
    }

    // while := 'while' list 'do' list 'done'
    NodePtr parseWhile() {
        auto node = std::make_unique<Node>(NodeKind::While);
        expect(Tok::While, "'while'");
        node->while_cond = parseList();
        expect(Tok::Do, "'do'");
        while (at(Tok::Newline)) advance();
        node->while_body = parseList();
        expect(Tok::Done, "'done'");
        return node;
    }

    // until := 'until' list 'do' list 'done'  (runs body while cond is FALSE)
    NodePtr parseUntil() {
        auto node = std::make_unique<Node>(NodeKind::Until);
        expect(Tok::Until, "'until'");
        node->while_cond = parseList();
        expect(Tok::Do, "'do'");
        while (at(Tok::Newline)) advance();
        node->while_body = parseList();
        expect(Tok::Done, "'done'");
        return node;
    }

    // simple := (assignment)* (word | redirection)+   (all optional if assigns)
    NodePtr parseSimple() {
        auto node = std::make_unique<Node>(NodeKind::Simple);

        // leading assignments
        while (at(Tok::Assignment)) {
            const std::string& s = peek().text;
            const auto eq = s.find('=');
            node->assigns.push_back(Assignment{s.substr(0, eq), s.substr(eq + 1)});
            advance();
        }

        // words and redirections, in any order
        for (;;) {
            if (at(Tok::Word)) {
                node->words.push_back(peek().text);
                advance();
            } else if (at(Tok::Less) || at(Tok::Great) || at(Tok::DGreat)) {
                Redirection r;
                r.op = at(Tok::Less) ? RedirOp::In
                     : at(Tok::Great) ? RedirOp::Out : RedirOp::Append;
                advance();
                if (!at(Tok::Word)) {
                    throw PErr{"expected filename after redirection", peek().line, peek().col};
                }
                r.target = peek().text;
                advance();
                node->redirs.push_back(std::move(r));
            } else if (at(Tok::DLess) || at(Tok::DLessDash)) {
                // here-document: << DELIM  followed by a HeredocBody token
                Redirection r;
                r.op = RedirOp::Heredoc;
                advance();
                if (!at(Tok::Word)) {
                    throw PErr{"expected here-document delimiter", peek().line, peek().col};
                }
                r.target = peek().text;   // the delimiter (informational)
                advance();
                if (!at(Tok::HeredocBody)) {
                    throw PErr{"missing here-document body", peek().line, peek().col};
                }
                {
                    const std::string& bt = peek().text;
                    r.expand_body = !bt.empty() && bt[0] == 'E';
                    r.body = bt.empty() ? std::string() : bt.substr(1);
                }
                advance();
                node->redirs.push_back(std::move(r));
            } else {
                break;
            }
        }

        if (node->assigns.empty() && node->words.empty() && node->redirs.empty()) {
            throw PErr{"expected a command but found '" + peek().text + "'",
                       peek().line, peek().col};
        }
        return node;
    }

    const std::vector<Token>& t_;
    std::size_t pos_ = 0;
};

} // namespace

NodePtr parse(const std::vector<Token>& tokens, ParseError& err) {
    try {
        Parser p(tokens);
        auto node = p.parseProgram();
        err = ParseError{};
        return node;
    } catch (const PErr& e) {
        err = ParseError{e.message, e.line, e.col};
        return nullptr;
    }
}

} // namespace sleela::sh