বটম-আপ পার্সিং — শিফট-রিডিউস

# টয় গ্রামার (ইচ্ছাকৃতভাবে দ্ব্যর্থক, শিফট-রিডিউস কনফ্লিক্ট দেখানোর জন্য):
#   S ::= S + S | number

class ShiftReduceParser:
    """স্ট্যাক (../dsa/-এর ক্লাসিক স্ট্রাকচার) ব্যবহার করে -- প্রতিটি ধাপে হয় শিফট,
    নয় রিডিউস। কনফ্লিক্টের সমাধান: বাম-সহযোজন (left-associativity) নিশ্চিত করতে
    S + S . + এ সবসময় রিডিউসকে অগ্রাধিকার দেওয়া হয় (stated convention)।"""

    def __init__(self, tokens):
        self.stack = []
        self.input = list(tokens)
        self.trace = []

    def can_reduce_number(self):
        return bool(self.stack) and self.stack[-1].isdigit()

    def can_reduce_splus_s(self):
        return len(self.stack) >= 3 and self.stack[-3:] == ["S", "+", "S"]

    def step(self):
        # নিয়ম ১: স্ট্যাকের টপে একটি বেয়ার number থাকলে সাথে সাথে রিডিউস (S -> number)
        if self.can_reduce_number():
            self.stack[-1:] = ["S"]
            self.trace.append(("reduce S->number", list(self.stack), list(self.input)))
            return True
        # নিয়ম ২: স্ট্যাকে S + S থাকলে -- এটি একটি শিফট-রিডিউস কনফ্লিক্ট যদি ইনপুটে
        # আরেকটি '+' অপেক্ষা করে থাকে (শিফট করা এবং রিডিউস করা দুটোই ব্যাকরণগতভাবে বৈধ)।
        if self.can_reduce_splus_s():
            if self.input and self.input[0] == "+":
                self.trace.append((
                    "CONFLICT: stack=[S,+,S], lookahead='+' -> রিডিউস বেছে নেওয়া হলো (বাম-সহযোজন কনভেনশন)",
                    list(self.stack), list(self.input)))
            self.stack[-3:] = ["S"]
            self.trace.append(("reduce S->S+S", list(self.stack), list(self.input)))
            return True
        # নিয়ম ৩: নাহলে পরবর্তী ইনপুট টোকেন শিফট করো
        if self.input:
            tok = self.input.pop(0)
            self.stack.append(tok)
            self.trace.append((f"shift '{tok}'", list(self.stack), list(self.input)))
            return True
        return False

    def parse(self):
        while self.step():
            pass
        return self.stack == ["S"] and not self.input


tokens = ["2", "+", "3", "+", "4"]
parser = ShiftReduceParser(tokens)
accepted = parser.parse()

print(f"{'action':<70s} {'stack':<20s} input")
for action, stack, remaining in parser.trace:
    print(f"{action:<70s} {str(stack):<20s} {remaining}")

print(f"\nParse সফল হয়েছে: {accepted}, চূড়ান্ত স্ট্যাক: {parser.stack}")
assert accepted and parser.stack == ["S"]

result = 2 + 3 + 4  # left-associative মান নির্ণয়ের সাথে ক্রস-চেক
print(f"বাম-সহযোজিত মান নির্ণয়: 2+3+4 = {result}")
assert result == 9
print("ALL OK -- শিফট-রিডিউস ট্রেস ও মান দুটোই মিলেছে")