还剩3页未读,继续阅读
文本内容:
实验二编写语法分析程序实验类型
2.1设计型实验学时,6实验目的
2.2通过设计、编写、调试一个递归下降语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,掌握递归下降语法分析方法背景知识
2.3递归下降分析程序的实现思想是分析程序由一组子程序组成,每个子程序对应于一个非终结符号递归下降分析程序实现思想简单易懂,程序结构和文法产生式有直接的对应关系,添加语义加工工作比较方便每一个子程序的功能选择正确的右部,扫描完相应的字符,产生式右部有非终结符号时,调用该非终结符号对应的子程序来完成自上向下分析过程中,如果带回溯,则分析过程是穷举所有可能的推导,看是否能推导出待检查的符号串,分析速度慢而无回溯的自上向下分析技术,当选择某非终结符的产生时,可根据输入串的当前符号以及各产生式右部首符号而进行,效率高,且不易出错实现不带回溯的自顶向下分析,文法满足下述条件文法不含左递归1文法的任何一个非终结符的各个产生式的右部符号串的集两两不相交,2A FIRST即若有届,贝Af ai|ot2|…1JFIRST aiA FIRST为=F i#j,IWiJWn文法的任何一个非终结符3A,若有且存在柒,有则Af ai|ct2|…%8eFIRST%,FIRSTa jA FOLLOWA=6i Wj,j=l,2,.・.,n文法的左递归消除算法要求无环路形如的推导和无£-产生式A=+A、把非终结符按某一顺序排序为1A1,A2…An o、2fbri=l;i=n;i++{fdrj=l;j=i-l;j++{ifAjf5l|32|・・・|3k,Ai-Aj丫把改写成Aif AjyAif31丫|32丫卜・|Sky;}消除关于产生式的直接左递归;Ai}、化简由所得到的文法、化简改写之后的文法,删除多余产生式323文法的直接左递归消除公式直接左递归形式;U—Ux|y其中不以打头x,ye VNUVT*,y U直接左递归的消除一,U yU归U—xU直接左递归的一般形式:;U-Uxi|Ux|...|Ux|yi|y|...|yn2m2其中在,都不以打头Xi yU一般形式直接左递归的消除,U—yiU1y2U]..|ynUU―X1U|X2U|…|XmU|£回溯的消除前提文法不得含有左递归,可提左因子来消除回溯递归下降分析程序的基本架构先定义变量ch当前符号;函数READch读输入串下一符号;对于每个非终结符号处理的方法如下U-ai|a2|…|anP U〃处理的程序部分ifcheFIRSTai then Pai al〃处理的程序部分else ifcheFIRSTathen Paa222else ifcheFIRSTathenPan n〃处理空产生式情况else ifch FOLLOWUthen returnelseerror对于每个右部・・的处理架构如下0t=XlX
2.XnPa〃处理的程序PX1;XI;〃处理的程序PX2X2••••••;〃处理的程序PX Xnn对于右部中的每个符号;X1如果为终结符号Xii*ch=a〃对于终结符,直接将指针前调READ chelseen*or如果引为非终结符号,直接调用相应的过程XioP编写递归下降分析程序一般步骤改写文法,消除二义性;1消除左递归、提取左因子;2求集、集;3FIRST FOLLOW检查是不是文法,若不是说明文法的复杂性超过自顶向下方法的分4LL1LL1,析能力直接根据产生式设计相应的程序5实验内容
2.
4、语法规则1本实验的语言的语法规则如下TESTlprogram::={declaration_liststatement_list}2declaration_list::=declaration_listdeclaration_stat|£3declaration_stat::=int ID;4statement_list::=statement_liststatement|85statement::=if^stat|while_stat|fbr_stat|read_stat|write_stat|command_stat|expression_stat6if^stat:~if exprstatement[elsestatement]7while_stat::=while exprstatement8fdr_stat::=fbrexpr;expr;exprstatement9write_stat::=write expression;10read_stat::=read ID;1lcompound_stat::={statement_l ist}12expression_stat::=expression;|;13expression::=lD=bool_expr|bool_expr14bool_expr::=additive_expr|additive_expr||=|=|==|!=additive_expr15additive_expr::=term{+|-term}16term::=factor{*|/factor}17factor::=expression|ID|NUM、要求2根据递归下降分析方法,完成语言的递归下降语法分析程序的构造,主要完TEST成:、改造文法,使之满足无回溯的递归下降分析条件,给出改写后的文法(写入实验报告);
12、编写递归下降分析程序;(将〈statement,,v expression>的程序流程图写入实验报告)、测试编写的递归下降分析程序(用实验一的输出作为本实验的测试输入)3实验分析与思考、语言语法规则中哪些不满足无回溯的递归下降分析条件?你是怎么处理的?给出你的1TEST处理方案、所有文法都可以改写为满足递归下降分析条件的文法吗?如果不能,请给出一个反例
2、改写文法有什么弊端?3。