编译实验报告LL1文法java版（代码运行）..docx

1、实验目的通过设计、编写、调试LL(1)语法分析程序，加深对LL(1) 语法分析器构造原理的理解，增强对应用LL(1) 语法分析器对语句进行语法分析的认识，且了解其语法分析过程。2、实验要求1)、分析和给出LL(1)语法分析器构造的算法思想、步骤、程序结构。2)、用自己熟悉的计算机语言编写符合要求的LL(1)语法分析器。 3)、 采用LL(1)语法分析器对教材上的几个实例，判别其是否为LL(1)文法。4)、对相应的LL(1)文法，设计几个输入符号串，然后应用所构造的LL(1)语法分析器进行分析，给出分析过程。3、LL(1)语法分析器的构造思想3.1 LL(1)语法分析器原理一个上下无关的文法是LL(1)文法的充要条件时，对每个非终结符A的两个不同产生式，A-αA-β满足 SELECT（A-α）∩SELECT（A-β）φ，其中α和β不同时推出ξ。如果某个文法满足上述条件，称该文法为LL(1)文法。LL(1)分析法是一种采用确定的自顶向下的语法分析技术，其含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可以决定如何推导，即便选择哪个产生式规则进行推导。语法分析程序的流程图如图所示。开始读入文法有效？判断句型报错结束语法分析程序流程图是LL(1) 文法？3.2 求出能推出空的终结符1） 建立一个以VN的个数为上限的一维数组X[ ]，数组元素为VN，对应每个VN有一标志位；（该标志位记录能否推出ε，其值为：“未定”、“是”、“否” ）2） 置初值——将数组X[ ]中对应的每一个VN的标记置为“未定”；3） 删除所有右部含VT的产生式，若某一VN为左部的产生式全被删除，则将数组中对应的标记值改为“否”；4） 若某一的某产生式右部为ε，则数组中对应的标记值为“是”，并删除该VN为左部的所有产生式；5） 扫描产生式右部的每个VN，若该VN在数组中对应标志为“是”，则删去该VN，转6 ；若该VN在数组中对应标志为“否”，则转7；6） 若该VN删去后，所在产生式右部为空，则该产生式左部的VN在数组中对应的标志改为“是”，并删去该VN为左部的所有产生式 ；否则转8 ；7） 删去该产生式，若该产生式左部在剩余的产生式中是唯一的左部（即A→α…，再无其它“A→β”的产生式），则把书组中该VN对应的标志改为“否”； 8）返回5，直至扫描完一遍文法的产生式后，数组中的标志不再改变。3.3 FIRST集的确定给定一个由终结符号和非终结符号组成的字符串E，FIRST（E）是从E可以推导出的任意字符串中的开头是终结符组成的集合。求First(x)的算法：若x∈VT ,则first(x)={x}若X∈VN ,且有产生式 Xa… , a∈VT ,则a∈first(X)若X∈VN ,xε,则ε∈first(X)若X∈VN ,且有产生式 XY1Y2…Yn ,其中Y1,Y2,… Yn都∈VN当Y1,Y2,… Yi-1都能推导出ε时(1=i=n),则 first(Y1) - {ε}∈first(X)first(Y2) - {ε}∈first(X) …first(Yi-1) - {ε} ∈first(X)当Y1,Y2,… Yn都能推导出ε时,则first(X) = (first(Y1)-{ε})∪(first(Y2)-{ε})∪ ……∪(first(Yn)-{ε})∪{ε}3.4 FOLLOW集的确定设 G = (VT ,VN , S , P) 是上下文无关文法，A∈VN , S是开始符号。FOLLOW(A)={a|SA 且 a∈FIRST(), ∈VT*,∈V+}若S A , 且 ε，则规定#∈FOLLOW(A) ,#作为输入串的结束符，或为句子括号，FOLLOW(A)={a|S …Aa… ,a∈VT }若S … A，则规定 #∈FOLLOW(A)设S为开始符号，把{#}加入Follow(S)中（#为句子括号）若A→αBβ，则把 First(β)–{ε} 加入Follow(B)中，如果βε，则把 Follow(A)也加入Follow(B)中。反复2，直到每个VN的Follow集不再增大为止。3.5 SELECT集的确定给定上下文无关文法的产生式A→α，A∈VN , α∈V*，若αε，则 SELECT(A→α) = First(α)若α ε，则 SELECT(A→α) = (First(α)-{ε})∪Follow(A)3.6 逻辑结构一个LL(1)分析器由一张分析表、一个分析栈和一个总控程序组成。其逻辑结构如图1所式。图1 LL(1)分析器的逻辑结构3.7 句子的判定左部相同的产生式的SELECT集的交集均为空。 4、程序代码package base;import java.awt.*