exp -> factor exp’.inh = factor.val exp’ exp.val = exp’.syn exp’ -> + factor exp’1.inh = exp’.inh + factor.val exp1’ exp’.syn = exp’1.syn exp’ -> ε exp’.syn = exp’.inh factor -> (exp) factor.val = exp.val factor -> number factor.val = number.val (4) Implement the SDT of (3) as a recursive-descent parser.

首先，需要定义一些数据结构来保存语法分析过程中的中间值。我们可以定义一个类`Token`来表示词法单元，其中包含`type`表示类型，`value`表示值，以及`pos`表示其在源代码中的位置。

class Token:
    def __init__(self, type, value, pos):
        self.type = type
        self.value = value
        self.pos = pos

接下来，我们开始实现递归下降解析器，首先是最高级别的非终结符`exp`：

class Parser:
    def __init__(self, lexer):
        self.lexer = lexer
        self.current_token = None

    def parse(self):
        self.advance()
        return self.exp()

    def advance(self):
        self.current_token = self.lexer.get_next_token()

    def exp(self):
        node = self.factor()
        return self.exp_prime(node)

    def exp_prime(self, inh):
        if self.current_token.type == "+":
            self.advance()
            node = self.factor()
            inh += node.value
            return self.exp_prime(inh)
        else:
            return inh

在`exp`中，先解析一个`factor`，然后将其传入`exp_prime`。`exp_prime`中，如果下一个词法单元是加号，则继续解析`factor`，并将其值加到传入的中间值`inh`中，然后递归调用`exp_prime`，将新的中间值传入。如果下一个词法单元不是加号，则直接返回传入的中间值。

接下来是`factor`：

    def factor(self):
        if self.current_token.type == "number":
            node = Node("factor", self.current_token.value)
            self.advance()
            return node
        elif self.current_token.type == "(":
            self.advance()
            node = self.exp()
            if self.current_token.type == ")":
                self.advance()
                return node
            else:
                raise Exception("Expected ')' at position %d." % self.current_token.pos)
        else:
            raise Exception("Invalid token at position %d." % self.current_token.pos)

如果当前词法单元是数字，生成一个值为该数字的节点，并获取下一个词法单元。如果当前词法单元是左括号，则解析一个`exp`，然后判断下一个词法单元是否为右括号，如果是，则获取下一个词法单元并返回解析出来的节点。如果不是，则抛出异常。如果当前词法单元既不是数字也不是左括号，则抛出异常。

最后，我们需要定义一个`Node`类来表示语法树上的节点：

class Node:
    def __init__(self, type, value, children=None):
        self.type = type
        self.value = value
        self.children = children or []

现在，我们可以使用上面的代码来解析一个表达式了：

lexer = Lexer("(1+2+3)")
parser = Parser(lexer)
print(parser.parse())

输出结果为`6`，说明解析成功。

完整代码如下：