如何为符合w+w'结构的语言编写recursive-descent parser？

这类w+w'结构的语言可以先构造匹配该语法的LL(1)上下文无关文法，再基于文法实现递归下降逻辑，核心是利用递归调用的调用栈替代你手动维护的栈存储前缀字符。

第一步：定义匹配文法 #

我们可以用如下文法精确描述该语言的所有合法句子：

S → a S a | b S b | c S c | ... | z S z | '+'

这个文法的推导逻辑刚好对应：每一层生成一对相同的小写字母，最内层嵌套的是加号，最终生成的字符串天然满足「前缀+前缀反转」的结构。

第二步：实现递归下降逻辑 #

递归下降的核心是每个非终结符对应一个解析函数，这里只有一个非终结符S，因此只需要实现对应的parse_S函数，逻辑如下：

• 读取当前读头指向的字符：
  • 如果是小写字母：记录当前字符，读头后移一位，递归调用parse_S，等递归返回后，校验当前读头指向的字符是否和之前记录的字符一致，一致则读头后移返回成功，否则返回失败
  • 如果是加号：读头后移一位，直接返回成功
  • 如果是其他字符/已经到输入末尾：直接返回失败
• 解析入口处额外校验：调用parse_S返回成功后，必须确认读头刚好走到输入末尾，避免前缀匹配成功但末尾残留多余字符的情况

代码示例（Python） #

class WReverseParser:
    def __init__(self, input_str: str):
        self.input = input_str
        self.pos = 0  # 记录当前读头位置

    def parse_S(self) -> bool:
        if self.pos >= len(self.input):
            return False
        
        current_char = self.input[self.pos]
        if current_char.islower():
            # 存储当前前缀字符到调用栈，递归处理内层
            matched_char = current_char
            self.pos += 1
            if not self.parse_S():
                return False
            # 递归返回后校验对称位置的反转字符
            if self.pos >= len(self.input) or self.input[self.pos] != matched_char:
                return False
            self.pos += 1
            return True
        elif current_char == '+':
            # 到达中间分界点，返回上层校验反转字符
            self.pos += 1
            return True
        else:
            # 非法字符
            return False

    def parse(self) -> bool:
        # 入口函数：解析完成后必须读完所有输入
        return self.parse_S() and self.pos == len(self.input)

测试用例验证 #

• WReverseParser("racecar+racecar").parse() 返回 True
• WReverseParser("example+elpmaxe").parse() 返回 True
• WReverseParser("a+b").parse() 返回 False
• WReverseParser("ab+baa").parse() 返回 False

这个实现的逻辑和你手动用栈的实现完全等价：递归调用栈天然存储了加号前的所有前缀字符，递归到加号后逐层返回校验，不需要额外手动维护栈结构。如果需要处理超长输入避免栈溢出，可以把递归逻辑转成手动栈，就是你原来的实现方案。

内容的提问来源于stack exchange，提问作者Khanh Nguyen