词法分析器 C C.doc

词法分析器 C C
词法分析(1)---词法分析的有关概念以及转换图
词法分析是编译的第一个阶段,前面简介中也谈到过词法分析器的任务就是:
字符流--词法记号流
这里词法分析和语法分析会交错进行,也就是说,词法分析器不会读取所有的词法记号再使用语法分析器来处理,通常情况下,每取一个词法记号,就送入语法分析器进行分析,图解:
词法分析器是编译器中与源程序直接接触的部分,因此词法分析器可以做诸如
1).去掉注释,自动生成文档(c#中的///注释)
2).提供错误位置(可以通过记录行号来提供),当字符流变成词法记号流以后,就没有了行的概念
3).完成预处理,比如宏定义
,词法单元(lexeme),模式
模式是一种规则
每个词法单元都有一个特定记号
比如int a=3,这里int,a,=,3都是词法单元,每个词法单元都属于某个词法记号,比如3就是"num"这个词法记号的一个词法单元,而模式规定了什么样的字符串的词法记号是什么样的(模式是一种规则)
某一特定模式规定了某个词法记号下的一类词法单元,比如:
模式:用字母开头的包含字母和数字的串
上面模式的词法记号:id(所有符合上面模式的字符串的记号都是id)
词法单元:a123或者aabc等
词法记号举例(简称为记号):
1)每个的关键字都有属于自己的一个记号,比如关键字for,它可以使用记号for;关键字int,可以使用记号int 2)所有的关系运算符只有一个记号,比如=,=都用记号relation 3)所有的标识符只有一个记号,比如a123,aab使用记号id 4)所有的常数只有一个记号,比如123,22,,23E10使用记号num 5)所有的字符串只有一个记号,比如"123","ab1"使用记号literal
在实际的编译器设计中,词法记号,一般用一个整形数字表示
词法记号的属性:
我们喜欢用词法记号,属性这个二元组来描述一个词法单元,比如,对于源代码:position:=initial+rate*60
对于词法单元+,我们可以使用add_op,'+'来表示。
有些情况,更加复杂一点,比如对于position,我们表示是这样的,id,指向符号表中的position元素的指针,详细来说应该是这样的,假定属性是一个字符串,那么id将指向这样一个字符串"position[message]",我们把存放这个字符串的地方叫做符号表。有些时候,属性是不必要的,比如:=,表示赋值,我们可以使用assign_op,257这样的表示这个词法单元,不过这个显得有些多于,因为assign_op和词法单元是一对一的,也就是assign_op只对应了:=,所以额外信息(属性)就显得多余的了
词法错误:
词法分析器是很难(有些错误还是可以检测)检测错误的,因为词法分析器的目的是产生词法记号流,它没有能力去分析程序结构,因此无法检测到和程序结构有关的错误,比如:
fi(a==b)
词法分析器不会找到这个错误,它认为fi是一个标识符,而不是一个关键字,只有在后面的阶段中,这个错误才会被发现,这是一个与程序结构有关的错误
词法分析器,只能检测到词法单元上的问题,,作为一个词法单元,却不没有对应的模式,那么就是产生一个错误。
:
前面说过模式是一种规则,为了使用,我们需要一种规范的方式来表达模式,这就是正规式
1)串和语言
字符类(又叫字母表):关于字符的有限集合
串:字符类上字符的有穷序列,串这个概念,具体来说是,某个字符类上的串
串的长度:串中字符的个数,比如串s=abc,那么串的长度为3,用|s|表示串的长度
空串:用ε表示
语言:某字符类上的串的集合,属于语言的串,成为语言的句子或字
比如:{abc,a}这就是一个语言,abc和a就是句子。另外空集也是属于语言
连接:x是串,y是串,x和y连接,结果就是xy这个串。假如x是串,x^3为xxx。对于x^n(n=0),x^0=ε
语言的运算(假定L和M是语言):
UM={s|s属于L或者M},例如:
L={1,2}M={3,4}那么L UM={1,2,3,4}
={st|s属于L且t属于M},例如:
L={a,b}M={1,2}那么LM={a1,a2,b1,b2}ML={1a,1b,2a,2b}
^n=(n个L),例如:
L={a,b}那么L^3={aaa,aab,aba,abb,baa,bab,bbb,bba}
注意n可以为0,L^0={ε}
*=L^0 UL^1 UL^2 UL^3 U.
L*表示,语言L中,所有的句子(串)以任意数目任意顺序组成的句子的集合,包括ε,例如:
{a