编译原理语法分析器实验

语法分析器的设计 一、实验内容 语法分析程序用 LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用 LL(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST 集合，每个非终结符号的FOLLOW 集合，以及每个规则的SELECT 集合，并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空，如果是，则输入文法符合 LL(1)文法，可以进行分析。 对于文法： G[E]: E->E+T|T T->T*F|F F->i|(E) 分析句子 i+i*i 是否符合文法。 二、基本思想 1、语法分析器实现 语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。 语法分析程序的流程图如图 5-4 所示。 该程序可分为如下几步： （1）读入文法 （2）判断正误 （3）若无误，判断是否为 LL(1)文法 （4）若是，构造分析表； （5）由句型判别算法判断输入符号串是为该文法的句型。 三、核心思想 该分析程序有 15 部分组成： （1）首先定义各种需要用到的常量和变量； 开始 读入文法 有效？ 判断句型 报错 结束 语法分析程序流程图 是 LL(1) 文法？ （2）判断一个字符是否在指定字符串中； （3）读入一个文法； （4）将单个符号或符号串并入另一符号串； （5）求所有能直接推出&的符号； （6）求某一符号能否推出‘ & ’； （7）判断读入的文法是否正确； （8）求单个符号的FIRST； （9）求各产生式右部的FIRST； （10）求各产生式左部的FOLLOW； （11）判断读入文法是否为一个LL(1)文法； （12）构造分析表 M； （13）句型判别算法； （14）一个用户调用函数； （15）主函数； 下面是其中几部分程序段的算法思想： 1、求能推出空的非终结符集 Ⅰ、实例中求直接推出空的empty 集的算法描述如下： void emp(char c){ 参数 c 为空符号 char temp[10];定义临时数组 int i; for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为 1, then 将该条产生式左部符号保存在临时数组 temp 中 将临时数组中的元素合并到记录可推出&符号的数组 empty 中。 } Ⅱ、求某一符号能否推出'&' int _emp(char c) { //若能推出&，返回 1；否则，返回 0 int i...