语法分析实验报告442

第二次实验报告一、实验题目表达式语法分析设计二、实验目的熟悉并设计一个表达式的语法分析；三、实验内容1．设计表达式的语法分析器算法2．编写代码并上机调试运行通过四、概要设计1、递归下降子程序E---E+T|E-T|TT---T*F|T/F|FF---i|(E)因为递归下降子程序需要文法满足一定的条件即必须是LL(1)文法格式，所以需要对上述文法进行变形。变为如下所述：E---TE`E`---+TE`|-TE`|?T---FT`T`---*FT`|/FT`|?F---i|(E)为了叙述方便，我将w1代替“+”和“-”，w2代替“*”和“/”。语法分析的核心技术是“文法”的机内表示问题：递归子程序法直接把文法变成程序。递归子程序法属于自顶向下语法分析方法，故又名递归下降法。设计原理：对每一个非终结符，构造一个子程序，用以识别该非终结符所定义的符号串。每个子程序以产生式左部非终结符命名，以产生式右部构造子程序内容。流程图：主控程序nyerr0开始NEXT(W)E#结束JJEISHU子程序E子程序T子程序E_1遇空yny子程序FNNerr1yYNerr22、LL(1)文法变形后的LL1文法：这里为了简便就没有考虑“-”和“/”这两种情况，其中?代表空产生式。E---TAA---+TA|?T---FBB---*FB|?F---i|(E)LL(1)分析法是指从左到右扫描、最左推导(LL)和只查看一个当前符号（括号中的1）之意；LL(1)分析法又称预测分析法，与递归子程序法同属于自顶向下确定性语法分析方法。LL(1)分析法的基本要点有三：⑴利用一个分析表，登记如何选择产生式的知识；⑵利用一个分析栈，记录分析过程；入口TE_1出口入口Fw2NEXT(w)F出口入口w1NEXT(w)TE_1出口入口iNEXT(w)出口(NEXT(w)E)⑶此分析法要求文法必须是LL(1)文法。得到LL(1)分析表后就可以进行如下流程分析：yynnerrnerrnnyyerr开始PUSH(#)PUSH(E)NEXT(w)POP(x)x属于VTx属于VNw==#结束x==w查LL(1)分析表空？PUSH(i(R))3、简单优先分析法简单优先分析法是一种从左到右扫描、最左归约分析法；它属于自底向上分析方法。该方法利用文法符号之间的优先关系来确定待归约的句柄，即可确定当前句型的句柄。简单优先分析法的基本要点有三：⑴利用一个分析表，登记选择句柄产生式的知识；⑵利用一个分析栈，记录分析过程；⑶【分析算法】依次读取单词，并进行如下操作：当栈顶出现句柄时，规约之，否则移进。获得优先分析表后，可以根据以下流程图进行分析：YerrnNY4、SLR(1)文法LR()分析法的关键技术是句柄识别器的设计问题；如果句柄识别器发生了冲突，此时，LR(0)分析法失效!需要改进句柄识别器的构造方法，于是出现了各种不同的LR()分析法。SLR(1)文法就是其中的一种。SLR(1)解决思想，通过查看‘当前单词’，是否可以解决？为此：求：follow(A)={b}。通过查看当前单词，从而解决冲突。获得SLR分析表后，按照以下流程进行分析：开始PUSH(#)NEXT(w)空？查优先分析表结束PUSH(w)①从sj（栈顶符）开始，往栈内查找，找到第一个使si-1·si的si（句柄的头）②用sisi+1…sj去查文法产生式，若有Asisi+1…sj，则：POP(sj)，POP(sj-1)，…POP(si)；PUSH(A)。yerrnynYnNerry开始PUSH(#0)NEXT(w)查SLR()分析表空？结束R=WiPUSH(Wi)R=r(j)取A-ɑ(j)①POP(ɑ);②若R(Xk,A)=Ai则PUSHAi;R=OK五、源程序（包含注释）六、测试数据及运行结果1，测试文法及结果：2，测试文法及结果：3，测试文法及结果：4，测试文法及结果：