Python解释器开发中的解析器死循环问题及解决方案

1. 解释器基础：词法分析与解析

构建一个简单的语言解释器通常涉及至少两个主要阶段：词法分析（Lexing/Scanning）和语法分析（Parsing）。

• 词法分析器（Lexer）：负责将源代码字符串分解成一系列有意义的“令牌”（Tokens）。例如，PRINT "HELLO" 会被分解为 PRINT 令牌和 STRING:"HELLO" 令牌。
• 语法分析器（Parser）：接收词法分析器生成的令牌流，并根据语言的语法规则构建一个抽象语法树（AST）或直接执行相应的操作。

在提供的Python解释器代码中，lex 函数充当词法分析器，而 parse 函数则负责语法分析和执行。

1.1 词法分析器 (lex 函数)

lex 函数负责读取文件内容，并将其转换为一系列令牌。它识别以下几种令牌类型：

• PRINT：关键字 "PRINT" 或 "print"。
• STRING:：以双引号包围的字符串，例如 STRING:"HELLO WORLD"。
• NUM:：数字序列，例如 NUM:566755664645454。
• EXPR:：包含数字和加号的表达式，例如 EXPR:5+6。

示例代码片段：

立即学习“Python免费学习笔记（深入）”；

# ... (部分lex函数代码)
def lex(filecontents):
    tok = ""
    state = 0 # 0 for normal, 1 for string
    string = ""
    expr = ""
    isexpr = 0 # 0 for NUM, 1 for EXPR
    tokens = []
    for char in filecontents:
        tok += char
        if tok == " ":
            if state == 0:
                tok = ""
            else:
                tok = " "
        elif tok == "\n" or tok =="":
            if expr != "" and isexpr == 1:
                tokens.append("EXPR:" + expr)
                expr = ""
            elif expr != "" and isexpr == 0:
                tokens.append("NUM:" + expr)
                expr = ""
            tok = ""
            isexpr = 0 # Reset for next line
        elif tok.lower() == "print": # Handles both "PRINT" and "print"
            tokens.append("PRINT")
            tok = ""
        elif tok in "0123456789":
            expr += tok
            tok = ""
        elif tok == "+":
            isexpr = 1
            expr += tok
            tok = ""
        elif tok == "\"":
            if state == 0:
                state = 1
            elif state == 1:
                tokens.append("STRING:" + string + "\"")
                string = ""
                state = 0
                tok = ""
        elif state == 1: # Inside a string
            string += tok
            tok = ""
    return tokens
# ...

词法分析输出示例 (对于输入 test.lang)：

PRINT "HELLO WORLD"
print "string"
566755664645454
5 + 6
print 55
print 5 + 8

经过 lex 函数处理后，tokens 列表可能包含：

['PRINT', 'STRING:HELLO WORLD"', 'PRINT', 'STRING:string"', 'NUM:566755664645454', 'EXPR:5+6', 'PRINT', 'NUM:55', 'PRINT', 'EXPR:5+8']

2. 解析器死循环问题分析

原始的 parse 函数设计存在一个关键缺陷，导致程序在处理某些令牌时陷入无限循环。

2.1 原始 parse 函数代码

def parse(toks):
    i = 0
    while(i < len(toks)):
        # 只有当令牌序列匹配 "PRINT STRING" 或 "PRINT NUM" 或 "PRINT EXPR" 时，i 才会递增
        if toks[i] + " " + toks[i+1][0:6] == "PRINT STRING" or \
           toks[i] + " " + toks[i+1][0:3] == "PRINT NUM" or \
           toks[i] + " " + toks[i+1][0:4] == "PRINT EXPR":
            if toks[i+1][0:6] == "STRING":
                print(toks[i+1][7:])
            elif toks[i+1][0:3] == "NUM":
                print(toks[i+1][4:])
            elif toks[i+1][0:4] == "EXPR":
                print(toks[i+1][5:])
            i+= 2 # 只有在这里，索引 i 才递增

2.2 问题根源：条件式索引递增

从上述代码可以看出，i += 2 这条语句被嵌套在一个复杂的 if 条件内部。这意味着只有当当前的令牌 toks[i] 是 "PRINT" 并且其后的令牌 toks[i+1] 是 "STRING"、"NUM" 或 "EXPR" 时，索引 i 才会向前推进两个位置。

考虑以下令牌流：

Kuwebs企业网站管理系统3.1.5 UTF8

酷纬企业网站管理系统Kuwebs是酷纬信息开发的为企业网站提供解决方案而开发的营销型网站系统。在线留言模块、常见问题模块、友情链接模块。前台采用DIV+CSS，遵循SEO标准。 1.支持中文、英文两种版本，后台可以在不同的环境下编辑中英文。 3.程序和界面分离，提供通用的PHP标准语法字段供前台调用，可以为不同的页面设置不同的风格。 5.支持google地图生成、自定义标题、自定义关键词、自定义描

下载

['PRINT', 'STRING:HELLO WORLD"', 'PRINT', 'STRING:string"', 'NUM:566755664645454', 'EXPR:5+6', ...]

1. i=0: toks[0] 是 PRINT，toks[1] 是 STRING:HELLO WORLD". 条件为真，打印 "HELLO WORLD", i 变为 2。
2. i=2: toks[2] 是 PRINT，toks[3] 是 STRING:string". 条件为真，打印 "string", i 变为 4。
3. i=4: toks[4] 是 NUM:566755664645454。此时，toks[i] (NUM:566...) 不等于 "PRINT"，因此整个 if 条件为假。
4. 由于 if 条件为假，i += 2 不会被执行。这意味着 i 的值仍然是 4。
5. while(i

结果就是程序会无限地循环在处理 NUM:566755664645454 这个令牌上，因为 i 永远不会递增，导致 while 循环条件 i

3. 解决方案：确保索引始终递增

解决这个问题的核心在于确保解析器在每次循环迭代中，无论是否成功匹配某个语法规则，都必须推进其令牌流的索引。对于未处理的令牌，解析器应该至少跳过它们，或者更好地是，提供相应的处理逻辑或报错。

3.1 修正后的 parse 函数

为了使解析器更健壮，我们不仅要修复死循环，还要使其能够处理非 PRINT 语句的独立数字和表达式。

def parse(toks):
    i = 0
    while i < len(toks):
        # 尝试匹配 "PRINT" 语句
        if i + 1 < len(toks) and toks[i] == "PRINT":
            # 确保有足够的令牌进行检查，防止 IndexError
            next_token = toks[i+1]
            if next_token.startswith("STRING:"):
                print(next_token[7:]) # 打印字符串内容
                i += 2 # 消耗 "PRINT" 和字符串令牌
            elif next_token.startswith("NUM:"):
                # 实际解释器会计算表达式，这里简化为打印数值
                print(next_token[4:]) # 打印数字内容
                i += 2 # 消耗 "PRINT" 和数字令牌
            elif next_token.startswith("EXPR:"):
                # 实际解释器会计算表达式，这里简化为打印表达式内容
                print(next_token[5:]) # 打印表达式内容
                i += 2 # 消耗 "PRINT" 和表达式令牌
            else:
                # PRINT 后面跟着一个未知或不支持的令牌
                print(f"语法错误：'PRINT' 后遇到未知令牌 '{next_token}'")
                i += 2 # 即使出错也前进，避免死循环
        # 处理独立的数字令牌
        elif toks[i].startswith("NUM:"):
            print(toks[i][4:]) # 打印数字内容
            i += 1 # 消耗一个数字令牌
        # 处理独立的表达式令牌
        elif toks[i].startswith("EXPR:"):
            print(toks[i][5:]) # 打印表达式内容
            i += 1 # 消耗一个表达式令牌
        # 处理独立的字符串令牌 (如果需要)
        elif toks[i].startswith("STRING:"):
            print(toks[i][7:])
            i += 1
        else:
            # 遇到无法识别的令牌类型，打印错误并前进
            print(f"语法错误：无法识别的令牌 '{toks[i]}'")
            i += 1 # 消耗未知令牌，防止死循环

代码说明：

1. 分层处理： 首先尝试匹配多令牌的 PRINT 语句。如果匹配成功，则根据其后的令牌类型进行处理并递增 i。
2. 独立令牌处理： 如果不是 PRINT 语句，则检查当前的令牌是否是独立的 NUM 或 EXPR。如果是，则进行相应处理并递增 i by 1。
3. 错误处理与前进： else 块捕获所有未能被上述规则匹配的令牌。在这种情况下，解析器会打印一个错误消息，但最重要的是，它会执行 i += 1 来消耗这个未知令牌，从而确保循环能够继续进行，避免死循环。

3.2 运行修正后的解释器

使用修正后的 parse 函数，当输入文件 test.lang 运行时，输出将是：

"HELLO WORLD"
"string"
566755664645454
5+6
55
5+8

所有语句都得到了正确的处理和打印，不再出现 KeyboardInterrupt。

4. 注意事项与总结

在开发解释器或编译器时，以下几点至关重要：

1. 确保循环索引递增： 这是避免无限循环的基本原则。在任何迭代循环中，必须确保循环变量（如 i）在每一步都向着终止条件前进。
2. 全面覆盖令牌类型： 解析器应该能够处理词法分析器生成的所有令牌类型。对于未预期的令牌，应有明确的错误处理机制，而不是简单地忽略它们，这可能导致未定义的行为或死循环。
3. 错误报告机制： 当解析器遇到语法错误时，应提供清晰的错误消息，指出错误类型和位置，这对于调试和用户体验至关重要。
4. 清晰的语法规则： 明确定义语言的语法规则有助于设计一个高效且无错误的解析器。例如，区分表达式是独立语句还是作为 PRINT 的参数。

通过遵循这些原则，可以构建出更健壮、更可靠的语言解释器。