计算机13-3班实验报告

1、编译原理实验班级：计算机科学与技术 13-3 班学号：2013211683：完成日期：2015 年 6 月 13 日实验一词法分析设计能描述：从原文件中读入字符对文件中的各类字符进行词法分析 统计行数和列数用于错误单词的定位打印出分析后的结果如果发现错误则出错二、程序结构描述：数组 k数组 a数组 b数组 s关键字运算符关系运算符分解符动态数组 id 存放标识符动态数组 ci 存放常数p指针strtoken 存放row 行数line 列数单词符号的字符串char ch 字符变量，存放读进的源程序字符void GetChar() 将下一字符读到 ch 中void GetBC检查 ch 中的字符是

2、否为空，若是，则调用 GetChar()直到读入非空 void Retract指针回调一个字符位置，ch 置空bool sdigit(char c) 判断当前字符是否是数字，若是返回 true,否则返回 false bool isletter(char c) 判断当前字符是否字母，若是返回 true,否则返回 false Reserve(String s)判断 s 是否是保留字，若是返回编码，否则返回-1void snum()识别数字串ss(char sa(charsb(charc)判断字符 c 是否在分界符表中x) 判断字符 c 是否在运算符表中x) 判断字符 c 是否在关系运算符表中voi

3、dyze()输入串分析处理三、详细算法描述：四、五、实验总结通过本次试验，更次的理解了词法分析器的作用以及实现过程，也对编译原理这门课有了更深的认识。在程序实现的过程中，状态转换是重点，要详细地考虑到每一种情况，我在开始的时候就因为会忽略了标识符与保留字的区别浪费了时间。其次要注意运算符+、-还有关系运算符=的判断。最后要注意各种出错情况处理。实验二 LL(1)分析法一、LL(1)分析法的：当一个文法满足 LL(1)条件时，就可以为它构造一个不带回溯的自上而下的分析程序，这个分析程序是有一组递归过程组成的，每个过程对应文法的一个非终结符。实现 LL(1)分析的一种有效的方法是使用一张分析表和一

4、个栈进行联合控制。分析表是一个 MA,a形式的矩阵，着分析规则；栈STACK用于存放文法符号。从栈顶取符号，按照分析表给出的规则进行有步骤的分析。符合 LL(1)分析法的文法：文法G的任意两个具有相同左部的产生式A| 满足下列条件：（1）文法不含左递归。如果、均不能推导出，则 和 至多有一个能推导出 。() () = 。（4）如果 * ，则() FOLLOW(A) = 。将满足上述条件的文法称为LL(1)文法。二、程序结构描述：数组数组数组数组数组char vtchar vn终结符 非终结符存放文法的集Follow存放文法的 Follow 集String Graphic构建文法的 LL(1)分

5、析表vn_loc(char c) 返回 c 在非终结符表中的位置vt_loc(char c) 返回 c 在终结符表中的位置void()求文法的集void follow()求文法的 follow 集void graphic()构建分析表voidyze()输入串分析处理三、详细算法描述：四、：五、实验总结：通过本次实验，我深入了解了词法分析器和 LL(1)文法的分析法设的计。LL(1)分析方法较难的地方是文法的集和 Follow 集的求解。因为用到了大量的递归算法，而我对递归掌握的不是很透彻，因此花费了许多时间。集和 Follow 集求解成功后分析表的构造就相对轻松，用栈来存放文法符号，当栈顶符号

6、遇到输入符号时要分好多种情况，容易漏掉，出错情况也要考虑。实验三 LR(1)分析法一、LR（1）语法分析程序设计：(1)总控程序，也可以称为驱动程序。对所有的 LR 分析器总控程序都是相同的。 (2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的 LR 分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。二、程序结构描述：数组 char vt数组 char vn终结符非终结符isvn(char c)

7、判断字符 c 是否为非终结符isvt(char c) 判断字符 c 是否为终结符ACTION(GOTO(a,char b)状态栈顶元素遇到终结符的动作a,char b) 状态栈顶元素遇到非终结符的动作voidyze(String s) 输入串 s 分析处理三、详细的算法描述：四、：五、实验总结通过本次试验，我对 LR 文法有了更深刻的认识。LR 分析法的归约过程是规范推导的逆过程，所以 LR 分析过程是一种规范归约过程。LR 分析法正是给出一种能根据当前分析栈中的符号串和向右顺序查看输入串的 K 个(K0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄

8、。其中 LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，然而，它是构造其它 LR 类分析器的基础。当K=1 时，已能满足当前绝大多数高级语言编译程序实现的需要。LR(1)项目集族的构造是LALR(1)分析器的构造原理和基础。首先根据文法构建 LR(1)项目集规范族，再根据项目集族构建规范 LR 分析表，最后用状态栈与符号栈两个栈来分析输入串，分析输入串时有 ACTION 和 GOTO 两个动作，要注意各种情况下的出错处理。附录：实验一源代码：import java.util.*; import java.awt.*; import javax.swing.*;pub

9、lic class Wordy extends JFrameJTextArea A1 = new JTextArea();String k = do,end,for,if,prf,scanf,then,while; ArrayList id=new ArrayList();ArrayList ci=new ArrayList(); String a = +,-,*,/,+,-;String b = ,=,; char s = ,;,(,),;String inputstring; String strToken = ; char ch;p;row; line;Wordy(String s)su

10、per(s); this.setSize(800,400); this.setVisible(true);Container c = getContentPane();c.add(A1);inputstring = if i = 0then n+;na = 3b %); row = 1;line = 1;p= -1;A1.append(源程序字符串：n); A1.append(inputstring+nn); A1.append(分析：n);A1.append(t+单词+tt+二元序列+tt+类型+tt+位置（行，列）+n);void GetChar() p+;if(p= 48 & c = 6

11、5 & c = 97 & c = 122) return true;return false;Reserve(String s) i;for(i=0;i k.length;i +) if(s.equals(ki)return i;return -1;Insertid(String s) i;for(i=0;i id.size();i +)if(s.equals(id.get(i) return i;elseid.add(s);return -1;InsertConst(String s) i;for(i = 0;i )return true;return false;readnext1()ch

12、ar a = inputstring.charAt(p+1); if(a = + | a = -)return true;return false;ss(char c)i;for(i = 0;i s.length;i+) if(c = si)output(2, ,c); GetChar(); return i;return -1;sa(char x) i;if(readnext1() = false)for(i = 0;i a.length;i +) if(ai.length() = 1)if(ai.equals(Character.toString(x) output(3, ai, );Ge

13、tChar(); return i;elsechar m = new char2; m0 = x;GetChar(); m1 = ch;for(i = 0;i a.length;i +) if(ai.length() = 2)if(ai.equals(String.copyValueOf(m) output(3, ai, );GetChar(); return i;Retract();return -1;sb(char x) i;if(readnext() = false)for(i = 0;i b.length;i +) if(bi.length() = 1)if(bi.equals(Cha

14、racter.toString(x)output(4, bi, ); GetChar();return i;elsechar m = new char2; m0 = x;GetChar(); m1 = ch;for(i = 0;i b.length;i+) if(bi.length() = 2)if(bi.equals(String.copyValueOf(m) output(4, bi, );GetChar(); return i;Retract();return -1;void output(switch(i) case -1:i,String s,char a)A1.append(t+a

15、+tt+Error+tt+Error+tt+(+row+,+line+)+n); break;case 0: A1.append(t+s+tt+Error+tt+Error+tt+(+row+,+line+)+n); break;case 1:A1.append(t+s+tt+(1,+s+)+tt+tt+(+row+,+line+)+n); break;case 2: A1.append(t+a+tt+(2,+a+)+tt+tt+(+row+,+line+)+n); break;case 3: A1.append(t+s+tt+(3,+s+)+tt+tt+(+row+,+line+)+n);

16、break;case 4:关键字分界符算术运算符A1.append(t+s+tt+(4,+s+)+tt+tt+(+row+,+line+)+n); break;case 5:A1.append(t+s+tt+(5,+s+)+tt+常数+tt+(+row+,+line+)+n); break;case 6:关系运算符A1.append(t+s+tt+(6,+s+)+tt+tt+(+row+,+line+)+n); break;line+;标识符voidyze()= -1;pGetChar();whilnt TG,G-+TG|-TG,G-,T-FS,S-*FS|/FS,S-,F-(E),F-i;

17、char Vn = E,G,T,S,F;char Vt = +,-,*,/,(,),i,#,; = newFollow = new510;510;String Graphic = new String58; LL1(String s)super(s); this.setSize(600,400); this.setVisible(true);Container c=getContentPane(); c.add(A2);();follow(); graphic();loc_vn(char c)for(i = 0;i 5;i +) if(c = Vni)return i;return -1;lo

18、c_vt(char c)for(i = 0;i 9;i +) if(c = Vti)return i;return -1;void_of_each(String s,p)a = loc_vn(s.charAt(0); if(loc_vt(s.charAt(p) != -1)aloc_vt(s.charAt(p) = true;elseif(loc_vn(s.charAt(p)9 != true)_of_vn(s.charAt(p);for(i = 0;i 9;i +)if(loc_vn(s.charAt(p)i & Vti != )ai = true;if(loc_vn(s.charAt(p)

19、loc_vt() = true) if(p = s.length()-1)aloc_vt() = true;if(s.charAt(p+1) != |) p +;_of_each(s,p);elsealoc_vt() = true;void follow_of_each(String s,p)if(p = s.length()-1 | (ps.length()-1 & s.charAt(p+1) = |)if(s.charAt(0) != s.charAt(p)if(!Followloc_vn(s.charAt(0)9) follow_of_vn(s.charAt(0);for(i = 0;i

20、 Vt.length;i +) if(Followloc_vn(s.charAt(0)i)Followloc_vn(s.charAt(p)i = true;if(p s.length()-1 & s.charAt(p+1) != |)if(loc_vt(s.charAt(p+1) != -1) Followloc_vn(s.charAt(p)loc_vt(s.charAt(p+1) = true;elsefor(i = 0;i 9;i+)if(loc_vn(s.charAt(p+1)i & Vti != ) Followloc_vn(s.charAt(p)i = true;t = true;i

21、 = p + 1;i s.length();i +) if(loc_vt(s.charAt(i) != -1)t = false; break;if(s.charAt(i) = |) break;if(!loc_vn(s.charAt(i)loc_vt() t = false;for(if(t)if(!Followloc_vn(s.charAt(0)9) follow_of_vn(s.charAt(0);for(i = 0;i 9;i +)if(Followloc_vn(s.charAt(0)i) Followloc_vn(s.charAt(p)i = true;locate(i,String

22、 s)for(i = i + 1;i s.length();i +) if(s.charAt(i) = |)return i;return -1;void_of_vn(char c)for(i = 0;i grammar.length;i+) String s = grammari; if(s.charAt(0) = c)p = 3;_of_each(s,p);while( locate(p,s) != -1 & p s.length()p = locate(p,s);_of_each(s,p+1);loc_vn(c)9 = true;void follow_of_vn(char c ) if

23、(c = E)Followloc_vn(c)loc_vt(#) = true;String s;for(i = 0;i grammar.length;i +) s = grammari;for(p = 3;p s.length();p +)if(s.charAt(p) = c ) follow_of_each(s,p);Followloc_vn(c )9 = true;void()for(i = 0;i 5;i +) if(i9 != true)_of_vn(Vni);void follow()for(i = 0;i 5;i +) if(Followi9 != true)follow_of_v

24、n(Vni);void add_to_gra(p,i,String s)char a = grammari.charAt(0); if(loc_vt(grammari.charAt(p) != -1)if(grammari.charAt(p) != ) Graphicloc_vn(a)loc_vt(grammari.charAt(p) = s;else for(k = 0;k 8;k+)if(Followloc_vn(a)k) Graphicloc_vn(a)k = s;elsefor(k = 0;k 8;k +)if(loc_vn(grammari.charAt(p)k) Graphiclo

25、c_vn(a)k = s;if(loc_vn(grammari.charAt(p)loc_vt()for(k = 0;k Vt.length - 1;k +) if(Followloc_vn(a)k)Graphicloc_vn(a)k = s;void graphic()p,l; String s;for(i = 0;i grammar.length;i +) p = 3;while(p grammari.length() l = locate(p,grammari); if(l = -1)l = grammari.length();s = grammari.substring(p, l);

26、add_to_gra(p,i,s);p = l+1;voidyze(String s)A2.append(输入串：+s+n+分析：+n);A2.append(步骤+t+分析栈+t+剩余输入串+t+所用产生式+t+动作n);Stack as = new Stack (); as.push(new Character(#);as.push(new Character(E); char a,b;i = 0,temp = 0;String str,action = 初始化,rule = ; while(i s.length()a = s.charAt(i);A2.append( +temp+t);fo

27、r(j = 0;j + str; if(!str.equals()action = action+,PUSH(;for(j = str.length()-1;j -1;j -) action = action + str.charAt(j);as.push(new Character(str.charAt(j);action = action + );elserule = ;A2.append(出错啦！); return;elserule = ;if(b = a)if(b = #)A2.append(suc return;elsei+;s!);action = GETNEXT(I);elser

28、eturn;temp+;public sic void main(String args) String s;Scanner reader = new Scanner(System.in); s = reader.next();LL1 a = new LL1(LL(1)分析器！);a.yze(s);实验三源代码：import java.util.Scanner;import java.util.Stack;public class LR1 char Vn = E,T,#; char Vt = +,*,(,),i;Stack m = new Stack (); Stack n = new Sta

29、ck (); String explain;public LR1() System.out.prln( 步骤+tt+ 状态栈 +tt+ 符号栈 +tt+ 剩余输入串+tt+动作说明);isvn(char c)for(i = 0;i Vn.length;i+) if(c = Vni)return true;return false;isvt(char c)for(i = 0;i T 规约, GOTO( + i + ,E) = +j+入栈;return 2;else if(a = 2 & b = ) m.pop();i = m.peek();j = GOTO(i, E);m.push(j); n.

30、pop();n.push(E);explain = r2:E-T 规约, GOTO( + i + ,E) = +j+入栈;return 2;else if(a = 2 & b = #) m.pop();i = m.peek();j = GOTO(i, E);m.push(j); n.pop();n.push(E);explain = r2:E-T 规约, GOTO( + i + ,E) = +j+入栈;return 2;else if(a = 5 & b = +) m.pop();i = m.peek();j = GOTO(i, F);m.push(j); n.pop();n.push(F);

31、explain = r6:F-i 规约, GOTO( + i + ,F) = +j+入栈;return 2;else if(a = 3 & b = +) m.pop();i = m.peek();j = GOTO(i, T);m.push(j); n.pop();n.push(T);explain = r4:T-F 规约, GOTO( + i + ,T) = +j+入栈;return 2;else if(a = 3 & b = ) m.pop();i = m.peek();j = GOTO(i, T);m.push(j); n.pop();n.push(T);explain = r4:T-F

32、规约, GOTO( + i + ,T) = +j+入栈;return 2;else if(a = 3 & b = #) m.pop();i = m.peek();j = GOTO(i, T);m.push(j); n.pop();n.push(T);explain = r4:T-F 规约, GOTO( + i + ,T) = +j+入栈;return 2;else if(a = 5 & b = *) m.pop();i = m.peek();j = GOTO(i, F);m.push(j); n.pop();n.push(F);explain = r6:F-i 规约, GOTO( + i +

33、,F) = +j+入栈;return 2;else if(a = 5 & b = ) m.pop();i = m.peek();j = GOTO(i, F);m.push(j); n.pop();n.push(F);explain = r6:F-i 规约, GOTO( + i + ,F) = +j+入栈;return 2;else if(a = 3 & b = *) m.pop();i = m.peek();j = GOTO(i, T);m.push(j); n.pop();n.push(T);explain = r4:T-F 规约, GOTO( + i + ,T) = +j+入栈;retur

34、n 2;else if(a = 5 & b = #) m.pop();i = m.peek();j = GOTO(i, F);m.push(j); n.pop();n.push(F);explain = r6:F-i 规约, GOTO( + i + ,F) = +j+入栈;return 2;else if(a = 10 & b = #) m.pop(); m.pop();i = m.peek();j = GOTO(i, T);m.push(j); n.pop();n.pop();n.push(T);explain = r3:T-T*F 规约, GOTO( + i + ,T) = +j+入栈;r

35、eturn 2;else if(a = 10 & b = +) m.pop(); m.pop();i = m.peek();j = GOTO(i, T);m.push(j); n.pop();n.pop();n.push(T);explain = r3:T-T*F 规约, GOTO( + i + ,T) = +j+入栈;return 2;else if(a = 10 & b = ) m.pop(); m.pop();i = m.peek();j = GOTO(i, T);m.push(j); n.pop();n.pop();n.push(T);explain = r3:T-T*F 规约, GO

36、TO( + i + ,T) = +j+入栈;return 2;else if(a = 9 & b = +) if(!m.empty()m.pop();m.pop();i = m.peek();j = GOTO(i, E);m.push(j); n.pop();n.pop();n.push(E);explain = r1:E-E+T 规约, GOTO( + i + ,E) = +j+入栈; return 2;else if(a = 9 & b = )m.pop(); m.pop(); i = m.peek();j = GOTO(i, E);m.push(j); n.pop();n.pop();n

37、.push(E);explain = r1:E-E+T 规约, GOTO( + i + ,E) = +j+入栈;return 2;else if(a = 9 & b = #) m.pop(); m.pop();i = m.peek();j = GOTO(i, E);m.push(j); n.pop();n.pop();n.push(E);explain = r1:E-E+T 规约, GOTO( + i + ,E) = +j+入栈;return 2;else if(a = 11 & b = +) m.pop(); m.pop();i = m.peek();j = GOTO(i, F);m.pus

38、h(j); n.pop();n.pop();n.push(F);explain = r5:F-(E)规约, GOTO( + i + ,F) = +j+入栈;return 2;else if(a = 11 & b = *) m.pop(); m.pop();i = m.peek();j = GOTO(i, F);m.push(j); n.pop();n.pop();n.push(F);explain = r5:F-(E)规约, GOTO( + i + ,F) = +j+入栈;return 2;else if(a = 11 & b = ) m.pop(); m.pop();i = m.peek();j = GOTO(i, F);m.push(j); n.pop();n.pop();n.push(F);explain = r5:F-(E)规约, GOTO( + i + ,F) = +j+入栈;return 2;else if(a = 11 & b = #) m.pop(); m.