编译原理实验报告

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

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

3、 判断字符c是否在关系运算符表中输入串分析处理详细算法描述:else ifCssCch)四、测试结果ScKr 0 CoMiOlt 罚jplltiponl fifswn/Liewar/JavayjawaVIfTualMacMneBj 1.6.0jdtComeniVHomflbl但java (ZOl5年6月 1?H 59:ZZ:M1泻程萍字誹出：If i = C then ri+：a 0艾宇（1,1）h(6j)（1,?）(4,=)(13)Q(&.0)常ft(1,4)then(l.rhen)关M宇(1,5)n(n)掃朗+ +R+)运(1,7)(?,；)（i,a）a(6,a掃识符(2,1) =(4,

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

5、效的方法是使用一张分析表和一个栈进行 联合控制。预测分析表是一个 MA,a形式的矩阵，存储着分析规则；栈 STACK 用于存放文法符号。从栈顶取符号，按照分析表给出的规则进行有步骤的分析。 符合LL(1)分析法的文法：文法G的任意两个具有相同左部的产生式 A a |满足下列条件：(1) 文法不含左递归。(2) 如果a 供均不能推导出，贝U FIRST(a ) A FIRST( P )=。(3) a和P至多有一个能推导出(4) 如果 P * 则 FIRST(a ) A FOLLOW(A)=将满足上述条件的文法称为LL(1)文法。二、程序结构描述:数组数组数组数组数组char vt存储终结符cha

6、r vn存储非终结符boolean First存放文法的First 集boolean Follow存放文法的Follow 集String Graphic构建文法的LL(1)分析表int vn_loc(char c)返回 c在非终结符表中的位置int vt_loc(char c)返回c在终结符表中的位置 void first()求文法的 first 集void follow()求文法的follow 集void graphic()构建分析表void analyze()输入串分析处理三、详细算法描述:财1程序入 取一入符号a 弹出挨顶持号Sfe入孟取一入持号a四、测试结果:TJu LLX是移如?喩5

7、若腰存在規则X-X1X2X3.JQjtMx=a ?J岀错咸功LL(4)预ffl分析程序壷程LfCb #)A2 . oppendCiLjCMfifi! return;lsertft OOL人富：J+iMr pf-步豪Olj3fl-S67pubUc static void mStnng s; IScanner rea血= s reader, neKtTGPOrPUSHCCT)i+rirT-fSPOppuSHcsfri*rr#F-iPOPfU 百 H+i*iffCETNEXT川+ripS-EPOP+i*irG-+TCPC 眄 PUSHICTH叶cnrixTciai-i#T-FSPOPfU呂阡F-iP

8、OPPUSHCi)r#CETNEXTChS-*F&PCiP,PUSHciF*)litCETHErr 弭ijrF-iptip.puSHcirCETNEXTW#S-EPOPG-ePOP和 MA S*rvrf S CortKHe S3 |口 J OfW.jAva2732742752762772782792802812822832M2852862876 o 1if WordArtalyJu H人#： *e1se pul ifCpublic static v| String s;Scanner red s reader.)LLl 0 new工 javN EE My 比 Eclipse /U$r$/m讥老

9、2/Poumm$/wortc$paCSF/Q.analyzeCu 2930313233d success*AW生式朗作i+ro+i/w初tt化WZ/NE-TCPOP.PUSH(CT)i*i 伽”0*T-FSPOP.PUSH(SF)i+ro+i/wF-lPOP,PUSHTCPOP.PUSH(CT+)CCTNEXTd)T-rsPOP.PUSH(SF)F-lPOP.PUSHO)(i+i/WCCTNEXTd)(i+l/iKS-FSPOP.PUSH(SF)+4/WCETNEXTd)(i+i/i)#FPOP.PUSHOEOi+i阳CTNEXTTCPOP.PUSH(CT)T-FSPOP.PUSH(SF)iH

10、/orF tPOP.PUSMOJ*i/iKCCTNEXTd)+i/i#S-tPOP+I/WC-+TCPOP.PUSH(CT+)i/iWCCTNEXTd)i/i*T-FSPOP.PUSHGF)l/WF-lPOP.PUSHO)/MCETNEXTd)/i#S-/FSPOP.PUSH(SF/WCCTNEXTO)iMF-iPOP.PUSHO)#CETNEXTd)WS-tPOPC-ePOP#CETNEXTd)*S-tPOP#C*ePOP口 hoptrtxs A Servers OLLl Java Apptlcatiovt /Systm/boratv1.6.0Jdk/Cemws/Home/rnfl/java

11、 (ZOl5上年 12 $7 46)131415161718-192021222324252627282930 3ie32boolean First口 - new boolean510： boolean FollowDO new booleonCS10; String GrophicDD new String58;LLlCStri ft obLLdWtWHintCorc.(人析赛 01234諭分步 o I 2345678911 1忻 Ttxss TTWSSy?我 ss ECCCCCCGCCCCCCC亲人串Ufli#+i*ii#i*ii# Hi# ru#*11# *U# ii# ji i#所用产

12、生式E-TC T-FS F-iS-e C-4TCT-FS F-iS-*FSF-i动作 初贻化 POP.PUSH(CT) POP.PUSH(SF) POP,PlJSH(i) CETNEXTd) POP POP,PU5H(CT+) CETNEXTd) POP,PUSH(SF) POP. PUSH CETNEXTd) POP.PtlSHfSF*) CETNEXTd) POP.PUSHO) CETNEXTd)n Properties 41 Stm LI Mv AppHWionl Z! i+i*U#-一五、实验总结:通过本次实验，我深入了解了词法分析器和LL(1)文法的预测分析法设的计和实现。LL(1)

13、分析方法较难的地方是文法的First集和Follow集的求解。因为用到了大量的递归算法，而我对递归掌握的不是很透彻，因此花费了许多时间。First集和Follow集求解成功后分析表的构造就相对轻松，用栈来存放文法符号，当栈顶符号遇到输入符号时要分好多 种情况，容易漏掉，出错情况也要考虑周全。实验三LR(1)分析法、LR (1)语法分析程序设计思想:(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表(ACTION )和状态转换(GOTO)表两个部分，它们都

14、可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。、程序结构描述:LR分析器结构:数组char vt存储终结符 数组char vn存储非终结符boolean isvn(char c) 判断字符c是否为非终结符 boolean isvt(char c) 判断字符 c是否为终结符 int ACTION。nt a,char b)状态栈顶元素遇到终结符的动作 int GOTO(i nt a,char b)状态栈顶元素遇到非终结符的动作void analyze(String s)输入串s分析处理、详细的算法描述:四、测试结果

15、:37a379獗313睨30 3L爰亠涉1-IZ3冲5td?0专他口垃71以5谢7 7 7S J & & & & 0 G & 6 -b & & 屛加脸毗机沉毗机沉毗机沉毗动柞说甲#i+i*US,W5A#i+ifp6:F-m 规约，QOTO【dF) - SAtt#F+ii#r4：TTF规妁，COTOC0,T) - 2人梯jfT+i*i#r2:ET规亂 GOTDCai IE： = 1人槌#E+ir#s6,U6Affi#E*S5,!tt态臥栈#E+i*itfrt：Foi规亂 GOTO低号=JAH#E+F*UOOTDCe.-Q - 9人栈#*Ts人tt态7人栈#E+T*iffS,WJA#E+T*i#p

16、6:F-Ai规妁，mTDC7,F -*fE+TFIfT:TtTF規妁，G0T0C6,T) - gxte#E+T#rl;E-AE+T規釣，GOTQCej) = iA挨#EAw：廿祈感功！lfCnAfltEl*ttcnt()=、麗 n.svieQ = Z)System.out.prtntCAcc:功！ 5； brwk：else if LR| Qavd Ap|ic3Tion| y$yEt-rrijrUbr3ryJm.；j3Vd.Virtual Mach me%/TContcnts/Homcn jiwz (旳 15 年 fif吓H 上平4：耶:聘)皆3状态栈苒号補刺余辅入串列作逞10#航加ss入理Z0

17、5#i+i+Ci*O#rt汗-H规釣,CffTtKBpFJ - 3入弐3阳#F+i+C-i*O#r4:T-AF规豹.MTOC0.T) - 2人档40Z#6eie*e+5%沁5小7eigs#+申阳：F-Hgl的，GCT0C6J5 = 3人柱B0163#+Fr壮T-aFEJ绅，QOTIOCGJ) - 9人挨90価#t+Ti护rl:E-E+Tffl), 6011&S5,状态5人桂1301645#t+CLpr6:F-Lje, 60710(4,F) - 3人桟1401G43托+F-5r4汀附妁，GOTOC4/n - 2人桂IS01642#+crs7,W态？人栈16016427#+CT*O#s5tt态$人

18、校170164275#t+cr*i冲旳：F-Ai規均,GaT107,F) - 10人桶la01642710#E+cr-FMrT*Fjffi约.G0T(X4,D - 2A1901642#+cr)#rEE-xT規釣，00710(4,E5 七 B人桟2&a264B#t+CE歸*1,状态1认挨Z10164S11#+CE5凸汗佳】规妁，mX6,F . 3人型2201甜#+Fjtr4：T-AF規纽GOTOT) = 9人找Z30169*+Tarl:E-AE+T约，GCTTCK叽 Ej 1A疲2401#EgAh:井析战功1 PX5(tiQi 葩 ServerseK聞U.1 雀ua.Ap口lidtiBn fSy

19、tt已rtifUbriXyA.vd/JirvdYirtuMI詁aCKirtt盯 1.6.0.jdhj匚OrtFcfila闭口ffl日hrt/jAvz (Ml5址6戸诣日上辱丄立月门即1 *i+( I * COrlSOlf 篮W态越哥号越用亲*A；tiSO柞说1fli 斗(jriU+OHJ5.U$5AfllZ相+i*Ci+i*Ci-HiJDfrrt;FifiFh OffTOCTFJ - iAtt3jfMT-aF毘虬 GOTO他T) -4旣JfTrZiE-Tfitn, QffTOt址 EJ - LAtt5et#+Li 我呎&秋商6AJS6flueJ翦比人理7eu6sffi+ir6:F-iaHpff

20、ilDCe.FJ - 3AflESJrt寸F网gF叽COTDfdT- 9AJ43區斗TWn舷孑人栈leeifl7+T*54用恋4A握111974昉再杰5人理1Zflues 科 sr6iFiaH,：4,l=5 3A13jrt 寸 T%F十讣 Cirl)#rtzTfF規约.C0TDf4,IJ - 2人践14妊订牡TGffTDCA上5 - 8人図15eia74B+T*C+i*Ci+iJfrIhflia74fl6純17e啊4朋5tfE+T*CE+i弋ii怎；Fd砂.WTOC&iF)IS啊4蜩岸 E+T*fE+F粧i卄3r机TjF脚 COTOCt.n1$此iT住斗TZQeiJ6974ffie7岸 E+T

21、*fE+T*21flijea74fla74iS.USAUtfE+T-CE+T*Cir；F-iftS, ajTDCiJJ . lAtt23ei374flfl74i(*E+T*CE+T*CF卄iJMr4:T-Ffi*9, OCTOO/n - 2A栈24fllj6a74Afi9742“OHr2：E-Tjfttt, 5OTtX4,E) - $ArtZS*E+rcE+rcEE6.ttiS6A2B#E十卩fE十卩fE十出參拥-3A 9入拽五、实验总结LR分析法的归约过程是规范推导的 分析法正是给出一种能根据当前分析 K个(K 0)符号就可唯一地确定分析器的动作是移 进还是归约和用哪个产生式归约，因而也就能

22、唯一地确定句柄。其中LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，然而，它是构造其它LR类分析器的基础。当K=1时，已能满足当前绝大多数高级语言编译程序实现的需要。LR(1)项目集族的构造是LALR(1)分析器的构造原理和基础。首先根据文法构建 LR(1)项目集规范族，再根据项目集族构建规范 LR分析表，最后用 状态栈与符号栈两个栈来分析输入串，分析输入串时有ACTION和GOTO两个动作，要注意各种情况下的出错处理。文法有了更深刻的认识。LR通过本次试验，我对逆过程，所以LR分析过程是一种规范归约过程。 栈中的符号串和向右顺序查看输入串的LR附录:import

23、java.util.*;import java.awt.*;import javax.swi ng.*;p ublic class WordA naly exte nds JFrameJTextArea A1 = new JTextArea();Stri ng k = do,e nd,for,if, prin tf,sca nf,the n,while;ArrayList id=new ArrayListvStri ng();ArrayList ci=new ArrayListvStri ng();Stri ng a = +,-,*,/,+,-;Stri ng b = ,=,;char s =

24、 ,;,(,),;String inpu tstri ng;Stri ng strToke n =;char ch;int pint;int row;int line;WordA naly(Stri ng s)sup er(s);this.setSize(800,400);this.setVisible(true);Container c = getC ontentPan e();c.add(A1);inpu tstri ng = if i = 0the n n+;na = 3b %);row = 1;li ne = 1;pint = -1;A1.a ppen d(源程序字符串：n ”)；A1

25、.a ppen d(i npu tstri ng+nn ”)；A1.append(分析：n);A1.append(t+单词+tt+二元序列+tt+类型+tt+位置(行，列) +n);void GetChar()pin t+;if(pint = 48 & c = 65 & c = 97 & c = 122) return true;return false;int Reserve(Stri ng s)int i;for(i=0;i k.le ngth;i +)if(s.equals(ki)return i;return -1;int In sertid(Stri ng s)int i;for(i

26、=0;i id.size();i +) if(s.equals(id.get(i) return i;elseid.add(s); return -1;int In sertC on st(Stri ng s)int i;for(i = 0;i )return true;return false;boolea n readn ext1()char a = inpu tstri ng.charAt (pin t+1); if(a = + | a = -)return true;return false;int ss(char c) int i;for(i = 0;i s.le ngth;i+)

27、if(c = si)out put(2, ”,c);GetChar(); return i;return -1;int sa(char x)int i;if(read next1() = false)for(i = 0;i a.le ngth;i +)if(ai.le ngth() = 1) if(ai.equals(Character.toStri ng(x) out pu t(3, ai,);GetChar();return i;elsechar m = new char2;m0 = x;GetChar();m1 = ch;for(i = 0;i a.le ngth;i +)if(ai.l

28、e ngth() = 2) if(ai.equals(Stri ng.co pyValueOf(m) outpu t(3, ai,);GetChar();return i;RetractO;return -1;int sb(char x)int i;if(read next() = false)for(i = 0;i 宀 匸+u =宀 系qM=u _=+=(=JU=+=-=+M0+=)=+b=+= =+=+=(=+s+=-9)=+fe=+s+=A-)psdde5& SEO 系q=+=+=(=+s+=-g)=+fe=+s+=A-)psdde5G SEO 系q =s=+=+oc-+=+l+=+=+

29、=+=+=(=+s+=-寸)=+fe=+s+=A-)pu dde5 elseout pu t(-1, ”,ch);GetChar();p ublic static void main( Stri ng args)throws Excep ti on WordAnaly a = new WordAnaly(” 词法分析器！); a.a nalyze();import java.util.*;import java.awt.C ontainer;import javax.swi ngJFrame;import javax.swi ngJTextArea;p ublic class LL1 exte

30、 nds JFrameJTextArea A2 = new JTextArea();Stri nggrammarE-TG,G-+TG|-TG,G- ，”TFS,S-*FS|/FS,S- ,F(E),F-i;char Vn = E,G,T,S,F; ;char Vt = +,- ,*,/,(,),i,#, boolean First = new boolea n5 10; boolean Follow = new boolea n5 10; Stri ng Grap hic = new Stri ng5 8;LL1(Stri ng s)sup er(s);this.setSize(600,400

31、); this.setVisible(true);Container c=getC ontentPan e(); c.add(A2);first();follow();grap hic();int loc_vn( char c)for(i nt i = 0;i 5;i +) if(c = Vn i) return i;return -1;int loc_vt(char c)for(i nt i = 0;i 9;i +) if(c = Vti) return i;return -1;void first_of_each(Stn ng s, int p)int a = loc_vn( s.char

32、At(O);if(loc_vt(s.charAt( p) != -1) Firstaloc_vt(s.charAt( p) = true;elseif(Firstloc_v n(s.charAt( p)9 != true)first_ of_vn( s.charAt (p);for(i nt i = 0;i 9;i +) ) ) = true)if(Firstloc_vn(s.ch arAt(p)i & Vti !=Firstai = true; if(Firstloc_v n(s.charAt( p)loc_vt(if(p = s.le ngth()-1) ) = true;Firstalo

33、c_vt(if(s.charAt( p+1) != |)P +; first_of_each(s ,p);else ) = true;Firstaloc_vt(void follow_of_each(Stri ng s,i nt p)if(p = s.le ngth()-1 | (ps.le ngth()-1 & s.charAt( p+1) = |) if(s.charAt(0) != s.charAt( p)if(!Followloc_v n(s.charAt(0)9) follow_of_v n(s.charAt(0);for(i nt i = 0;i Vt.le ngth;i +)if

34、(Followloc_v n(s.charAt(0)i)Followloc_v n( s.charAt (p )i = true;if(p s.le ngth()-1 & s.charAt( p+1) != |)if(loc_vt(s.charAt( p+1) != -1)Followloc_v n(s.charAt( p)loc_vt(s.charAt( p+1) = true; elsefor(i nt i = 0;i 9;i+)s )s )if(Firstloc_v n(s.charAt( p+1)i& Vti !=Followloc_v n( s.charAt (p )i = true

35、;boolea n t = true;for(i nt i = p + 1;i s.len gth();i +)if(loc_vt(s.charAt(i) != -1)t = false;break;if(s.charAt(i) = |)break;if(!Firstloc_v n(s.charAt(i)loc_vt(t = false;if(!Followloc_v n(s.charAt(0)9) follow_of_v n(s.charAt(0);for(i nt i = 0;i 9;i +)if(Followloc_v n(s.charAt(0)i) Followloc_v n( s.c

36、harAt (p )i = true;int locate(i nt i,Stri ng s)for(i = i + 1;i s.le ngth();i +) if(s.charAt(i) = T) return i;return -1;void first_ of_vn( char c)for(i nt i = 0;i grammaren gth;i+)Stri ng s = grammar;if(s.charAt(O) = c)int p = 3;first_of_each(s ,p);while( locate( p,s) != -1 & p s.le ngth()p = locate

37、(p, s);first_o1_each(s ,p+1);Firstloc_vn(c)9 = true;void follow_ of_vn( char c )if(c = E)Followloc_v n(c)loc_vt(#) = true; String s;for(i nt i = 0;i grammaren gth;i +)s = grammari;for(i nt p = 3;p s.le ngth();p +) if(s.charAt (p) = c ) follow_of_each(s ,p);Followloc_v n(c )9 = true;void first()for(i

38、 nt i = 0;i 5;i +) if(Firsti9 != true) first_of_v n(Vni);void follow()for(i nt i = 0;i 5;i +) if(Followi9 != true) follow_ of_vn (V n i);void add_to_gra(i nt p ,i nt i,Stri ng s)char a = grammari.charAt(0); if(loc_vt(grammari.charAt( p) != -1) if(grammari.char At(p) != Grap hicloc_v n( a)loc_vt(grammari.charAt (p) = s; else for(i nt k = 0;k 8;k+) if(Followloc_v n(a)k)Grap hicloc_v n( a)k = s;e