实验三 语法分析程序 （一）学习经典的语法分析器 一、实验目的 学习已有编译器的经典语法分析源程序。 二、实验任务 阅读已有编译器的经典语法分析源程序，并测试语法分析器的输出。 三、实验内容 （1）选择一个编译器，如：TINY，其它编译器也可（需自备源代码）。 （2）阅读语法分析源程序，加上你自己的理解。尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。TINY语言请参考《编译原理及实践》第3.7节。对TINY语言要特别注意抽象语法树的定义与应用。 （3）测试语法分析器。对TINY语言要求输出测试程序的字符形式的抽象语法树。（手工或编程）画出图形形式的抽象语法树。 TINY语言： 测试用例一：sample.tny。

（二）实现一门语言的语法分析器 一、实验目的 通过本次实验，加深对语法分析的理解，学会编制语法分析器。 二、实验任务 用C或C++语言编写一门语言的语法分析器。 三、实验内容 （1）语言确定：C－语言，其定义在《编译原理及实践》附录A中。也可选择其它语言，不过要有该语言的详细定义（可仿照C－语言）。一旦选定，不能更改，因为要在以后继续实现编译器的其它部分。鼓励自己定义一门语言。也可选择TINY语言，但需要使用与TINY现有语法分析代码不同的分析算法实现，并在实验报告中写清原理。 （2）完成C－语言的BNF文法到EBNF文法的转换。通过这一转换，消除左递归，提取左公因子，将文法改写为LL（1）文法，以适用于自顶向下的语法分析。规划需要将哪些非终结符写成递归下降函数。 （3）为每一个将要写成递归下降函数的非终结符，如：变量声明、函数声明、语句序列、语句、表达式等，定义其抽象语法子树的形式结构，然后定义C－语言的语法树的数据结构。 （4）仿照前面学习的语法分析器，编写选定语言的语法分析器。可以自行选择使用递归下降、LL(0)、LR(0)、SLR、LR(1)中的任意一种方法实现。 （5）准备2~3个测试用例，测试并解释程序的运行结果。

阅读已有编译器的经典语法分析源程序，并测试语法分析器的输出。 （1）选择一个编译器，如：TINY，其它编译器也可（需自备源代码）。 （2）阅读语法分析源程序，加上你自己的理解。尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。TINY语言请参考《编译原理及实践》第3.7节。对TINY语言要特别注意抽象语法树的定义与应用。 （3）测试语法分析器。对TINY语言要求输出测试程序的字符形式的抽象语法树。（手工或编程）画出图形形式的抽象语法树。 TINY语言： 测试用例一：sample.tny。

我选择的经典词法分析程序是TINY源码，下面我就变量作用介绍，函数功能，语法树构建方法以及样例测试这4个方面对TINY词法分析器进行心得总结：

在头文件globals.h中我们定义了一些节点类型的变量和结构，T I N Y有两种基本的结构类型：语句和表达式。语句共有 5类（ i f语句、 r e p e a t语句、 a s s i g n语句、 r e a d语句和w r i t e语句） ，表达式共有 3类（算符表达式、常量表达式和标识符表达式） 。 因此，语法树节点首先按照它是语句还是表达式来分类，接着根据语句或表达式的种类进行再次分类。树节点最大可有 3个孩子的结构（仅在带有 e l s e部分的i f语句中才需要它们） 语句通过同属域而不是使用子域来排序。 ①节点类型：

②表达式类型：

③表达式种类：

④语法树的节点定义： 树的结点种类NodeKind分为StmtK和ExpK两类，两类又有各自的子类。在语法树中标明种类有利于代码生成，当遍历语法树检测到特定类型时就可以进行特定的处理。treeNode结构为指向孩子和兄弟的节点。 语句通过同属域而不是子域来排序，即由父亲到他的孩子的唯一物理连接是到最左孩子的。孩子则在一个标准连接表中自左向右连接到一起，这种连接称作同属连接,用于区别父子连接。

三.函数功能 （1）在文件parse.c中我们生命并且实现了这样的一些函数，这些函数将会帮助构建我们的语法树： 函数 功能

（2）下面我会对几个关键的函数做详细介绍：

①token是一个静态全局变量这个是主循环。在循环中匹配分号，再匹配新行（statement）

②然后在statement函数中根据首token的类别通过switch case将解析交给match函数：用来判断当前token是否与当前表达式的下一个值匹配

③比如：对if语句来说，if_stmt : IF exp THEN stmt_seq END 在句法的严格限制下，if，then，end三个关键字是必须匹配的，match进行“匹配”确认，错误就报错，成功则运行词法分析读取下一个token

④总共有五种语句，就不一个个详细分析了。 四.语法树构建方法 （1）用递归下降法写parser程序的过程，就是把图中的文法用程序翻译出来。每个文法都对应一个处理该文法的子例程

（2）比较麻烦的是对左递归的处理，递归下降和LL（1）使用不同的方法来处理左递归的问题。递归下降使用拓展巴克斯范式（EBNF）把左递归写成其他形式，类似exp->exp addop term | term这样的表达式是左递归的，并不好直接用递归下降程序来翻译所以通过改写成 exp->term { addop term } 可以方便表示（大括号( { } )内包含的为可重复0至无数次的项。）

exp -> exp + num|num #这里就是递归，我们在定义“exp”这个概念，而它的定义里面又用到了自己本身！ exp -> term { addop term } #都是匹配形如 num (+ num) (+ num) … 的串 。在数学上，这两个表达式是等价的。

（3）对应的exp匹配程序如下：

五.样例测试分析 现在需要将语法树结构的描述用图形表示出来，并且画出示例程序的语法树。为了做到这 一点，我们使用矩形框表示语句节点，用圆形框或椭圆形框表示表达式节点。语句或表达式的类型用框中的标记表示，额外的属性在括号中也列出来了。属性指针画在节点框的右边，而子指针则画在框的下面。我们还在图中用三角形表示额外的非指定的树结构，其中用点线表示可能出现也可能不出现的结构。语句序列由同属域连接（潜在的子树由点线和三角形表示） 。则该图如下：

(1)if 语句（带有3个可能的孩子）如下所示 (2)repeat 语句有两个孩子。第1个是表示循环体的语句序列，第 2个是一个测试表达式 (3)assign 语句有一个表示其值是被赋予的表达式的孩子（被赋予的变量名保存在语句节点中）

(4)write 语句也有一个孩子，它表示要写出值的表达式： (5)算符表达式有两个孩子，它们表示左操作数表达式和右操作数表达式：

其他所有的节点（ r e a d语句、标识符表达式和常量表达式）都是叶子节点。 最后准备显示一个 T I N Y程序的树。程序清单 3 - 3中有来自第1章计算一个整型阶乘的示例程序，它的语法树在图3 - 6中。

我们将会构建出如图所示的语法树：

（1）语言确定： C－语言，其定义在《编译原理及实践》附录A中。也可选择其它语言，不过要有该语言的详细定义（可仿照C－语言）。一旦选定，不能更改，因为要在以后继续实现编译器的其它部分。鼓励自己定义一门语言。也可选择TINY语言，但需要使用与TINY现有语法分析代码不同的分析算法实现，并在实验报告中写清原理。 （2）完成C－语言的BNF文法到EBNF文法的转换： 通过这一转换，消除左递归，提取左公因子，将文法改写为LL（1）文法，以适用于自顶向下的语法分析。规划需要将哪些非终结符写成递归下降函数。 （3）为每一个将要写成递归下降函数的非终结符如：变量声明、函数声明、语句序列、语句、表达式等，定义其抽象语法子树的形式结构，然后定义C－语言的语法树的数据结构。 （4）仿照前面学习的语法分析器，编写选定语言的语法分析器。可以自行选择使用递归下降、LL(0)、LR(0)、SLR、LR(1)中的任意一种方法实现。 （5）准备2~3个测试用例，测试并解释程序的运行结果。

我在实验3中自定义了一门语言Quary，Quary语言的定义是一个很有挑战性的过程，我模仿C—和python成功定义了它（也许并不完备，随着实验的推进我会一一完善），定义语言的过程中，我对BNF语法有了新的了解和学习。 关于语法和语义，我将仿照C-的定义给出Quary语言的BNF语法：

程序由声明的列表(或序列)组成，声明可以是函数或变量声明，顺序是任意的。至少必须有一个声明。接下来是语义限制(这些在C中不会出现)。所有的变量和函数在使用前必须声明(这避免了向后backpatching引用)。程序中最后的声明必须是一个函数声明，名字为main。注意，Quary缺乏原型，因此声明和定义之间没有区别

变量声明或者声明了简单的整数类型int / 字符类型char变量，或者是基类型为整数/字符的数组变量，索引范围从0到 NUM-1。注意，在一个变量声明中，只能使用类型 指示符int/char。void用于函数声明(参见下面)，也要注意，每个声明只能声明一个变量。

函数声明由返回类型指示符、标识符以及在圆括号内的用逗号分开的参数列表组成，后面 跟着一个复合语句，是函数的代码。如果函数的返回类型是void，那么函数不返回任何值(即 是一个过程)。函数的参数可以是void(即没有参数)，或者一列描述函数的参数。参数后面跟 着方括号是数组参数，其大小是可变的。简单的整型参数由值传递。数组参数由引用来传递 (也就是指针)，在调用时必须通过数组变量来匹配。注意，类型“函数”没有参数。一个函数 参数的作用域等于函数声明的复合语句，函数的每次请求都有一个独立的参数集。函数可以是递归的(对于使用声明允许的范围)。

复合语句由用: end围起来的一组声明和语句组成。复合语句通过用给定的顺序执行语句 序列来执行。局部声明的作用域等于复合语句的语句列表，并代替任何全局声明。

注意声明和语句列表都可以是空的(非终结符empty表示空字符串，有时写作)

表达式语句有一个可选的且后面跟着分号的表达式。这样的表达式通常求出它们一方的结 果。因此，这个语句用于赋值和函数调用。

if语句有通常的语义：表达式进行计算；非0值引起第一条语句的执行；0值引起第二条语 句的执行，如果它存在的话。这个规则导致了典型的悬挂else二义性，可以用一种标准的方法解决：else部分通常作为当前if的一个子结构立即分析(“最近嵌套”非二义性规则)。 同样的他们用: end包裹起来。

while语句是Quary中的一种重复语句。它重复执行表达式，并且如果表达式的求值为非0， 则执行语句，当表达式的值为0时结束。

forEach语句是Quary中遍历列表数组的语句，它重复执行表达式，顺序遍历列表直到到达列表尾结束。

返回语句可以返回一个值也可无值返回。函数没有说明为void就必须返回一个值。函数 声明为void就没有返回值。return引起控制返回调用者(如果它在main中，则程序结束)。

表达式是一个变量引用，后面跟着赋值符号(等号)和一个表达式，或者就是一个简单的表 达式。赋值有通常的存储语义：找到由var表示的变量的地址，然后由赋值符右边的子表达式进行求值，子表达式的值存储到给定的地址。这个值也作为整个表达式的值返回。var是简单的(整型)变量或下标数组变量。负的下标将引起程序停止(与C不同)。然而，不进行下标越界检查。 var表示Quary比C的进一步限制。在C中赋值的目标必须是左值(l-value)，左值是可以由许多操作获得的地址。在Quary中唯一的左值是由var语法给定的，因此这个种类按照句法进行检查，代替像C中那样的类型检查。故在Quary中指针运算是禁止的。

简单表达式由无结合的关系操作符组成(即无括号的表达式仅有一个关系操作符)。简单表 达式在它不包含关系操作符时，其值是加法表达式的值，或者如果关系算式求值为ture，其值为1，求值为false时值为0。

加法表达式和项表示了算术操作符的结合性和优先级。符号表示整数除；即任何余数都被 截去。

因子是围在括号内的表达式；或一个变量，求出其变量的值；或者一个函数调用，求出函 数的返回值；或者一个NUM，其值由扫描器计算。数组变量必须是下标变量，除非表达式由单个ID组成，并且以数组为参数在函数调用中使用(如下所示)。

函数调用的组成是一个ID(函数名)，后面是用括号围起来的参数。参数或者为空，或者由 逗号分割的表达式列表组成，表示在一次调用期间分配的参数的值。函数在调用之前必须声明，声明中参数的数目必须等于调用中参数的数目。函数声明中的数组参数必须和一个表达式匹配，这个表达式由一个标识符组成表示一个数组变量。最后，上面的规则没有给出输入和输出语句。在C－的定义中必须包含这样的函数，因为 与C不同，C－没有独立的编译和链接工具；因此，考虑两个在全局环境中预定义的函数，好像它们已进行了声明：

input函数没有参数，从标准输入设备(通常是键盘)返回一个整数值。print函数接受 一个整型参数或整型数组或字符参数或字符数组，其值和一个换行符一起打印到标准输出设备(通常是屏幕)。

递归下降使用拓展巴克斯范式（EBNF）把左递归写成其他形式，类似exp->exp addop term | term这样的表达式是左递归的，并不好直接用递归下降程序来翻译所以通过改写成 exp->term { addop term } 可以方便表示（大括号( { } )内包含的为可重复0至无数次的项。）

对应的exp匹配程序如下：

我们只需要将文法定义中的左递归BNF按照规则exp->exp addop term | term改写成 exp->term { addop term } 进行替换即可。

对于抽象语法树的结构，我仿照TINY的语法分析器来定义它。在头文件globals.h中我们定义了一些节点类型的变量和结构，Quary

1.变量和结构 （1）有两种基本的结构类型：语句StmtK和表达式ExpK。 （2）语句共有 5类（ i f语句、 while语句、 assign语句、 Input语句和PrintK语句） （3）表达式共有 3类（算符表达式OpK、常量表达式ConstK和标识符表达式IdK） 。

因此，语法树节点首先按照它是语句还是表达式来分类，接着根据语句或表达式的种类进行再次分类。树节点最大可有 3个孩子的结构（仅在带有 e l s e部分的i f语句中才需要它们） 语句通过同属域而不是使用子域来排序。 节点类型：

表达式类型：

表达式种类：

语法树的节点定义： 树的结点种类NodeKind分为StmtK和ExpK两类，两类又有各自的子类。在语法树中标明种类有利于代码生成，当遍历语法树检测到特定类型时就可以进行特定的处理。treeNode结构为指向孩子和兄弟的节点。 语句通过同属域而不是子域来排序，即由父亲到他的孩子的唯一物理连接是到最左孩子的。孩子则在一个标准连接表中自左向右连接到一起，这种连接称作同属连接,用于区别父子连接。

2.函数功能 （1）在文件parse.c中我们生命并且实现了这样的一些函数，这些函数将会帮助构建我们的语法树： 函数 功能

(1)实现思路： 在编写语法分析器时，我选用的方法是递归下降法，基本思路是把图中的文法用程序翻译出来。每个文法都对应一个处理该文法的子例程。每次用stmt_sequence在循环中匹配新的行，然后用match匹配语句开头的第一个字段，判断不同的文法，交给不同的文法处理程序处理。其处理程序的结构关系图如下：

经过statement匹配的语句，交给不同的文法处理器处理，包括了if_stmt, while_stmt, forEach_stmt, assign_stmt, input_stmt, print_stmt, 如果匹配错误将会触发异常。在每个语法处理程序中，包含了表达式节点，这个时候语法处理程序将会有express匹配表达式，表达式采用递归的形式构建，按照逻辑顺序，会先后由逻辑表达式节点，大小判断节点，加减法节点，乘除法节点，项节点处理，然后每一个项又可能有新的express组成，这样循环递归执行，直到表达式匹配到表达式类型（expression）算符表达式、常量表达式和标识符表达式{OpK,ConstK,IdK}终止。

(2)下面我会对几个关键的函数做详细介绍： ①stmt_sequence函数在循环中匹配分号，再匹配新的行

② token是一个静态全局变量这个是主循环。在循环中匹配分号，再匹配新行（statement）

③ 然后在statement函数中根据首token的类别通过switch case将解析交给match函数：用来判断当前token是否与当前表达式的下一个值匹配

④ 对if语句来说，if_stmt : IF exp THEN stmt_seq END 在句法的严格限制下，if，then，end三个关键字是必须匹配的，match进行“匹配”确认，错误就报错，成功则运行词法分析读取下一个token

⑤对于WHILE循环语句，他总是先匹配保留字WHILE，然后再匹配接着他的”:”， 然后匹配执行语句，他只有一个子节点，递归使用stmt_sequenc(), 最后匹配终结符号end。

⑥对于赋值语句语句，他总是先设置属性name为当前的串，然后匹配一个新的ID和=号，最后通过express匹配子节点表达式。

⑦ 输入输出语法类似，首先匹配保留字，然后添加name属性，对于PRINT，子节点点则是一个表达式。

⑦下面是表达式的处理，表达式处理具有高度的一致性，表达式采用递归的形式构建，按照逻辑顺序，会先后由逻辑表达式节点，大小判断节点，加减法节点，乘除法节点，项节点处理，然后每一个项又可能有新的express组成，这样循环递归执行，直到表达式匹配到表达式类型（expression）算符表达式、常量表达式和标识符表达式{OpK,ConstK,IdK}终止。如下图：

上面是一大小表达式的例子，剩下的大小表达式compareExpress，加减法表达式simple_exp，乘除法表达式term与此类似。

⑧项的处理： 一个表达式expresss可能由子表达式， ID或NUM组成，也就是ENBF表达式(expression) | NUM | ID ，因此我们可以这样处理项，判断当前的串如果是一个NUM，那么新建一个子节点，将它的val设置为当前串的值; 如果当前串是ID，那么新建节点设置属性为当前串; 如果当前串是( 那么要匹配子表达式调用函数express，然后匹配)号。

经过上面的处理，语法树就能成功构建起来，为了输出语法树，我们还需要借助工具类中的函数printTree将节点打印出来，基本思路很简单，对于当前的一个节点，我们要先判断他的类型，如果是语句类型，直接打印;如果是表达式类型，那么打印属性。然后扩展所有的子节点。

我共设置了三组样例，下面我将会对他们一一分析: （1）样例1： 下图左侧样例1是一个简单的if条件语句测试，首先使用input输入一个值x，然后用对x进行判断，如果x小于0,那么facts=0；如果x> 2, 那么facts=1, 如果x > 3, 那么facts=2， 否则facts=3。最后将facts用print打印出来。

上图右侧是样例1的执行结果，首先语法树的第一层应该有两个节点，也就是input和IF，然后IF语句内部则有两个分支，一个是从fact=0到end，另外一个是else部分，在地一个分支内部存在一个IF语句，同样的，IF语句内部又有一个IF语句嵌套，因此有三层IF，然后处理Else分支，在Else分支中只有两个语句，一个是赋值语句fact=3,相应的语法树结果为Assign to: fact，Const: 3 最后是Print语句，内部是一个表达式ID ：fact，观察测试结果，符合预期。

（2）样例2： 下图左侧样例2是一个while-if-else分支测试，程序求和0~10的平方和,输入一个值,判断sum和他的大小关系，下面是测试结果：

观察测试代码，语法树第一层有4个语句节点，分别是Input，Assign，Assign，While，If，然后我们看到重点位置while循环，在while循环内部有3条语句，因此有三个语句节点，他们分别是赋值语句Assign，Assign，打印语句Print，在while语句的后面，我们还有一个表达式节点，他用于确定循环执行的条件，Op: \ Id: sum \ Id: y ，接下来就是else分支，Print \ Const: 1,观察测试结果，符合分析预期。

（3）样例3： sample3.qy 测试样3, 它计算一个斐波拉契数列Fibonacci的值，输入一个数x，程序计算Fibonacci(x) 并且打印，下面我将仔细分析语法树的结果。

观察测试代码，语法树第一层有2个语句节点，分别是Input，If。第一个节点Input: n输入n的值，然后来到IF节点，他只是简单判断n