递归下降语法分析实验实现

现在前面：

由于本人对编译技术并无兴趣（我觉得我这种数字动漫方向的根本没必要做实验😅），所以只完成最基本的 Icoding 上的内容，而全部非终结符对应函数的实现，我实在无心也无力，==完整代码在最后==

特别鸣谢：

本文是我通过学习分析前人大佬的代码而得出的 —— 实名吃香菜（大佬我给你跪了）

特别感谢，没有他的代码，根本不知道 Icoding 的检查规则，再次吐槽 Icoding 题目描述能不能多打几个字，一些描述模模糊糊的，还有一些细节也不清楚，整体结构也模糊，狗屎！！！

” rdlab2.h “：

注意这里面声明了一个全局变量 cur_token

#include <stddef.h>
#include "node_type.h"

enum yytokentype {
	num_INT = 258,
	num_FLOAT = 259,

	Y_ID = 260,

	Y_INT = 261,
	Y_VOID = 262,
	Y_CONST = 263,
	Y_IF = 264,
	Y_ELSE = 265,
	Y_WHILE = 266,
	Y_BREAK = 267,
	Y_CONTINUE = 268,
	Y_RETURN = 269,

	Y_ADD = 270,
	Y_SUB = 271,
	Y_MUL = 272,
	Y_DIV = 273,
	Y_MODULO = 274,
	Y_LESS = 275,
	Y_LESSEQ = 276,
	Y_GREAT = 277,
	Y_GREATEQ = 278,
	Y_NOTEQ = 279,
	Y_EQ = 280,
	Y_NOT = 281,
	Y_AND = 282,
	Y_OR = 283,
	Y_ASSIGN = 284,

	Y_LPAR = 285,
	Y_RPAR = 286,
	Y_LBRACKET = 287,
	Y_RBRACKET = 288,
	Y_LSQUARE = 289,
	Y_RSQUARE = 290,
	Y_COMMA = 291,
	Y_SEMICOLON = 292,

	Y_FLOAT = 293
};

typedef struct _TokenType{
	enum yytokentype token;
	union {
		int		ivalue;
		float   fvalue;
		char*	svalue;
	}attr;
}TokenType;


void set_cur_tok_index(int ind); // 没用到
int get_cur_tok_index(); // 没用到
TokenType advance();
extern TokenType cur_token;


///Non-terminator，不知道在哪用，没有用到
enum Non_terminator
{
    。。。
};

typedef struct _ast ast;
typedef struct _ast *past;

struct _ast{
	int ivalue;
	float fvalue;
	char* svalue;
	node_type nodeType;
	past left;
	past right;
	past if_cond;
	past next;
};


// 库提供的函数
past rd_block();
past rd_array_subscripts();

past newAstNode();
past newID(char* value); // 没用到
past newInt(int value);

// 要完成的函数
past rd_call_paras();
past rd_relexp();
past rd_stmt();

1 节点设计

Icoding给出的节点是这样的：

其实不合理，该节点的如果是操作符，只能保存到 ivalue 中，可 ivalue 一看就是保存整型数值的，但改不了其数据结构，只能将就用

typedef struct _ast ast;
typedef struct _ast *past;
struct _ast{
	int ivalue; // 这三个储存节点的值
	float fvalue;
	char* svalue;
	node_type nodeType; // 节点类型
	past left;
	past right;
	past if_cond; // if_cond 仅限于 if 语句中的条件
	past next; // 并列关系
};

只有 if 语句节点才有“三只脚”

并列关系必须由 next 指针串联

并列关系通常出现在参数列表：在函数或方法的定义中，参数通常是并列的，它们的顺序与声明顺序相同。例如，以下是一个函数定义的AST，其中参数 param1 和 param2 是并列的：

param1 和 param2 是函数参数的并列节点

[FunctionDeclaration]
├── [Parameter param1]
└── [Parameter param2]

2 NodeType

这些node_type是不同类型的节点类型（声明、表达式、语句等）枚举值，简要描述：

Expression Kinds（表达式类型）:
- CALL_EXPR: 函数调用表达式
- BLOCK_EXPR: 块表达式
- INTEGER_LITERAL: 整数文字
- FLOATING_LITERAL: 浮点数文字
- IMAGINARY_LITERAL: 虚数文字
- STRING_LITERAL: 字符串文字
- CHARACTER_LITERAL: 字符文字
- UNARY_OPERATOR: 一元操作符表达式
- ARRAY_SUBSCRIPT_EXPR: 数组下标表达式
- BINARY_OPERATOR: 二元操作符表达式
Statement Kinds（语句类型）:
- COMPOUND_STMT: 复合语句（块）
- IF_STMT: if 语句
- WHILE_STMT: while 语句
- FOR_STMT: for 语句
- CONTINUE_STMT: continue 语句
- BREAK_STMT: break 语句
- RETURN_STMT: return 语句
- NULL_STMT: 空语句
- DECL_STMT: 声明语句

其实很多都没用到，所以下面我的代码不太严谨，感觉 Icoding 检查了像没检查一样

3 具体实现

以”new”开头的函数（例如 newWhileStmt、newIfStmt、newCompoundStmt、newBinaryOper、newParaDecl、newBreakStmt、newContinueStmt 和 newReturnStmt）是用于创建新的AST节点的函数。这些函数用于构造AST的不同节点类型，并返回一个新的**AST节点**。这些函数通常接受一些参数，用于指定节点的属性和子节点。
以 “rd” 开头的函数（例如 rd_add_exp、rd_mul_exp、rd_unary_exp、rd_primary_exp、rd_l_or_exp、rd_l_and_exp 和 rd_eq_exp）是用于构建抽象语法树（AST）的函数。它们执行递归下降语法分析，根据文法规则逐步构造AST的不同部分。这些函数通常返回**AST的一部分**，如表达式、运算符等。

3.1 “new” 创建函数

3.1.1 二元操作节点

// 创建一个新的二元操作节点
past newBinaryOper(int oper, past left, past right) {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为二进制操作符
        node->nodeType = BINARY_OPERATOR;
        // 存储操作符
        node->ivalue = oper;
        // 存储左右操作数
        node->left = left;
        node->right = right;
    }
    return node;
}

下图中，方括号 [] 表示节点，节点包含不同的值，如 5 和 3 是整数节点，+ 和 * 是二元操作节点

       [*]
      /   \
    [+]    [2]
   /   \
  [5]  [3]

3.1.2 声明引用表达式节点

// 创建一个新的声明引用表达式节点
past newDeclRefExp(char *name, past left, past right) {  
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为声明引用表达式
        node->nodeType = DECL_REF_EXPR;
        // 存储名称
        node->svalue = name;
        // 存储左右子节点
        node->left = left;
        node->right = right;
    }
    return node;
}

例如：

x = 42;

在这个片段中，我们有一个变量声明 int x，然后将其初始化为 42，我们可以使用 newDeclRefExp 函数来表示变量 x 的引用

past left = newDeclRefExp("x", NULL, NULL);

这行代码创建了一个声明引用表达式节点，表示变量 x 的引用。"x" 是标识符的名称，NULL 被用作左右子节点，因为在这个上下文中，没有子节点。这个节点可以用以下方式表示：

这个节点表示了对变量 x 的引用

[x]

接下来，如果我们希望创建一个表示整个初始化语句的赋值表达式，我们可以使用上面的 newBinaryOper 函数：

past assignment_expr = newBinaryOper(Y_ASSIGN, identifier_ref, newInt(42));

这里，我们将标识符引用节点作为左操作数，将整数常量节点（newInt(42)）作为右操作数，并将操作符 Y_ASSIGN 传递给 oper 参数。这将创建一个表示赋值操作的二元操作节点

       [=]
      /   \
    [x]   [42]

3.1.3 while 语句节点

// 创建一个新的 while 语句节点
past newWhileStmt(past condition, past body) {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 while 语句
        node->nodeType = WHILE_STMT;
        // 存储条件表达式和循环体
        node->left = condition;
        node->right = body;
    }
    return node;
}

示例，表示一个简单的 while 循环：

while (Condition) {
    Body
}

对应的语法树结构如下所示：

     [WHILE_STMT]
       /       \
 [Condition]    [Body]

3.1.4 if 语句节点

// 创建一个新的 if 语句节点
past newIfStmt(past condition, past ifBody, past elseBody) {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 if 语句
        node->nodeType = IF_STMT;
        // 存储条件表达式、if 分支和else分支
        node->if_cond = condition;
        node->left = ifBody;
        node->right = elseBody;
    }
    return node;
}

以下是一个简单的 if 语句的示例：

if (Condition) {
    IF_BODY
} else {
    ELSE_BODY
}

对应的抽象语法树结构：

           [IF_STMT]
        /      |      \
[Condition] [IF_BODY] [ELSE_BODY]

3.1.5 break 语句节点

// 创建一个新的 break 语句节点
past newBreakStmt() {   
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 break 语句
        node->nodeType = BREAK_STMT;
    }
    return node;
}

“break” 语句通常用于从循环中跳出，例如 for 或 while 循环；这个节点没有左子节点或右子节点，因为它不包含表达式或操作数

[BREAK_STMT]

3.1.6 continue 语句节点

// 创建一个新的 continue 语句节点
past newContinueStmt() {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 continue 语句
        node->nodeType = CONTINUE_STMT;
    }
    return node;
}

同理，它不包含表达式或操作数，没有左子节点或右子节点

[CONTINUE_STMT]

3.1.7 return 语句节点

// 创建一个新的 return 语句节点
past newReturnStmt(past left, past right) {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 return 语句
        node->nodeType = RETURN_STMT;
        // 存储返回表达式
        node->left = left;
        node->right = right;
    }
    return node;
}

如果函数不返回任何值（即 return;），那么左子节点将为空，右子节点也将为空

在实际使用中，right 通常会为空，因为一个 return 语句只能返回一个值

所以，一般情况下，你可以只传递一个值给 newReturnStmt 函数，将其作为 left 参数，而将 right 参数设置为 NULL。

示例：

past returnValue = astAddExp(); // 假设 astAddExp() 返回一个表达式节点
past returnStatement = newReturnStmt(returnValue, NULL);

在这个示例中，returnValue 是你要返回的值的表达式节点，而 returnStatement 就是一个包含了这个返回值的 return 语句节点。

 [RETURN_STMT]
      |
 [ReturnValue]

3.2 “rd” 解析函数

3.2.1 基本表达式

PrimaryExp: Y_LPAR Exp Y_RPAR
          | LVal
          | num_INT
          | num_FLOAT
          
LVal: Y_ID
    | Y_ID ArraySubscripts

LVal
- 简单标识符：x
- 带有数组下标的标识符：arr[2]
42：一个整数常量
(x + y)：一个用括号括起来的表达式

// 解析基本表达式
past rd_primary_exp() {
    past node = NULL; // 初始化节点为NULL

    if (cur_token.token == Y_LPAR) { // (表达式)
        advance(); 
        node = rd_add_exp(); // 见下面的rd_add_exp()函数
        if (cur_token.token != Y_RPAR) { // 缺右括号
            return NULL; 
        }
        advance(); 
    } else if (cur_token.token == Y_ID) { // LVal
        char *s = cur_token.attr.svalue;
        past Arr = rd_array_subscripts();
        node = newDeclRefExp(s, Arr, NULL);
        advance();
    } else if (cur_token.token == num_INT) { 
        node = newInt(cur_token.attr.ivalue); // 构造整数节点
        advance(); 
    } else if (cur_token.token == num_FLOAT) { 
        node = newAstNode(); // 构造浮点数节点
        advance(); 
        node->fvalue = cur_token.attr.fvalue;
    }

    return node; // 返回表达式树
}

最后其得到的会是：

跟加法表达式一样的（见下面）
一个单节点：标识符 / 数组 / 整数 / 浮点数

3.2.2 一元表达式

UnaryExp: PrimaryExp
        | Y_ID Y_LPAR Y_RPAR
        | Y_ID Y_LPAR CallParams Y_RPAR
        | Y_ADD UnaryExp
        | Y_SUB UnaryExp
        | Y_NOT UnaryExp                    

PrimaryExp
-x：表示对变量 x 取负
!flag：表示对变量 flag 进行逻辑非操作
++i：表示对变量 i 进行递增操作
func(a, b)：一个函数调用表达式

// 解析一元表达式
past rd_unary_exp() {
    past node = rd_primary_exp(); // 获取基本表达式

    while (node == NULL) { // 当基本表达式为空时
        if (cur_token.token == Y_ID) { // 当当前符号为标识符时
            char *s = cur_token.attr.svalue;
            advance();
            if (cur_token.token == Y_LPAR) {
                advance();
				past params = NULL;
                if (cur_token.token != Y_RPAR) {
                    params = rd_call_paras(); // 解析函数调用参数
                }
                node = newDeclRefExp(s, params, NULL); // 构造声明引用表达式
            }
        } else if (cur_token.token == Y_ADD || cur_token.token == Y_SUB || cur_token.token == Y_NOT) { // 当当前符号为加号、减号或取反符号
            int oper = cur_token.token; // 记录运算符
            advance(); 
            past operand = rd_unary_exp(); // 获取一元表达式
            node = newBinaryOper(oper, NULL, operand); // 构造二元操作表达式
        } else {
            return NULL; // 无法匹配其他情况，返回空
        }
    }

    return node; // 返回表达式树
}

例1：

-5

初始时，cur_token.token 指向符号 -

第一次循环：

当前不是基本表达式，进入循环
当前符号不是 Y_ID，进入 else if
记录运算符为减号 (Y_SUB)
调用 advance() 向前移动，现在当前标记是数字 5
再次调用 rd_unary_exp() 函数，这次是基本表达式，会获取一元表达式，得到节点表示数字 5
使用 newBinaryOper() 构建一个二元操作表达式，操作符为减号，左子树为空，右子树为数字 5

结果为：

  [-]
   |
  [5]

例2：

func(a, b)

最后得到：

       [DECL_REF_EXPR]
            /   \
       "func"   [a] —— [b]                           

3.2.3 加法表达式

AddExp: MulExp
      | AddExp Y_ADD MulExp
      | AddExp Y_SUB MulExp

// 解析加法表达式
past rd_add_exp() {
    past left = rd_mul_exp(); // 获取乘法表达式

    while (cur_token.token == Y_ADD || cur_token.token == Y_SUB) { // 当当前符号为加号或减号时
        int oper = cur_token.token; // 记录运算符
        advance(); // 向前移动到下一个符号
        past right = rd_mul_exp(); // 获取乘法表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

通过一个具体的例子来解释这个函数，假设有如下的加法表达式：

2 + 3 - 1

初始时，cur_token.token 会指向数字 2 的标记，调用 rd_mul_exp() 函数来获取乘法表达式，得到节点表示数字 2

第一次循环：

当前标记是 Y_ADD，符合循环条件，所以进入循环
记录运算符为加号 Y_ADD
调用 advance() 向前移动，现在当前标记是数字 3
调用 rd_mul_exp() 函数来获取乘法表达式，得到节点表示数字 3
使用 newBinaryOper() 构建一个二元操作表达式，操作符为加号，左子树为数字 2，右子树为数字 3

结果为：

   [+]
  /   \
[2]   [3]

第二次循环：

当前标记是 Y_SUB，符合循环条件，所以进入循环
记录运算符为减号 Y_SUB
调用 advance() 向前移动，现在当前标记是数字 1
调用 rd_mul_exp() 函数来获取乘法表达式，得到节点表示数字 1
使用 newBinaryOper() 构建一个二元操作表达式，操作符为减号，左子树为之前构建的表达式，右子树为数字 1

结果为：

      [-]
     /   \
   [+]    [1]
  /   \
[2]   [3]

3.2.4 乘法表达式

MulExp: UnaryExp
      | MulExp Y_MUL UnaryExp
      | MulExp Y_DIV UnaryExp
      | MulExp Y_MODULO UnaryExp

// 函数定义：解析乘法表达式
past rd_mul_exp() {
    past left = rd_unary_exp(); // 获取一元表达式

    while (cur_token.token == Y_MUL || cur_token.token == Y_DIV || cur_token.token == Y_MODULO) { // 当当前符号为乘号、除号或取模符号时
        int oper = cur_token.token; // 记录运算符
        advance(); // 向前移动到下一个符号
        past right = rd_unary_exp(); // 获取一元表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

跟上面的同理，例：

4 * 3 / 2

最终得到：

      [/]
     /   \
   [*]   [2]
  /   \
[4]   [3]

3.2.5 相等表达式

EqExp: RelExp
     | RelExp Y_EQ EqExp
     | RelExp Y_NOTEQ EqExp

// 解析相等表达式
past rd_eq_exp() {
    past left = rd_relexp(); // 获取关系表达式

    while (cur_token.token == Y_EQ || cur_token.token == Y_NOTEQ) { // 当当前符号为等号或不等号时
        int oper = cur_token.token; // 记录运算符
        advance(); 
        past right = rd_relexp(); // 获取关系表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

跟之前的加法表达式相似，例：

3 == 4 != 5

     [!=]
    /    \
 [==]    [5]
 /  \
[3] [4]

3.2.6 关系表达式

RelExp: AddExp
      | AddExp Y_LESS RelExp
      | AddExp Y_GREAT RelExp
      | AddExp Y_LESSEQ RelExp
      | AddExp Y_GREATEQ RelExp

// 解析关系表达式
past rd_relexp() {
    past left = rd_add_exp(); // 获取加法表达式

    while (true) {
        switch (cur_token.token) {
            case Y_LESS:
            case Y_LESSEQ:
            case Y_GREAT:
            case Y_GREATEQ: { // 当当前符号为小于、小于等于、大于或大于等于时
                int oper = cur_token.token; // 记录运算符
                advance(); 
                past right = rd_add_exp(); // 获取加法表达式
                left = newBinaryOper(oper, left, right); // 构造二元操作表达式
                break;
            }
            default:
                return left; // 返回表达式树
        }
    }
}

其实跟加法表达式也是同理的，一个 while 循环递归构建，例：

3 < 4 <= 5

     [<=]
    /    \
  [<]    [5]
 /   \
[3]  [4]

3.2.7 逻辑与表达式

LAndExp: EqExp
       | EqExp Y_AND LAndExp

// 解析逻辑与表达式
past rd_l_and_exp() {
    past left = rd_eq_exp(); // 获取相等表达式

    while (cur_token.token == Y_AND) { // 当当前符号为逻辑与符号时
        int oper = cur_token.token; // 记录运算符
        advance(); 
        past right = rd_eq_exp(); // 获取相等表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

跟之前的加法表达式相似，例：

true && false && true

        [&&]
       /    \
    [&&]    [TRUE]
   /    \
[TRUE] [FALSE]

3.2.8 逻辑或表达式

LOrExp: LAndExp
      | LAndExp Y_OR LOrExp

// 解析逻辑或表达式
past rd_l_or_exp() {
    past left = rd_l_and_exp(); // 获取逻辑与表达式

    while (cur_token.token == Y_OR) { // 当当前符号为逻辑或符号时
        int oper = cur_token.token; // 记录运算符
        advance(); 
        past right = rd_l_and_exp(); // 获取逻辑与表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

同理，例：

a || b || c

        [&&]
       /    \
    [&&]    [c]
   /    \
 [a]    [b]

3.2.9 函数调用参数

CallParams: Exp
          | Exp Y_COMMA CallParams

// 解析函数调用参数
past rd_call_paras() {
    past head = rd_add_exp(); // 获取加法表达式
    past current = head;

    while (cur_token.token) {
        if (cur_token.token != Y_COMMA) { // 当当前符号不为逗号时
            break;
        }
        advance(); 
        past new_node = rd_add_exp(); // 获取加法表达式
        current->next = new_node;
        current = current->next;
    }

    return head; // 返回参数链表头节点
}

CallParams 节点就是一个链表，通过 next 指针表示并列关系，例如：

func(a, b, c)

得到：

 head
  |
 [a] -> [b] -> [c]

3.2.10 语句

Stmt: LVal Y_ASSIGN Exp Y_SEMICOLON
    | Y_SEMICOLON
    | Exp Y_SEMICOLON
    | Block
    | Y_WHILE Y_LPAR LOrExp Y_RPAR Stmt
    | Y_IF Y_LPAR LOrExp Y_RPAR Stmt
    | Y_IF Y_LPAR LOrExp Y_RPAR Stmt Y_ELSE Stmt
    | Y_BREAK Y_SEMICOLON
    | Y_CONTINUE Y_SEMICOLON
    | Y_RETURN Exp Y_SEMICOLON
    | Y_RETURN Y_SEMICOLON

// 解析语句
past rd_stmt() {
    switch (cur_token.token) {
        case Y_ID: { // LVal 开头 ———— 赋值语句
            char *s = cur_token.attr.svalue; // 处理LVal（等号左边）
            past Arr = rd_array_subscripts();
            past lval = newDeclRefExp(s, Arr, NULL);
            advance(); 
            if (cur_token.token != Y_ASSIGN) { // 语法错误
                return NULL; 
            }
            advance(); 
            past left = rd_add_exp(); // 获取加法表达式（等号右边）
            if (cur_token.token != Y_SEMICOLON) { // 语法错误
                return NULL; 
            }
            advance(); 
            return newBinaryOper(Y_ASSIGN, lval, left); // 返回赋值表达式
        }
        case Y_SEMICOLON: { // 分号开头 ———— 空语句
            advance(); 
            return NULL; 
        }
        case Y_LBRACKET: { // 左大括号开头 ———— 代码块
            advance(); 
            past block = rd_block(); // 获取块语句
            if (cur_token.token != Y_RBRACKET) { // 语法错误
                return NULL; 
            }
            advance(); 
            return block; // 返回块语句
        }
        case Y_WHILE: { // WHILE语句
            advance(); 
            if (cur_token.token != Y_LPAR) { // 如果下一个符号不是左括号，语法错误
                return NULL; 
            }
            advance(); 
            past condition = rd_l_or_exp(); // 获取逻辑或表达式
            if (cur_token.token != Y_RPAR) { // 如果下一个符号不是右括号，语法错误
                return NULL; 
            }
            advance(); 
            past stmt = rd_stmt(); // 获取语句
            return newWhileStmt(condition, stmt); // 返回WHILE语句
        }
        case Y_IF: { // IF语句
            advance(); 
            if (cur_token.token != Y_LPAR) { // 如果下一个符号不是左括号，语法错误
                return NULL;
            }
            advance(); 
            past condition = rd_l_or_exp(); // 获取逻辑或表达式
            if (cur_token.token != Y_RPAR) { // 如果下一个符号不是右括号，语法错误
                return NULL; 
            }
            advance(); 
            past if_stmt = rd_stmt(); // 获取语句
            if (cur_token.token != Y_ELSE) { // 如果下一个符号不是ELSE关键字 ———— 无else
                return newIfStmt(condition, if_stmt, NULL); // 返回IF语句
            }
            advance(); 
            past else_stmt = rd_stmt(); // 获取ELSE分支语句
            return newIfStmt(condition, if_stmt, else_stmt); // 返回IF-ELSE语句
        }
        case Y_BREAK: { // BREAK语句
            advance(); 
            if (cur_token.token != Y_SEMICOLON) { // 如果下一个符号不是分号，语法错误
                return NULL; 
            }
            advance(); 
            return newBreakStmt(); // 返回BREAK语句
        }
        case Y_CONTINUE: { // CONTINUE语句
            advance(); 
            if (cur_token.token != Y_SEMICOLON) { // 如果下一个符号不是分号，语法错误
                return NULL; 
            }
            advance(); 
            return newContinueStmt(); // 返回CONTINUE语句
        }
        case Y_RETURN: { // RETURN语句
            advance(); 
            past left = rd_add_exp(); // 获取加法表达式
            if (cur_token.token != Y_SEMICOLON) { // 如果下一个符号不是分号，语法错误
                return NULL;
            }
            advance();
            return newReturnStmt(left, NULL); // 返回RETURN语句
        }
        default:
            return NULL;
    }
}

示例1: 赋值语句 (case Y_ID)

x[1] = 42;

   [=]
  /   \
x[1]  42

示例2: 空语句 (case Y_SEMICOLON)

; //  NULL

示例3: 代码块 (case Y_LBRACKET)

{
    x = 1;
    y = 2;
}

    [Block]
   /       \
(x = 1)  (y = 2)

示例4: WHILE 语句 (case Y_WHILE)

while (x > 0) {
    x = x - 1;
}

       [WHILE]
      /       \
   [>]         [=]
  /   \       /   \
[x]   [0]    [x]   [-]
           	      /   \
        	    [x]   [1]

示例5: IF 语句 (case Y_IF)

if (x > 0) {
    x = x - 1;
} else {
    x = x + 1;
}

            [IF]
    /        |        \
(x > 0) (x = x - 1) (x = x + 1)

示例6: BREAK 语句 (case Y_BREAK)

break;

  [BREAK]

示例7: CONTINUE 语句 (case Y_CONTINUE)

continue;

  [CONTINUE]

示例8: RETURN 语句 (case Y_RETURN)

return 5;

  [RETURN]
     |
     5

4 完整代码

#include "rdlab2.h"
#include <stdbool.h>

// 声明函数
past newBinaryOper(int oper, past left, past right);  // 创建一个新的二元操作节点
past newDeclRefExp(char *name, past left, past right);  // 创建一个新的声明引用表达式节点
past newWhileStmt(past condition, past body);  // 创建一个新的 while 语句节点
past newIfStmt(past condition, past ifBody, past elseBody);  // 创建一个新的 if 语句节点
past newBreakStmt();  // 创建一个新的 break 语句节点
past newContinueStmt();  // 创建一个新的 continue 语句节点
past newReturnStmt(past left, past right);  // 创建一个新的 return 语句节点

past rd_add_exp();  // 解析加法和减法表达式
past rd_mul_exp();  // 解析乘法、除法和取模表达式
past rd_unary_exp();  // 解析一元表达式
past rd_primary_exp();  // 解析基本表达式
past rd_l_or_exp();  // 解析逻辑或表达式
past rd_l_and_exp();  // 解析逻辑与表达式
past rd_eq_exp();  // 解析相等性表达式
past rd_call_paras();  // 解析函数调用参数列表
past rd_relexp();  // 解析关系运算表达式
past rd_stmt();  // 解析语句

// 函数定义

// 创建一个新的二元操作节点
past newBinaryOper(int oper, past left, past right) {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为二进制操作符
        node->nodeType = BINARY_OPERATOR;
        // 存储操作符
        node->ivalue = oper;
        // 存储左右操作数
        node->left = left;
        node->right = right;
    }
    return node;
}

// 创建一个新的声明引用表达式节点
past newDeclRefExp(char *name, past left, past right) {  
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为声明引用表达式
        node->nodeType = DECL_REF_EXPR;
        // 存储名称
        node->svalue = name;
        // 存储左右子节点
        node->left = left;
        node->right = right;
    }
    return node;
}

// 创建一个新的 while 语句节点
past newWhileStmt(past condition, past body) {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 while 语句
        node->nodeType = WHILE_STMT;
        // 存储条件表达式和循环体
        node->left = condition;
        node->right = body;
    }
    return node;
}

// 创建一个新的 if 语句节点
past newIfStmt(past condition, past ifBody, past elseBody) {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 if 语句
        node->nodeType = IF_STMT;
        // 存储条件表达式、if 分支和else分支
        node->if_cond = condition;
        node->left = ifBody;
        node->right = elseBody;
    }
    return node;
}

// 创建一个新的 break 语句节点
past newBreakStmt() {   
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 break 语句
        node->nodeType = BREAK_STMT;
    }
    return node;
}

// 创建一个新的 continue 语句节点
past newContinueStmt() {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 continue 语句
        node->nodeType = CONTINUE_STMT;
    }
    return node;
}

// 创建一个新的 return 语句节点
past newReturnStmt(past left, past right) {
    past node = newAstNode();
    if (node) {
        // 设置节点的类型为 return 语句
        node->nodeType = RETURN_STMT;
        // 存储返回表达式
        node->left = left;
        node->right = right;
    }
    return node;
}

// 解析基本表达式
past rd_primary_exp() {
    past node = NULL; // 初始化节点为NULL

    if (cur_token.token == Y_LPAR) { // (表达式)
        advance(); 
        node = rd_add_exp(); // 见下面的rd_add_exp()函数
        if (cur_token.token != Y_RPAR) { // 缺右括号
            return NULL; 
        }
        advance(); 
    } else if (cur_token.token == Y_ID) { // LVal
        char *s = cur_token.attr.svalue;
        past Arr = rd_array_subscripts();
        node = newDeclRefExp(s, Arr, NULL);
		advance();
    } else if (cur_token.token == num_INT) { 
        node = newInt(cur_token.attr.ivalue); // 构造整数节点
        advance(); 
    } else if (cur_token.token == num_FLOAT) { 
        node = newAstNode(); // 构造浮点数节点
        advance(); 
        node->fvalue = cur_token.attr.fvalue;
    }

    return node; // 返回表达式树
}

// 解析一元表达式
past rd_unary_exp() {
    past node = rd_primary_exp(); // 获取基本表达式

    while (node == NULL) { // 当基本表达式为空时
        if (cur_token.token == Y_ID) { // 当当前符号为标识符时
            char *s = cur_token.attr.svalue;
            advance();
            if (cur_token.token == Y_LPAR) {
                advance();
				past params;
                if (cur_token.token != Y_RPAR) {
                    params = rd_call_paras(); // 解析函数调用参数
                }
                node = newDeclRefExp(s, params, NULL); // 构造声明引用表达式
            }
        } else if (cur_token.token == Y_ADD || cur_token.token == Y_SUB || cur_token.token == Y_NOT) { // 当当前符号为加号、减号或取反符号
            int oper = cur_token.token; // 记录运算符
            advance(); 
            past operand = rd_unary_exp(); // 获取一元表达式
            node = newBinaryOper(oper, NULL, operand); // 构造二元操作表达式
        } else {
            return NULL; // 无法匹配其他情况，返回空
        }
    }

    return node; // 返回表达式树
}

// 解析加法表达式
past rd_add_exp() {
    past left = rd_mul_exp(); // 获取乘法表达式

    while (cur_token.token == Y_ADD || cur_token.token == Y_SUB) { // 当当前符号为加号或减号时
        int oper = cur_token.token; // 记录运算符
        advance(); 
        past right = rd_mul_exp(); // 获取乘法表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

// 解析乘法表达式
past rd_mul_exp() {
    past left = rd_unary_exp(); // 获取一元表达式

    while (cur_token.token == Y_MUL || cur_token.token == Y_DIV || cur_token.token == Y_MODULO) { // 当当前符号为乘号、除号或取模符号时
        int oper = cur_token.token; // 记录运算符
        advance(); 
        past right = rd_unary_exp(); // 获取一元表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}


// 解析相等表达式
past rd_eq_exp() {
    past left = rd_relexp(); // 获取关系表达式

    while (cur_token.token == Y_EQ || cur_token.token == Y_NOTEQ) { // 当当前符号为等号或不等号时
        int oper = cur_token.token; // 记录运算符
        advance(); 
        past right = rd_relexp(); // 获取关系表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

// 解析关系表达式
past rd_relexp() {
    past left = rd_add_exp(); // 获取加法表达式

    while (true) {
        switch (cur_token.token) {
            case Y_LESS:
            case Y_LESSEQ:
            case Y_GREAT:
            case Y_GREATEQ: { // 当当前符号为小于、小于等于、大于或大于等于时
                int oper = cur_token.token; // 记录运算符
                advance(); 
                past right = rd_add_exp(); // 获取加法表达式
                left = newBinaryOper(oper, left, right); // 构造二元操作表达式
                break;
            }
            default:
                return left; // 返回表达式树
        }
    }
}

// 解析逻辑与表达式
past rd_l_and_exp() {
    past left = rd_eq_exp(); // 获取相等表达式

    while (cur_token.token == Y_AND) { // 当当前符号为逻辑与符号时
        int oper = cur_token.token; // 记录运算符
        advance(); 
        past right = rd_eq_exp(); // 获取相等表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

// 解析逻辑或表达式
past rd_l_or_exp() {
    past left = rd_l_and_exp(); // 获取逻辑与表达式

    while (cur_token.token == Y_OR) { // 当当前符号为逻辑或符号时
        int oper = cur_token.token; // 记录运算符
        advance(); 
        past right = rd_l_and_exp(); // 获取逻辑与表达式
        left = newBinaryOper(oper, left, right); // 构造二元操作表达式
    }

    return left; // 返回表达式树
}

// 解析函数调用参数
past rd_call_paras() {
    past head = rd_add_exp(); // 获取加法表达式
    past current = head;

    while (cur_token.token) {
        if (cur_token.token != Y_COMMA) { // 当当前符号不为逗号时
            break;
        }
        advance(); 
        past new_node = rd_add_exp(); // 获取加法表达式
        current->next = new_node;
        current = current->next;
    }

    return head; // 返回参数链表头节点
}

// 解析语句
past rd_stmt() {
    switch (cur_token.token) {
        case Y_ID: { // LVal 开头 ———— 赋值语句
            char *s = cur_token.attr.svalue; // 处理LVal（等号左边）
            past Arr = rd_array_subscripts();
            past lval = newDeclRefExp(s, Arr, NULL);
            advance(); 
            if (cur_token.token != Y_ASSIGN) { // 语法错误
                return NULL; 
            }
            advance(); 
            past left = rd_add_exp(); // 获取加法表达式（等号右边）
            if (cur_token.token != Y_SEMICOLON) { // 语法错误
                return NULL; 
            }
            advance(); 
            return newBinaryOper(Y_ASSIGN, lval, left); // 返回赋值表达式
        }
        case Y_SEMICOLON: { // 分号开头 ———— 空语句
            advance(); 
            return NULL; 
        }
        case Y_LBRACKET: { // 左大括号开头 ———— 代码块
            advance(); 
            past block = rd_block(); // 获取块语句
            if (cur_token.token != Y_RBRACKET) { // 语法错误
                return NULL; 
            }
            advance(); 
            return block; // 返回块语句
        }
        case Y_WHILE: { // WHILE语句
            advance(); 
            if (cur_token.token != Y_LPAR) { // 如果下一个符号不是左括号，语法错误
                return NULL; 
            }
            advance(); 
            past condition = rd_l_or_exp(); // 获取逻辑或表达式
            if (cur_token.token != Y_RPAR) { // 如果下一个符号不是右括号，语法错误
                return NULL; 
            }
            advance(); 
            past stmt = rd_stmt(); // 获取语句
            return newWhileStmt(condition, stmt); // 返回WHILE语句
        }
        case Y_IF: { // IF语句
            advance(); 
            if (cur_token.token != Y_LPAR) { // 如果下一个符号不是左括号，语法错误
                return NULL;
            }
            advance(); 
            past condition = rd_l_or_exp(); // 获取逻辑或表达式
            if (cur_token.token != Y_RPAR) { // 如果下一个符号不是右括号，语法错误
                return NULL; 
            }
            advance(); 
            past if_stmt = rd_stmt(); // 获取语句
            if (cur_token.token != Y_ELSE) { // 如果下一个符号不是ELSE关键字 ———— 无else
                return newIfStmt(condition, if_stmt, NULL); // 返回IF语句
            }
            advance(); 
            past else_stmt = rd_stmt(); // 获取ELSE分支语句
            return newIfStmt(condition, if_stmt, else_stmt); // 返回IF-ELSE语句
        }
        case Y_BREAK: { // BREAK语句
            advance(); 
            if (cur_token.token != Y_SEMICOLON) { // 如果下一个符号不是分号，语法错误
                return NULL; 
            }
            advance(); 
            return newBreakStmt(); // 返回BREAK语句
        }
        case Y_CONTINUE: { // CONTINUE语句
            advance(); 
            if (cur_token.token != Y_SEMICOLON) { // 如果下一个符号不是分号，语法错误
                return NULL; 
            }
            advance(); 
            return newContinueStmt(); // 返回CONTINUE语句
        }
        case Y_RETURN: { // RETURN语句
            advance(); 
            past left = rd_add_exp(); // 获取加法表达式
            if (cur_token.token != Y_SEMICOLON) { // 如果下一个符号不是分号，语法错误
                return NULL;
            }
            advance();
            return newReturnStmt(left, NULL); // 返回RETURN语句
        }
        default:
            return NULL;
    }
}

上篇OpenCV实现多目三维重建（多张图片增量式生成稀疏点云）

下篇Three.js 实现简单的PCD加载器