【编译原理】语法、语义分析器设计（山东大学实验二）

核心思想：

1、LL（1）、SLR（1）、LR（0）、LR（1）、LALR算法等都是通用语法分析器算法，能够根据语法规则生成语法分析器。

2、但是这个通用不是绝对的，因为不同算法对文法（语法）有不同的要求。例如LL（1）要求文法没有左递归、公共左因子。LR系列算法要求文法不能出现规约-规约冲突、规约-移进冲突，虽然LR（1）、SLR（1）一定程度上都减少了这类冲突发生的可能性，但是并没有完全解决这类问题。

3、上面所有的算法都无法处理文法二义性的问题，因此还需要规定文法的优先级、结合性等

但是本实验，我并没有采用LL（1）等通用性的语法分析器算法去完成，而是采用手工编写的方式去写出语法分析器

核心思想：

1、不使用通用算法而是使用手工编写方式写出语法分析器。

2、人工分析文法规则，利用判断、循环等方法实现语法检查。

3、手工方法不是通用的，仅仅使用特定语言的语法。

语法分析器整体架构如下：

如果是LL（1）、LR（1）等通用算法则是：

如果是手工编写则是：

咦~抽象语法树去哪里了？

抽象语法树作用：

1、语法分析阶段需要形成抽象语法树的原因在于程序存在block的概念，也就是作用域，只有同一个域中的变量才是同一级别的，不同级别间互相不干扰。

2、为了实现这一个作用域功能，就引入树这个数据结构，实现层级效果。

3、LL（1）、LR算法在运行过程中隐式地形成了语法树。每一个程序的输入，经过一级级判断最终就是形成一个完整语法树结构，从而判断程序是否符合语法要求。

4、手工编写同样必须有上述的层级思想。但是我们没有引用树这一结构，而是使用记录level这个变量从而实现变量、函数的作用域效果，其本质相当于树。

总之，语法分析器是对代码是否符合文法表面看起来的结构的一种判断。

举个例子🌰：

我们有下面的文法结构：

S->Ac|Be
A->db|b
B->da|a

当输入字符串dbc，就要判断这个是不是能从文法结构中制造出来。

在本次实验中，我们的文法结构如下：

语法分析的作用就是要分析程序是不是能够由上面的文法推导出来，推导不出来则报错。

例如：

1.2 语义分析器

那么，语义分析又是什么？

这里我想做一点阐释，为什么这个实验要求我们进行的是语法、语义分析，而不是分开进行语法和语义分析写两份代码。

本质上语法和语义是不可以分离的，原因在于：

语义分析和语法分析都是对代码错误的一种寻找
语法分析是浅层的仅仅设计结构的错误寻找
语义分析是对结构背后蕴含的意义的错误寻找

那么将两者分开写就变为语法分析产生一个抽象语法树，语义分析再将抽象语法树还原，然后再进行错误判断。如此一来，不如直接进行语法语义的错误判断，如果没有问题再生成抽象语法树。

有了这个思想作为基础，我再带大家详细去看看语义分析器是什么。

不同于语法分析，语义分析在语法分析保证结构正确的同时还要求其内在含义的正确性。

说的更具体一点，语义分析是一种上下文分析，分析语句在上下文层面上是否正确。

举个例子🌰：

语义分析是在语法分析结构正确基础上，对变量、运算符的语义层面上是否正确的进一步分析

回到本实验代码，我们会对运算符两边的类型进行审查，也会对变量是否声明进行审查，如下：

重点！！！！！！

符号表：属于语义分析需要，变量检查

文法结构上的错误：语法分析内容

上下文相关分析上的错误：语义分析内容

emit语句：代码生成器内容，作用为生成低级代码（汇编指令）

通过上面的分析，我想大家应该清楚语法分析和语义分析的区别了，接下来我们就不再区分语法和语义分析，统一进行代码层面的讲解。

2. 代码分析

PL/0编译程序采用一遍扫描的方法，所以语法分析和代码生成都有在BLOCK中完成。BLOCK的工作分为两步：

2.1 说明部分的处理

说明部分的处理任务就是对每个过程（包括主程序，可以看成是一个主过程）的说明对象造名字表。填写所在层次（主程序是0层，在主程序中定义的过程是1层，随着嵌套的深度增加而层次数增大。PL/0最多允许3层），标识符的属性和分配的相对地址等。标识符的属性不同则填写的信息不同。

所造的表放在全程量一维数组TABLE中，TX为指针，数组元素为结构体类型数据。LEV给出层次，DX给出每层的局部量的相对地址，每说明完一个变量后DX加1。

例如：一个过程的说明部分为：

const a=35,b=49;
var c,d,e;
procedure p;
var g;

对它的常量、变量和过程说明处理后，TABLE表中的信息如下：

NAME: a

NAME: b

NAME: c

NAME: d

NAME: e

NAME: p

KIND: CONSTANT

KIND: VARIABLE

KIND: VAEIABLE

KIND: PROCEDURE

VAL: 35

VAL: 49

LEVEL: LEV

ADR: DX

ADR: DX+1

ADR: DX+2

ADR:

NAME: g

。

KIND: VARIABLE

。

LEVEL: LEV+1

。

ADR: DX

。

对于过程名的ADR域，是在过程体的目标代码生成后返填过程体的入口地址。TABLE表的索引TX和层次单元LEV都是以BLOCK的参数形式出现，在主程序调用BLOCK时实参的值为0。每个过程的相对起始位置在BLOCK内置初值DX=3。

2.2 语句处理和代码生成

对语句逐句分析，语法正确则生目标代码,当遇到标识符的引用则去查TABLE表,看是否有过正确的定义，若有则从表中取出相关的信息,供代码生成用。PL/0语言的代码生成是由过程GEN完成。GEN过程有三个参数，分别代表目标代码的功能码、层差、和位移量。生成的目标代码放在数组CODE中。CODE是一维数组，数组元素是结构体类型数据。

PL/0语言的目标指令是一种假想的栈式计算机的汇编语言，其格式如下：

其中f代表功能码，l代表层次差，a代表位移量。目标指令有8条：

① LIT：将常数放到运栈顶，a域为常数。

② LOD：将变量放到栈顶。a域为变量在所说明层中的相对位置，l为调用层与说明层的层差值。

③ STO：将栈顶的内容送到某变量单元中。a,l域的含义与LOD的相同。

④ CAL：调用过程的指令。a为被调用过程的目标程序的入中地址，l为层差。

⑤ INT：为被调用的过程（或主程序）在运行栈中开辟数据区。a域为开辟的个数。

⑥ JMP：无条件转移指令，a为转向地址。

⑦ JPC：条件转移指令，当栈顶的布尔值为非真时，转向a域的地址，否则顺序执行。为0跳转，为1顺序执行

⑧ OPR：关系和算术运算。具体操作由a域给出。运算对象为栈顶和次顶的内容进行运算，结果存放在次顶。a域为0时是退出数据区。

2.3 PL0语法规则

语法分析所用产生式：

〈程序〉→〈分程序〉。

〈分程序〉→ [<常量说明部分>][<变量说明部分>][<过程说明部分>]〈语句〉

<常量说明部分> → CONST<常量定义>{ ,<常量定义>}；

<常量定义> → <标识符>=<无符号整数>

<变量说明部分> → VAR<标识符>{ ,<标识符>}；

<过程说明部分> → <过程首部><分程序>；{<过程说明部分>}

<过程首部> → procedure<标识符>；

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

<复合语句> → begin<语句>{ ；<语句>}<end>

<条件> → <表达式><关系运算符><表达式>|odd<表达式>

<表达式> → [+|-]<项>{<加减运算符><项>}

<项> → <因子>{<乘除运算符><因子>}

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

<条件语句> → if<条件>then<语句>

<过程调用语句> → call<标识符>

<当型循环语句> → while<条件>do<语句>

<读语句> → read(<标识符>{ ，<标识符>})

<写语句> → write(<标识符>{，<标识符>})

核心思想（！！！！！本篇最重要思想！！！！！）：

1、手工编写语法分析器本质也就是：对一个个语法产生式的左边（非终结符）根据右边的语法规则手工写代码来处理。

2、语法分析过程也就是：建立语法树的过程

3、建立语法树的也就是：从根节点（第一个非终结符）开始，对非终结符不停展开

4、语法检查：输入code从根节点开始往叶子走，能够走到一个叶子节点，存在至少一条通路，则说明该code是合法的。

3. 具体核心代码分析

2 语法分析标识符表项由结构体symbol定义。int kind表示标识符种类，char name[12]存放标识符名，val存放常量标识符值，int level存放标识符层数，int addr存放偏移值。

/*For constants, you must store kind, name and value.
For variables, you must store kind, name, L and M.
For procedures, you must store kind, name, L and M.*/
struct symbol
{
int kind; // const = 1, var = 2, proc = 3
char name[12]; // name up to 11 chars
int val; // number (ASCII value)
int level; // L level
int addr; // M address
};

3 语法分析目标代码表项由结构体instruction表示

struct instruction{
ins_type ins; //Opcode
int l; //L
int m; //M
};

4 全局变量：table为符号表，code为目标代码表，tx表示符号表序号，cx表示代码表序号，lev表示当前层数 ，dx表示当前过程偏移，lexemeListIndex是词法分析结果当前读入位置，curToken是最新读入tokenStruct，blank是打印空格数。

symbol table[MAX_SYMBOL_TABLE_SIZE]; //符号表
instruction code[CODE_SIZE]; //目标代码
int tx, cx, lev = -1; //tx表示符号表序号，cx表示代码表序号，lev表示当前层数
//tx已经占据，cx没有占据
int dx = 3; //表示当前过程偏移
int lexemeListIndex = 0; //词法分析结果当前读入位置
tokenStruct curToken; //最新读入tokenStruct
int blank = 0; //打印空格数

5 自上而下的语法分析需要为每一个非终结符构造一个语法分析函数。

void program(); //程序
void block(); //分程序
void constDeclaration(); //常量说明部分
void constDefinition(); //常量定义
void varDeclaration(); //变量说明部分
void varDefinition(); //变量定义
void procedureDeclaration();//过程说明部分
void procedureHead(); //过程首部
void statement(); //语句
void condition(); //条件
void expression(); //表达式
void term(); //项
void factor(); //因子
void assignment(); //赋值语句
void callProcedure(); //过程调用语句
void conditionStatement(); //条件语句
void compoundStatement(); //复合语句
void loopStatement(); //循环语句
void writeStatement(); //写语句
void readStatement(); //读语句

6 getNextToken()从词法分析结果中获得下一个输入非终结符。存放到全局变量curToken中。全局变量int lexemeListIndex 表示当前读入终结符的个数。

void getNextToken() {
curToken.tokenID = lexList[lexemeListIndex].tokenID;
if (curToken.tokenID == 2)
strcpy(curToken.name, lexList[lexemeListIndex].name);
else if (curToken.tokenID == 3)
curToken.numberValue = lexList[lexemeListIndex].numberValue;
lexemeListIndex++;
}

7 enter()向标识符表中添加变量、常量、过程。根据类型赋值不同的成员变量。

symbol table[MAX_SYMBOL_TABLE_SIZE]为符号表。

void enter(int kind) {
tx++;
strcpy(table[tx].name, curToken.name);
table[tx].kind = kind;
//const
if (kind == 1)
table[tx].val = curToken.numberValue;
else if (kind == 2) {
table[tx].level = lev;
table[tx].addr = dx;
dx++;
} else if (kind == 3)
table[tx].level = lev;
}

8 全局变量int tx为当前标识符表最后一项。Int lev表示当前层数，int dx表示当前层的偏移量，

9 position()函数进行查标识符表，只能查找当前层或当前层的所有父层，如果找到则返回位置，如果没有找到返回0。

int position() {
int curLev = lev;
for (int i = tx; i > 0; i--) {
if (table[i].kind == 3 && table[i].level == curLev - 1)
curLev--;
if (table[i].level > curLev)
continue;
if (strcmp(table[i].name, curToken.name) == 0)
return i;
}
return 0;
}

10 error(int errorCase)函数输出语法分析错误。便于调试。

11 语法分析树输出。通过打印制表符\t，表示树的层级。通过全局变量blank存放需打印制表符\t的个数。printBlank()进行打印制表符\t。在每个语法分析函数终结符处进行输出，打印语法树

void printBlank() {
for (int i = 0; i < blank; i++)
fprintf(ofp, "\t");
}

12 emit()生成目标代码到代码表。

void emit(ins_type ins, int l, int m) {
if (cx >= CODE_SIZE) {
printf("Program too long! cx > CODE_SIZE\n");
exit(1);
} else {
code[cx].ins = ins;
code[cx].l = l;
code[cx].m = m;
cx++;
}
}

12处理非终结符<程序>

void program() {
printBlank();
fprintf(ofp, "program\n");
blank++;
int cx0 = cx;
emit(JMP, 0, 0);
getNextToken();
block();
code[cx0].m = mainCode;
if (curToken.tokenID != periodsym)
error(1); //Period expected.
printBlank();
fprintf(ofp, ".\n");
blank--;
}

13 处理非终结符<分程序>

void block() {
printBlank();
fprintf(ofp, "block\n");
blank++;
lev++;
if (lev > MAX_LEXI_LEVELS)
error(2); //errors for above max lexi level
int oldDx = dx;
dx = 3;
int tx0 = tx;
do {
if (curToken.tokenID == constsym) {
constDeclaration();
}
if (curToken.tokenID == varsym) {
varDeclaration();
}
while (curToken.tokenID == procsym) {
procedureDeclaration();
}
} while ((curToken.tokenID == constsym) || (curToken.tokenID == varsym) || (curToken.tokenID == procsym));
if (lev == 0)
mainCode = cx;
table[tx0].addr = cx;
emit(INT, 0, dx);
statement();
emit(OPR, 0, 0);
dx = oldDx;
lev--;
blank--;
}

14 处理非终结符<常量说明部分>

void constDeclaration() {
printBlank();
fprintf(ofp, "constDeclaration\n");
blank++;
printBlank();
fprintf(ofp, "const\n");
getNextToken();
constDefinition();
while (curToken.tokenID == commasym) {
printBlank();
fprintf(ofp, ",\n");
getNextToken();
constDefinition();
}
if (curToken.tokenID == semicolonsym) {
printBlank();
fprintf(ofp, ";\n");
getNextToken();
} else {
error(3); //常量声明部分缺少;
}
blank--;
}

15 处理非终结符

void constDefinition() {
printBlank();
fprintf(ofp, "constDefinition\n");
blank++;
if (curToken.tokenID == identsym) {
printBlank();
fprintf(ofp, "%s\n", curToken.name);
getNextToken();
if ((curToken.tokenID == eqsym) || (curToken.tokenID == becomessym)) {
if (curToken.tokenID == becomessym)
error(6); //Use = instead of := in constDefinition
printBlank();
fprintf(ofp, ":=\n");
getNextToken();
if (curToken.tokenID == numbersym) {
printBlank();
fprintf(ofp, "%d\n", curToken.numberValue);
enter(1);
getNextToken();
} else {
error(8); //常量定义赋值的不是整数
}
} else {
error(7); //常量未赋值
}
} else {
error(5); //常量定义缺少标识符
}
blank--;
}

其他代码，学弟学妹们自己好好去研究，我这里就不一一展开了

注意：

上面的示例代码和我上传的实际代码存在一定的不同

逻辑完全一样，可能在注释和一些变量命名上存在区别

4. 完整代码

parse.cpp:

//
// Created by csh on 2024/10/28 in shangDongUniversity
//


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "data.h"
#include "parse.h"

symbol table[MAX_SYMBOL_TABLE_SIZE];    // 符号表，用于存储常量、变量和过程的符号信息
instruction code[CODE_SIZE];            // 目标代码数组，用于生成中间代码（机器指令）

int tx, cx, lev = -1;                   // tx：符号表当前索引，cx：代码生成器当前语句编号，lev：当前作用域层级
                                        // tx用于符号表，cx用于代码生成器

int dx = 3;                             // dx 表示当前过程的偏移量，通常为局部变量的空间偏移量，初始化为 3

int lexemeListIndex = 0;                // 词法分析结果当前读入位置
tokenStruct curToken;                   // 当前读入的 token 结构体，存储当前的词法单元信息

int blank = 0;                          // 用于控制输出时的缩进量，用于美化输出
FILE *ofp;                              // 用于输出语法分析过程的文件指针
FILE *codeFp;                           // 用于输出中间代码的文件指针
FILE *tableFp;                          // 用于输出符号表的文件指针

int mainCode;                           // 主程序代码位置

/**
 * parse函数：
        1、初始化符号表和代码生成器的状态。
        2、打开输出文件并开始解析程序。
        3、调用 program() 函数解析整个程序。
        4、在解析完毕后，输出符号表和生成的中间代码到指定文件。
 */
void parse(char *parsefilename,char *tablefilename,char *codefilename) {
    memset(table,0, sizeof(table)); // 清空符号表
    tx = 0, cx = 0, lev = -1;       // 初始化符号表索引、代码索引和层级
    dx = 3;                         // 初始化变量栈大小
    lexemeListIndex = 0;            // 初始化词法分析位置
    blank = 0;                      // 初始化空格数
    table[0].level = -1;            // 根级别的符号表项，通常是全局作用域

    // 语法分析过程、中间代码、符号表
    ofp = fopen(parsefilename, "w");
    codeFp = fopen(codefilename,"w");
    tableFp = fopen(tablefilename,"w");

    // 调用程序解析函数
    program();
    // 输出符号表
    for (int i = 0; i <= tx; i++) {
        fprintf(tableFp,"kind:%d\tval:%d\tlev:%d\taddr:%d\tname:%s\n", table[i].kind, table[i].val, table[i].level,
               table[i].addr, table[i].name);
    }
    // 输出生成的中间代码
    for (int i=0; i<cx;i++) {
        fprintf(codeFp,"%d %d %d\n", code[i].ins, code[i].l, code[i].m);
    }
    // 关闭文件
    fclose(ofp);
    fclose(codeFp);
}

/**
 * 在code中添加新的语句
 * @param ins 语句类型
 * @param l   语句所在层级
 * @param m   语句操作数
 */
void emit(ins_type ins, int l, int m) {
    // cx是语句序号
    if (cx >= CODE_SIZE) {
        printf("Program too long! cx > CODE_SIZE\n");
        exit(1);
    } else {
        code[cx].ins = ins;
        code[cx].l = l;
        code[cx].m = m;
        cx++;
    }
}

/**
 * program：
    1、开始解析程序结构。
    2、生成初始的跳转指令，跳到主程序的位置。
    3、解析程序块，确保程序以句号结束。
 */
void program() {
    printBlank();                                    // 输出当前缩进（控制输出格式）
    fprintf(ofp, "program\n");        // 进入程序结构处理
    blank++;                                         // 增加缩进，进入下一个层级

    int cx0 = cx;
    emit(JMP, 0, 0);                       // 生成跳转指令，初始化时跳到主程序位置

    getNextToken();                                  // 获取下一个 token（通常是程序的开始部分）
    block();                                         // 解析程序块（程序主体部分）

    code[cx0].m = mainCode;                          // 更新初始跳转指令的目标位置为主程序的起始位置

    if (curToken.tokenID != periodsym)
        error(1);                           // 如果没有遇到句号，报错（程序必须以句号结束）

    printBlank();
    fprintf(ofp, ".\n");              // 输出程序结束的符号
    blank--;                                        // 缩进回退
}

/**
 * block：
 * 作用：1、相当于{}，将代码块具体的部分和函数（函数名调用接口）本身在层级上区分开
 * 背景：在语法处理上，需要构建一颗语法分析树，因此形成层级相当重要
 */
void block() {
    printBlank();
    fprintf(ofp, "block\n");  // 输出 "block" 表示进入当前代码块的处理
    blank++;  // 递增 blank，通常用于控制输出的缩进级别，便于调试时查看嵌套层次

    lev++;  // block代码块意味着全新层次
    // 检查嵌套层级是否超过最大允许值
    if (lev > MAX_LEXI_LEVELS)
        error(2);

    // 每一个block后都是全新的栈去处理（保证变量等不冲突）
    // dx含义：1、栈指针；3、栈大小
    int oldDx = dx;
    dx = 3;
    // 保存当前的符号表索引 tx，tx 用于标记符号表中的位置
    int tx0 = tx;

    // 处理代码块中的声明（代码块中的语句）
    do {
        if (curToken.tokenID == constsym) {
            constDeclaration();
        }
        if (curToken.tokenID == varsym) {
            varDeclaration();
        }
        while (curToken.tokenID == procsym) {
            procedureDeclaration();
        }
    } while ((curToken.tokenID == constsym) || (curToken.tokenID == varsym) || (curToken.tokenID == procsym));

    // 如果当前是顶层块（即嵌套层级 lev 为 0），记录主程序的代码位置
    if (lev == 0)
        mainCode = cx;  // mainCode 记录主程序的起始位置，cx 是指令计数器

    // 将符号表中的某个项（tx0 索引的项）地址字段更新为当前代码位置
    table[tx0].addr = cx;

    // 发出指令，分配栈空间
    emit(INT, 0, dx);

    // 处理当前块的语句
    statement();

    // 发出返回指令，表示程序块的结束
    emit(OPR, 0, 0);

    // 恢复栈指针（dx）和嵌套层级（lev）
    dx = oldDx;
    lev--;

    blank--;
}

/**
 * constDeclaration
 * 作用：处理常量声明操作
 * 处理范围：1、声明包括定义；2、定义是声明的一部分
 */
void constDeclaration() {
    printBlank();  // 打印空白，控制缩进
    fprintf(ofp, "constDeclaration\n");  // 输出constDeclaration到输出文件
    blank++;  // 增加缩进层级

    printBlank();  // 打印当前缩进
    fprintf(ofp, "const\n");  // 输出const关键字

    getNextToken();  // 获取下一个token，继续分析
    constDefinition();  // 解析常量定义

    // 处理多个常量定义，用逗号分隔
    while (curToken.tokenID == commasym) {
        printBlank();
        fprintf(ofp, ",\n");  // 输出逗号
        getNextToken();  // 获取下一个token
        constDefinition();  // 解析下一个常量定义
    }

    // 检查是否有分号，标志着常量声明的结束
    if (curToken.tokenID == semicolonsym) {
        printBlank();
        fprintf(ofp, ";\n");  // 输出分号
        getNextToken();  // 获取下一个token
    } else {
        error(3);  // 报错：缺少分号
    }

    blank--;  // 减少缩进层级
}

/**
 * constDefinition：
 * 作用：常量具体定义（完成常量赋值等）
 * 背景：词法分析器：1、保证每个Token正确；2、记录每一个Token关键信息（num、类型、name）
 * 错误可能：1、没有标识符；2、常数未赋值；3、赋值出现小数
 */
void constDefinition() {
    printBlank();
    fprintf(ofp, "constDefinition\n");
    blank++;

    if (curToken.tokenID == identsym) {
        printBlank();
        fprintf(ofp, "%s\n", curToken.name);

        getNextToken();
        if ((curToken.tokenID == eqsym) || (curToken.tokenID == becomessym)) {
            if (curToken.tokenID == becomessym)
                error(6);       //Use = instead of := in constDefinition

            printBlank();
            fprintf(ofp, ":=\n");

            getNextToken();
            if (curToken.tokenID == numbersym) {
                printBlank();
                fprintf(ofp, "%d\n", curToken.numberValue);

                enter(1);
                getNextToken();
            } else {
                error(8);       //常量定义赋值的不是整数
            }

        } else {
            error(7);           //常量未赋值
        }
    } else {
        error(5);       //常量定义缺少标识符
    }

    blank--;
}

/**
 * varDeclaration
 * 作用：处理变量声明
 * 处理范围：
 */
void varDeclaration() {
    printBlank();
    fprintf(ofp, "varDeclaration\n");
    blank++;

    printBlank();
    fprintf(ofp, "var\n");

    getNextToken();
    varDefinition();
    // 连续定义的处理
    while (curToken.tokenID == commasym) {
        printBlank();
        fprintf(ofp, ",\n");

        getNextToken();
        varDefinition();
    }
    // 遇到分号结束处理
    if (curToken.tokenID == semicolonsym) {
        printBlank();
        fprintf(ofp, ";\n");

        getNextToken();
    } else {
        error(4); // 没有分号
    }

    blank--;
}

/**
 * varDefinition：
 * 作用：变量具体定义
 * 辨析：1、变量定义就是自己，常量定义包括具体的数字；2、enter会将变量写入符号表
 */
void varDefinition() {
    if (curToken.tokenID == identsym) {
        printBlank();
        fprintf(ofp, "%s\n", curToken.name);

        enter(2);
        getNextToken();
    } else
        error(9);
}

/**
 * procedureDeclaration：
 * 作用：过程声明（过程相当于函数）
 * 背景：1、声明包括定义；定义是声明的一部分
 */
void procedureDeclaration() {
    printBlank();
    fprintf(ofp, "procedureDeclaration\n");
    blank++;

    procedureHead();
    block();
    // 分号检查
    // 过程没法连续定义
    if (curToken.tokenID == semicolonsym) {
        printBlank();
        fprintf(ofp, ";\n");

        getNextToken();
    } else
        error(33);                  //; not find in procedureDeclaration()

    blank--;
}

/**
 * procedureHead：
 * 作用：1、用procedureHead将procedure包装成整体；2、让procedureHead与上面同级
 */
void procedureHead() {
    printBlank();
    fprintf(ofp, "procedureHead\n");
    blank++;

    printBlank();
    fprintf(ofp, "procedure\n");

    getNextToken();
    if (curToken.tokenID == identsym) {
        printBlank();
        fprintf(ofp, "%s\n", curToken.name);

        enter(3);
        getNextToken();

        if (curToken.tokenID == semicolonsym) {
            printBlank();
            fprintf(ofp, ";\n");

            getNextToken();
        } else
            error(32);                  //; not find in procedureHead()
    } else
        error(31);                      //identsym not find in procedureHead()

    blank--;
}

/**
 * statement：
 * 背景：1、procedure后面跟着函数（函数处理以及变量定义）；2、begin/end封装程序块，让程序一起执行
 * 作用：对所有语句进行分类处理
 * 语句类型：赋值语句、回调语句、条件判断语句、复合语句、循环语句、写入语句、读取语句
 */
void statement() {
    printBlank();
    fprintf(ofp, "statement\n");
    blank++;

    // 对一般语句中的不同语句分类处理
    if (curToken.tokenID == identsym) {
        assignment();
    } else if (curToken.tokenID == callsym) {
        callProcedure();
    } else if (curToken.tokenID == ifsym) {
        conditionStatement();
    } else if (curToken.tokenID == beginsym) {
        compoundStatement();
    } else if (curToken.tokenID == whilesym) {
        loopStatement();
    } else if (curToken.tokenID == writesym) {
        writeStatement();
    } else if (curToken.tokenID == readsym) {
        readStatement();
    }

    blank--;
}

/**
 * assignment：
 * 作用：遇到:=赋值语句的处理
 */
void assignment() {
    printBlank();
    fprintf(ofp, "assignment\n");
    blank++;

    printBlank();
    fprintf(ofp, "%s\n", curToken.name);

    int i = position();
    if (i == 0)
        error(10);          //identsym not find in table in assignment
    else if (table[i].kind != 2)
        error(11);          //identsym in assignment must be var

    getNextToken();
    if (curToken.tokenID == becomessym) {
        printBlank();
        fprintf(ofp, ":=\n");

        getNextToken();
        expression();
    } else
        error(12);          //becomessym not find in assignment

    emit(STO, lev - table[i].level, table[i].addr);

    blank--;
}

/**
 * callProcedure：
 * 作用：回调语句的处理
 * 背景：1、需要用到positon实现定位
 */
void callProcedure() {
    printBlank();
    fprintf(ofp, "callProcedure\n");
    blank++;

    printBlank();
    fprintf(ofp, "call\n");

    getNextToken();
    if (curToken.tokenID != identsym)
        error(13);          //identsym not find in callProcedure
    else {
        printBlank();
        fprintf(ofp, "%s\n", curToken.name);

        // 查找回调函数在表中的位置（充分性）
        int i = position();
        if (i == 0)
            error(14);      //identsym not find in table in callProcedure
        else if (table[i].kind != 3)
            error(15);      //identsym called must be procedure
        else {
            getNextToken();

            emit(CAL, lev - table[i].level, table[i].addr);
        }
    }

    blank--;
}

/**
 * conditionStatement：
 * 背景：1、存在结构、功能两方面讲究的部分会分为两个函数；2、一个负责结构，一个负责功能
 * 背景：1、语法分析过程中完成中间代码生成；2、中间代码生成作用是语义分析
 * 背景：1、if后面的是condition，then后面的是一般语句
 */
void conditionStatement() {
    printBlank();
    fprintf(ofp, "conditionStatement\n");
    blank++;

    printBlank();
    fprintf(ofp, "if\n");

    getNextToken();
    condition();

    if (curToken.tokenID == thensym) {
        printBlank();
        fprintf(ofp, "then\n");

        getNextToken();
    } else
        error(16);                  //then not find in conditionStatement

    int cx0 = cx;                           //回填
    emit(JPC, 0, 0);

    statement();

    code[cx0].m = cx;

    blank--;
}

/**
 * compoundStatement：
 * 作用：begin，end包围的语句，要求一起执行的语句
 * 背景：1、复合语句就是外面整体是一个statement，里面又由statement构成
 */
void compoundStatement() {
    printBlank();
    fprintf(ofp, "compoundStatement\n");
    blank++;

    printBlank();
    fprintf(ofp, "begin\n");

    getNextToken();

    statement();
    while (curToken.tokenID == semicolonsym) {
        printBlank();
        fprintf(ofp, ";\n");

        getNextToken();
        statement();
    }
    // 复合语句中分号；需要在end结束时出现
    if (curToken.tokenID == endsym) {
        printBlank();
        fprintf(ofp, "end\n");

        getNextToken();
    } else {
        error(17);                  //end not find in compoundStatement()
    }

    blank--;
}

/**
 * loopStatement：
 * 作用：1、实现循环
 * 背景：1、利用JPC和JMP两个语句实现循环
 */
void loopStatement() {
    printBlank();
    fprintf(ofp, "loopStatement\n");
    blank++;

    printBlank();
    fprintf(ofp, "while\n");

    getNextToken();

    int cx0 = cx;           // 标号，用于循环跳转

    condition();            // 条件判断

    int cx1 = cx;           // 回填。记录下JPC所在的位置，后续回填
    emit(JPC, 0, 0);        // 条件成立则跳转。这里是退出while循环

    if (curToken.tokenID == dosym) {
        printBlank();
        fprintf(ofp, "do\n");

        getNextToken();
    } else
        error(18);                      //do not find in loopStatement()

    statement();

    emit(JMP, 0, cx0);

    code[cx1].m = cx;

    blank--;
}

/**
 * writeStatement：
 * 作用：打印表达式到控制台
 */
void writeStatement() {
    printBlank();
    fprintf(ofp, "writeStatement\n");
    blank++;

    printBlank();
    fprintf(ofp, "write\n");

    getNextToken();

    if (curToken.tokenID == lparentsym) {
        printBlank();
        fprintf(ofp, "(\n");

        getNextToken();
        expression();

        // 操作指令：输出操作
        emit(OPR, 0, WRITE);
        // 连续输出write
        while (curToken.tokenID == commasym) {
            printBlank();
            fprintf(ofp, ",\n");

            getNextToken();
            expression();

            emit(OPR, 0, WRITE);
        }

        if (curToken.tokenID == rparentsym) {
            printBlank();
            fprintf(ofp, ")\n");

            getNextToken();
        } else
            error(21);              //) not find in writeStatement()
    } else
        error(20);                  //( not find in writeStatement()

    blank--;
}

/**
 * readStatement：
 * 作用：执行read操作，从（）中读取
 */
void readStatement() {
    printBlank();
    fprintf(ofp, "readStatement\n");
    blank++;

    printBlank();
    fprintf(ofp, "read\n");

    getNextToken();

    if (curToken.tokenID == lparentsym) {
        printBlank();
        fprintf(ofp, "(\n");

        getNextToken();
        identifier();

        while (curToken.tokenID == commasym) {
            printBlank();
            fprintf(ofp, ",\n");

            getNextToken();
            identifier();
        }

        if (curToken.tokenID == rparentsym) {
            printBlank();
            fprintf(ofp, ")\n");

            getNextToken();
        } else
            error(25);              //) not find in readStatement()
    } else
        error(24);                  //( not find in readStatement()

    blank--;
}

/**
 * identifier：
 * 作用：输出标识符变量
 * 背景：针对变量而不是常量或数字等
 */
void identifier() {
    if (curToken.tokenID == identsym) {
        printBlank();
        fprintf(ofp, "%s\n", curToken.name);

        int i = position();
        if (i == 0)
            error(22);                      //identifier is not find in table in identifier()
        else if (table[i].kind != 2)
            error(23);                      //identifier is not var in identifier()

        getNextToken();

        emit(OPR, 0, READ);
        emit(STO, lev - table[i].level, table[i].addr);
    } else {
        error(19);                          //identifier not find in identifier()
    }
}

/**
 * condition：
 * 作用：对条件判断的核心部分（条件判断式）进行处理
 */
void condition() {
    printBlank();
    fprintf(ofp, "condition\n");
    blank++;

    // PL0中的Odd奇数判断是单独分离出来的
    if (curToken.tokenID == oddsym) {
        printBlank();
        fprintf(ofp, "odd\n");

        getNextToken();
        expression();

        emit(OPR, 0, ODD);
    } else {
        expression();

        // 没有条件判断部分，报错
        if ((curToken.tokenID != eqsym) && (curToken.tokenID != neqsym) && (curToken.tokenID != lessym) &&
            (curToken.tokenID != leqsym) && (curToken.tokenID != mresym) && (curToken.tokenID != geqsym))
            error(26);
        else {
            // 记录下条件判断位置
            token_type relop = curToken.tokenID;

            printBlank();
            fprintf(ofp, "%s\n", strPrint[curToken.tokenID]);

            getNextToken();
            expression();
            // 语义处理部分
            switch (relop) {
                case eqsym:
                    emit(OPR, 0, EQ);
                    break;
                case neqsym:
                    emit(OPR, 0, NE);
                    break;
                case lessym:
                    emit(OPR, 0, LT);
                    break;
                case leqsym:
                    emit(OPR, 0, LE);
                    break;
                case mresym:
                    emit(OPR, 0, GT);
                    break;
                case geqsym:
                    emit(OPR, 0, GE);
                    break;
                default:
                    break;
            }
        }
    }

    blank--;
}

/**
 * expression：
 * 作用：1、对运算式子进行处理
 * 背景：1、把运算式理解为：符号+项的形式
 */
void expression() {
    printBlank();
    fprintf(ofp, "expression\n");
    blank++;

    // 表达式处理包括：项处理、符号处理
    if (curToken.tokenID == plussym || curToken.tokenID == minussym) {
        printBlank();
        fprintf(ofp, "%s\n", strPrint[curToken.tokenID]);

        token_type relop = curToken.tokenID;

        getNextToken();
        term();

        if (relop == minussym)
            emit(OPR, 0, MINUS);
    } else {
        term();
    }

    while (curToken.tokenID == plussym || curToken.tokenID == minussym) {
        printBlank();
        fprintf(ofp, "%s\n", strPrint[curToken.tokenID]);

        token_type relop = curToken.tokenID;

        getNextToken();
        term();

        if (relop == plussym)
            emit(OPR, 0, ADD);
        else
            emit(OPR, 0, SUB);
    }

    blank--;
}

/**
 * term：
 * 作用：对项进行处理
 * 背景：1、单个字符为一个项；2、字符之间的乘积为一个项；
 * 背景：3、项在这里可以理解为整体部分
 */
void term() {
    printBlank();
    fprintf(ofp, "term\n");
    blank++;
    // 提取因子
    factor();
    while (curToken.tokenID == multsym || curToken.tokenID == slashsym) {
        printBlank();
        fprintf(ofp, "%s\n", strPrint[curToken.tokenID]);

        token_type relop = curToken.tokenID;

        getNextToken();
        factor();

        if (relop == multsym)
            emit(OPR, 0, MUL);
        else
            emit(OPR, 0, DIV);
    }

    blank--;
}

/**
 * factor:
 * 作用：因子解析（解析表达式中的常数、变量等）
 * 背景：判断语句需要查找前面定义的符号表
 */
void factor() {
    printBlank();
    fprintf(ofp, "factor\n");
    blank++;

    if (curToken.tokenID == identsym) {
        printBlank();
        fprintf(ofp, "%s\n", curToken.name);

        int i = position();
        if (i == 0)
            error(27);                  //identsym not find in table in factor()
        else if (table[i].kind == 3)
            error(28);                  //identsym in factor() cannot be procedure
        else if (table[i].kind == 1)
            emit(LIT,0,table[i].val);
        else if (table[i].kind == 2)
            emit(LOD,lev - table[i].level,table[i].addr);

        getNextToken();
    } else if (curToken.tokenID == numbersym) {
        printBlank();
        fprintf(ofp, "%d\n", curToken.numberValue);

        emit(LIT,0,curToken.numberValue);

        getNextToken();
    } else if (curToken.tokenID == lparentsym) {
        printBlank();
        fprintf(ofp, "(\n");

        getNextToken();
        expression();

        if (curToken.tokenID == rparentsym) {
            printBlank();
            fprintf(ofp, ")\n");

            getNextToken();
        } else
            error(29);                      //) not find in factor()
    } else
        error(30);                          //factor() cannot be right

    blank--;
}

void getNextToken() {
    curToken.tokenID = lexList[lexemeListIndex].tokenID;

    //var
    if (curToken.tokenID == 2)
        strcpy(curToken.name, lexList[lexemeListIndex].name);
    else if (curToken.tokenID == 3)
        curToken.numberValue = lexList[lexemeListIndex].numberValue;

    lexemeListIndex++;
}

/**
 * printBlank：
 * 函数作用：缩进
 * 一个blank缩进一个tab（4字符）
 */
void printBlank() {
    for (int i = 0; i < blank; i++)
        fprintf(ofp, "\t");
}

/**
 * enter：
 * 作用：把字符（常量、变量、过程）都存入table表中
 * 背景：1、常量值确定，所以直接存储值；2、变量无具体值，因此存储地址。
 * 背景：3、过程是用来封装子程序，控制程序走向的一类变量。其
 * @param kind
 */
void enter(int kind) {
    tx++;

    strcpy(table[tx].name, curToken.name);
    table[tx].kind = kind;

    //const
    if (kind == 1)
        table[tx].val = curToken.numberValue;
    else if (kind == 2) {
        table[tx].level = lev;
        table[tx].addr = dx;
        dx++;
    } else if (kind == 3)
        table[tx].level = lev;
}

/**
 * position：
 * 作用：符号表查询函数
 * 背景：1、符号表中有三个类型（变量、常量、过程）；2、由于不同层级之间的变量不会冲突，因此有level、
 * 背景：3、符号表查询采用线性查询，时间效率较低；4、符号表从后往前level是降低的
 * 背景：5、函数只能给level大于函数本身level的作用域使用；6、优先使用自己作用域的函数
 * @return
 */
int position() {
    int curLev = lev;

    for (int i = tx; i > 0; i--) {
        if (table[i].kind == 3 && table[i].level == curLev - 1)
            curLev--;

        if (table[i].level > curLev)
            continue;

        if (strcmp(table[i].name, curToken.name) == 0)
            return i;
    }
    return 0;
}

/**
 * error：
 * 作用：使用Switch完成不同错误的打印，比起ifelse更适合选项多的情况
 */
void error(int errorCase) {
    switch (errorCase) {
        case 1:
            printf("Error 1: ");
            printf("Period(.) expected in end of program\n");               //program不以句号结尾
            break;
        case 2:
            printf("Error 2: ");
            printf("Level is larger than the maximum allowed lexicographical levels!\n");   //层数过大
            break;
        case 3:
            printf("Error 3: ");
            printf("Semicolon(;) missing in constDeclaration.\n");     //常量声明部分缺少;
            break;
        case 4:
            printf("Error 4: ");
            printf("Semicolon(;) missing in varDeclaration.\n");        //变量声明部分缺少;
            break;
        case 5:
            printf("Error 5: ");
            printf("Identifier missing in constDefination.\n");         //常量定义缺少标识符
            break;
        case 6:
            printf("Error 6: ");
            printf("Use = instead of := in constDefination.\n");
            break;
        case 7:
            printf("Error 7: ");
            printf("Constant not assigned in constDefination.\n");      //常量定义未赋值
            break;
        case 8:
            printf("Error 8: ");
            printf("Constant not assigned by num in constDefination.\n");    //常量定义赋值的不是整数
            break;
        case 9:
            printf("Error 9: ");
            printf("Identifier missing in varDefination.\n");               //变量定义缺少标识符
            break;
        case 10:
            printf("Error 10: ");
            printf("identsym not find in table in assignment.\n");          //赋值语句中变量没有在表中找到
            break;
        case 11:
            printf("Error 11: ");
            printf("identsym in assignment must be var.\n");                //赋值语句中必须为变量
            break;
        case 12:
            printf("Error 12: ");
            printf("becomessym not find in assignment.\n");                 //赋值语句中没有:=
            break;
        case 13:
            printf("Error 13: ");
            printf("identsym not find in callProcedure.\n");                //过程调用必须有过程名
            break;
        case 14:
            printf("Error 14: ");
            printf("identsym not find in table in callProcedure.\n");       //过程名没有找到
            break;
        case 15:
            printf("Error 15: ");
            printf("identsym called must be procedure in callProcedure().\n");                 //调用的过程不是过程
            break;
        case 16:
            printf("Error 16: ");
            printf("then not find in conditionStatement().\n");                //条件语句中没有then
            break;
        case 17:
            printf("Error 17: ");
            printf("end not find in compoundStatement().\n");                   //复合语句中没有end
            break;
        case 18:
            printf("Error 18: ");
            printf("do not find in loopStatement().\n");                        //循环语句中没有找到do
            break;
        case 19:
            printf("Error 19: ");
            printf("identifier not find in identifier().\n");                   //identifier()没有标识符
            break;
        case 20:
            printf("Error 20: ");
            printf("( not find in writeStatement().\n");                        //写语句中没找到(
            break;
        case 21:
            printf("Error 21: ");
            printf(") not find in writeStatement().\n");                        //写语句中没找到)
            break;
        case 22:
            printf("Error 22: ");
            printf("identifier is not find in table in identifier().\n");       //identifier()中标识符查表没有找到
            break;
        case 23:
            printf("Error 23: ");
            printf("identifier is not var in identifier().\n");                 //identifier()标识符不是var
            break;
        case 24:
            printf("Error 24: ");
            printf("( not find in readStatement().\n");                         //读语句中没有(
            break;
        case 25:
            printf("Error 25: ");
            printf(") not find in readStatement().\n");                         //读语句中没有)
            break;
        case 26:
            printf("Error: 26 ");
            printf("relationSwitch not find in condition().\n");                //条件中没有关系运算符
            break;
        case 27:
            printf("Error: 27 ");
            printf("identsym not find in table in factor().\n");                //因子 标识符没有在表中
            break;
        case 28:
            printf("Error: 28 ");
            printf("identsym in factor() cannot be procedure.\n");              //因子 标识符不能为过程
            break;
        case 29:
            printf("Error: 29 ");
            printf(") not find in factor().\n");              //因子 )没有
            break;
        case 30:
            printf("Error: 30 ");
            printf("factor() cannot be right.\n");              //因子 不匹配
            break;
        case 31:
            printf("Error: 31 ");
            printf("identsym not find in procedureHead().\n");              //过程头中标识符找不到
            break;
        case 32:
            printf("Error: 32 ");
            printf("; not find in procedureHead().\n");              //过程头中 ;找不到
            break;
        case 33:
            printf("Error: 33 ");
            printf("; not find in procedureDeclaration().\n");              //过程说明部分 ;找不到
            break;
        default:
            break;
    }
    //stops program when error occurs
    printf("%d\t%s\n", curToken.tokenID, strPrint[curToken.tokenID]);
    exit(1);
}

parse.h:

//
// Created by csh on 2024/10/28 in shangDongUniversity
//

// 使用宏防止头文件重复包含
#ifndef COMPILE_PARSE_H
#define COMPILE_PARSE_H

// 引入其他定义的头文件 "data.h"（假定该头文件定义了相关的数据结构或常量）
#include "data.h"

/*
 * 该结构体用于存储符号表项。
 * 符号表项有三种类型：
 * - 常量（const）：存储常量的值。
 * - 变量（var）：存储变量的标识符及其在内存中的位置。
 * - 过程（proc）：存储过程的标识符及相关信息。
 */
struct symbol
{
    int kind;       // 表示符号的类型：
    // const = 1, var = 2, proc = 3
    char name[12];  // 符号名称，最多 11 个字符
    int val;        // 常量值或数字（对于常量符号有效）
    int level;      // 程序的层次（L，通常表示嵌套的作用域层级）
    int addr;       // 地址 addr（对于变量，表示变量的内存地址）
};

// 以下是函数声明部分，涉及到编译过程中的不同功能模块

// 主程序入口点
void program();             // 程序的入口，开始解析整个程序

// 分程序块的解析
void block();               // 解析分程序块（如函数或过程的定义部分）

// 常量声明部分的解析
void constDeclaration();    // 解析常量声明部分

// 常量定义的解析
void constDefinition();     // 解析常量定义，如常量的名字和值

// 变量声明部分的解析
void varDeclaration();      // 解析变量声明部分

// 变量定义部分的解析
void varDefinition();       // 解析变量定义，包括变量名和初始值

// 过程声明部分的解析
void procedureDeclaration();// 解析过程声明部分

// 过程首部的解析
void procedureHead();       // 解析过程的头部（如过程名、参数等）

// 一般语句的解析
void statement();           // 解析一般语句

// 条件语句的解析
void condition();           // 解析条件表达式

// 表达式的解析
void expression();          // 解析表达式（包括算术运算等）

// 项的解析（如乘除法）
void term();                // 解析表达式中的项（如乘除法运算）

// 因子的解析（如数字、变量、括号表达式等）
void factor();              // 解析表达式中的因子（如常量、变量或括号内的表达式）

// 赋值语句的解析
void assignment();          // 解析赋值语句

// 过程调用语句的解析
void callProcedure();       // 解析过程调用语句

// 条件语句的解析（if-else 语句）
void conditionStatement();  // 解析条件语句（如 if-else）

// 复合语句的解析（复合语句包含多个语句块）
void compoundStatement();   // 解析复合语句（多个语句组合在一起）

// 循环语句的解析（如 while 或 for 循环）
void loopStatement();       // 解析循环语句（如 while、for）

// 输出语句的解析
void writeStatement();      // 解析输出语句（如 print）

// 输入语句的解析
void readStatement();       // 解析输入语句（如 read）

// 解析标识符（如变量名、常量名、过程名等）
void identifier();          // 解析标识符（用于区分变量、常量、过程等）

//
// 以下是符号表和错误处理等辅助函数的声明
//

// 将一个符号（如常量、变量或过程）加入符号表中
void enter(int kind);       // 向符号表中添加一个符号

// 错误处理函数，根据错误代码进行错误报告
void error(int errorCase);  // 错误处理函数

// 生成指令并输出，通常用于代码生成阶段
void emit(ins_type ins, int l, int m); // 生成指令，发射（emit）机器代码

// 获取当前符号在符号表中的位置
int position();             // 获取符号表中符号的位置

// 获取下一个输入的记号（token）
void getNextToken();        // 获取下一个记号

// 输出一个空格或换行（用于格式化输出）
void printBlank();          // 打印空格或换行

#endif // COMPILE_PARSE_H