ch4词法分析(张素琴)

《ch4词法分析(张素琴)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、词法分析程序的设计单词的描述工具单词的识别系统实现词法分析程序的自动构造第4章词法分析4.1词法分析(lexicalanalysis)程序设计逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留关键字、标识符、常量、运算符、标点符号、分界符等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。4.1.1词法分析程序和语法分析程序的关系源程序词法分析程序语法分析程序Tokeng

2、ettoken….4.1.2词法分析程序的主要任务及输出读源程序，产生用二元组表示的单词符号(单词种类，单词自身的值)。单词种类是语法分析需要的信息，单词自身的值是语义分析和代码生成阶段需要的信息。如consti=25,yes=1;两个单词种类是常数，常数值分别为25,1.滤掉空格，跳过注释、换行符记录源程序的行号，以便出错处理程序准确定位源程序的错误宏展开等……词法分析程序的主要任务读源程序，产生用二元组表示的单词符号(单词种别，单词自身的值)。对某些单词来说，不仅仅需要它的值，还需要其它信息以方便代码生成

3、。如标识符还需要记载它的层次，类别(整形、实形、布尔等)，这些属性都收集到一个符号表中。可以将词法分析输出的单词二元表示设计成(标识符,指向该标示符所在符号表中位置指针)。6界符和运算符:常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。一类型一码。所有的标识符分为一类。一类一码。词类编码原则:一字一码。7表1单词词类编码8对于关键字、界符、运算符来说，它们的词类编码就可以表示其完整的信息，故对于这类单词，其单词自身的属性值通常为空对于标识符，词类编码所反映的信息不够充分，标识符的

4、具体特性还要通过单词自身的属性进行互相区分。标识符的单词自身的属性常用其在符号表中的入口指针来表示对于常数，其单词自身的属性常用其在常数表中的入口指针来表示4.1.3词法分析工作分离的考虑简化设计改进编译效率增加编译系统的可移植性10词法分析的设计形式(1)设计成一个独立程序，完成词法分析的任务，结果以文件的形式组织，做为语法分析的输入源程序词法分析符号表TOKEN字错误信息11词法分析语法分析语义分析和中间代码生成源程序中间代码符号表管理错误的诊查处理(2)作为语法分析和语义分析的子程序用正规文法或者正则表

5、达式描述单词符号的词法构成4.2.1正规文法正规(3型)文法G=(VN,VT,P,S),其中P中的产生式的形式为A→B或者A→，其中A和B是非终结符号，VT*。高级语言中几类单词的3型文法描述：标识符、无符号整数、运算符、标点符号、关键词、无符号实数等。4.2单词的描述工具124.2.2正规式正规式也称正则表达式,是描述单词的构成语法的有效工具，是定义正规集的数学工具。正规表达式（regularexpression）是说明单词的模式(pattern)的一种重要的表示法（记号），用以描述单词符号。正规式

6、的递归定义(1)和都是字母表上的正规式，对应正规集为{}和；(2)任何a,a是上的一个正规式，表示的正规集分别为{a}；(3)假设e1和e2都是上的正规式，表示的正规集分别为L(e1)和L(e2)，则(e1),e1

7、e2,e1.e2,e1*都是上的正规式,它们表示的正规集分别为L(e1)，L(e1)L(e2),L(e1)L(e2),(L(e1))*；(4)仅由有限次使用上述三步骤定义的表达式才是上的正规式，仅有这些正规式表示的子集才是上的正规集。*.

8、三个符号的优先级一次降低，都是左

9、结合的正规式等价：如果它们所表示的正规集相同，称两个正规式等价正规式服从的代数规律：或交换律或的可结合律连接的可结合律分配律或的抽取律存在连接的恒等元素教科书p53例1.={a，b}，上的正规式和相应的正规集aabab(ab)(ab)a(ab)(ab)(aabb)(ab){a}{a,b}{ab}{aa,ab,ba,bb}{,a,aa,……任意个a的串}{,a,b,aa,ab,bb……所有由a和b组成的串}{上所有含有两个相继的a或两个相继的b组成的串}例2.令={l，d}

10、，则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……},其中l代表字母,d代表数字,正规式即是字母(字母

11、数字),它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是程序设计语言允许的标识符词法规则.例3.={d，.，e，+，-},则上的正规式d(.dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。4.2.3正规文