北邮-语法分析实验报告

编译原理 语法分析实验报告 by 坏学长 2 一、 实验题目和要求 题目：语法分析程序的设计与实现。 实验内容：编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达 式由如下的文法产生。 numEidFFT|)(/*| 实验要求：在对输入表达式进行分析的过程中，输出所采用的产生式。 方法 1：编写递归调用程序实现自顶向下的分析。 方法 2：编写 LL(1)语法分析程序，要求如下。 (1) 编程实现算法 4.2，为给定文法自动构造预测分析表。 (2) 编程实现算法 4.1，构造 LL(1)预测分析程序。 方法 3：编写语法分析程序实现自底向上的分析，要求如下。 (1) 构造识别所有活前缀的 DFA。 (2) 构造 LR 分析表。 (3) 编程实现算法 4.3，构造 LR 分析程序。 方法 4：利用 YACC 自动生成语法分析程序，调用 LEX 自动生成的词法分析程序。 二、 程序设计及步骤： 此次实验使用第一种方法：递归调用预测分析 1. 提取左公因子及消除左递归： E-TE； E-EE E- E-+T E-T T-FT T-TT T- T-*F T-/F F-id E-(E) E-num 2. 做状态转换图并化简： 4 3. 程序实现分析 根据上图产生式，读入字符串并以$结尾，根据字符串情况分别采取不同的过 程，为每个过程编写子程序，并返回是否成功，1 代表成功， -1 代表失败，当 字符串格式错误时，最终 E 过程返回 -1，不能被接收。 读取一个字符，根据状态转换图的自动机进行转换状态，并判断是否正确并 读取下一个字符。直到读取$，过程未产生错误（返回值为 1） ，则表达式被接 收，语法分析结束。 4. 源代码： #include #include #include #include using namespace std; int i; 全局变量，标志当前读到的字符位置 int E(string str,int / E 产生式过程解析 int T(string str,int /T 产生式过程解析 int F(string str,int /F 产生式过程解析 int main() coutTEn“; coutEEn“; coutn“; cout+Tn“; cout-Tn“; coutFTn“; coutTTn“; coutn“; cout*Fn“; cout/Fn“; coutidn“; cout(E)n“; coutnumn“; coutstr; str=str+“$“; /为字符串增加$作为结束标识符 coutTEn“; if(stri!=$) /读到$结束读入 if(T(str,i)=1) result=1; coutEEn“; /i+; if(stri=+|stri=-) 6 cout+Tn“; else cout-Tn“; i+; result=E(str,i); else if(stri=$|stri=) coutn“; result=1; else result=-1; else result=-1; else result=1; return result; int T(string str,int coutFTn“; if(F(str,i)=1) coutTTn“; result=1; /i+; if(stri=*|stri=/) cout*Fn“; else cout/Fn“; i+; result=T(str,i); else if(stri=$|stri=+|stri=-|stri=) /coutn“; result=1; else result=-1; else result=-1; return result; int F(string str,int if(stri=() cout(E)n“; i+; if(E(str,i)=1) / i+; if(stri=) coutid|numn“; else result=-1; i+; return result; 5. 实验结果： 10 6. 实验总结： 实验过程中，原来看到题目无从下手，翻阅书本知识，先把产生式消除左递 归和提取左公因子，才能进行递归预测分析的程序实现，根据原产生式，作 出化简的状态转换图，递归的思路就变得清晰了。 分别为每个过程做一个程序分析，然后通过递归实现不同过程的调用。这种 12 方法思路清晰且代码量较少。 在代码处理过程中，怎么判断输入错误并终止分析？后来想到用一个 result 标志成功与否，通过不同步骤处返回 result，判断是否成功，在递归调用中， 如果有一处错误，result 通过层层返回值，分析即刻得到终止。 关于空转移，读取的字符可能是错误字符也可能是下一个过程的正确字符， 需要解决这个矛盾。这里用到了 FOLLOW 集的一些思想，如果某过程需要进 行