实验一词法分析.docVIP

编译原理实验一 词法分析 1.实验目的 通过实验掌握词法分析的理论、原理和方法，为语法分析做准备。 2.实验内容: 十六进制数识别器：规定是：必须以十六进制数字打头，以H结尾，十六进制数中允许使用的数字为0-9，字母为A，B，C，D，E, F(分别表示0~15)。试设计一个DFA，使它能识别无符号的十六进制整数，并编制相应的识别程序。 输入：学生自行确定符号串的输入形式，如键盘输入、文本文件、字符数组等。 输出：标识出规范的符号串与不合规范的符号串。 词法分析：设计、编制、调试一个识别一个Little语言单词的词法分析程序（见附录1）。 输入：学生自行确定符号串的输入形式，如键盘输入、文本文件、字符数组等。 输出：二元组。 3.实验要求： 上机前编写完整的实验报告，报告中要体现分析?设计?实现等几个过程；如无实验报告，则取消本次上机资格，实验成绩以0分记。 严禁相互抄袭，否则实验成绩以0分记； 有完整的源代码，源码有规范的注释，无明显的语法错误； 4.实验步骤 分析与设计 a、 文法：该语言的十六进制，如：0aH，77H，7BH等由以数字打头及以H结尾；该语言的标识符，如：Num，a3，go等由A到Z(or a到z)和0至9所组成；该语言的无符号的十进制，如：8，90，123等由0到9之间的任意数字组成。由以上可得出该语言的文法可表示如下： G(S) = (VN，VT，P，S) ???????其中VN?=?{S，X’，Y’，Z’，M’，W’，α，β，γ，μ，υ，ω} ????VT?= {0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z, A,B,C,D,E,F,G,H,I,G,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z} ???α= 0|1| 2|3|4|5|6|7|8|9 ????β?= a|b|c|d|e|f|A|B|C|D|E|F γ?=g|?h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|G|H|I|G|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z ??????S??→?X’|Y’|Z’ ???????X’?→?υ|υM’ ?M’?→ω|ωM’ υ?→β|γ ω?→α|β|γ ????????Y’?→?α|αY’ ????????Z’?→?αH|αW’H ?W’?→μ|μW’ ?μ?→α|β 可见，上式方法中，X’表示出了语言的标识符，而Y’表示出了语言的无符号的十进制，Z’表示出了语言中的十六进制。 ∵?上式G(S)文法中，各式右边只有单个的终结符号 ∴?显然，以上文法G(S)已是正规文法。 (2)正规文法转成正规式：具体步骤如下： ∵???M’?→?ω|ωM’???? ??可表示为M’?→ω*ω W’?→?μ|μW’???????可表示为W’?→μ*μ??? ??????????????Z’??→?α|αZ’?????????可表示为Z’?→?α*α ????∴ 转换成正规表达式为：S=υ| υω*ω |αH | αμ*μH |α*α 代入可得：S= (β|γ) | (β|γ) (α|β|γ)*(α|β|γ) |αH | α(α|β)*?(α|β)H |α*α ? (3)正规式转成NFA（分裂法） 初始的NFA图下所示： 图1?初始NFA图 经过替换规则替换后得到的最终NFA图如下所示： ? 图2?最终的NFA图 (4)NFA转成DFA及DFA最小化（造表法） 对应以上的NFA图，我们可用造表法来表示如下： ? ????显然，由图可看出，状态2与状态5等价，而状态1与状态3等价，这里省去状态3和状态5，并将所以指向状态3的状态都指向状态1，指向状态5的都指向状态2。由此可画出最小化的DFA图如下： 图3??最小化的DFA图 ? 可见，终结状态1表示出了无符号的十进制，终结状态2表示出了标识符，状态6表示出了十六进制的整数。 b、 单词的BNF表示 标识符- 字母字母数字串 字母数字串-字母字母数字串|数字字母数字串| 下划线字母数字串|ε 无符号整数- 数字数字串 数字串- 数字数字串 |ε 加法运算符- + 减法运算符- - 大于关系运算符- 大于等于关系运算符- = 由此可知，需将单词分为五种： 关键字1 标识符2 常数3 运算符4 分隔符5 printf a 0 + , main b 1 _ ; int c 2 * ( if student 3 / ) then sum 4 = { else k 5 } return m 6 …. …. …. 7 = 8 = 9 != 编码实现