Truth Table Generator

কেন এই প্রজেক্ট

দেখতে ছোট, কিন্তু এটা আসলে একটা mini compiler। আপনি যা যা করবেন — tokenize, parse, AST বানানো, evaluate — Level 5-এ compiler বানানোর সময় হুবহু একই ধাপ, শুধু অনেক বড় স্কেলে।

আর সাথে সাথে propositional logic-টাও হাতে-কলমে পাকা হবে।

লক্ষ্য

এই রকম কিছু চালাতে পারা:

$ ./truthtable "(p AND q) OR NOT r"

 p | q | r | (p AND q) OR NOT r
---+---+---+--------------------
 0 | 0 | 0 |         1
 0 | 0 | 1 |         0
 0 | 1 | 0 |         1
 0 | 1 | 1 |         0
 1 | 0 | 0 |         1
 1 | 0 | 1 |         0
 1 | 1 | 0 |         1
 1 | 1 | 1 |         1

Result: contingency (5/8 rows true)

ধাপে ধাপে

১. Grammar ঠিক করুন

Parser লেখার আগে grammar লিখুন — এটাই সবচেয়ে গুরুত্বপূর্ণ ধাপ, আর সবাই এটা এড়িয়ে যেতে চায়।

expr    := implies
implies := or ( "->" or )*          # right associative
or      := and ( "OR" and )*
and     := not ( "AND" not )*
not     := "NOT" not | atom
atom    := VARIABLE | "(" expr ")" | "0" | "1"

লক্ষ্য করুন grammar-টার গঠনই precedence ঠিক করে দিচ্ছে: and যেহেতু or-এর ভেতরে, তাই AND বেশি শক্তভাবে বাঁধে।

২. Tokenizer

import re

TOKEN = re.compile(r'\s*(->|<->|\(|\)|[A-Za-z_]\w*|[01])')

def tokenize(src):
    pos, out = 0, []
    while pos < len(src):
        m = TOKEN.match(src, pos)
        if not m:
            raise SyntaxError(f'অচেনা অক্ষর position {pos}: {src[pos]!r}')
        out.append(m.group(1))
        pos = m.end()
    return out

৩. Recursive descent parser

প্রতিটা grammar rule = একটা function। এটাই recursive descent-এর পুরো ধারণা।

class Parser:
    def __init__(self, tokens):
        self.t, self.i = tokens, 0

    def peek(self):  return self.t[self.i] if self.i < len(self.t) else None
    def eat(self, x=None):
        tok = self.peek()
        if x and tok != x:
            raise SyntaxError(f'{x!r} আশা করেছিলাম, পেলাম {tok!r}')
        self.i += 1
        return tok

    def expr(self):    return self.implies()

    def implies(self):
        left = self.or_()
        if self.peek() == '->':
            self.eat('->')
            return ('->', left, self.implies())   # right assoc
        return left

    def or_(self):
        node = self.and_()
        while self.peek() and self.peek().upper() == 'OR':
            self.eat()
            node = ('OR', node, self.and_())
        return node

    def and_(self):
        node = self.not_()
        while self.peek() and self.peek().upper() == 'AND':
            self.eat()
            node = ('AND', node, self.not_())
        return node

    def not_(self):
        if self.peek() and self.peek().upper() == 'NOT':
            self.eat()
            return ('NOT', self.not_())
        return self.atom()

    def atom(self):
        tok = self.eat()
        if tok == '(':
            node = self.expr()
            self.eat(')')
            return node
        if tok in ('0', '1'):
            return ('CONST', tok == '1')
        return ('VAR', tok)

৪. Evaluate

def evaluate(node, env):
    kind = node[0]
    if kind == 'VAR':   return env[node[1]]
    if kind == 'CONST': return node[1]
    if kind == 'NOT':   return not evaluate(node[1], env)
    a = evaluate(node[1], env)
    b = evaluate(node[2], env)
    if kind == 'AND': return a and b
    if kind == 'OR':  return a or b
    if kind == '->':  return (not a) or b
    raise ValueError(kind)

৫. সব combination ঘোরান

nটা variable থাকলে 2^n টা row। প্রতিটা row একটা binary সংখ্যা:

from itertools import product

def truth_table(ast, variables):
    for combo in product([False, True], repeat=len(variables)):
        env = dict(zip(variables, combo))
        yield combo, evaluate(ast, env)

নিজেকে চ্যালেঞ্জ করুন

যখন উপরেরটা কাজ করবে, এগুলো যোগ করুন:

1. XOR আর <-> যোগ করুন
2. Equivalence checker — দুইটা expression-এর table একরকম কি না
3. De Morgan verifier — NOT (p AND q) আর NOT p OR NOT q সমান কি না প্রমাণ করান
4. CNF converter — যেকোনো expression-কে conjunctive normal form-এ আনুন (SAT solver-এর প্রথম ধাপ, Level 13-এ কাজে লাগবে)
5. Pretty printer — AST থেকে আবার string বানান, অপ্রয়োজনীয় bracket বাদ দিয়ে

এটা যেখানে গিয়ে মিশবে

এখানে যা শিখলেন	পরে কোথায় লাগবে
Tokenizer	Level 5 — Compiler (lexical analysis)
Recursive descent	Level 5 — Parser
AST	Level 5 — সব compiler-এর মেরুদণ্ড
Precedence handling	Level 5 — Pratt parsing
Boolean evaluation	Level 2 — Digital logic simulator
CNF	Level 13 — SAT solver, formal methods