语法分析：从 Token 到 AST
本文代码去这里下载【手搓编译器】齐天编译器 第一棒 梯云八纵（8颗流水灯） - SDCC, IAR C++ for 51, GCC, VSCode，Linux, MacOS 国芯人工智能技术交流网站 - AI32位8051交流社区
原理解读
什么是语法分析？
语法分析是编译器的第二个阶段，它承上（词法分析）启下（语义分析和抽象语法树生成）。根据源语言的语法规则，判断 Token（记号流，上篇文章介绍过）是否合法。如果合法，则生成 AST（抽象语法树），不合法则报错（成熟的编译器一般会尝试恢复，可以给出所有的错误）。
一个生动的比喻
想象一下你在阅读一篇新闻：
- 词法分析：比如这句话 “紫板老狠了，对拉第三板被冲死了”，会拆解成一堆 Token：“紫板”“老”“很” 等记号。
- 语法分析：有两个关键词——合法和结构。
- 你的大脑会自动将这些单词组织成有意义的短语和句子结构。你会理解句子符合正常语法结构（比如 “老紫板了狠” 就不是合法的结构）。
- 如果正常就生成语法树，体现语言的层次结构。本例中会生成类似下图。
语法分析的核心任务
- 任务：从**“合法”到“有结构”**
- 这个程序在语法上合法吗？它是否符合编程语言所规定的语法规则？比如，if 后面必须跟括号，括号里必须有条件表达式。
- 它的内在结构是什么？如果程序合法，它的逻辑层次是怎样的？哪些语句是 if 的分支？哪些是循环体？哪些是函数定义？
- 语法分析的本质，就是根据一个形式化的语法规则（文法），为输入的 Token 序列构建一棵语法分析树。而 AST，正是这棵语法分析树经过简化、提炼后的核心骨架。
语法分析的两大技术流派
- 自顶向下分析
- 核心思想：从文法的开始符号 <程序> 出发，不断地应用产生式，尝试推导出与输入 Token 序列完全匹配的终结符序列。这是一种预测性的方法。
- 乒乓球比喻：这就像一位教练在赛前制定战术：
- （<程序>）我们的目标是赢下比赛。
- （<函数定义>）要赢下比赛，我们需要先赢下至少三局。
- （<语句>）要赢下一局，我们需要先发球得分。
- （<if 语句>）要发球得分，我们最好用侧旋发球……
- 它从开始符号出发，一步步分解成具体的、可执行的战术动作。
- 技术实现：递归下降
- 齐天编译器的 ParseDelay() 函数，就是递归下降分析法的完美体现。
- 每个非终结符（如 ）对应一个解析函数（如 ParseDelayLoop()）。
Expect(Tok.Delay); // 匹配* "delay"*
Expect(Tok.LParen); // 匹配* "("*
var count = ParseNumber(); // 调用另一个函数解析数字
Expect(Tok.RParen); // 匹配* ")"*
Expect(Tok.Semi); // 匹配* ";"*
return new DelayLoop(count); // 构建 AST 节点
- 优点：直观、易于理解和实现。它就像是你自己手写解析逻辑，完全符合人类的思维习惯。
- 缺点：能力有限。它只能处理一类特定的文法——LL 文法（以后再展开）。
- 自底向上分析
- 核心思想：与自顶向下相反，它从输入的 Token 序列（终结符）出发，不断地寻找可以“归约”的模式，将其替换成对应的非终结符，最终归约到文法的开始符号。这是一种归纳性的方法。
- 乒乓球比喻：
- “看，这是一记漂亮的侧旋发球[delay]。”
- “球过来了，对手回球[ ( ]。”
- “他拉了一板弧圈球[100]。
- “球又回来了……好，这一回合结束了，得分了！[ ) ]
- “这是一个成功的发球抢攻战术（）……”
- 它从每一个具体的动作（每一板球）开始，逐步组合，识别出更高层次的战术意图，最终拼凑出整场比赛的完整图景。
- 技术实现：LR 分析器（挺复杂的，这里先不展开）
- 从语法分析树到抽象语法树
- 无论是自顶向下还是自底向上，语法分析构建的产物是语法分析树。这棵树忠实地记录了应用每一条产生式的细节，因此会包含很多冗余。去掉冗余信息就是抽象语法树（AST）。
- 回到乒乓球比喻：
- 语法分析树：比赛的慢动作逐帧回放。它记录了每一次挥拍、每一次移动、每一次球的旋转，无比详尽，但信息过载。
- 抽象语法树：赛后技术统计和战术分析图。它去掉了无关紧要的细节，只保留了关键信息：发球得分率、相持板数、侧身爆冲的成功率、得分手段分布。是指导未来训练和比赛的数据。
代码分析
- 构造函数
public Parser(List t) => _t = t;
- 解释：这是 Parser 类的构造函数。
- => _t = t;：这是一个表达式体成员的简洁写法，等同于 { _t = t; }。完成初始化。
- 核心辅助方法
private Token Eat() => _t[_i++];
- 解释：Eat 方法是解析器最基本、最重要的辅助方法之一。
- 功能：“吃掉”当前 Token，并将索引 _i 向后移动一位。返回被“吃掉”的那个 Token。
private void Expect(Tok k)
{
if (\_i >= \_t.Count || \_t[\_i].Kind != k)
throw new Exception(\$"Expected {k} at token {\_i}");
\_i++;
}
- 解释：Expect 方法用于判断下一个 Token 的类型。
- 功能：检查当前 Token（_t[_i]）的类型是否为期望的类型 k。
- if (_i >= _t.Count || _t[_i].Kind != k)：首先检查是否已经到达列表末尾，或者当前 Token 的类型（Kind）不是我们期望的 k。
- _i++：如果检查通过（Token 类型符合预期），则调用 Eat 的逻辑，吃掉这个 Token 并前进。
- 与****Eat 的区别：Eat 只是简单地吃掉并返回，不关心类型。Expect 则带有类型检查，用于强制语法规则。
- 通用语句解析器
private AstNode ParseStmt()
{
return \_t[\_i].Kind switch
{
Tok.Delay => ParseDelay(),
Tok.Ident => ParseAssign(),
Tok.While => ParseWhileForever(),
\_ => throw new Exception("Unexpected token"),
};
}
- 解释：ParseStmt 方法用于解析 “非顶级语句”（Statement）。
- 功能：根据当前 Token 的类型，分发给更具体的解析方法。
- 模式匹配：
- Switch 的语法糖 不用写case 和break了，=> 符号前面是case，后面是case内部
- Tok.Delay => ParseDelay()：如果当前 Token 是 Delay 关键字，就调用 ParseDelay() 方法来解析 delay 语句。
- 其余的类似，_ 是default，表示如果都不匹配则抛出异常。
- 统一数值解析器
private T ParseNumber() where T : IBinaryInteger
{
var tok = Eat();
if (tok.Kind != Tok.Num)
throw new Exception(\$"Expected number at token {\_i - 1}");
return tok.Text.StartsWith("0x", StringComparison.OrdinalIgnoreCase)
? T.Parse(tok.Text[2..], NumberStyles.HexNumber, null)
: T.Parse(tok.Text, NumberStyles.None, null);
}
- 解释：泛型方法，用于解析数值。
- 功能：统一处理十进制和十六进制数字字符串，并将其转换为指定的整数类型（如 byte, ushort）。
- where T : IBinaryInteger：
- 泛型T 的意思，就是在调用的时候才决定T的类型
- ：定义了一个泛型类型参数 T。
- where T : IBinaryInteger：这是一个泛型约束。它限制了 T 必须是一个实现了 IBinaryInteger 接口的类型。.NET 中的 byte, ushort, int, long 等都实现了此接口。这保证了 T 类型一定有 Parse 方法，并且是整数。
- 流程：
- var tok = Eat();：吃掉当前的 Token。
- if (tok.Kind != Tok.Num)：检查被吃掉的 Token 类型是否为 Tok.Num。如果不是，则抛出异常。
- tok.Text.StartsWith(...)：检查是否以 "0x" 或 "0X" 开头（不区分大小写）。
- ? ... : ...：这是问号表达式。根据是否以 "0x" 开头，返回十六进制或十进制解析结果。
- 主入口方法
public List Parse()
{
var nodes = new List<AstNode>();
while (\_i < \_t.Count && \_t[\_i].Kind != Tok.Eof)
{
nodes.Add(\_t[\_i].Kind switch
{
Tok.Sfr => ParseSfr(),
Tok.While => ParseWhileForever(),
Tok.Void when \_i + 1 < \_t.Count && \_t[\_i + 1].Kind is Tok.Main => ParseFuncMain(),
\_ => ParseStmt(),
});
}
return nodes;
}
- 解释：这是 Parser 类的公共入口方法，启动整个解析过程。
- 功能：遍历整个 Token 列表，构建一个包含所有顶层声明和语句的 AstNode 列表。
- 流程：
- var nodes = new List();：创建一个空列表，用于存放最终生成的 AST 节点。
- while (_i < _t.Count && _t[_i].Kind != Tok.Eof)：只要还没结束或越界，就继续循环。
- nodes.Add(...)：将解析出的节点添加到 nodes。
- switch 表达式：这是解析的核心逻辑，它决定了如何处理顶层的 Token。
- Tok.Sfr => ParseSfr()：如果是 sfr 关键字，调用 ParseSfr() 解析特殊功能寄存器声明。
- Tok.While 和 Tok.Void 等其他顶级语句类似。
- _ => ParseStmt()：如果以上都不匹配，则默认调用 ParseStmt() 来解析普通语句（如 delay）。这处理了 main 函数内部的语句，或者顶层允许的普通语句。
- return nodes;：循环结束后，返回包含所有 AST 节点的列表。
- 具体语法规则解析方法
ParseSfr -解析sfr****声明
private SfrDecl ParseSfr()
{
Eat(); *// sfr*
var name = Eat().Text; *//* *获取寄存器名*
Expect(Tok.Eq); *//* *判断下一个* *Token* *是等号*
var addr = ParseNumber<byte>(); *//* *解析地址*
Expect(Tok.Semi); *//* *判断下一个* *Token* *是分号*
return new SfrDecl(name, addr); *//* *创建并返回* *AST* *节点*
}
private FuncDecl ParseFuncMain()
{
Eat(); *// void*
Eat(); *// main*
Expect(Tok.LParen); *// (*
Expect(Tok.RParen); *// )*
Expect(Tok.LBrace); *// {*
var body = new List<AstNode>();
while (\_i < \_t.Count && \_t[\_i].Kind != Tok.RBrace && \_t[\_i].Kind != Tok.Eof)
{
body.Add(ParseStmt());
}
Expect(Tok.RBrace); *// }*
return new FuncDecl("main", body);
}
private WhileForever ParseWhileForever()
{
Eat(); *// while*
Expect(Tok.LParen);
var val = ParseNumber<byte>();
if (val != 1) throw new Exception("while condition must be 1");
Expect(Tok.RParen);
Expect(Tok.LBrace);
var body = new List<AstNode>();
while (\_i < \_t.Count && \_t[\_i].Kind != Tok.RBrace && \_t[\_i].Kind != Tok.Eof)
{
body.Add(ParseStmt());
}
Expect(Tok.RBrace);
return new WhileForever(body);
}
- 解释：解析形如 while(1) { ... } 的无限循环。
- 流程：
- Eat();：吃掉 while 关键字。
- Expect(Tok.LParen);：吃掉 (.
- var val = ParseNumber();：解析括号中的表达式。
- if (val != 1) throw new Exception("while condition must be 1");：这是一个语法限制。目前解析器只支持 while(1) 这种形式的无限循环。如果括号里的值不是 1，它会直接报错，正常是需要处理布尔表达式。
- 其余部分一样，收集 {} 内的语句，最后返回一个 WhileForever AST 节点。
ParseAssign - 解析赋值语句
private Assign ParseAssign()
{
var reg = Eat().Text; *//* *获取寄存器名*
Expect(Tok.Eq); *//* *判断下一个* *Token* *是等号*
var val = ParseNumber<byte>(); *//* *解析值*
Expect(Tok.Semi); *//* *判断下一个* *Token* *是分号*
return new Assign(reg, val); *//* *创建并返回* *AST* *节点*
}
-
解释：解析形如 P0 = 0xFE; 的赋值语句。
-
流程：逻辑同上。
ParseDelay -解析delay****语句
private DelayLoop ParseDelay()
{
Eat(); *// delay*
Expect(Tok.LParen);
var count = ParseNumber<ushort>();
Expect(Tok.RParen);
Expect(Tok.Semi);
return new DelayLoop(count);
}
- 解释：解析形如 delay(10); 的延时语句。
-
流程：逻辑同上。
简单点说，像阅读一本书：
- _i 是你的手指，Eat() 是读一个单词并移动手指。
- Expect() 是确认下一个单词是否是你预期的，不是就抛出异常，说明源码有错误。
- 每个 ParseXxx() 方法则是理解一个完整的句子或段落（如一个声明或一个循环），并将其结构化信息（AST 节点）记录下来。
- Parse() 方法读完整本书，返回一个包含了所有章节和段落结构的大纲（AST 列表）。
代码解释得很清晰了，已经包含了各种类型的语句解析，就不带入整个测试案例分析了
|手机版|深圳国芯人工智能有限公司
( 粤ICP备2022108929号-2 )
发表于 
发表于