"""
DFA（決定性有限オートマトン）シミュレータ
 
任意の DFA を定義し、入力文字列の受理/拒否を判定する。
"""
 
from typing import Dict, Set, Tuple
 
 
class DFA:
    """決定性有限オートマトン（DFA）の実装"""
 
    def __init__(
        self,
        states: Set[str],
        alphabet: Set[str],
        transition: Dict[Tuple[str, str], str],
        start_state: str,
        accept_states: Set[str],
    ):
        """
        DFA を初期化する。
 
        Args:
            states: 状態の集合 Q
            alphabet: 入力アルファベット Σ
            transition: 遷移関数 δ を辞書で表現
                        {(状態, 入力記号): 次の状態}
            start_state: 初期状態 q₀
            accept_states: 受理状態の集合 F
        """
        self.states = states
        self.alphabet = alphabet
        self.transition = transition
        self.start_state = start_state
        self.accept_states = accept_states
        self._validate()
 
    def _validate(self) -> None:
        """DFA の定義が正しいか検証する。"""
        # 初期状態が状態集合に含まれるか
        if self.start_state not in self.states:
            raise ValueError(
                f"初期状態 '{self.start_state}' が状態集合に含まれていない"
            )
 
        # 受理状態が状態集合の部分集合か
        if not self.accept_states.issubset(self.states):
            invalid = self.accept_states - self.states
            raise ValueError(
                f"受理状態 {invalid} が状態集合に含まれていない"
            )
 
        # 遷移関数が全域関数か（すべての状態×記号の組に対して定義されているか）
        for state in self.states:
            for symbol in self.alphabet:
                if (state, symbol) not in self.transition:
                    raise ValueError(
                        f"遷移 δ({state}, {symbol}) が未定義"
                    )
                next_state = self.transition[(state, symbol)]
                if next_state not in self.states:
                    raise ValueError(
                        f"遷移先 '{next_state}' が状態集合に含まれていない"
                    )
 
    def process(self, input_string: str) -> Tuple[bool, list]:
        """
        入力文字列を処理し、受理/拒否を返す。
 
        Args:
            input_string: 処理する入力文字列
 
        Returns:
            (受理したか, 状態遷移の履歴)
        """
        current = self.start_state
        history = [current]
 
        for symbol in input_string:
            if symbol not in self.alphabet:
                raise ValueError(
                    f"入力記号 '{symbol}' がアルファベットに含まれていない"
                )
            current = self.transition[(current, symbol)]
            history.append(current)
 
        accepted = current in self.accept_states
        return accepted, history
 
    def accepts(self, input_string: str) -> bool:
        """入力文字列を受理するかどうかを返す。"""
        accepted, _ = self.process(input_string)
        return accepted
 
    def trace(self, input_string: str) -> str:
        """入力文字列の処理過程を文字列で返す。"""
        accepted, history = self.process(input_string)
        display_input = input_string if input_string else "ε"
        transitions = []
        for i, state in enumerate(history):
            if i < len(input_string):
                transitions.append(f"{state} →{input_string[i]}→ ")
            else:
                transitions.append(state)
        path = "".join(transitions)
        result = "受理" if accepted else "拒否"
        return f"入力 \"{display_input}\": {path} → {result}"
 
 
# --- 使用例: 偶数個の 'a' を含む文字列を受理する DFA ---
 
dfa_even_a = DFA(
    states={"q0", "q1"},
    alphabet={"a", "b"},
    transition={
        ("q0", "a"): "q1",
        ("q0", "b"): "q0",
        ("q1", "a"): "q0",
        ("q1", "b"): "q1",
    },
    start_state="q0",
    accept_states={"q0"},
)
 
# テスト
test_cases = ["", "a", "b", "aa", "ab", "abba", "aba", "aabba"]
for tc in test_cases:
    print(dfa_even_a.trace(tc))
 
# 出力:
# 入力 "ε": q0 → 受理
# 入力 "a": q0 →a→ q1 → 拒否
# 入力 "b": q0 →b→ q0 → 受理
# 入力 "aa": q0 →a→ q1 →a→ q0 → 受理
# 入力 "ab": q0 →a→ q1 →b→ q1 → 拒否
# 入力 "abba": q0 →a→ q1 →b→ q1 →b→ q1 →a→ q0 → 受理
# 入力 "aba": q0 →a→ q1 →b→ q1 →a→ q0 → 受理
# 入力 "aabba": q0 →a→ q1 →a→ q0 →b→ q0 →b→ q0 →a→ q1 → 拒否

"""
NFA（非決定性有限オートマトン）シミュレータ
 
ε遷移をサポートし、部分集合追跡法で受理判定を行う。
"""
 
from typing import Dict, FrozenSet, Set, Tuple
 
 
class NFA:
    """非決定性有限オートマトン（NFA）の実装"""
 
    def __init__(
        self,
        states: Set[str],
        alphabet: Set[str],
        transition: Dict[Tuple[str, str], Set[str]],
        start_state: str,
        accept_states: Set[str],
    ):
        """
        NFA を初期化する。
 
        Args:
            states: 状態の集合 Q
            alphabet: 入力アルファベット Σ（εを含まない）
            transition: 遷移関数 δ
                        {(状態, 入力記号またはε): 次の状態の集合}
                        ε遷移はキーに ("状態", "") を使用
            start_state: 初期状態 q₀
            accept_states: 受理状態の集合 F
        """
        self.states = states
        self.alphabet = alphabet
        self.transition = transition
        self.start_state = start_state
        self.accept_states = accept_states
 
    def epsilon_closure(self, states: Set[str]) -> Set[str]:
        """
        与えられた状態集合の ε 閉包を計算する。
 
        ε遷移のみで到達可能なすべての状態を含む集合を返す。
        """
        closure = set(states)
        stack = list(states)
 
        while stack:
            state = stack.pop()
            # ε遷移先を取得（ε遷移は空文字列 "" で表現）
            epsilon_targets = self.transition.get((state, ""), set())
            for target in epsilon_targets:
                if target not in closure:
                    closure.add(target)
                    stack.append(target)
 
        return closure
 
    def process(self, input_string: str) -> Tuple[bool, list]:
        """
        入力文字列を処理し、受理/拒否を返す。
 
        同時に到達可能な状態の集合を追跡する方法で実装する。
        これは部分集合追跡（on-the-fly subset construction）に相当する。
 
        Returns:
            (受理したか, 各ステップでの状態集合の履歴)
        """
        # 初期状態のε閉包から開始
        current_states = self.epsilon_closure({self.start_state})
        history = [frozenset(current_states)]
 
        for symbol in input_string:
            next_states = set()
            for state in current_states:
                targets = self.transition.get((state, symbol), set())
                next_states.update(targets)
            # 遷移先のε閉包を計算
            current_states = self.epsilon_closure(next_states)
            history.append(frozenset(current_states))
 
        # 現在の状態集合に受理状態が含まれていれば受理
        accepted = bool(current_states & self.accept_states)
        return accepted, history
 
    def accepts(self, input_string: str) -> bool:
        """入力文字列を受理するかどうかを返す。"""
        accepted, _ = self.process(input_string)
        return accepted
 
    def trace(self, input_string: str) -> str:
        """入力文字列の処理過程を文字列で返す。"""
        accepted, history = self.process(input_string)
        display_input = input_string if input_string else "ε"
        parts = []
        for i, state_set in enumerate(history):
            sorted_states = sorted(state_set)
            states_str = "{" + ", ".join(sorted_states) + "}"
            if i < len(input_string):
                parts.append(f"{states_str} →{input_string[i]}→ ")
            else:
                parts.append(states_str)
        path = "".join(parts)
        result = "受理" if accepted else "拒否"
        return f"入力 \"{display_input}\": {path} → {result}"
 
 
# --- 使用例: "abb" で終わる文字列を受理する NFA ---
 
nfa_ends_abb = NFA(
    states={"q0", "q1", "q2", "q3"},
    alphabet={"a", "b"},
    transition={
        ("q0", "a"): {"q0", "q1"},
        ("q0", "b"): {"q0"},
        ("q1", "b"): {"q2"},
        ("q2", "b"): {"q3"},
    },
    start_state="q0",
    accept_states={"q3"},
)
 
# テスト
test_cases_nfa = ["abb", "aabb", "babb", "ab", "abab", "aabbabb"]
for tc in test_cases_nfa:
    print(nfa_ends_abb.trace(tc))
 
# 出力:
# 入力 "abb": {q0} →a→ {q0, q1} →b→ {q0, q2} →b→ {q0, q3} → 受理
# 入力 "aabb": {q0} →a→ {q0, q1} →a→ {q0, q1} →b→ {q0, q2} →b→ {q0, q3} → 受理
# 入力 "babb": {q0} →b→ {q0} →a→ {q0, q1} →b→ {q0, q2} →b→ {q0, q3} → 受理
# 入力 "ab": {q0} →a→ {q0, q1} →b→ {q0, q2} → 拒否
# 入力 "abab": {q0} →a→ {q0, q1} →b→ {q0, q2} →a→ {q0, q1} →b→ {q0, q2} → 拒否
# 入力 "aabbabb": ... → 受理

"""
NFA から DFA への変換（部分集合構成法）
 
NFA を等価な DFA に変換するアルゴリズムの実装。
"""
 
from typing import Dict, FrozenSet, Set, Tuple
 
 
def nfa_to_dfa(nfa: "NFA") -> "DFA":
    """
    部分集合構成法で NFA を DFA に変換する。
 
    Args:
        nfa: 変換元の NFA
 
    Returns:
        等価な DFA
    """
    # DFA の初期状態 = NFA の初期状態のε閉包
    dfa_start = frozenset(nfa.epsilon_closure({nfa.start_state}))
 
    # DFA の状態集合と遷移関数を構築
    dfa_states: Set[FrozenSet[str]] = set()
    dfa_transition: Dict[Tuple[FrozenSet[str], str], FrozenSet[str]] = {}
    worklist = [dfa_start]
    dfa_states.add(dfa_start)
 
    while worklist:
        current = worklist.pop()
 
        for symbol in nfa.alphabet:
            # 現在の DFA 状態（= NFA 状態の集合）の各 NFA 状態から
            # symbol で遷移可能な NFA 状態を集め、ε閉包を取る
            next_nfa_states = set()
            for nfa_state in current:
                targets = nfa.transition.get((nfa_state, symbol), set())
                next_nfa_states.update(targets)
 
            next_dfa_state = frozenset(
                nfa.epsilon_closure(next_nfa_states)
            )
            dfa_transition[(current, symbol)] = next_dfa_state
 
            if next_dfa_state not in dfa_states:
                dfa_states.add(next_dfa_state)
                worklist.append(next_dfa_state)
 
    # DFA の受理状態 = NFA の受理状態を含む DFA 状態
    dfa_accept = {
        s for s in dfa_states
        if s & nfa.accept_states
    }
 
    # 状態名を読みやすくする
    state_names = {}
    for i, s in enumerate(sorted(dfa_states, key=lambda x: sorted(x))):
        nfa_label = "{" + ",".join(sorted(s)) + "}"
        state_names[s] = f"S{i}_{nfa_label}"
 
    # DFA オブジェクトを構築
    named_states = {state_names[s] for s in dfa_states}
    named_transition = {
        (state_names[s], sym): state_names[t]
        for (s, sym), t in dfa_transition.items()
    }
    named_start = state_names[dfa_start]
    named_accept = {state_names[s] for s in dfa_accept}
 
    return DFA(
        states=named_states,
        alphabet=nfa.alphabet,
        transition=named_transition,
        start_state=named_start,
        accept_states=named_accept,
    )
 
 
# --- 使用例 ---
 
# "abb" で終わる文字列を受理する NFA を DFA に変換
nfa = NFA(
    states={"q0", "q1", "q2", "q3"},
    alphabet={"a", "b"},
    transition={
        ("q0", "a"): {"q0", "q1"},
        ("q0", "b"): {"q0"},
        ("q1", "b"): {"q2"},
        ("q2", "b"): {"q3"},
    },
    start_state="q0",
    accept_states={"q3"},
)
 
dfa = nfa_to_dfa(nfa)
 
print("=== 変換された DFA ===")
print(f"状態: {dfa.states}")
print(f"初期状態: {dfa.start_state}")
print(f"受理状態: {dfa.accept_states}")
print(f"遷移関数:")
for (state, symbol), target in sorted(dfa.transition.items()):
    print(f"  δ({state}, {symbol}) = {target}")
 
# 変換後の DFA でテスト
for tc in ["abb", "aabb", "ab", "babb"]:
    print(dfa.trace(tc))

"""
正規表現エンジン（Thompson 構成法 + NFA シミュレーション）
 
対応する正規表現の構文:
  - 連結:   ab
  - 選択:   a|b
  - 閉包:   a*
  - 1回以上: a+
  - 0回か1回: a?
  - 括弧:   (a|b)*
  - 任意文字: .
 
内部で NFA に変換し、入力文字列を O(n*m) でマッチングする。
"""
 
from dataclasses import dataclass, field
from typing import List, Optional, Set
 
 
@dataclass
class NFAState:
    """NFA の状態ノード"""
    id: int
    is_accept: bool = False
    # ε遷移先
    epsilon: List["NFAState"] = field(default_factory=list)
    # 文字遷移: {文字: [遷移先状態]}
    transitions: dict = field(default_factory=dict)
 
 
class NFAFragment:
    """NFA の断片（開始状態と末尾状態のペア）"""
    def __init__(self, start: NFAState, accept: NFAState):
        self.start = start
        self.accept = accept
 
 
class RegexEngine:
    """Thompson 構成法ベースの正規表現エンジン"""
 
    def __init__(self):
        self._state_counter = 0
 
    def _new_state(self, is_accept: bool = False) -> NFAState:
        """新しい NFA 状態を生成する。"""
        state = NFAState(id=self._state_counter, is_accept=is_accept)
        self._state_counter += 1
        return state
 
    # --- パーサー（正規表現 → 構文木） ---
 
    def _parse(self, pattern: str) -> "NFAFragment":
        """正規表現をパースして NFA を構築する。"""
        self._pos = 0
        self._pattern = pattern
        nfa = self._parse_expr()
        nfa.accept.is_accept = True
        return nfa
 
    def _parse_expr(self) -> NFAFragment:
        """式: term ('|' term)*"""
        left = self._parse_term()
        while self._pos < len(self._pattern) and self._peek() == "|":
            self._consume("|")
            right = self._parse_term()
            left = self._build_union(left, right)
        return left
 
    def _parse_term(self) -> NFAFragment:
        """項: factor*"""
        # 空の項（ε に対応）
        if (self._pos >= len(self._pattern)
                or self._peek() in ("|", ")")):
            s = self._new_state()
            return NFAFragment(s, s)
 
        left = self._parse_factor()
        while (self._pos < len(self._pattern)
               and self._peek() not in ("|", ")")):
            right = self._parse_factor()
            left = self._build_concat(left, right)
        return left
 
    def _parse_factor(self) -> NFAFragment:
        """因子: atom ('*' | '+' | '?')?"""
        atom = self._parse_atom()
        if self._pos < len(self._pattern):
            if self._peek() == "*":
                self._consume("*")
                return self._build_star(atom)
            elif self._peek() == "+":
                self._consume("+")
                return self._build_plus(atom)
            elif self._peek() == "?":
                self._consume("?")
                return self._build_optional(atom)
        return atom
 
    def _parse_atom(self) -> NFAFragment:
        """原子: '(' expr ')' | '.' | 文字"""
        if self._peek() == "(":
            self._consume("(")
            nfa = self._parse_expr()
            self._consume(")")
            return nfa
        elif self._peek() == ".":
            self._consume(".")
            return self._build_dot()
        else:
            ch = self._peek()
            self._pos += 1
            return self._build_char(ch)
 
    def _peek(self) -> str:
        return self._pattern[self._pos]
 
    def _consume(self, expected: str) -> None:
        if self._pos < len(self._pattern) and self._peek() == expected:
            self._pos += 1
        else:
            raise ValueError(
                f"Expected '{expected}' at position {self._pos}"
            )
 
    # --- NFA 構築（Thompson 構成法） ---
 
    def _build_char(self, ch: str) -> NFAFragment:
        """文字リテラルに対応する NFA 断片を構築する。"""
        start = self._new_state()
        accept = self._new_state()
        start.transitions[ch] = [accept]
        return NFAFragment(start, accept)
 
    def _build_dot(self) -> NFAFragment:
        """任意文字 '.' に対応する NFA 断片を構築する。"""
        start = self._new_state()
        accept = self._new_state()
        # 特殊キー "ANY" で任意文字マッチを表現
        start.transitions["ANY"] = [accept]
        return NFAFragment(start, accept)
 
    def _build_concat(
        self, left: NFAFragment, right: NFAFragment
    ) -> NFAFragment:
        """連結: left の受理状態から right の開始状態へε遷移。"""
        left.accept.epsilon.append(right.start)
        left.accept.is_accept = False
        return NFAFragment(left.start, right.accept)
 
    def _build_union(
        self, left: NFAFragment, right: NFAFragment
    ) -> NFAFragment:
        """選択 (|): 新しい開始状態から左右へε遷移。"""
        start = self._new_state()
        accept = self._new_state()
        start.epsilon.extend([left.start, right.start])
        left.accept.epsilon.append(accept)
        left.accept.is_accept = False
        right.accept.epsilon.append(accept)
        right.accept.is_accept = False
        return NFAFragment(start, accept)
 
    def _build_star(self, inner: NFAFragment) -> NFAFragment:
        """クリーネ閉包 (*): 0回以上の繰り返し。"""
        start = self._new_state()
        accept = self._new_state()
        start.epsilon.extend([inner.start, accept])
        inner.accept.epsilon.extend([inner.start, accept])
        inner.accept.is_accept = False
        return NFAFragment(start, accept)
 
    def _build_plus(self, inner: NFAFragment) -> NFAFragment:
        """1回以上の繰り返し (+): inner · inner*"""
        start = self._new_state()
        accept = self._new_state()
        start.epsilon.append(inner.start)
        inner.accept.epsilon.extend([inner.start, accept])
        inner.accept.is_accept = False
        return NFAFragment(start, accept)
 
    def _build_optional(self, inner: NFAFragment) -> NFAFragment:
        """0回か1回 (?): inner | ε"""
        start = self._new_state()
        accept = self._new_state()
        start.epsilon.extend([inner.start, accept])
        inner.accept.epsilon.append(accept)
        inner.accept.is_accept = False
        return NFAFragment(start, accept)
 
    # --- NFA シミュレーション ---
 
    def _epsilon_closure(self, states: Set[NFAState]) -> Set[NFAState]:
        """ε閉包を計算する。"""
        closure = set(states)
        stack = list(states)
        while stack:
            state = stack.pop()
            for next_state in state.epsilon:
                if next_state not in closure:
                    closure.add(next_state)
                    stack.append(next_state)
        return closure
 
    def _step(
        self, states: Set[NFAState], ch: str
    ) -> Set[NFAState]:
        """1文字読んで遷移し、ε閉包を返す。"""
        next_states = set()
        for state in states:
            # 通常の文字遷移
            if ch in state.transitions:
                next_states.update(state.transitions[ch])
            # 任意文字マッチ
            if "ANY" in state.transitions:
                next_states.update(state.transitions["ANY"])
        return self._epsilon_closure(next_states)
 
    def match(self, pattern: str, text: str) -> bool:
        """
        正規表現パターンがテキスト全体にマッチするか判定する。
 
        Args:
            pattern: 正規表現パターン
            text: マッチ対象の文字列
 
        Returns:
            マッチすれば True
        """
        self._state_counter = 0
        nfa = self._parse(pattern)
 
        current = self._epsilon_closure({nfa.start})
        for ch in text:
            current = self._step(current, ch)
            if not current:
                return False
 
        return any(s.is_accept for s in current)
 
    def search(self, pattern: str, text: str) -> Optional[str]:
        """
        テキスト中で最初にマッチする部分文字列を返す。
 
        Args:
            pattern: 正規表現パターン
            text: 検索対象の文字列
 
        Returns:
            最初にマッチした部分文字列、なければ None
        """
        self._state_counter = 0
        nfa = self._parse(pattern)
 
        for start_pos in range(len(text)):
            current = self._epsilon_closure({nfa.start})
            # 開始位置で即座に受理される場合（ε を受理する NFA）
            if any(s.is_accept for s in current):
                return ""
            for end_pos in range(start_pos, len(text)):
                current = self._step(current, text[end_pos])
                if not current:
                    break
                if any(s.is_accept for s in current):
                    return text[start_pos:end_pos + 1]
 
        return None
 
 
# --- 使用例 ---
 
engine = RegexEngine()
 
# 基本的なマッチング
test_patterns = [
    ("abc",      "abc",    True),
    ("a|b",      "a",      True),
    ("a|b",      "b",      True),
    ("a|b",      "c",      False),
    ("a*",       "",       True),
    ("a*",       "aaa",    True),
    ("a+",       "",       False),
    ("a+",       "aaa",    True),
    ("ab?c",     "ac",     True),
    ("ab?c",     "abc",    True),
    ("(a|b)*abb", "aabb",  True),
    ("(a|b)*abb", "ab",    False),
    (".+",       "hello",  True),
]
 
print("=== 正規表現エンジンのテスト ===")
for pattern, text, expected in test_patterns:
    result = engine.match(pattern, text)
    status = "OK" if result == expected else "NG"
    print(f"  [{status}] match('{pattern}', '{text}') = {result}")
 
# 検索
print("\n=== 部分文字列検索 ===")
found = engine.search("(a|b)+c", "xxxabcyyy")
print(f"  search('(a|b)+c', 'xxxabcyyy') = '{found}'")
 
# 出力:
# === 正規表現エンジンのテスト ===
#   [OK] match('abc', 'abc') = True
#   [OK] match('a|b', 'a') = True
#   [OK] match('a|b', 'b') = True
#   [OK] match('a|b', 'c') = False
#   [OK] match('a*', '') = True
#   [OK] match('a*', 'aaa') = True
#   [OK] match('a+', '') = False
#   [OK] match('a+', 'aaa') = True
#   [OK] match('ab?c', 'ac') = True
#   [OK] match('ab?c', 'abc') = True
#   [OK] match('(a|b)*abb', 'aabb') = True
#   [OK] match('(a|b)*abb', 'ab') = False
#   [OK] match('.+', 'hello') = True
#
# === 部分文字列検索 ===
#   search('(a|b)+c', 'xxxabcyyy') = 'abc'

"""
DFA ベースの字句解析器（レクサー / トークナイザー）
 
簡易プログラミング言語のソースコードをトークン列に分解する。
各トークンの認識は DFA の原理に基づいている。
 
対応するトークン:
  - キーワード: if, else, while, return, int, float
  - 識別子: [a-zA-Z_][a-zA-Z0-9_]*
  - 整数リテラル: [0-9]+
  - 浮動小数点リテラル: [0-9]+\.[0-9]+
  - 演算子: +, -, *, /, =, ==, !=, <, >, <=, >=
  - 区切り文字: (, ), {, }, ;, ,
  - 空白・コメントは読み飛ばす
"""
 
from dataclasses import dataclass
from enum import Enum, auto
from typing import List, Optional
 
 
class TokenType(Enum):
    """トークンの種類"""
    # キーワード
    KW_IF = auto()
    KW_ELSE = auto()
    KW_WHILE = auto()
    KW_RETURN = auto()
    KW_INT = auto()
    KW_FLOAT = auto()
    # リテラル
    INT_LITERAL = auto()
    FLOAT_LITERAL = auto()
    # 識別子
    IDENTIFIER = auto()
    # 演算子
    PLUS = auto()
    MINUS = auto()
    STAR = auto()
    SLASH = auto()
    ASSIGN = auto()
    EQ = auto()
    NEQ = auto()
    LT = auto()
    GT = auto()
    LE = auto()
    GE = auto()
    # 区切り文字
    LPAREN = auto()
    RPAREN = auto()
    LBRACE = auto()
    RBRACE = auto()
    SEMICOLON = auto()
    COMMA = auto()
    # 特殊
    EOF = auto()
    ERROR = auto()
 
 
@dataclass
class Token:
    """トークン"""
    type: TokenType
    value: str
    line: int
    column: int
 
    def __repr__(self) -> str:
        return f"Token({self.type.name}, '{self.value}', L{self.line}:C{self.column})"
 
 
# キーワードテーブル
KEYWORDS = {
    "if": TokenType.KW_IF,
    "else": TokenType.KW_ELSE,
    "while": TokenType.KW_WHILE,
    "return": TokenType.KW_RETURN,
    "int": TokenType.KW_INT,
    "float": TokenType.KW_FLOAT,
}
 
# 単一文字トークン
SINGLE_CHAR_TOKENS = {
    "+": TokenType.PLUS,
    "-": TokenType.MINUS,
    "*": TokenType.STAR,
    "/": TokenType.SLASH,
    "(": TokenType.LPAREN,
    ")": TokenType.RPAREN,
    "{": TokenType.LBRACE,
    "}": TokenType.RBRACE,
    ";": TokenType.SEMICOLON,
    ",": TokenType.COMMA,
}
 
 
class Lexer:
    """DFA ベースの字句解析器"""
 
    def __init__(self, source: str):
        self.source = source
        self.pos = 0
        self.line = 1
        self.column = 1
 
    def _peek(self) -> Optional[str]:
        """現在位置の文字を返す（消費しない）。"""
        if self.pos < len(self.source):
            return self.source[self.pos]
        return None
 
    def _advance(self) -> str:
        """現在位置の文字を消費して返す。"""
        ch = self.source[self.pos]
        self.pos += 1
        if ch == "\n":
            self.line += 1
            self.column = 1
        else:
            self.column += 1
        return ch
 
    def _skip_whitespace_and_comments(self) -> None:
        """空白とコメントを読み飛ばす。"""
        while self.pos < len(self.source):
            ch = self._peek()
            if ch in (" ", "\t", "\n", "\r"):
                self._advance()
            elif ch == "/" and self.pos + 1 < len(self.source):
                if self.source[self.pos + 1] == "/":
                    # 行コメント
                    while self.pos < len(self.source) and self._peek() != "\n":
                        self._advance()
                else:
                    break
            else:
                break
 
    def _read_number(self) -> Token:
        """
        数値リテラルを読み取る DFA:
 
        状態遷移:
          START --[0-9]--> INTEGER --[0-9]--> INTEGER
                                   --[.]--> DOT
          DOT --[0-9]--> FLOAT --[0-9]--> FLOAT
 
        受理状態: INTEGER, FLOAT
        """
        start_col = self.column
        value = ""
 
        # 状態: INTEGER（整数部分）
        while self.pos < len(self.source) and self._peek().isdigit():
            value += self._advance()
 
        # 小数点チェック
        if (self.pos < len(self.source)
                and self._peek() == "."
                and self.pos + 1 < len(self.source)
                and self.source[self.pos + 1].isdigit()):
            value += self._advance()  # '.'
            # 状態: FLOAT（小数部分）
            while self.pos < len(self.source) and self._peek().isdigit():
                value += self._advance()
            return Token(TokenType.FLOAT_LITERAL, value, self.line, start_col)
 
        return Token(TokenType.INT_LITERAL, value, self.line, start_col)
 
    def _read_identifier_or_keyword(self) -> Token:
        """
        識別子/キーワードを読み取る DFA:
 
        状態遷移:
          START --[a-zA-Z_]--> IDENT --[a-zA-Z0-9_]--> IDENT
 
        受理状態: IDENT
        受理後にキーワードテーブルを参照して種類を判定
        """
        start_col = self.column
        value = ""
 
        while (self.pos < len(self.source)
               and (self._peek().isalnum() or self._peek() == "_")):
            value += self._advance()
 
        token_type = KEYWORDS.get(value, TokenType.IDENTIFIER)
        return Token(token_type, value, self.line, start_col)
 
    def next_token(self) -> Token:
        """次のトークンを返す。"""
        self._skip_whitespace_and_comments()
 
        if self.pos >= len(self.source):
            return Token(TokenType.EOF, "", self.line, self.column)
 
        start_col = self.column
        ch = self._peek()
 
        # 数値リテラル
        if ch.isdigit():
            return self._read_number()
 
        # 識別子またはキーワード
        if ch.isalpha() or ch == "_":
            return self._read_identifier_or_keyword()
 
        # 2文字演算子の処理
        if ch == "=" and self.pos + 1 < len(self.source) and self.source[self.pos + 1] == "=":
            self._advance()
            self._advance()
            return Token(TokenType.EQ, "==", self.line, start_col)
        if ch == "!" and self.pos + 1 < len(self.source) and self.source[self.pos + 1] == "=":
            self._advance()
            self._advance()
            return Token(TokenType.NEQ, "!=", self.line, start_col)
        if ch == "<" and self.pos + 1 < len(self.source) and self.source[self.pos + 1] == "=":
            self._advance()
            self._advance()
            return Token(TokenType.LE, "<=", self.line, start_col)
        if ch == ">" and self.pos + 1 < len(self.source) and self.source[self.pos + 1] == "=":
            self._advance()
            self._advance()
            return Token(TokenType.GE, ">=", self.line, start_col)
 
        # 単一文字演算子
        if ch == "=":
            self._advance()
            return Token(TokenType.ASSIGN, "=", self.line, start_col)
        if ch == "<":
            self._advance()
            return Token(TokenType.LT, "<", self.line, start_col)
        if ch == ">":
            self._advance()
            return Token(TokenType.GT, ">", self.line, start_col)
 
        # 単一文字トークン
        if ch in SINGLE_CHAR_TOKENS:
            self._advance()
            return Token(SINGLE_CHAR_TOKENS[ch], ch, self.line, start_col)
 
        # 不正な文字
        self._advance()
        return Token(TokenType.ERROR, ch, self.line, start_col)
 
    def tokenize(self) -> List[Token]:
        """ソースコード全体をトークン列に変換する。"""
        tokens = []
        while True:
            token = self.next_token()
            tokens.append(token)
            if token.type == TokenType.EOF:
                break
        return tokens
 
 
# --- 使用例 ---
 
source_code = """
// フィボナッチ数列
int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}
"""
 
lexer = Lexer(source_code)
tokens = lexer.tokenize()
 
print("=== 字句解析結果 ===")
for token in tokens:
    print(f"  {token}")
 
# 出力:
# === 字句解析結果 ===
#   Token(KW_INT, 'int', L3:C1)
#   Token(IDENTIFIER, 'fib', L3:C5)
#   Token(LPAREN, '(', L3:C8)
#   Token(KW_INT, 'int', L3:C9)
#   Token(IDENTIFIER, 'n', L3:C13)
#   Token(RPAREN, ')', L3:C14)
#   Token(LBRACE, '{', L3:C16)
#   Token(KW_IF, 'if', L4:C5)
#   Token(LPAREN, '(', L4:C8)
#   Token(IDENTIFIER, 'n', L4:C9)
#   Token(LE, '<=', L4:C11)
#   Token(INT_LITERAL, '1', L4:C14)
#   Token(RPAREN, ')', L4:C15)
#   Token(LBRACE, '{', L4:C17)
#   Token(KW_RETURN, 'return', L5:C9)
#   Token(IDENTIFIER, 'n', L5:C16)
#   Token(SEMICOLON, ';', L5:C17)
#   Token(RBRACE, '}', L6:C5)
#   Token(KW_RETURN, 'return', L7:C5)
#   Token(IDENTIFIER, 'fib', L7:C12)
#   Token(LPAREN, '(', L7:C15)
#   Token(IDENTIFIER, 'n', L7:C16)
#   Token(MINUS, '-', L7:C18)
#   Token(INT_LITERAL, '1', L7:C20)
#   Token(RPAREN, ')', L7:C21)
#   Token(PLUS, '+', L7:C23)
#   Token(IDENTIFIER, 'fib', L7:C25)
#   Token(LPAREN, '(', L7:C28)
#   Token(IDENTIFIER, 'n', L7:C29)
#   Token(MINUS, '-', L7:C31)
#   Token(INT_LITERAL, '2', L7:C33)
#   Token(RPAREN, ')', L7:C34)
#   Token(SEMICOLON, ';', L7:C35)
#   Token(RBRACE, '}', L8:C1)
#   Token(EOF, '', L9:C1)

"""演習1の解答: "01" を含む文字列を受理する DFA"""
 
# 上記の DFA クラスを使用
dfa_contains_01 = DFA(
    states={"q0", "q1", "q2"},
    alphabet={"0", "1"},
    transition={
        ("q0", "0"): "q1",
        ("q0", "1"): "q0",
        ("q1", "0"): "q1",
        ("q1", "1"): "q2",
        ("q2", "0"): "q2",
        ("q2", "1"): "q2",
    },
    start_state="q0",
    accept_states={"q2"},
)
 
# テスト
accept_cases = ["01", "001", "010", "1101", "0100"]
reject_cases = ["", "0", "1", "00", "11", "10", "110"]
 
print("=== 受理されるべきケース ===")
for tc in accept_cases:
    result = dfa_contains_01.accepts(tc)
    status = "OK" if result else "NG"
    print(f"  [{status}] \"{tc}\": {result}")
 
print("\n=== 拒否されるべきケース ===")
for tc in reject_cases:
    result = dfa_contains_01.accepts(tc)
    status = "OK" if not result else "NG"
    print(f"  [{status}] \"{tc}\": {result}")

"""
演習3の解答: CYK アルゴリズムの実装
 
CNF（チョムスキー標準形）の文法に対して、
与えられた文字列が文法から生成可能かどうかを判定する。
"""
 
from typing import Dict, List, Set, Tuple
 
 
def cyk_parse(
    grammar: Dict[str, List[Tuple[str, ...]]],
    start_symbol: str,
    input_string: str,
) -> bool:
    """
    CYK アルゴリズムで入力文字列の所属判定を行う。
 
    Args:
        grammar: CNF 文法の生成規則
                 {変数: [(右辺のタプル), ...]}
                 例: {"S": [("A", "B"), ("a",)]}
        start_symbol: 開始記号
        input_string: 判定する文字列
 
    Returns:
        input_string が文法から生成可能なら True
    """
    n = len(input_string)
    if n == 0:
        # 空文字列の場合、S → epsilon が存在するか確認
        return ("",) in grammar.get(start_symbol, [])
 
    # CYK テーブル: table[i][j] = w[i..j] を生成できる変数の集合
    # i, j は 0-indexed
    table: List[List[Set[str]]] = [
        [set() for _ in range(n)] for _ in range(n)
    ]
 
    # 基底ケース: 長さ1の部分文字列
    for i in range(n):
        for var, productions in grammar.items():
            for prod in productions:
                if len(prod) == 1 and prod[0] == input_string[i]:
                    table[i][i].add(var)
 
    # 帰納ステップ: 長さ 2 以上の部分文字列
    for length in range(2, n + 1):       # 部分文字列の長さ
        for i in range(n - length + 1):  # 開始位置
            j = i + length - 1           # 終了位置
            for k in range(i, j):        # 分割点
                for var, productions in grammar.items():
                    for prod in productions:
                        if (len(prod) == 2
                                and prod[0] in table[i][k]
                                and prod[1] in table[k + 1][j]):
                            table[i][j].add(var)
 
    # デバッグ出力: CYK テーブルの表示
    print(f"\n=== CYK テーブル（入力: \"{input_string}\"） ===")
    print(f"    ", end="")
    for j in range(n):
        print(f"  {input_string[j]}(j={j})  ", end="")
    print()
    for i in range(n):
        print(f"  i={i}", end="")
        for j in range(n):
            if j < i:
                print("          ", end="")
            else:
                cell = table[i][j]
                cell_str = "{" + ",".join(sorted(cell)) + "}" if cell else "empty"
                print(f"  {cell_str:8s}", end="")
        print()
 
    return start_symbol in table[0][n - 1]
 
 
# --- 使用例 ---
 
# CNF 文法の定義
grammar = {
    "S": [("A", "B"), ("B", "C")],
    "A": [("B", "A"), ("a",)],
    "B": [("C", "C"), ("b",)],
    "C": [("A", "B"), ("a",)],
}
 
# テスト
test_strings = ["aabb", "ab", "aab", "b", "aaaa"]
for s in test_strings:
    result = cyk_parse(grammar, "S", s)
    print(f"  \"{s}\" in L(G)? -> {result}\n")