编译原理作业与实验，正整数计算解释器+源代码+文档说明

## 1. 语言说明 本语法分析器中实现了**函数定义**、**函数调用**、**变量定义**、**if条件语句**、**if-else条件语句**、**while循环语句**、**for循环语句**、**函数调用**、**多级指针**、**多维数组**、**代码块**、**return**语句。 - 在运算符上：支持C98标准中定义的所有运算符，并正确处理了左右结合性以及优先级的问题。 - 在类型修饰符上：支持C98标准中定义的所有类型修饰符。 - 在类型上：支持C98标准所有的类型。 语言描述如下： *注：以下所说的**符号**指**Symbol**，而非**Operator**。* ### 1.1. 表达式 在处理表达式之前，首先需要考虑运算符，根据cppreference网站上查阅的资料，C语言的运算符如下：  表达式中需要注意的是，C语言中还有一元运算符。例如`!`、`~`、`++`、`--`，甚至还有`+`和`-`也可以作为一元运算符使用。此外，对于同样的符号也有左右结合的情况。归纳后我们定义以下文法： ``` <可用数值> ::= <子表达式> | <常量> | <符号调用> | <一元运算结果> <一元运算结果> ::= (<运算符> <表达式>) | (<表达式> <运算符>) <表达式> ::= <可用数值> | (<运算符> <表达式>) ``` 这里尽管没有消除左递归，是由于这里符号较多，我们如果采用一条条文法表示的方法内容非常长，而编程上亦是如此。 因此在我的程序中尽管大的部分采用了递归下降，但**处理表达式**采用的是根据结合性和优先级构建二叉分析树的方法：每个非叶节点都是运算符。然后将表达式变成一颗二叉树进行处理。这样的做法是顺序扫描符号的，因此不会导致程序陷入死循环。 具体方法详见实验报告的第二部分。 ### 1.2. 类型 ``` <类型> ::= {"void","int","long","short","float","double","char","unsigned","signed","struct","union","auto","enum"} <识别类型> ::= (<'struct'>|<'union'> <'用户自定义类型'>) | <类型> ``` ### 1.3. 类型修饰符 ``` <类型修饰符> ::= {"const","static","volatile","register","inline","extern","restrict"} <多个类型修饰符> ::= <空集> | <类型修饰符> <多个类型修饰符> ``` *注：考虑到后续使用的多个类型修饰符也可以为空* ### 1.4. 指针 ``` <指针> ::= <空集> | <'*'> <指针> ``` *注：考虑到后续使用时可以为空* ### 1.5. 数组符号定义 ``` <一维数组> ::= <'['> <表达式> <']'> <数组> ::= <空集> | <一维数组> <数组> ``` ### 1.6. 变量定义 ``` <单个变量定义> ::= <指针> <符号名> <数组> (<空集>|<'='><表达式>) <多个变量定义> ::= <单个变量定义> (<空集>|<','><多个变量定义>) <变量定义> ::= <多个类型修饰符> <识别类型> <指针> <多个变量> ``` ### 1.7. 函数定义 ``` <参数定义> ::= <多个类型修饰符> <指针> <参数名> (<空集>|<'='><表达式>) <多个参数定义> ::= <空集> | <参数定义> (<空集>|<','><多个参数定义>) <函数定义> ::= <多个类型修饰符> <指针> <函数名> <'('> <多个参数定义> <')'> <代码块> ``` ### 1.8. 符号声明语句 ``` <符号声明语句> ::= <变量定义> | <函数定义> ``` ### 1.9. 语句 ``` <语句> ::= <符号声明语句> | <表达式> | <if语句> | <while语句> | <for语句> | <return语句> | <'代码块'> <多条语句> ::= <空集> | (<语句><多条语句>) ``` ### 1.10. 代码块 ``` <代码块> ::= <'{'><多条语句><'}'> ``` ### 1.11. 符号调用 ``` <参数使用> ::= <表达式> (<空集>|<','><表达式>) <函数调用> ::= <函数符号><'('><参数使用><函数调用> <符号调用> ::= <除函数外的符号><数组> | <函数调用> ``` *注：符号中函数与其他符号已在实验一的词法分析阶段通过判断定义时其后是否有括号进行了预处理。* ### 1.12. if语句 ``` <if语句> ::= <if> <'('> <表达式> <')'> <代码块> (<空集>|<else><代码块>) ``` ### 1.13. for语句 ``` <for语句> ::= <for> <'('><表达式><';'><表达式><';'><表达式><')'> <代码块> ``` ### 1.14. while语句 ``` <while语句> ::= <'while'> <'('> <表达式> <')'> <代码块> ``` ## 2. 语法分析方法 在本程序中，主要的语法分析方法采用的是递归下降。但对于表达式的识别则采用了手动顺序构建二元运算二叉树的方法。 ### 2.1. 表达式的识别 首先，我们限定表达式转换为一颗二叉树，如下： <img src="img/2.png" alt="2" style="zoom:50%;" /> 这里，我们建立一颗这样的表达式二叉树，对于每颗子树（单节点的树除外），其根节点都是一个运算符，下接两个子表达式。 特别地：对于一元运算符，例如`i++`，我们采用左子树为`i`，而右子树为`NULL`的方式来表示。 然后，我们需要在每个运算符节点存储该运算符的优先级，在树中优先级问题简化为：这棵树要满足自下往上优先级单调不降（相等或上升）。这样，我们可以根据上一个节点所在的位置向上遍历这棵树找到合适的插入位置。 此外还要考虑结合律，由于C语言中一个优先级一定只有一种结合律，而仅有优先级相同的时候才需要考虑左结合还是右结合的问题，因此我们只需要维护一个表格，在识别到新符号的时候能够得到结合律即可。 而对于相邻两个运算符优先级相同的情况下，我们需要考虑左结合与右结合的问题。如果是右结合则直接替换上一次的节点，然后将上一次的节点作为左子节点；如果是左结合，我们需要找到同样优先级的最高点，然后替换它作为左子节点。并记录新节点的位置，在下一次读取到数值的时候插入在该节点的右子节点。 例如：对于`1+2*3`，分析树构造如下： <img src="img/3.png" alt="3" style="zoom:50%;" /> 归纳来说，将符号合并到分析树上按照以下流程： 1. 优先级相同，右结合：直接与上一次操作的节点结合 2. 优先级相同，左结合：从上一次操作的节点一直向上找到相同优先级的最高层，然后结合 3. 优先级不同且新符号优先级排名更高：直接与上一次操作的节点结合 4. 优先级不同且新符号优先级排名更低： 1. 向上能够找到优先级相同的地方：根据结合性确定链上的位置，若右结合在相等链的最低端，若左结合则在相等链的最顶端 2. 若向上不能找到优先级相同的地方：一直向上找到了第一个优先级大于的现在要插入运算符的节点，直接左结合 这一部分代码位于`src/grammar_parser.hpp:898`。 之后，根据前文提到的C语言运算符表我们可以发现，C语言中还存在同一运算符具有多种不同的意义的问题，这些意义下也有不同的优先级，这些运算符如下： | 优先级 | 运算符 | 意义 | 结合方向 | | ------ | ------ | -------- | -------- | | 2 | - | 一元减 | RL | | 4 | - | 减法 | LR | | 1 | -- | 后缀自减 | LR | | 2 | -- | 前缀字减 | RL | | 1 | ( | 函数调用 | LR | | 2 | ( | 转型 | RL | | 1 | ) | 函数调用 | LR | | 2 | ) | 转型 | RL | | 2 | * | 解引用 | RL | | 3 | * | 乘法 | LR | | 2 | & | 取址 | RL | | 8 | & | 逐位与 | LR | | 2 | + | 一元加 | RL | | 4 | + | 加法 | LR | | 1 | ++ | 后缀自增 | LR | | 2 | ++ | 前缀自增 | RL | 基于以上运算符，我们发现：这些相同的运算符结合方向都不一样。因此我们可以在程序中记录上一次所读取的类型属于数值还是符号（对于括