/* Copyright (C) 2022-2025 Davide Faconti - All Rights Reserved
*
* Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
* The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
#include "behaviortree_cpp/scripting/script_parser.hpp"
#include "behaviortree_cpp/scripting/operators.hpp"
#include
namespace BT
{
namespace Scripting
{
class ScriptParser
{
public:
explicit ScriptParser(std::vector tokens) : tokens_(std::move(tokens))
{}
std::vector parseAll()
{
std::vector stmts;
while(!atEnd())
{
stmts.push_back(parseExpr(0));
// consume optional semicolons between statements
while(check(TokenType::Semicolon))
{
advance();
}
}
return stmts;
}
private:
std::vector tokens_;
size_t current_ = 0;
int depth_ = 0;
// Upper bound on the nesting of the recursive-descent grammar. Each open
// paren / unary prefix / right-hand operand adds one parseExpr frame, so a
// crafted expression like "((((...0...))))" would otherwise recurse until the
// native stack is exhausted. This mirrors the kMaxNestingDepth cap the XML
// parser already applies in VerifyXML and recursivelyCreateSubtree.
static constexpr int kMaxNestingDepth = 256;
// Binding power constants. Higher value = tighter binding.
static constexpr int kAssignmentBP = 2;
static constexpr int kTernaryBP = 4;
static constexpr int kComparisonBP = 10;
static constexpr int kMulDivBP = 18;
static constexpr int kPrefixBP = 20; // tighter than any infix
//--- Token access ---
const Token& peek() const
{
return tokens_[current_];
}
const Token& advance()
{
const Token& tok = tokens_[current_];
if(!atEnd())
current_++;
return tok;
}
bool atEnd() const
{
return peek().type == TokenType::EndOfInput;
}
bool check(TokenType type) const
{
return peek().type == type;
}
const Token& expect(TokenType type, const char* msg)
{
if(!check(type))
{
throw RuntimeError(StrCat("Parse error at position ", std::to_string(peek().pos),
": ", msg, " (got '", peek().text, "')"));
}
return advance();
}
//--- Binding power helpers ---
// Returns the left binding power of an infix/postfix operator,
// or -1 if the token is not an infix operator.
static int leftBP(TokenType type)
{
switch(type)
{
// Assignment (level 1, non-associative)
case TokenType::ColonEqual:
case TokenType::Equal:
case TokenType::PlusEqual:
case TokenType::MinusEqual:
case TokenType::StarEqual:
case TokenType::SlashEqual:
return kAssignmentBP;
// Ternary (level 2, non-associative)
case TokenType::Question:
return kTernaryBP;
// Logical OR (level 3)
case TokenType::PipePipe:
return 6;
// Logical AND (level 4)
case TokenType::AmpAmp:
return 8;
// Comparison (level 5, chainable)
case TokenType::EqualEqual:
case TokenType::BangEqual:
case TokenType::Less:
case TokenType::Greater:
case TokenType::LessEqual:
case TokenType::GreaterEqual:
return kComparisonBP;
// Bitwise OR/XOR (level 6)
case TokenType::Pipe:
case TokenType::Caret:
return 12;
// Bitwise AND (level 7)
case TokenType::Ampersand:
return 14;
// Add/Sub/Concat (level 8)
case TokenType::Plus:
case TokenType::Minus:
case TokenType::DotDot:
return 16;
// Mul/Div (level 9)
case TokenType::Star:
case TokenType::Slash:
return kMulDivBP;
default:
return -1;
}
}
static bool isComparison(TokenType type)
{
return type == TokenType::EqualEqual || type == TokenType::BangEqual ||
type == TokenType::Less || type == TokenType::Greater ||
type == TokenType::LessEqual || type == TokenType::GreaterEqual;
}
static bool isAssignment(TokenType type)
{
return type == TokenType::ColonEqual || type == TokenType::Equal ||
type == TokenType::PlusEqual || type == TokenType::MinusEqual ||
type == TokenType::StarEqual || type == TokenType::SlashEqual;
}
//--- Parsing ---
/// Prefix: atoms and unary prefix operators
Ast::expr_ptr parsePrefix()
{
const auto& tok = peek();
// Unary minus
if(tok.type == TokenType::Minus)
{
advance();
auto operand = parseExpr(kPrefixBP);
return std::make_shared(Ast::ExprUnaryArithmetic::negate,
std::move(operand));
}
// Bitwise complement
if(tok.type == TokenType::Tilde)
{
advance();
auto operand = parseExpr(kPrefixBP);
return std::make_shared(
Ast::ExprUnaryArithmetic::complement, std::move(operand));
}
// Logical NOT
if(tok.type == TokenType::Bang)
{
advance();
auto operand = parseExpr(kPrefixBP);
return std::make_shared(
Ast::ExprUnaryArithmetic::logical_not, std::move(operand));
}
// Parenthesized expression
if(tok.type == TokenType::LeftParen)
{
advance();
auto expr = parseExpr(0);
expect(TokenType::RightParen, "expected ')'");
return expr;
}
// Boolean literal
if(tok.type == TokenType::Boolean)
{
advance();
double val = (tok.text == "true") ? 1.0 : 0.0;
return std::make_shared(Any(val));
}
// Integer literal
if(tok.type == TokenType::Integer)
{
advance();
int64_t val = 0;
const char* first = tok.text.data();
const char* last = first + tok.text.size();
if(tok.text.size() > 2 && tok.text[0] == '0' &&
(tok.text[1] == 'x' || tok.text[1] == 'X'))
{
std::from_chars(first + 2, last, val, 16);
}
else
{
std::from_chars(first, last, val, 10);
}
return std::make_shared(Any(val));
}
// Real literal
if(tok.type == TokenType::Real)
{
advance();
double val = convertFromString(tok.text);
return std::make_shared(Any(val));
}
// String literal
if(tok.type == TokenType::String)
{
advance();
return std::make_shared(Any(std::string(tok.text)));
}
// Identifier
if(tok.type == TokenType::Identifier)
{
advance();
return std::make_shared(std::string(tok.text));
}
// Error token from tokenizer
if(tok.type == TokenType::Error)
{
throw RuntimeError(
StrCat("Invalid token '", tok.text, "' at position ", std::to_string(tok.pos)));
}
throw RuntimeError(StrCat("Expected operand at position ", std::to_string(tok.pos),
" (got '", tok.text, "')"));
}
/// Main Pratt expression parser
Ast::expr_ptr parseExpr(int minBP)
{
// Bound the recursion so a deeply nested expression can't overflow the
// stack. Every open paren / unary prefix / right-hand operand adds one
// parseExpr frame; depth_ is decremented before the normal return below so
// it tracks the current nesting rather than the total call count. A parse
// failure throws and discards the parser, so the error paths need no reset.
if(++depth_ > kMaxNestingDepth)
{
throw RuntimeError(StrCat("Parse error at position ", std::to_string(peek().pos),
": expression nesting is too deep (limit ",
std::to_string(kMaxNestingDepth), ")"));
}
auto left = parsePrefix();
while(true)
{
auto tokType = peek().type;
int lbp = leftBP(tokType);
if(lbp < 0 || lbp < minBP)
{
break;
}
// Assignment (non-associative: parse once, then break)
if(isAssignment(tokType))
{
left = parseAssignment(std::move(left));
break;
}
// Ternary (non-associative: parse once, then break)
if(tokType == TokenType::Question)
{
left = parseTernary(std::move(left));
break;
}
// Chained comparison
if(isComparison(tokType))
{
left = parseChainedComparison(std::move(left));
continue;
}
// Regular left-associative binary operator
const auto& opTok = advance();
// Right BP = LBP + 1 for left-associativity
auto right = parseExpr(lbp + 1);
left = makeBinary(std::move(left), opTok.type, std::move(right));
}
--depth_;
return left;
}
Ast::expr_ptr parseAssignment(Ast::expr_ptr left)
{
const auto& opTok = advance();
Ast::ExprAssignment::op_t op{};
switch(opTok.type)
{
case TokenType::ColonEqual:
op = Ast::ExprAssignment::assign_create;
break;
case TokenType::Equal:
op = Ast::ExprAssignment::assign_existing;
break;
case TokenType::PlusEqual:
op = Ast::ExprAssignment::assign_plus;
break;
case TokenType::MinusEqual:
op = Ast::ExprAssignment::assign_minus;
break;
case TokenType::StarEqual:
op = Ast::ExprAssignment::assign_times;
break;
case TokenType::SlashEqual:
op = Ast::ExprAssignment::assign_div;
break;
default:
throw RuntimeError("Internal error: unexpected assignment op");
}
// Parse RHS -- use minBP=0 to allow full expression
auto right = parseExpr(0);
return std::make_shared(std::move(left), op, std::move(right));
}
Ast::expr_ptr parseTernary(Ast::expr_ptr condition)
{
advance(); // consume '?'
auto thenExpr = parseExpr(0); // full expression inside
expect(TokenType::Colon, "expected ':' in ternary expression");
auto elseExpr = parseExpr(kTernaryBP);
return std::make_shared(std::move(condition), std::move(thenExpr),
std::move(elseExpr));
}
Ast::expr_ptr parseChainedComparison(Ast::expr_ptr first)
{
auto node = std::make_shared();
node->operands.push_back(std::move(first));
while(isComparison(peek().type))
{
node->ops.push_back(mapComparisonOp(advance().type));
// Parse the next operand above comparison level
// so that arithmetic binds tighter
node->operands.push_back(parseExpr(kComparisonBP + 1));
}
return node;
}
static Ast::ExprComparison::op_t mapComparisonOp(TokenType type)
{
switch(type)
{
case TokenType::EqualEqual:
return Ast::ExprComparison::equal;
case TokenType::BangEqual:
return Ast::ExprComparison::not_equal;
case TokenType::Less:
return Ast::ExprComparison::less;
case TokenType::Greater:
return Ast::ExprComparison::greater;
case TokenType::LessEqual:
return Ast::ExprComparison::less_equal;
case TokenType::GreaterEqual:
return Ast::ExprComparison::greater_equal;
default:
throw RuntimeError("Internal error: not a comparison op");
}
}
static Ast::expr_ptr makeBinary(Ast::expr_ptr left, TokenType opType,
Ast::expr_ptr right)
{
Ast::ExprBinaryArithmetic::op_t op{};
switch(opType)
{
case TokenType::Plus:
op = Ast::ExprBinaryArithmetic::plus;
break;
case TokenType::Minus:
op = Ast::ExprBinaryArithmetic::minus;
break;
case TokenType::Star:
op = Ast::ExprBinaryArithmetic::times;
break;
case TokenType::Slash:
op = Ast::ExprBinaryArithmetic::div;
break;
case TokenType::DotDot:
op = Ast::ExprBinaryArithmetic::concat;
break;
case TokenType::Ampersand:
op = Ast::ExprBinaryArithmetic::bit_and;
break;
case TokenType::Pipe:
op = Ast::ExprBinaryArithmetic::bit_or;
break;
case TokenType::Caret:
op = Ast::ExprBinaryArithmetic::bit_xor;
break;
case TokenType::AmpAmp:
op = Ast::ExprBinaryArithmetic::logic_and;
break;
case TokenType::PipePipe:
op = Ast::ExprBinaryArithmetic::logic_or;
break;
default:
throw RuntimeError("Internal error: unknown binary operator");
}
return std::make_shared(std::move(left), op,
std::move(right));
}
};
std::vector parseStatements(const std::string& script)
{
auto tokens = tokenize(script);
ScriptParser parser(std::move(tokens));
return parser.parseAll();
}
} // namespace Scripting
//--- Public API ---
Expected ParseScript(const std::string& script)
{
try
{
auto exprs = Scripting::parseStatements(script);
if(exprs.empty())
{
return nonstd::make_unexpected("Empty Script");
}
return [exprs = std::move(exprs), script](Ast::Environment& env) {
try
{
for(size_t i = 0; i < exprs.size() - 1; ++i)
{
exprs[i]->evaluate(env);
}
return exprs.back()->evaluate(env);
}
catch(RuntimeError& err)
{
throw RuntimeError(StrCat("Error in script [", script, "]\n", err.what()));
}
};
}
catch(RuntimeError& err)
{
return nonstd::make_unexpected(err.what());
}
}
Expected ParseScriptAndExecute(Ast::Environment& env, const std::string& script)
{
auto executor = ParseScript(script);
if(executor)
{
try
{
return executor.value()(env);
}
catch(RuntimeError& err)
{
return nonstd::make_unexpected(err.what());
}
}
return nonstd::make_unexpected(executor.error());
}
Result ValidateScript(const std::string& script)
{
try
{
auto exprs = Scripting::parseStatements(script);
if(exprs.empty())
{
return nonstd::make_unexpected("Empty Script");
}
return {};
}
catch(RuntimeError& err)
{
return nonstd::make_unexpected(err.what());
}
}
} // namespace BT