基于递归下降分析的赋值语句语法分析器

一、项目背景与目标

在编译器的前端阶段，语法分析（Parsing）位于词法分析之后，负责把线性 Token 流组织成具有层次结构的抽象语法树，为后续语义分析、优化与代码生成奠定基础。本实验聚焦于赋值语句这一最小可用片段，目标是：

1. 输入：一个赋值语句源码文件（如 x:=(-(x))*((5+b)/(c-d))+799）
2. 输出：
   • 解析树（语法树）层次化文本
   • 发现语法错误时给出定位与报错信息
3. 方法：手写递归下降分析器，不依赖 Yacc/Bison/Flex 等工具

完成后你将熟悉：

• 如何从文法到代码一步步映射
• 如何设计语法树并打印友好的结果
• 如何处理一元、二元运算符的歧义
• LL(1) 语法的判定方法及左递归消除技巧

二、相关理论

2.1 赋值语句文法

<赋值语句> ::= <标识符> ':=' <表达式>

<表达式>   ::= ['+' | '-'] <项> { ('+' | '-') <项> }

<项>       ::= <因子> { ('*' | '/') <因子> }

<因子>     ::= <标识符> | <无符号整数> | '(' <表达式> ')'

• 标识符、无符号整数 由词法分析阶段返回
• 所有算术与括号均为终结符

2.2 递归下降分析原理

2.3 LL(1) 条件与左递归消除

LL(1) 需要满足：

1. 无左递归：如 <A> ::= <A> α | β 必须改写
2. FIRST/FOLLOW 不冲突：产生式选择集互不相交
3. 空产生式处理：若能推出空，FIRST(α) 与 FOLLOW(A) 也要互斥

本实验文法天然满足 LL(1)，无需改写；若后续扩展 if/while 等，需要重新检查 FIRST/FOLLOW。

三、系统总体设计

3.1 模块划分

┌───────────────┐
│ 词法分析器    │  ← getsym.h / getsym.cpp
└──────┬────────┘
       │(Token 流)
┌──────▼────────┐
│ 语法分析器    │
│  1. assi_sen  │
│  2. expression│
│  3. item      │
│  4. factor    │
└──────┬────────┘
       │(构造)
┌──────▼────────┐
│  语法树(AST)  │
│  - 打印       │
│  - 后续优化…  │
└───────────────┘

3.2 词法分析接口

string sym;        // 当前 Token 类型，如 "identifier" "number" "+"
string debugId;    // 若 sym == "identifier"，记录标识符文本
string debugNum;   // 若 sym == "number"，记录数字文本

string GETSYM();   // 读入下一个记号并更新以上全局变量

注意：词法分析要能跳过空白、注释等本文仅用到上述全局变量，其余字段可根据需要扩展（行号、列号等）

3.3 语法树数据结构

struct treeNode {
    string element;              // 标签 / 类型
    vector<treeNode*> child;     // 子节点
    explicit treeNode(string e) : element(e) {}
};

• 使用 new 创建节点，内存管理可后续改用智能指针
• 打印函数递归缩进，直观显示层次
• 若将来生成中间代码，可在节点上增加属性字段（类型、值、寄存器位置…）

四、核心代码实现详解

这一节给出关键函数及完整可编译文件，每行代码配详细注释。

4.1 assi_sen——赋值语句

// <赋值语句> ::= <标识符> ':=' <表达式>
void assi_sen(treeNode* tn)
{
    // ① 匹配标识符
    if (sym == "identifier") {
        auto *idTag = new treeNode("标识符");
        idTag->child.push_back(new treeNode(debugId));
        tn->child.push_back(idTag);
        sym = GETSYM();
    } else {
        throw runtime_error("赋值语句缺少左侧标识符");
    }

    // ② 匹配 :=
    if (sym == ":=") {
        tn->child.push_back(new treeNode(":="));
        sym = GETSYM();
    } else {
        throw runtime_error("缺少 := ");
    }

    // ③ 匹配表达式
    auto *exprNode = new treeNode("表达式");
    tn->child.push_back(exprNode);
    expression(exprNode);
}

4.2 expression——表达式

// <表达式> ::= ['+' | '-'] <项> { ('+' | '-') <项> }
void expression(treeNode* tn)
{
    // 一元 + / -
    if (sym == "+" || sym == "-") {
        tn->child.push_back(new treeNode(sym));  // 直接挂符号叶子
        sym = GETSYM();
    }

    // 首项
    auto *firstItem = new treeNode("项");
    tn->child.push_back(firstItem);
    item(firstItem);

    // 后续 (+|-) 项
    while (sym == "+" || sym == "-") {
        auto *opNode = new treeNode("加减运算符");
        opNode->child.push_back(new treeNode(sym));
        tn->child.push_back(opNode);
        sym = GETSYM();

        auto *nextItem = new treeNode("项");
        tn->child.push_back(nextItem);
        item(nextItem);
    }
}

4.3 item——项

// <项> ::= <因子> { ('*' | '/') <因子> }
void item(treeNode* tn)
{
    auto *firstFactor = new treeNode("因子");
    tn->child.push_back(firstFactor);
    factor(firstFactor);

    while (sym == "*" || sym == "/") {
        auto *opNode = new treeNode("乘除运算符");
        opNode->child.push_back(new treeNode(sym));
        tn->child.push_back(opNode);
        sym = GETSYM();

        auto *nextFactor = new treeNode("因子");
        tn->child.push_back(nextFactor);
        factor(nextFactor);
    }
}

4.4 factor——因子

// <因子> ::= <标识符> | <无符号整数> | '(' <表达式> ')'
void factor(treeNode* tn)
{
    if (sym == "identifier" || sym == "number") {
        string tag = sym == "identifier" ? "标识符" : "无符号整数";
        auto *tagNode = new treeNode(tag);
        tagNode->child.push_back(new treeNode(sym == "identifier" ? debugId : debugNum));
        tn->child.push_back(tagNode);
        sym = GETSYM();
    }
    else if (sym == "(") {
        tn->child.push_back(new treeNode("("));
        sym = GETSYM();

        auto *exprNode = new treeNode("表达式");
        tn->child.push_back(exprNode);
        expression(exprNode);

        if (sym == ")") {
            tn->child.push_back(new treeNode(")"));
            sym = GETSYM();
        } else {
            throw runtime_error("括号未闭合");
        }
    }
    else {
        throw runtime_error("非法因子");
    }
}

4.5 完整 main.cpp

仅保留核心流程，实测通过全部测试。

#include "getsym.h"
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

// ---------- treeNode 结构 ----------
struct treeNode {
    string element;
    vector<treeNode*> child;
    explicit treeNode(string e) : element(e) {}
};

// ---------- 函数声明 ----------
void assi_sen(treeNode*);
void expression(treeNode*);
void item(treeNode*);
void factor(treeNode*);

void printTree(treeNode* root, int depth = 0)
{
    if (!root) return;
    for (int i = 0; i < depth; ++i) cout << "|  ";
    cout << ">  " << root->element << '\n';
    for (auto* ch : root->child) printTree(ch, depth + 1);
}

int main()
{
    string file;
    if (!(cin >> file)) return 0;

    ifstream fin(file);
    if (!fin) { cerr << "打开失败\n"; return 0; }
    cin.rdbuf(fin.rdbuf());

    sym = GETSYM();                     // 初始化第一记号
    auto* root = new treeNode("赋值语句");
    try {
        assi_sen(root);
        printTree(root);
    } catch (const exception& e) {
        cerr << "语法错误: " << e.what() << '\n';
    }
    return 0;
}

五、错误处理与调试技巧

六、测试用例与结果分析

6.1 测试集合

6.2 结果截图

由于篇幅限制，此处展示 demo5.txt 输出的一部分（完整内容与评测平台一致）。

>  赋值语句
|  >  标识符
|  |  >  x
|  >  :=
|  >  表达式
|  |  >  项
|  |  |  >  因子
|  |  |  |  >  (
|  |  |  |  >  表达式
|  |  |  |  |  >  -
|  |  |  |  |  >  项
...

解析树层次与符号完全符合预期，说明递归下降流程正确。

七、性能评估与复杂度

• 时间复杂度：LL(1) 递归下降在无回溯情况下遍历一次记号流，故 O(n)
• 空间复杂度：
  • 语法树：节点数 ≈ 终结符 + 非终结符 ≈ O(n)
  • 递归调用栈深度 ≤ 文法嵌套层数，最坏 O(n)，实际远小于 n

对于课程级示例，完全不构成瓶颈；若扩展为上万行源码，仍可胜任。

八、进阶拓展

九、常见问题 FAQ

十、总结与参考资料

本文完成了从文法定义→递归下降原理→代码实现→测试调优的全链路演示。通过该实验，你应当掌握：

1. LL(1) 文法判断与转换
2. 递归下降函数编写规范
3. 一元/二元运算符差异处理
4. AST 设计与可视化打印

建议阅读Aho, Lam, Sethi, Ullman. Compilers – Principles, Techniques & Tools（龙书）Pratt Parsing vs Recursive Descent – Robert Nystrom Crafting Interpreters《现代编译原理（C 语言实现）》郑莉等

只要掌握以上关键点，便可以轻松扩展到完整的表达式求值器，甚至自研一门小语言的编译器前端。祝学习愉快！

深入理解 PL/0 语法分析——从词法到语法树的完美补全

在编译原理的学习中，构建语法分析器是一项极具挑战性的任务。本文围绕“PL/0 语言的递归下降语法分析器构建”这一主题，结合某高校实验平台提供的不完整系统代码，系统介绍了如何进行分析器的功能补全。通过逐步拆解任务目标，我们不仅实现了各类语法规则的还原，还在调试中解决了多组测试用例失败的问题。本博客将从题目解析、实现思路、关键补丁代码、调试策略与注意事项等多个维度展开详细说明，帮助读者全面理解如何从一个“残缺系统”中一步步构建出符合预期输出的语法分析器。

OnePixeltengmmvp