《mswova编译原理课程设计(语法分析程序)》由会员分享，可在线阅读，更多相关《mswova编译原理课程设计(语法分析程序)（24页珍藏版）》请在金锄头文库上搜索。
1、秋风清，秋月明,落叶聚还散,寒鸦栖复惊。 编编 译译 原原 理理 实实 验验 报报 告告 题目题目：对下面的文法对象，使用 c 语言构造它的预测分析程序；并任意给一算术表达式 进行分析测试 分析对象对象定义如下： 算术表达式项算术表达式+项算术表达式项 项因式项*因式 项因式 因式变量（算术表达式） 变量字母 字母A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z 实验日期实验日期：2005-6-15 至 2005-6-30指导教师指导教师： 吴取劲 班级班级：计算机 029 班学号学号：20029440913姓名姓名：陈 强 一、分析一、分
2、析 语法分析部分我们我们采用（）方法实现，采用（）方法实现语法发分析 要求文法满足以下要求： 一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号 集合有关，当有右部能=*=时则与其左部非终结符的后跟符号集合也有关，此外在产生 式中不存在左递归即经过压缩，无左递归，无回溯。它的基本思想是从左到右扫描源程序， 同时从识别符号开始生成句子的最左推导， 并只向前查看一个输入符号， 便能唯一确定应选 择的规则。 下面将确切地定义满足确定的自顶向下分析条件的文法即LL(1)文法及LL(1)文法的判 别并介绍如何对非LL(1)文法进行等价变换问题，也就是消除一个文法中的左递归和左公共
3、 因子。 注意：注意： 一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自 顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价 变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中 不含左递归和左公共因子，只是LL(1)文法的必要条件。 LL(1) 文法的定义（5 种定义） ： 一个文法符号串的开始符号集合定义如下： 定义定义 1. 设 G=(VT，VN，S，P)是上下文无关文法,是任意的文法符号串 ,FIRST() 是从推导出的串的开始符号的终结符集合。 。 。 。 FIRST()=a|=*=a
4、,aVT，,V*若=*=,则规定FIRST() 当一个文法中相同左部非终结符的右部存在能=*=的情况则必须知道该非终结符的 后跟符号的集合中是否含有其它右部开始符号集合的元素。 为此， 我们定义一个文法非终结 符的后跟符号的集合如下： 定义定义 2. 设 G=(VT，VN，S，P)是上下文无关 文法，AVN，S 是开始符号 FOLLOW(A)=a|S=*=A,且 aVT，aFIRST(),VT* ,V+ 若 S=*=A,且, 则#FOLLOW(A)。也可定义为：FOLLOW(A)=a|S=*= Aa,a VT 若有 S=*= A，则规定#FOLLOW(A) 这里我们用#作为输入串的结束符，或称
5、为句子括号，如：#输入串#。 定义定义 3. 给定上下文无关文法的产生式 A, AVN,V*, 若=,则 SELECT(A)=FIRST() 如果=*=，则 SELECT(A)=FIRST()FOLLOW(A)。FIRST()表示 FIRST()的非元素。 更进一步可以看出能够使用自顶向下分析技术必须使文法满足如下条件， 我们称满足条件的 文法为 LL(1)文法，其定义为： 定义定义 4. 一个上下文无关文法是 LL(1)文法的充分必要条件是： 对每个非终结符 A 的两个不同产生式，A, A,满足 SELECT(A)SELECT(A )=空,其中，不同时能. 定义定义 5. LL（1）文法也可
6、定义为: 一个文法 G 是 LL（1）的，当且仅当对于 G 的每一个非终结符 A 的任何两个不同产生 式 A|，下面的条件成立： FIRST（）FIRST()= 空,也就是和推导不出以某个相同的终结符 a 为首的 符号串；它们不应该都能推出空字 假若那么，FIRST（) FOLLOW（A） 空也就是，若则所能推出 的串的首符号不应在 FOLLOW(A)中。 二、算法二、算法 该程序可分为如下几步： （1）读入文法 （2）判断正误 （3）若无误，判断是否为 LL(1)文法 （4）若是，构造分析表； （5）由总控算法判断输入符号串是否 为该文法的句型。 根据下面 LL(1)文法，对输入串 w: (
7、i+i)*(i+i)+i*i 进行 LL(1)分析,要求如下： 1、先手工建立 LL(1)分析表； 2、分析输入串，判断是否是语法上正确的句子，并输出整个分析过程。 LL(1)文法 G 为： E TE E+TE| T FT T*FT| F (E)|id 是 LL(1)文法？ 判断句型报错 结束 分析算法： 输入：串 w 和文法 G 的分析表 M。 输出：如果 W 属于 L（G） ，则输出 W 的最左推导，否则报告错误。 方法：开始时，#S 在分析栈中，其中 S 是文法的开始符号，在栈顶；令指针 ip 指向 W#的 第一个符号；repeat 让 X 等于栈顶符号，a 为 ip 所指向的符号； i
8、f X 是终结符号或# then If X=a then 把 X 从栈顶弹出并使 ip 指向下一个输入符号 else error() else/*X 是非终结符号*/ if Mx,a=Xy1y2yk then begin 从栈中弹出 X；把 yk,yk-1,y1 压入栈，y1 在栈顶； 输出产生式 Xy1y2yk；end else error() until X=#/*栈空*/ 语法分析的流程算法语法分析的流程算法 三、设计目的：三、设计目的： （1）理解和掌握 LL(1)语法分析方法的基本原理；根据给出的 LL(1)文法，掌握 LL(1) 分析表的构造及分析过程的实现。 （2）掌握预测分析程
9、序如何使用分析表和栈联合控制实现 LL(1)分析。 四、实现环境和要求四、实现环境和要求 选择实习环境为 486 以上 CPU,4M 内存,TURBO C2.0 语言. 实现程序见附录. 具体的实现要求： （1）对输入文法，它能判断是否为 LL(1)文法，若是，则转（2） ；否则报错并终止； （2）输入已知文法，由程序自动生成它的 LL(1)分析表； （3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。 五、总结五、总结 上机前应做好准备即根据实习目的、要求和分析，选择相应的数据结构，使用语言 参照算法中的流程编写词法分析的程序 将编好的程序上机进行调试 注意调试的例子应有 词法正确
10、的，也应有词法错误的或是超出所选数据结构范围的 实验完成达到实习目的之后， 若尚有余力者， 可以对所选子集适当扩大或是增加相应功 能如：扩充界符和保留字数目；允许实型常数；进行词法错误检查；最大范围扩充 以至 PASCAL 语言所有字符的集合 通过这次程序设计，更加清楚透彻的明白了(1)分析法的过程，从而也比较熟练掌 握了自上而下语法分析的基本思想，此外，巩固了所学的数据结构的知识，自己所学的知识 能够联系起来，使得知识自成系统。在实现和调试时次采取模块化的思想，使得本次课程设 计比较顺利，增强了自己的信心，提高了自己的编程能力和动手能力以及独立分析问题、解 决问题的能力和综合运用所学知识的能
11、力。 附录附录 /* 预测分析程序（语法分析程序） ，分析对象为 C 语言源程序文件。 该分析程序有 18 部分组成： 1首先定义各种需要用到的常量和变量； 2判断一个字符是否在指定字符串中； 3得到一个不是非终结符的符号； 4分解含有左递归的产生式； 5分解不含有左递归的产生式； 6读入一个文法； 7将单个符号或符号串并入另一符号串； 8求所有能直接推出的符号； 9求某一符号能否推出 ； 10判断读入的文法是否正确； 11求单个符号的 FIRST； 12求各产生式右部的 FIRST； 13求各产生式左部的 FOLLOW； 14判断读入文法是否为一个 LL(1)文法； 15构造分析表 M； 1
12、6总控算法； 17一个用户调用函数； 18主函数； /*/ WORDANALYSE DEMO FOR TURBO C 2.0 Copyright (c) 2005-6-30Author: 陈强 All rights reserved. /*/ #include #include #include int count=0;/*分解的产生式的个数*/ int number;/*所有终结符和非终结符的总数*/ char start;/*开始符号*/ char termin50;/*终结符号*/ char non_ter50;/*非终结符号*/ char v50;/*所有符号*/ char left5
13、0;/*左部*/ char right5050;/*右部*/ char first5050,follow5050;/*各产生式右部的 FIRST 和左部的 FOLLOW 集合*/ char first15050;/*所有单个符号的 FIRST 集合*/ char select5050;/*各单个产生式的 SELECT 集合*/ char f50,F50;/*记录各符号的 FIRST 和 FOLLOW 是否已求过*/ char empty20;/*记录可直接推出的符号*/ char TEMP50;/*求 FOLLOW 时存放某一符号串的 FIRST 集合*/ int validity=1;/*表
14、示输入文法是否有效*/ int ll=1;/*表示输入文法是否为 LL(1)文法*/ int M2020;/*分析表*/ char choose;/*用户输入时使用*/ char empt20;/*求_emp()时使用*/ char fo20;/*求 FOLLOW 集合时使用*/ /* 判断一个字符是否在指定字符串中 */ int in(char c,char *p) int i; if(strlen(p)=0) return(0); for(i=0;i+) if(pi=c) return(1);/*若在，返回 1*/ if(i=strlen(p) return(0);/*若不在，返回 0*/ /* 得到一个不是非终结符的符号 */ char c() char c=A; while(in(c,non_ter)=1) c+; return(c); /* 分解含有左递归的产生式 */ void recur(char *point) /*完整的产生式在 point中*
