编译原理课程设计-LL1文法分析器设计C++语言实现精选.docxVIP

集美大学计算机工程学院编译原理课程设计报告选题名称: LL（1）文法分析 院（系）: 计算机工程学院专 业: 计算机科学与技术班 级: 计算1412 指导教师: 付永刚 学年学期: 2016 ~ 2017 学年 第 2 学期 2017年 06 月 29 日摘要：选题要求：根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合。5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。?关键词：语法分析；FIRST集合；FOLLOW集合；分析表一、设计内容及要求(1) 基于PL/0语言，通过编程判断该文法是否为LL(1)文法； (2)计算出文法的First() Follow()(3)构造相应文法的预测分析表(4)对某个输入句子进行语法分析二、实现原理1．LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a )∩SELECT(A:=b)=?。（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导ATA…，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。● 直接左递归若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：A→Aα|β （α,β∈V*，且β不以A开头）对A引入一个新的非终结符A′，把上式改写为：A →βA′ A′→αA′|ε ● 间接左递归若文法中存在某一非终结符A，使得ATA…至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。 【方法二】直接改写文法：设有文法G10[S]： S→Aα|β ⑴ A→Sγ ⑵因为STAαTSγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）： S→Sγα|β ⑶⑶式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：S→βS′S′→γαS′|ε2. 计算First集(1) 若X∈VT ，则First(X)={X}(2) 若X∈VN ，且有产生式X→a…, a∈VT则First(X)={X}(3) 若X∈VN ，且有产生式X→ε,则First(X)={X}(4) 若X，Y1 ，Y2 ，…，Yn 都∈VN，而由产生式X→Y1 Y2 …Yn 。当Y1 ，Y2 ，…，Yi-1都能推导出ε时，（其中1≤i≤n），则First(Y1)-{ε}, First(Y2)-{ε},…, First(Yi)都包含在First(X)中(5)当(4)中所有Yi都能推导出ε，（i=1，2，…，n），则First(X)=First(Y1)∪First(Y2)∪…First(Yn)∪{ε}反复使用上述步骤直到每个符合的First集合不再增大为止。3. 计算Follow集对文法中的每个A∈VN，计算Follw(A)：(1) 设S为文法的开始符合，把{#}加入Follow(S)中；(2) 若A→αBβ是一个产生式，则把First(β)的非空元素加入Follow(B)中，如果β能推导出ε，则把Follow(A)也加入(B)中；(3) 反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。4. 预测分析方法预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程序；先进后出栈；预测分析表。预测分析程序的框图如下：目录1系统分析11.1选题要求11.2预期目标12.程序流程图12.1总流程图12.2First集和Follow集22.3预测分析表流程33.代码编写33.1检查左递归33.2first集合53.3follow集合63.4分析表输出84.程序调试105.总结116.指导教师评语127.源码13正文：1.系统分析 1.1选题要求根据某一文法编制调试LL(1) 文法语法分分析程序，以便对