东南大学-编译原理-词法分析器实验报告

1、东南大学-编译原理-词法分析 器实验报告词法分析设计1. 实验目的通过本实验的编程实践，了解词法分析的任 务，掌握词法分析程序设计的原理和构造方法， 对编译的基本概念、原理和方法有完整的和清楚 的理解，并能正确地、熟练地运用。2. 实验内容用C卄语言实现对C+语言子集的源程序进 行词法分析。通过输入源程序从左到右对字符串 进行扫描和分解，依次输出各个单词的内部编码 及单词符号自身值;若遇到错误则显示“Error”, 然后跳过错误部分继续显示；同时进行标识符 登记符号表的管理。3. 实验原理本次实验采用NFA->DFA->DFAO的过程：对待分析的简单的词法（关键词/id/num/

2、运算符/空白符等）先分别建立自己的FA,然后 将他们用£产生式连接起来并设置一个唯一的开 始符，终结符不合并。待分析的简单的词法(1) 关键字："asm", "auto", "bool", "break", "case", "catch", "char*, "class", "const", "const_cast"等(2) 界符(查表)9999(>)>>1>(3) 运算符

3、"%",""，"卄"，"一"，"%=relop：(4)其他单词是标识符(ID)和整型常数(SUM),通过正规式定义。id/keywords:letter ex dig"return (fcf7b<x#i().mnalUDl)digit:（3）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字, 词法分析阶段通常被忽略。空白、制表符和换行符:deMm4. 相关自动机描述DFA:DFAO：5.流程图5. 核心数据结构描述(1) 生成的 token 序列由 nam

4、e、type、attr 保 存。struct tokenstring name;string type;int erttr;(2) 本文的大多数数据结构都用map來保存，优点是査找方便，大大提侖时间复杂度。map<string, int> Keywords; map<string, int> Sep; map<string, int> Relop; map<string, int> Op; map<string, int>id; map<string, int>num;保存关键字保存界符/保存比较运算符保存其他运算符保存输

5、入字符串中的id保存数字vector<token>Token;/保存token序列，大小未知，所以采用vector保存6. 核心算法描述(1)void addToken(string sy int type) S为找到的字符串，type为可能类型。将分析出来的token ()序列添加到Token序列表中。如果是类型为1,查看关键词表，若找到,其类型为关键词并将其以类型为关键词存储到Token表中；若未找到，则查找id表，若找到,说明该id已经出现过，否则添加新的id到id表中，将该i字符串以类型为id添加到Token表中。如果类型为2,在界符表中查找，如果找 到以类型为界符存储到T

6、oken表中，同理其他几 种类型。可能类型为1-5,如果出现其他类型 表示是词法分析器中发现额错误，将错误信息记 录下来。void addToken(string s, int type)switch(type)case 1：l_it=Keywords. find(s);if (l.it! =Keywords. end 0) token t =s, "keywords： l_it->second;Token push_back (t);elsel_it=id. find(s);if (l_it=id. endO)ids=idNum;token t=s, "id&quo

7、t;, idNum+;Token push-back(t);else token t=s> *id*, l_it->second;Token push_back(t);break;case 2：l_it=Sep. find(s);if (l.it! =Sep. end () token t=s, separatrix*, l.it->second;Token push_back(t);break;case 3：l_it=0p. find(s);if (l_it! =0p end 0) token t=s, "op",second;Token push_ba

8、ck(t);break;case 4:l_it=Relop. find(s);if (l_it!=Relop. end () ) token t=s, "relop", l_it->second; Token push.back(t);break;case 5：l_it=num< find(s);if (t=nunL end 0)nums=nNnm;to ken t=s, "num： nNum+;Token push_back (t);else token t =s, "num", l-it>secon<l; Token

9、 push_back (t);break;defauIt：/errortoken t=s, *id*, -1;Token push-back (t);break;(2)void lexical 0 词法分析器，按字符读入文法并对其进行处理。从状态0开始处理，如果定空白符则一立在状态0,如果第一个字符为字母，继续往后寻找，II至不 是字母或是数字结束；若第一个字符为数字，将其拼凑成一个数字，数字可以有小数点等，详细见状 态转换图，注意以数字开头容易出现一种例如3a类型的错误，所以以数字开头的一定要往下多找一 个，看最后一个数字后面是否为空白符或界符或者其他允许出现的符号，如果后面紧跟着字母则报错

10、。 如上同理分析运算符等。注意每次处理完遇到一个字符串都要将其送到addToken0添加到Token表 中并回到状态0,继续往下处理。void lexical ()fstream ln("E：】ntxt");char ch, tempeh;int state=0;string s= , key=;while(! In. eof 0 )switch(state) case 0： ch=lnget();s=ch;if (ch=13! |ch=10| |ch=32| : ch=9)state=O; s二"；else if (ch='<)state=l;el

11、se if (ch=，=，) state=6;else if (ch=,) state=9;else if (isLetter(ch) state=13;else if (isDigit(ch) state=15;else if (ch=, +f | |ch=,| |ch=, | |ch=, P |ch=, 4" | |ch=, |") state=20; tempch=ch;else if (ch='"') state=44;else if (isSep(ch) !=T)state=47;else if (isOp(s)!=-l) state=4

12、8;else if (isRelop(s)!=-l) state=49;else state=5O;/errorbreak;case 1: ch=ln get ();if (ch=，| |ch=, >') state=2;else if(ch='<)state=4;else state=5;break;case 2：s+=ch;addToken (s, 4);state=O;break;case 4：s+=ch;addToken (s, 3);state=O;break;case 5：/*addToken(s； 4);ln seekgios：: cur);state

13、=O;break;case 6： ch=ln get ();if (ch=,) state=7;else state=8;break;case 7：s+=ch;addToken (s, 4);state=0;break;addToken (s> 3);ln seekg ("1, ios：: cur);state=0;break;case 9： ch=ln get ();if (ch= =，) state=10;else if (ch >* ) state=ll;else state=12; break;case 10:s+=ch;addToken (s, 4);state

14、=0;break;case 11：s+=ch;addToken(s, 3);state=0;break;case 12：/state=0;addToken (s, 4);ln seekg (-1, ios：: cur); break;case 13： ch=ln. get();if(isDigit(ch)11isLetter(ch) s+=ch;else state=14;break;case 14：/*state=0; addToken (s, 1); ln seekg(-1, ios：:cur); break;case 15： ch=ln< get ();if (isDigit(ch

15、) s+=ch;else if (ch=,")s+=ch;state=16;else state=18;break;case 16： ch=ln< get ();s+=ch;/errorif (isDigit(ch) state=17; else state=50;break;case 17： ch=ln. get ();if (isDigit(ch) s+=ch;state=17;else state=18; break;case 18：/*if (isLetter(ch)s+=ch; state=50;elseaddToken(s, 5);ln seekg (-1, ios

16、：:cur);state=0;break;case 20: ch=ln. get ();if (ch=tempch | | ch= =>) state=21; else state=23;break;case 21：s+=ch; addToken(s> 3); state=0;break;case 23：addToken (s,3);In. seekg(-1, ios：:cur); state=0;break;case 44： ch=ln< get ();if (ch=，=，) state=45;else state=46; break;case 45：s+=ch;addTo

17、ken(s, 3); break;case 46：addToken (s,3);ln seekg (-1, ios：: cur);break;case 47：addToken(s, 2);state=0;break;case 48：addToken(s, 3);state=0;break;case 49：addToken(s, 4);state=0;break;case 50：/errorwhile(ch=ln. getO) !=EOF) if(isSep(ch)! =-l | | ch=1311 ch=101 | ch=321 I ch=9) break;else s+=ch;addToke

18、n (s, 6);/errorIn. seek?(-1, ios：:cur);state=0;break;default：break;7. 测试用例待测字符串：void fun ()int a=2, b=3, 3a;a+;b一； a+二b; b*=a;int c=a+4; int d=b*5;产生结果在out. txt中（注意, 件都要保存在E盘根目录下）无论输入输出文token sequence:REtokenat trivoidkeywords58funid0(separatri/2)separatrix3separatriy6inikeywords27aid1op62Eium0ssepa

19、ratrix1bid2=op63num19separatrix13 aErrorseparatrix0aid1+4-op11bseparatrix0id2op129separatrix0aid1+=c>P13bid2bseparatrix0id2+=op15aid1zseparatrix0intkeywords27cid3二OD6aid1+op34num2/separatrix0irrtkeywords27did4c>p6id2cp0num3separatrix 0separatrix 7kejwords: asm auto bool break case catch char c

20、lass const constcast continue default delete do double dynamic_cast else enum cxpllcit extern false float for friend goto if inline int long mutable namespace new op er at oro 1 O - 3 4 5 6 T no 9 o 1 3 4 5 6 T 2 9 o 1 0. 01234567891111111111 2 22 0 2 2 22 2 23 3 3private33protected34public35register36reinterpret_cast37reitirn32short39si