基于自动机理论，能否不直接调用库实现Python re.findall()功能？

当然可以不直接调用re.findall()来实现文本匹配功能——findall()的核心逻辑本身就是基于**有限自动机（FA）**实现的，你完全可以基于自动机理论自己复现类似的功能，甚至可以借助其他库的基础字符串处理函数（比如str[i]取字符、len()取长度这类原生函数）来辅助实现。

先理解re.findall()的核心逻辑 #

re.findall()的工作流程本质是：

1. 将输入的正则表达式解析为非确定有限自动机（NFA）
2. 把NFA转换为确定有限自动机（DFA）（优化匹配效率）
3. 遍历输入文本，用DFA逐个字符匹配，收集所有非重叠的有效匹配子串

简化版findall()实现（基于DFA） #

下面是一个针对简单正则规则（固定字符串、.匹配任意字符）的my_findall()实现，完全不依赖re库：

def my_findall(pattern, text):
    matches = []
    pattern_len = len(pattern)
    text_len = len(text)
    
    if pattern_len == 0:
        return matches
    
    # 遍历文本的每个起始位置，尝试匹配
    for i in range(text_len - pattern_len + 1):
        match = True
        for j in range(pattern_len):
            p_char = pattern[j]
            t_char = text[i + j]
            # 处理通配符.
            if p_char != '.' and p_char != t_char:
                match = False
                break
        if match:
            matches.append(text[i:i+pattern_len])
    
    return matches

扩展支持*通配符的版本（基于NFA思想） #

如果要支持*（匹配零或多个前置字符）这类更复杂的规则，需要引入NFA的状态转移逻辑：

def my_findall_with_star(pattern, text):
    matches = []
    text_len = len(text)
    # 先解析pattern，处理*（这里假设*只跟在单个字符后，如a*、.*）
    parsed = []
    i = 0
    while i < len(pattern):
        if i + 1 < len(pattern) and pattern[i+1] == '*':
            parsed.append( (pattern[i], '*') )
            i += 2
        else:
            parsed.append( (pattern[i], '') )
            i += 1
    
    # 遍历文本起始位置，尝试匹配
    start = 0
    while start <= text_len:
        current_pos = start
        match_end = start
        valid = True
        
        for unit in parsed:
            char, flag = unit
            if flag == '*':
                # 匹配零或多个char（.匹配任意）
                while current_pos < text_len:
                    t_char = text[current_pos]
                    if char == '.' or char == t_char:
                        current_pos += 1
                        match_end = current_pos
                    else:
                        break
            else:
                # 匹配单个字符
                if current_pos >= text_len or (char != '.' and char != text[current_pos]):
                    valid = False
                    break
                current_pos += 1
                match_end = current_pos
        
        if valid and match_end > start:
            matches.append(text[start:match_end])
            start = match_end  # 非重叠匹配，跳过已匹配部分
        else:
            start += 1
    
    return matches

进一步扩展到完整正则 #

如果要支持更复杂的正则规则（分支|、分组()、范围[a-z]等），需要：

1. 实现正则表达式的词法分析（Tokenize）
2. 将Token转换为抽象语法树（AST）
3. 基于AST构建NFA
4. 将NFA转换为DFA（子集构造法）
5. 用DFA遍历文本完成匹配收集

这个流程完全可以自己实现，不需要依赖re库的核心匹配函数，只需要用到Python的原生字符串、列表等基础数据结构函数。

内容的提问来源于stack exchange，提问作者SARTH SHETH