如何针对给定算术表达式CFG构建输入串的自底向上分析树？

给定上下文无关文法（CFG） #

E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id

输入串：id * ( id + id )

自底向上分析（移进-归约）分步过程 #

自底向上分析的核心是移进输入符号到栈中，当栈顶匹配某产生式的右部时，将其归约为左部非终结符，重复此过程直到栈中只剩起始符号E且输入为空。以下是针对目标输入串的完整步骤：

1. 初始状态：栈为空，输入串：id * ( id + id )

   • 移进第一个id，栈：[id]，剩余输入：* ( id + id )
   • 匹配产生式F -> id，归约为F，栈变为[F]；此时树的叶子id的父节点为F。

2. 栈：[F]，剩余输入：* ( id + id )

   • 匹配产生式T -> F，归约为T，栈变为[T]；F的父节点为T。

3. 栈：[T]，剩余输入：* ( id + id )

   • 移进*，栈：[T, *]，剩余输入：( id + id )。

4. 栈：[T, *]，剩余输入：( id + id )

   • 移进(，栈：[T, *, (]，剩余输入：id + id )。

5. 栈：[T, *, (]，剩余输入：id + id )

   • 移进id，栈：[T, *, (, id]，剩余输入：+ id )
   • 匹配F -> id，归约为F，栈变为[T, *, (, F]；新增叶子id的父节点为F。

6. 栈：[T, *, (, F]，剩余输入：+ id )

   • 匹配T -> F，归约为T，栈变为[T, *, (, T]；F的父节点为T。

7. 栈：[T, *, (, T]，剩余输入：+ id )

   • 移进+，栈：[T, *, (, T, +]，剩余输入：id )。

8. 栈：[T, *, (, T, +]，剩余输入：id )

   • 移进id，栈：[T, *, (, T, +, id]，剩余输入：)
   • 匹配F -> id，归约为F，栈变为[T, *, (, T, +, F]；新增叶子id的父节点为F。

9. 栈：[T, *, (, T, +, F]，剩余输入：)

   • 匹配T -> F，归约为T，栈变为[T, *, (, T, +, T]；F的父节点为T。

10. 栈：[T, *, (, T, +, T]，剩余输入：)

    • 先将栈中T归约为E（匹配E -> T），栈变为[T, *, (, E, +, T]
    • 匹配E -> E + T，归约为E，栈变为[T, *, (, E]；此时E的子节点为E（原T）、+、T。

11. 栈：[T, *, (, E]，剩余输入：)

    • 移进)，栈：[T, *, (, E, )]，剩余输入为空
    • 匹配F -> ( E )，归约为F，栈变为[T, *, F]；F的子节点为(、E、)。

12. 栈：[T, *, F]，剩余输入为空

    • 匹配T -> T * F，归约为T，栈变为[T]；T的子节点为T、*、F。

13. 栈：[T]，剩余输入为空

    • 匹配E -> T，归约为E，栈变为[E]；分析完成，最终E为根节点。

最终分析树结构（文本形式） #

E
        |
        T
      / | \
     T  *  F
     |     |
     F    ( E )
     |       |
    id       E
           / | \
          E  +  T
          |     |
          T     F
          |     |
          F    id
          |
         id

代码示例（Python） #

以下代码模拟移进-归约过程，同时构建并打印分析树：

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

    def __repr__(self, level=0):
        ret = "\t" * level + repr(self.value) + "\n"
        for child in self.children:
            ret += child.__repr__(level + 1)
        return ret

# 输入token列表
tokens = ["id", "*", "(", "id", "+", "id", ")"]
stack = []

for token in tokens:
    # 移进当前token，创建叶子节点
    stack.append(Node(token))
    
    # 循环尝试归约，直到无法归约为止
    while True:
        reduced = False
        # 匹配 F -> id
        if len(stack) >= 1 and stack[-1].value == "id":
            child = stack.pop()
            stack.append(Node("F", [child]))
            reduced = True
        # 匹配 T -> F
        elif len(stack) >= 1 and stack[-1].value == "F":
            child = stack.pop()
            stack.append(Node("T", [child]))
            reduced = True
        # 匹配 E -> T
        elif len(stack) >= 1 and stack[-1].value == "T":
            child = stack.pop()
            stack.append(Node("E", [child]))
            reduced = True
        # 匹配 E -> E + T
        elif len(stack) >= 3 and stack[-3].value == "E" and stack[-2].value == "+" and stack[-1].value == "T":
            t = stack.pop()
            plus = stack.pop()
            e = stack.pop()
            stack.append(Node("E", [e, plus, t]))
            reduced = True
        # 匹配 T -> T * F
        elif len(stack) >= 3 and stack[-3].value == "T" and stack[-2].value == "*" and stack[-1].value == "F":
            f = stack.pop()
            star = stack.pop()
            t = stack.pop()
            stack.append(Node("T", [t, star, f]))
            reduced = True
        # 匹配 F -> ( E )
        elif len(stack) >= 3 and stack[-3].value == "(" and stack[-2].value == "E" and stack[-1].value == ")":
            close = stack.pop()
            e = stack.pop()
            open_p = stack.pop()
            stack.append(Node("F", [open_p, e, close]))
            reduced = True
        else:
            break

# 输出最终分析树
print("构建完成的分析树：")
print(stack[0])

内容的提问来源于stack exchange，提问作者Orion Blaze