রিকার্সিভ ডিসেন্ট পার্সিং

# ব্যাকরণ (L12-এর গ্রামার, left-recursion elimination করা):
# <expr>  ::= <term> <expr'>
# <expr'> ::= + <term> <expr'> | - <term> <expr'> | ε
# <term>  ::= <factor> <term'>
# <term'> ::= * <factor> <term'> | / <factor> <term'> | ε
# <factor>::= ( <expr> ) | number
#
# প্র্যাকটিসে <expr'>/<term'>-এর ডান-রিকার্শনকে একটি while লুপ দিয়ে বাস্তবায়ন করা হয় --
# টেইল-রিকার্শনকে ইটারেশনে রূপান্তরের এটাই স্ট্যান্ডার্ড কৌশল।

def tokenize(expr):
    tokens = []
    i = 0
    while i < len(expr):
        ch = expr[i]
        if ch.isspace():
            i += 1
            continue
        elif ch.isdigit():
            start = i
            while i < len(expr) and expr[i].isdigit():
                i += 1
            tokens.append(("NUMBER", expr[start:i]))
        elif ch in "+-*/()":
            tokens.append(("OP", ch))
            i += 1
        else:
            raise ValueError(f"অজানা ক্যারেক্টার: {ch!r}")
    tokens.append(("EOF", ""))
    return tokens


def parse_expr(tokens, pos):
    """<expr> ::= <term> <expr'>  -- <expr'>-এর রিকার্শন এখানে while লুপ"""
    left, pos = parse_term(tokens, pos)
    while tokens[pos][0] == "OP" and tokens[pos][1] in ("+", "-"):
        op = tokens[pos][1]
        pos += 1
        right, pos = parse_term(tokens, pos)
        left = (op, left, right)
    return left, pos


def parse_term(tokens, pos):
    """<term> ::= <factor> <term'>"""
    left, pos = parse_factor(tokens, pos)
    while tokens[pos][0] == "OP" and tokens[pos][1] in ("*", "/"):
        op = tokens[pos][1]
        pos += 1
        right, pos = parse_factor(tokens, pos)
        left = (op, left, right)
    return left, pos


def parse_factor(tokens, pos):
    """<factor> ::= ( <expr> ) | number"""
    kind, val = tokens[pos]
    if kind == "NUMBER":
        return ("num", int(val)), pos + 1
    elif kind == "OP" and val == "(":
        node, pos = parse_expr(tokens, pos + 1)
        assert tokens[pos] == ("OP", ")"), "বন্ধনী মিলছে না"
        return node, pos + 1
    else:
        raise SyntaxError(f"অপ্রত্যাশিত টোকেন: {tokens[pos]}")


def evaluate_tree(tree):
    if tree[0] == "num":
        return tree[1]
    op, l, r = tree
    lv, rv = evaluate_tree(l), evaluate_tree(r)
    if op == "+": return lv + rv
    if op == "-": return lv - rv
    if op == "*": return lv * rv
    if op == "/": return lv / rv


expr_text = "2 + 3 * 4"
tokens = tokenize(expr_text)
tree, final_pos = parse_expr(tokens, 0)
result = evaluate_tree(tree)

print(f"এক্সপ্রেশন: {expr_text!r}")
print(f"পার্স ট্রি: {tree}")
print(f"মান নির্ণয়ের ফলাফল: {result}")
assert result == 14, "precedence ভুল হলে ফলাফল 20 হতো, কিন্তু সঠিক উত্তর 14"
print("precedence সঠিক -- আগে গুণ, তারপর যোগ")

print()
print("--- naive left-recursive সংস্করণ কেন কাজ করবে না (bounded demo) ---")

def naive_left_recursive_expr(tokens, pos, depth=0, max_depth=6):
    # <expr> ::= <expr> + <term> | <term>  -- ইনপুট consume করার আগেই নিজেকে কল করে
    if depth >= max_depth:
        return f"(safety-limit-এ থামানো হলো depth={depth} -- বাস্তবে এটি অসীম রিকার্শন হতো)"
    return naive_left_recursive_expr(tokens, pos, depth + 1, max_depth)

print(naive_left_recursive_expr(tokens, 0))