编译实验报告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 FIR S T 集的确定 给定一个由终结符号和非终结符号组成的字符串 E，FIRST（E）是从 E 可以 推导出的任意字符串中的开头是终结符组成的集合。 求 First(x)的算法： 若 x∈VT ,则 first(x)={x} 2) 若 X∈VN ,且有产生式 X a…, a∈VT ,则 a∈first(X) 3) 若 X∈VN ,x ε ,则ε ∈first(X) 4) 若 X∈VN ,且有产生式 X Y1Y2…Yn,其中 Y1,Y2,…Yn 都∈VN 当 Y1,Y2,… Yi-1 都 能 推 导 出 ε 时 (1=i=n), 则 first(Y1) - {ε }∈first(X) first(Y2) - {ε }∈first(X) … 4 FOLLOW 集的确定 first(Yi-1) - {ε } ∈first(X) 当 Y1,Y2,…Yn 都能推导出ε 时, 则 first(X) = (first(Y1)-{ ε }) ∪ (first(Y2)-{ε })∪…… ∪(first(Yn)-{ε })∪{ε } 设 G = (VT ,VN , S , P) 是上下文无关文法，A∈VN , S 是开始符号。 FOLLOW(A)={a |Sμ Aβ且 a∈FIRST(β ), μ∈VT* ,β∈V+} 若 Sμ Aβ , 且β ε，则规定#∈FOLLOW(A) ,#作为输入串的结束符，或为 句子括号， FOLLOW(A)={a |S …Aa …,a∈VT } 若 S …A，则规定#∈FOLLOW(A) 1) 设 S 为开始符号，把{#}加入 Follow(S)中（#为句子括号） 2) 若 A→α Bβ ，则把 First(β )–{ε }加入 Follow(B)中，如果β ε ，则把 Follow(A)