【编译原理】手工打造语法分析器，编译原理，手工打造语法分析器详解

摘要：本文将介绍编译原理中的语法分析器手工打造过程。通过深入了解编程语言的结构和规则，手动实现语法分析器，对源代码进行解析并生成相应的中间代码。这一过程涉及对语言文法的细致研究和对解析技术的熟练运用，以确保程序的正确性和效率。手工打造语法分析器是编译器开发中的重要环节，为后续的语义分析和优化奠定基础。

递归下降算法

我们继续以“int age = 45”为例，深入探讨递归下降算法，对于给定的语法规则：

intDeclaration : Int Identifier ('=' additiveExpression)?;

我们可以将其翻译为以下伪代码：

MatchIntDeclare(){

MatchToken(Int); // 匹配 Int 关键字

MatchIdentifier(); // 匹配标识符

if (MatchToken(equal)) { // 如果存在等号，则匹配表达式

MatchExpression();

}

输出的抽象语法树（AST）大致如下：

Programm Calculator

IntDeclaration age

AssignmentExp =

IntLiteral 45

这个过程被称为递归下降算法，从顶层开始不断向下生成节点，其中可能包含递归调用的部分。

上下文无关文法

对于更复杂的算术表达式，如“2+3*5”或“2*3+5”，我们可以使用上下文无关文法来表述，这种文法可以处理具有不同结合性和优先级的表达式。

我们可以使用以下规则来表示乘法表达式和加法表达式：

additiveExpression

: multiplicativeExpression

| additiveExpression Plus multiplicativeExpression

;

multiplicativeExpression

: IntLiteral

| multiplicativeExpression Star IntLiteral

;

生成的AST能够清晰地表示计算顺序，便于后续求值。

左递归问题及解决方案

在处理上下文无关文法时，左递归问题可能会出现，导致无限循环，我们可以通过改变语法规则或算法逻辑来解决这个问题，一种常见的方法是改为右递归或使用扩展巴科斯范式（EBNF）。

执行代码

一旦我们将语句转换为AST，就可以通过遍历这个树来进行计算求值，以“2+3+4”为例，遍历的伪代码非常简单明了：

evaluate(node) {

if node.type == TYPE.ADD:

left_res = evaluate(node.getChild(0))

right_res = evaluate(node.getChild(1))

return left_res + right_res

else if node.type == TYPE.INT:

return node.val

小结

至此，我们已经实现了一个简单的计算器，能够完成词法分析、生成语法树和计算求值，在此基础上，您可以进一步扩展，增加更多的运算符、实现变量赋值等功能，逐步扩充为一个完整的脚本语言解释器。