编译原理-LL(1)文法源代码(实验三).docx

、实验目的及要求 1 ?掌握LL(1)分析法的基本原理； 掌握LL(1)分析表的构造方法； 用LL ( 1 )分析法分析高级语言表达式。 了解LL (1)分析器的工作过程。 文法：无二义性的算术表达式的文法 把词法分析作为语法分析的子程序实现( 5分) 独立的语法分析程序(4分) 对表达式文法消除左递归、构造 LL (1)分析表 LL (1)分析表可以直接输入(4分)，也可以用程序实现(5分) 给一个表达式，给出分析过程(分析栈、输入串、所用规则) (4分) 生成一个棵语法树(5分)用二叉树的形式表示出来 二、实验内容及原理 1、实验原理 (1 )、LL (1)文法的定义 LL(1)分析法属于确定的自顶向下分析方法。 LL(1)的含义是：第一个 L表明自顶向下 分析是从左向右扫描输入串，第 2个L表明分析过程中将使用最左推导， 1表明只需向右看 一个符号便可决定如何推导，即选择哪个产生式 (规则)进行推导。 LL(1)文法的判别需要依次计算 FIRST集、FOLLOWI和SELLEC■集,然后判断是否为LL(1) 文法,最后再进行句子分析。 需要预测分析器对所给句型进行识别。 即在LL(1)分析法中，每当在符号栈的栈顶出现 非终极符时，要预测用哪个产生式的右部去替换该非终极符； 当出现终结符时，判断其与剩 余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。 LL(1)分析方法要求 文法满足如下条件：对于任一非终极符 A的两个不同产生式 A ,A ，都要满足下面 条件：SELECT(A ) A SELECT(A )= (2 )、预测分析表构造 LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推 导。它的行对应文法的非终极符，列对应终极符， 表中的值有两种：一是产生式的右部的字 符串，一是null。若用M表示LL(1)分析表，则 M可表示如下： M: VNX VT PU {Error} M(A, t) = A a,当 t select(A a )，否则 M(A, t) = Error 其中P表示所有产生式的集合。 (3 )、语法分析程序构造 LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符 号，#为句子括号即输入串的括号。分析表用一个二位数组 M表示，数组元素 M[A, a]中的 下标A表示非终结符，a为终结符或句子括号 ‘ #二维数组中存放的是一条关于 A的产生 式，表明当非终结符 A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无 产生式时，则表明用 A的左部向下推导时出现了不该出现的符号，因此元素内容转向出错 处理的信息。 LL(1)分析过程主要包括以下四个动作： 替换：当X VN时选相应产生式的右部 去替换X。此时X出栈， 逆序入栈。 匹配：当X VT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号 栈中将X退栈并将输入流指针向前移动一位，否则报错。 接受：当格局为(#，空#)时报告分析成功。 报错：出错后，停止分析。并给出相应的错误提示信息。 2、实验内容 根据某一文法编制调试 LL( 1)分析程序，以便对任意输入的符号串进行分析。本次实 验的目的主要是加深对预测分析 LL( 1 )分析法的理解。 对下列文法，用LL( 1)分析法对任意输入的符号串进行分析： E-TG G-+TG TOC \o 1-5 \h \z G-s T-FS S-*FS S-￡ F-(E) F-i 程序输入一以#结束的符号串(包括+* () i#)，如：i+i*i#。 三、实验过程及步骤 总体思路分析及流程图 给定一个正规文法 G,在LL(1)预测分析中，必须先求出 First集和Follow集， 构造预测 分析表。求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析 过程。 功能模块分解图 主程序流程图 (2 )核心算法流程图 1.计算非终结符的First集的算法及流程： First集合的构造算法： (1 )若 X€ VT,贝U First (X) ={X}。 若X€ VN且有产生式 Xta……，则把a加入到First (X) 中；若也是一 条产生式，则把也加到 First (X) 中。 若XtY……是一个产生式且 Y€ VN则把First (Y) 中的所有非-元素都加到 First (X)中；若XtY1Y2…Yk是一个产生式，Y1,…，Yi-1都是非终结符，而且，对于任 何j , K j w i-1 , First (Yj) 都含有(即 Y1…Yi-1* ￡),则把First (Yj) 中的所有非 「元素都加到First (X)中；特别是，若所有的 First (Yj)均含有, j=1,2,…，k,则把 加到 F