编译原理课程设计-语法分析器.doc

福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：系：软件工程专 业：软件工程年 级：2012级学 号：3126016056指导教师：职 称：副教授20142015学年第二学期福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目 录1 正则表达式11.1 正则表达式11.2 确定化(化简)后的状态转换图11.3 分析程序代码11.4 程序运行截图21.5 小结32 ll(1)分析42.1 ll(1)文法42.2 ll(1)预测分析表42.3 分析程序代码42.4 程序运行截图62.5 小结73 算符优先分析83.1 算符优先文法83.2 算符优先关系表83.3 分析程序代码83.4 程序运行截图113.5 小结124 lr分析134.1 lr文法134.2 lr分析表134.3 分析程序代码134.4 程序运行截图174.5 小结19参考文献：191 正则表达式1.1 正则表达式(a*|b*)b(ba)*1.2 确定化(化简)后的状态转换图1.3 分析程序代码import java.util.scanner;import java.util.regex.matcher;import java.util.regex.pattern;public class main public static void main(string args)string a,b;scanner input = new scanner(system.in);system.out.println(请先输入【正则表达式】再输入【符号串】);while(input.hasnext() a = input.next();b = input.next();system.out.println(符号串【 + b + 】 + work(a,b) + 正则表达式【 + a + 】);private static string work(string a, string b) pattern pattern = ppile(a);/将给定的正则表达式编译并赋予给pattern类matcher matcher = pattern.matcher(b);/对输入的字串以该正则表达式为模开展匹配return matcher.matches()? 满足 : 不满足 ;/匹配检测#include#include#includeusing namespace std;int m100255;/m起点路径=终点bool end100;void init()m1a=2;m1b=3;m2a=2;m2b=4;m3b=6;m4b=5;m5a=4;m6a=4;m6b=6;end3=end4=end6=true;int main()puts(本程序的正则表达式为(a*|b*)b(ba)*，请输入符号串);string s;init();cins;int now=1;for(int i=0;si;i+)now=mnowsi;if(endnow)puts(符合);elseputs(不符合);return 0;1.4 程序运行截图javac+1.5 小结通过java自带的类库可以轻松完成动态输入【正则表达式】的程序，而c+的我目前不懂是否有这些类，如果要写自带构图的，代码会比较复杂，所以这题我用c+写的程序是固定的【正则表达式】的，这样只需要在运行核心代码前用固定方式构建好状态转换图就可以了。2 ll(1)分析2.1 ll(1)文法 sad dste| tbh|h hd| 2.2 ll(1)预测分析表aebd#ssadddsteddddtthtbhthhhhd2.3 分析程序代码#include#include#include#include#includeusing namespace std;string s,stack;string ll255255;string reverse(string str)/字符串倒置char t100=0;int len=str.length();for(int i=0;ilen;i+)ti=strlen-i-1;return t;void init()/0表示没有这种转化/表示for(int i=0;i255;i+)for(int j=0;j255;j+)llij=0;llsa=ad;llda=ste;llde=;lldb=;lldd=;lld#=;llte=h;lltb=bh;lltd=h;llhe=;llhd=d;stack=s;void work()puts(符号栈输入串 动作);coutleft;int i=0;putchar(#);coutsetw(23)stack;coutsetw(23)s.substr(i,s.length();trywhile(!stack.empty()if(stackstack.length()-1=si)/执行弹出cout弹出栈顶符号siendl;i+;stack=stack.substr(0,stack.length()-1);else if(llstackstack.length()-1si!=0)/执行转换coutstackstack.length()-1;if(llstackstack.length()-1si=)puts();elsecoutllstackstack.length()-1siendl;stack=stack.substr(0,stack.length()-1)+reverse(llstackstack.length()-1si);elsethrow 0;putchar(#);coutsetw(23)stack;coutsetw(23)s;s=s+#;work();return 0;2.4 程序运行截图2.5 小结以【”0”】作为错误输入的标志，把2.1中给定表格中无数据的项填入0，当匹配到0时，表示输入的数据错误。因为本题要求显示【符号栈】，所以我用string而不是用stack来表示符号栈，但运用的仍然是栈的思想。这题我出错的地方在于循环条件写成【si!=#】 （已改正），循环条件应该为【!stack.empty()】，而成功判断放在循环外，为【si=#】。当输入错误时，一定会在循环内部被找出，或者是程序运行时抛出的异常都代表输入错误。3 算符优先分析3.1 算符优先文法 ee+t | t tt*f | f f(e) | i3.2 算符优先关系表+*i()#+*i(#=3.3 分析程序代码#include#include#include#include#include#include#includeusing namespace std;char precedence66= , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , = ;char symbol255;string s;map ex;void init()/构造映射symbol+=0;symbol*=1;symboli=2;symbol(=3;symbol)=4;symbol#=5;exe+t=e;ext=e;ext+t=e;exf+t=e;ext+f=e;exf+f=e;exe+f=e;ext+f=e;ext*f=t;exf=t;exf*f=t;ex(e)=f;exi=f;ex(t)=f;ex(f)=f;char comp(char a,char b)/比较优先级 若ab无优先关系 则为非法输入，抛出异常if(precedencesymbolasymbolb= )throw 0;return precedencesymbolasymbolb;void work()string symbolstack=;/用于输出【符号栈】的字符串puts(符号栈输入串);coutleft;int i=0;stack ch;/符号栈【终结符】包括#stack letter;/符号栈【非终结符号】ch.push(#);putchar(#);coutsetw(23)symbolstack;coutsetw(23)s.substr(i,s.length()endl;trywhile(ch.top()!=#|si!=#)switch(comp(ch.top(),si)case :if(exstring()+ch.top()char t=exstring()+ch.top();ch.pop();symbolstack=symbolstack.substr(0,symbolstack.length()-1)+t;letter.push(t);else if(ch.top()!=)char sc=letter.top();letter.pop();char fc=letter.top();letter.pop();char t=exstring()+fc+ch.top()+sc;ch.pop();symbolstack=symbolstack.substr(0,symbolstack.length()-3)+t;letter.push(t);elsechar t=exstring()+letter.top()+);ch.pop();ch.pop();letter.pop();symbolstack=symbolstack.substr(0,symbolstack.length()-3)+t;letter.push(t);break;case =:symbolstack=symbolstack+si;ch.push(si+);break;putchar(#);coutsetw(23)symbolstack;coutsetw(23)s.substr(i,s.length()s;s=s+#;work();return 0;3.4 程序运行截图3.5 小结这题遇到了些麻烦，在这题中【i#】【+#】，且【fi】【ee+t】，其中【i】可以单独归约，而【+】需要与另外2个非终结符一起归约，我是直接判断字符是否能够单独归约，如果可以就归约，不行就从【非终结符栈】中取出2个，这是一点。而另一点因为【et】【tf】，当i进行归约时，应该把i归约成f或t还是e就不明确了，所以我就在程序中添加例如【ef】【ef+f】等转换。我这题的错误在于把优先级相等的符号直接进行归约而漏写了入栈过程（已改正）。4 lr分析4.1 lr文法 (1) ee+t (2) et (3) tt*f (4) tf (5) f(e) (6) fi4.2 lr分析表状态actiongotoi+*()#etf0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r54.3 分析程序代码#include#include#include#include#include#include#includeusing namespace std;struct xchar a;string b;ex7;string s;string action1126=/action状态符号 s5, , ,s4, , , ,s6, , , ,acc , ,r2,s7, ,r2,r2 , ,r4,r4, ,r4,r4 , s5, , ,s4, , , ,r6,r6, ,r6,r6 , s5, , ,s4, , , s5, , ,s4, , , ,s6, , ,s11, , ,r1,s7, ,r1,r1 , ,r3,r3, ,r3,r3 , ,r5,r5, ,r5,r5 ;char action2255;int goto1123=/goto状态符号 1 , 2 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 8 , 2 , 3 , 0 , 0 , 0 , 0 , 9 , 3 , 0 , 0 , 10 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,;int goto2255;void init()for(int i=0;i255;i+)action2i=goto2i=-1;action2i=0;action2+=1;action2*=2;action2(=3;action2)=4;action2#=5;goto2e=0;goto2t=1;goto2f=2;ex1.a=e;ex1.b=e+t;ex2.a=e;ex2.b=t;ex3.a=t;ex3.b=t*f;ex4.a=t;ex4.b=f;ex5.a=f;ex5.b=(e);ex6.a=f;ex6.b=i;void pop(string &s)/若s为【0,5,10】，则把s改为【0,5】，即删除最后一个逗号以后的数据。int l=s.length();for(;sl!=,;l-);s=s.substr(0,l);void work()puts(状态栈 符号栈 输入串);int i=0;coutleft;stack state;/状态栈stack ch;/符号栈string statestring=0;/状态栈的显示string chstring=;/符号栈的显示state.push(0);coutsetw(23)statestring;putchar(#);coutsetw(23)chstring;coutsetw(23)s.substr(i,s.length()endl;trywhile(1)if(a=si&si=z)/si为非终结符int k=goto1state.top()goto2si;ch.push(si);chstring=chstring+si;state.push(k);if(k10)statestring=statestring+,+char(k+0);elsestatestring=statestring+,1+char(k%10+0);i+;else/si为终结符if(action2si=-1)throw 0;string t1=action1state.top()action2si;if(t10=s)/sint k=t11-0;if(t12)k=k*10+t12-0;state.push(k);statestring=statestring+,+t11;if(t12)statestring=statestring+t12;ch.push(si);chstring=chstring+si;i+;else if(t10=r)/rif(chstring.substr(chstring.length()-ext11-0.b.length(),chstring.length()=ext11-0.b)/判断是否能够归约for(int i=0;iext11-0.b.length();i+)state.pop();pop(