// SleelaTerminal(TM) shell -- L3 parser implementation. // Original SLeeLa work (see NOTICE). #include "parser.hpp" #include 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& 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(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(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(NodeKind::Pipeline); node->negated = true; node->children.push_back(std::move(first)); return node; } return first; } auto node = std::make_unique(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(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(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(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(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(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(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(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(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& t_; std::size_t pos_ = 0; }; } // namespace NodePtr parse(const std::vector& 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