北京工业大学 编译原理实验报告.docx

递归子程序算法int Procedures(ifstream& from_file) Indent();cout<<HSH<<endl<<encil;indentation += 4;/子程序开始Indent ();Token* token = TokenScan(from_file);if (token->type = IF) cout<<token->name<<endl<<endl;ProcedureC(from_file);token = TokenScan(from_file);Indent ();if (token->type = THEN) cout<<token->name<<endl<<endl;Procedures(from_file); else exit (-1);) else if (token->type = WHILE) ProcedureC(from_file);token = TokenScan(from_file);Indent ();if (token->type = DO) cout<<token->name<<endl<<endl; Procedures(from_file); else exit (-1);) else if (token->type = IDN) cout<<nid : n<<token->name<<endl<<endl; token = TokenScan(from_file);if (token->type = EQU) Indent();cout<<token->name<<endl<<endl;ProcedureE(from_file); else exit (-1);)indentation -= 4;/子程序结束return 0;int ProcdureC(ifstream& from_file) Indent ();incantation += 4;/子程序开始 Token* token;ProcedureE(from_file);token = ToknScan(from_fil)； Indent();if (token->type = MORE) cout<<token->name<<endl<<endl; ProcedureE(from_file); else if (tokn->typ= LESS) cout<<token->name<<endl<<endl; ProcedureE(from_file); else exit(-1);)indentation -= 4;/子程序结束 return 0;int ProcedureE(ifstream& from_file) 工ndnt();cout<<nEn<<endl<<endl;indentation += 4;/子程序开始Token* token;ProcedureT(from_file);while (true) token = TokenScan(from_file);if (token->type = ADD) Indent();cout<<token->name<<endl<<endl;ProcdurT)； else if (token->type = MINUS) Indent();cout<<token->name<<endl<<endl; ProcedureT(from_file); else i+)for (int i = 0; i < (int)token->name.length(); f rom_f il ungt () ; / /回退indentation -= 4;/子程序结束return 0;indentation -= 4;/子程序结束return 0;int ProcedureT(ifstream& from_file) Indent ();indentation += 4;/子程序开始Token* token;ProcedureF(from_file);while (true) token = TokenScan(from_file);if (token->type = MUL) Indent();cout<<token->name<<endl<<endl;ProcedureF(from_file); else if (token->type = DIC) 工ndnt ();cout<<token->name<<endl<<endl;ProcedureF(from_file); else for (int i = 0; i < (int)tokn-namlength(); i+) f rom_f ile . unget () ; / / 回退)incantation -= 4;/子程序结束return 0;)indentation -= 4;/子程序结束return 0;int ProcedureF(ifstream&) 工ndnt();cout<<nFn<<endl<<endl;indentation += 4;/子程序开始Token* token;tokn = TokenScan(from_file);if (token->type = LBRAC) cout<<token->name<<endl<<endl;ProcedureE(from_file);token = ToknScan(from_fil)； cout<<token->name<<endl<<endl;Indent ();if (token->type = IDN) cout<<nid : n<<token->name<<endl<<endl;)if (token->type = INT8) cout<<nint8 : H<<ValueOfINT8(token->value)<<endl<<endl;)if (token->type = INT10) cout<<nintlO : n<<token->value<<endl<<endl;if (token->type = INTI 6) cout<<nintl6 : n<<ValueOfINTI6(token->value)<<endl<<encil;)indentation -= 4;/子程序结束return 0;)实验结果：实验中遇到的问题及其解决:1、消除左递归，提取左因子之后的E、T对应的子程序的编写问题:经过多次测试，我发现在一个expression超过两个运算符的时候我的E、T子 程序就只能成功的分析出第一段的式子，后来发现E->T (+T) *类似的产生式 没有写循环调用控制，后来在(+T)*的最外层加了一个while(true)循环，然后 在while(true)的首行加入了不是'+ '就return的判定，成功解决了问题。2、缩进的控制：这个实验中碰到的第二个问题就是语法树缩进的控制问题，最终通过一个全 局变量indentation来控制缩进的字符数量，一个Indent ()函数来输出缩进 (其实就是空格)，控制缩进数量的关键点有两个：一为进入子程序的时候 indentation+=4,二为结束子程序的时候indentation-=4o剩下的就是根 据调试来选择在哪里输出缩进空格的问题了。实验三语法制导的三地址代码生成程序语法制导定义:产生式语义规则S -> id = E ;S.code = E.code | gen(id.placeE.place)S -> if C then SC . true = newlabel;C.false = S.next;Si.next = S.next;S.code = C.code | gen (C.true ':，) | SI.codeS -> while C do SS.begin = newlabel;C.true = newlabel;C.false = S.next;Si.next = S.begin;S.code = gen(S.begin ':，) | C.code | gen(C.true ':，) | | Si.code | I gen( 'goto' S.begin);C -> Ei > E2C . code = Ei. code | | E2. code | |gen('if7Ei.place '>， E2.place 'goto， C.true) | | gen( 'gotoz C.false)C -> Ei < E2C . code = Ei. code | | E2. code | |gen('ifz Ei.place '<， E2.place 'goto， C.true) | | gen ( 'goto，C.false)E -> Ti (+ T2) *E.place = newtemp;(E.code = TI.code I IT2.code| |gen (E.placeTI.place ' + ' T2.place);TI.place = E.place;TI.code = E.code;)+E -> Ti (- T2) *E.place = newtemp;(E.code = TI.code I IT2.code| |gen (E.placeTI.place '-' T2.place);TI.place = E.place;TI.code = E.code;)+E -> TE.place = T.place;E.code = T.codeT -> FT.place = F.place;T.code = F.codeT -> Fl (* F2)*T.place = newtemp;(T.code = Fl.code | F2.code |gen (T.place' Fl.placeF2.place);Fl.place = T.place;Fl.code = T.code;)+T -> Fl (/ F2) *T.place = newtemp;(T.code = Fl.code | F2.code |gen (T.placeFl.place '/' F2.place);Fl.place = T.place;Fl.code = T.code;)+F -> ( E )F.place = E.place;F.code = E.codeF -> idF.place = id.name; F.code =F -> int8F.place = int8.value; F.code =F -> intlOF.place = intlO.value;F.code =F -> intl6F.place = intl6.value; F.code =三地址代码生成器的数据结构type def struct /*S 的属'性定义文/char codeCODESIZE; int begin; int next; AttrS; type def struct /*E 的属性定义大/char codeCODESIZE;/CodeSize = 500char placeBUFSIZE;/BufSize = 200AttrE;type def struct / *C 的属'性定义大/char codCODES工ZE;int c_fals；/用来标记入口 int c_true; /用来标i己入口AttrC;type def struct /*T 的属性定义文/char codCODES工ZE;/CodSiz=500char placBUFS工ZE:/BufSiz=200AttrT;type def struct /*F 的属 t生定义大/char codeCODESIZE;/CodeSize = 500 char placeBUFSIZE;/BufSize = 200 AttrF;type def struct /*IDN 的属'性定义大/char idnameBUFSIZE; int entry; AttrIDN;三地址生成器算法:int ProcdureS(ifstram&， AttrS &s) AttrC c;/C 的属性AttrS si; /si 的属性AttrE e;/e 的属性char tmp_idn_nam50 ;/用来暂存当下一个是工DN时，s->id: =E 的 id的 nameToken* token = TokenScan(from_file);/s-> if C then SI/ /if (token->type = IF) c. c_true = NewLabel () ; /c . c_true 出 口有了新标签si .begin = c . c_true; / C 真 则往 SI 走si. next = c . c_false = s . next; / c 假 贝U 走 s 的下一步 为 L0 标签， 在前面预置了一ProcedureC(from_filer c);token = TokenScan(from_file);if (token->type = THEN) Procedures(from_file, si);sprintf_s(s.code, nnt%snL%d:t%sH, c.code, c.c_true, si. code) ; /将中间代码输出至U s,code中 else exit(-1);)/s-> while C do SI/ / else if (token->type = WHILE) si.next = s.begin = NewLabel ();c . c_true = si .begin = NewLabel () ; /C M 往 SI 走c. c_false = s . next; / c假 则 走s的下一步 为L0标签，在前面预置了ProcedureC(from_file, c);token = TokenScan(from_file);if (token->type = DO) Procedures(from_file, si);sprintf_s(s.code,nnL%d:t%snL%d:t%sntgoto L%d ",s.begi n,c.code,c.c_true,si code,s.bagin); else exit(-1);/s-> id := E/ / else if (tokn->typ=工DN) strcpy_s(temp_idn_name, token->name.c_str();token = TokenScan(from_file);if (token-type = EQU) ProcedureE(from_file, e);sprintf_s(s.code,H%snt%s=%sn,e.code, temp_idn_name r e.pla ce); else exit(-1);)return 0;)int ProcedureC(ifstream& from_file, AttrC &c) AttrE1; /1的属性AttrE e2; /e2 的属性Token* token;ProcedureE(from_file, el);token = TokenScan(from_file);if (token->type = MORE) ProcedureE(from_filez e2);sprintf_s(c.code, n%s%sntif %ss goto L%dntgoto L%dH,el. code,2 , code,el.place,e2.place,c.c_true,c.c_false); else if (token->type = LESS) ProcedureE(from_file, e2);sprintf_s(c.code, n%s%sntif %s<%s goto L%dntgoto L%dn,el. code,2 , code,el.place,e2.plac,c c_tru,c , c_fals); else exit(-1);)return 0;int ProcdurE(ifstram& from_file, AttrE &) AttrT tl;AttrT t2;Token* token;ProcedureT(from_file, tl);while (true) tokn = TokenScan(from_file);if (token->type = ADD) ProcedureT(from_file, t2);strcpy_s(e.place,NewTemp();sprintf_s (e . code, n%s%snt%s=%s4-%sn, tl. code, t2 . code, e . pl ace,tl.plac,t2.place);/这里是关键，用tl.code和tl .plac临时记录了上一次while的e . code和 e.place,随着whil的不断加深，tl的代码会不断长长strcpy_s(tl. code,e.code);strcpy_s(tl.place,e.place); else if (token->type = MINUS) ProcedureT(from_file, t2);strcpy_s(e.place,NewTemp();sprintf_s(cod,"%s%snt%s=%s-%s”,tlcode, t2.cod, pl ace,tl.place,t2.place);strcpy_s(tl. code,e.code);strcpy_s(tl.place,e.place); else for (int i = 0; i < (int)token->name.length(); i+) f rom_f ile . unget () ; / /回退/E->T/ /strcpy_s(e.place,tl.place);sprintf_s(e.code,H%sn,tl.code);break;)return 0;int ProcedureT(ifstream& from_file, AttrT &t) AttrF fl;AttrF f2;Token* token;ProcedureF(from_file f fl);while (true) tokn = TokenScan(from_file);if (token->type = MUL) 目录实验一词法分析程序的设计与实现3词法的正规式描述: 3状态图：4词法分析程序数据结构与算法：4词法分析算法：5实验结果：7实验中遇到的问题及其解决：81、保留字的检测问题：82、关于。为首位的数字是int8、intlO和intl6的判断问题： 83、关于回退的问题：8实验二 自顶向下的语法分析一递归子程序法9改写后的产生式集合：9化简后的语法图：9递归子程序算法10实验结果：13实验中遇到的问题及其解决： 141、消除左递归，提取左因子之后的E、T对应的子程序的编写问题：142、缩进的控制：14实验三 语法制导的三地址代码生成程序15语法制导定义：15三地址代码生成器的数据结构16三地址生成器算法：17实验结果：21实验中遇到的问题及其解决：221、根据化简后的产生式修改语法制导定义：222、使用真假出口法和继承属性来确定goto的标号： 22ProcedureF(from_file, f2);strcpy_s(t.place,NewTemp();sprintf_s(t code,n%s%snt%s=%s*%sn,fl.code,f2.code,t.pla ce,fl.place,f2.place);strcpy_s(fl.code,t.code);strcpy_s(fl.place,t.place); else if (tokn->typ= DIC) ProcedureF(from_file, f2);strcpy_s(t.place,NewTemp();sprintf_s(t . code,"%s%snt%s=%s/%sn,f1.code,f2.code,t.pla ce,fl.plac,f2.place);strcpy_s(fl.cod,t cod);strcpy_s(fl.place,t.place); else for (int i = 0; i < (int)token->name.length(); i+) f rom_f ile . unget () ; / /回退)strcpy_s(t.place,fl.place);sprintf_s(t.code,"%sn,fl.code);break;)return 0;)int ProcedureF(ifstream& from_file, AttrF &f) AttrE e;Token* token;char temp_value50;token = ToknScan(from_fil)；if (token->type = LBRAC) ProcedureE(from_file, e);strcpy_s(f.place,e.place);/f.place = e.placesprintf_s(f.code,"%sn,e.code);token = TokenScan (f rom_f ile) ; / /匹酉己右括号if (token->type = IDN) strcpy_s(f .place,token->name.c_str();sprintf_s(f.code,"0H);)if (token->type = INT8) sprintf_s(temp_value, d”, ValueOfINT8(token->value);strcpy_s(f.place, temp_value);sprintf_s(f.code,"0H);if (token->type = INT10) /sprintf_s(temp_value, "d”， _itoa_s(token->value,);strcpy_s(f.place,token->value.c_str();sprintf_s(f code,n0n);)if (token->type = INTI 6) sprintf_s(temp_valuezn%d"r ValuOf工NT16(token->value); strcpy_s(f.place, temp_value);sprintf_s(f.code,n0n);)return 0;)实验结果：口input -记事本文件(F)编辑(E) 格式查看(V) 帮助(H)tvhi 1 e(a3+l5)>0xa do if x2>07 then while y<z do y=x*y/z这是三地址程序的输入，存 在名为it.txt由文本文 档中实验中遇到的问题及其解决:1、根据化简后的产生式修改语法制导定义:主要难点在于ET1什T2)*此种产生式当循环调用的次数多于1的时候需要做一步Tl.place = E.place;Tl.code = E.code 将上一次循环的E.code和E.place暂存到jTl.code和Tl.place 中，这样在下一次循环中通过E.code = Tl.code| |T2.code| |gen(E.place 二'Tl.place '+' T2.place) 就可以正确的重新生成E的新的三地址代码。2、使用真假出口法和继承属性来确定goto的标号：在本程序中并没有使用拉链回填的方法实现goto,而是使用下面的实现方法： 例如,S fife then S和Swhile C do S这种的产生式，(1)在S中，先创建所有用到的非终结符的属性结构体：AttrC c;/C的属性AttrS si; / /si的属性AttrE e;/e的属性(2)在match完if和while后，用以下语句构造真假出口if (token->type = IF) c . c_true = NewLabel () ; /c . c_truetB 口有了新标签si. begin = c . c_true; / C真则往 SI走si. next = c . c_false = s . next; / c假 贝lj 走s的下一步 为L0标签， 在前面预置了一else if (token->type = WHILE) si.next = s.begin = NewLabel();c . c_true = si .begin = NewLabel () ; /CM 则往 SI走c . c_false = s . next; / c假 则 走s的下一步 为L0标签，在前面预置了.一在构造完真假出口后进入C的子程序(将S中定义的C的属性传进去，也就实现了将标号 传进去)ProcedureC(from_file, c);(4)这样子在c子程序结亦需要goto的时候定位到正确的标号：sprintf_s(c.code, "%s%sntif %s>%s goto L%dntgoto L%dpr e 1. code,e2.code,el.place,e2.place,c.c_true,c.c_false);实验一词法分析程序的设计与实现词法的正规式描述：标识符字母(字母I数字字符)*十进制整数 0| (1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*八进制整数 0(0|1|2|3|4|5|6|7) (0|1|2|3|4|5|6|7)*十六进制整数0(x|X)(0|l|2|3|4|5|6|7|8|9|a|b|c|d|e|f)(0|l|2|3|4|5|6|7|8|9|a|b|c|d|e If)*运算符和分隔符+-*/=()；关键字 if then else while do .状态图:词法分析程序数据结构与算法：/单词类class Token public:int type;/种别string value;/属性值string name; /单词具体内容Token () type = DEFAULT;value = NONE_OF_VALUE;)Token(int type, string value, string name) : type(type)r value(value) , name (name)-Token() ；词法分析算法:Token* TokenScan(ifstream &from_file) char ch;/用于保存从文件中读取的字符/读第一个字符int i = 0;char value 30 = "，/用来存放tokn的属性值 ch = from_file.get();while (ch = BLANK | ch = TAB | ch = NEWLINE) ch = from_file.get();)/ 以下为标识符的检测 /if (isalpha (ch) valuei+ = ch;ch = from_file.get();/判断后续的是否为工DN的成分(数字或字母)while (isalnum(ch) valuei+ = ch;ch = from_file.get();)/直到不是工DN成分，回退一字符from_file.unget();/TODO：这里加上保留字检测部分/进行字符串的对比，即可比较出保留字，通过压栈的形式来获得完整的属性值 / 以下为保留字的检测 /if (strcmp(value, WORD_IF) = 0) return new Token(IF, NONE_OF_VALUE, WORD_IF);if (strcmp(value, WORD_THEN) = 0) return new Token(THEN, NONE_OF_VALUE, WORD_THEN);if (strcmp(value, WORD_ELSE) = 0) return new Token(ELSE, NONE_OF_VALUE, WORD_ELSE);if (strcmp(value, WORD_WHILE) = 0) return new Token(WHILE, NONE_OF_VALUE, WORD_WHILE);if (strcmp(value, WORD_DO) = 0)return new Token(DO, NONE_OF_VALUE, WORD_DO);return new Token(IDNZ value, value);n m m m m m m m n n m n m /以下为数字 的检测 /if (isdigit(ch) valuei+ = ch;/如果第一个数字是0,则有可能是工NT10的0、1NT8或工NT16if (ch =。)ch = from_file.get();if (ch >=。&& ch < 181) | | ch = 1x | | | ch = 1X1) /如果。后面紧跟着数字0-8,则为工NT8if (isdigit(ch) while (ch >= 101&& ch < * 8') valuei+ = ch;ch = from_file.get();)from_file.unget();return new Token(INT8, value, value);)valuei+ = ch;/到这一步的都是INT16 ch = from_file.get();while (isdigit(ch) | | (ch >= 1 a1&& ch <= 1f1) valuei+ = ch;/TODO:这里没有解决Oxrtr的问题 ch = from_file.get();)from_file.unget();return new Token(INT16, value, value); else /0后面的不为0-7的digit或x或X等 8或16进制特征字符，则为10进制的 0,回退一个字符from_file.unget();return new Token(INT10, value, value);)/能到这一步的都是工NT10,且不为0打头ch = from_file.get();while (isdigit(ch) valuei+ = ch;ch = from_file.get();)from_file.unget();return new Token(INT10, value, value);)/ 以下为运算符的检测 /valuei+ = ch;