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

《北京工业大学 编译原理实验报告.docx》由会员分享，可在线阅读，更多相关《北京工业大学 编译原理实验报告.docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归子程序算法int Procedures(ifstream& from_file) Indent();coutHSHendltype = IF) coutnameendltype = THEN) coutnameendltype = WHILE) ProcedureC(from_file);token = TokenScan(from_file);Indent ();if (token-type = DO) coutnameendltype = IDN) coutnid : nnameendltype = EQU) Indent();coutnameendltype = MORE) cout

2、nameendltyp= LESS) coutnameendlendl; ProcedureE(from_file); else exit(-1);)indentation -= 4;/子程序结束 return 0;int ProcedureE(ifstream& from_file) 工ndnt();coutnEnendltype = ADD) Indent();coutnameendltype = MINUS) Indent();coutnameendlendl; ProcedureT(from_file); else i+)for (int i = 0; i name.length();

3、 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();coutnameendltype = DIC) 工ndnt ()

4、;coutnameendlendl;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();coutnFnendltype = LBRAC) coutnameendlendl;ProcedureE(from_file);token = ToknSc

5、an(from_fil)； coutnameendltype = IDN) coutnid : nnameendltype = INT8) coutnint8 : Hvalue)endltype = INT10) coutnintlO : nvalueendltype = INTI 6) coutnintl6 : nvalue)endlT (+T) *类似的产生式 没有写循环调用控制，后来在(+T)*的最外层加了一个while(true)循环，然后 在while(true)的首行加入了不是+ 就return的判定，成功解决了问题。2、缩进的控制：这个实验中碰到的第二个问题就是语法树缩进的控制问

6、题，最终通过一个全 局变量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.

7、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，

8、C.true) | | gen( gotoz C.false)C - Ei E2C . code = Ei. code | | E2. code | |gen(ifz Ei.place 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.place

9、TI.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

10、.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 =三地址代码生成器的数

11、据结构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 cod

12、CODES工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 的属性At

13、trE 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 标签， 在前面预置了一Proced

14、ureC(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

15、= 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

16、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 的

17、属性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,

18、n%s%sntif %stype = 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); e

19、lse 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 name.length(); i+) f rom_f ile . unget () ; / /回退/E-T/ /strcpy_s(e.pla

20、ce,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实验中遇到的问题及其

21、解决：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的

22、标号： 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/%s

23、n,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 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;Tok

24、en* 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);

25、)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_v

26、aluezn%dr 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 x207 then while ytype = IF) c . c_true = NewLabel () ; /c . c_truetB 口有了新标签si. begin = c . c_true; / C真则往 SI走si. next = c . c_false = s

27、. 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的时候定位到正确的标号：s

28、printf_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

29、|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() ；词法分析算法:

30、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)

31、 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 (

32、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

33、 m /以下为数字 的检测 /if (isdigit(ch) valuei+ = ch;/如果第一个数字是0,则有可能是工NT10的0、1NT8或工NT16if (ch =。)ch = from_file.get();if (ch =。& ch = 101& 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;