词法分析(1)---词法分析的有关概念以及转换图
词法分析是编译的第一个阶段，前面简介中也谈到过词法分析器的任务就是：
字符流------>词法记号流

这里词法分析和语法分析会交错进行，也就是说，词法分析器不会读取所有的词法记号再使用语法分析器来处理，通常情况下，每取一个词法记号，就送入语法分析器进行分析，图解：



词法分析器是编译器中与源程序直接接触的部分，因此词法分析器可以做诸如
1). 去掉注释，自动生成文档(c#中的///注释)
2). 提供错误位置(可以通过记录行号来提供)，当字符流变成词法记号流以后，就没有了行的概
念
3). 完成预处理，比如宏定义


1. 词法记号，词法单元(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,32.3,23E10使用记号num
5) 所有的字符串只有一个记号，比如"123","ab1"使用记号literal
在实际的编译器设计中，词法记号，一般用一个整形数字表示

词法记号的属性：
我们喜欢用<词法记号, 属性>这个二元组来描述一个词法单元，比如，对于源代码：position := initial + rate * 60
对于词法单元 +，我们可以使用 <add_op, '+'> 来表示。
有些情况，更加复杂一点，比如对于 position，我们表示是这样的，<id, 指向符号表中的position元素的指针>，详细来说应该是这样的，假定属性是一个字符串，那么id将指向这样一个字符串"position\0"，我们把存放这个字符串的地方叫做符号表。有些时候，属性是不必要的，比如 := ，表示赋值，我们可以使用 <assign_op,257> 这样的表示这个词法单元，不过这个显得有些多于，因为assign_op和词法单元是一对一的，也就是assign_op只对应了:=，所以额外信息(属性)就显得多余的了

词法错误：
词法分析器是很难(有些错误还是可以检测)检测错误的，因为词法分析器的目的是产生词法记号流，它没有能力去分析程序结构，因此无法检测到和程序结构有关的错误，比如：
fi(a == b)
词法分析器不会到这个错误，它认为 fi 是一个标识符，而不是一个关键字，只有在后面的阶段中，这个错误才会被发现，这是一个与程序结构有关的错误
词法分析器，只能检测到词法单元上的问题，比如 12.ab ，作为一个词法单元，却不没有对应的模式，那么就是产生一个错误。


2. 正规式：
前面说过模式是一种规则，为了使用，我们需要一种规范的方式来表达模式，这就是正规式
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是语言)：
1. L U M = {s|s属于L或者M}，例如：
L={1,2} M={3,4} 那么 L U M = {1,2,3,4}

2. LM = {st|s属于L且t属于M}，例如：
L={a,b} M={1,2} 那么 LM = {a1,a2,b1,b2}  ML={1a,1b,2a,2b}

3. L^n = LLL (n个L)，例如：
L={a,b} 那么 L^3 = {aaa,aab,aba,abb,baa,bab,bbb,bba}
注意 n 可以为0，L^0 = {ε}

4. L* = L^0 U L^1 U L^2 U L^3 U ...
L*表示，语言L中，所有的句子(串)以任意数目任意顺序组成的句子的集合，包括 ε，例如：
{a,b}* = {ε,a,b,ab,ba,aab,aba,baa,bba,bab,abb,}
L*叫做L的闭包

5. L+ = L^1 U L^2 U L^
L+表示，语言L中，所有的句子(串)以任意数目任意顺序组成的句子的集合，但是不包括 ε
L+中的句子和 L*中的句子相比少一个 ε

那么，我们通过上面的知识就可以表示一个标识符了，我们知道一般语言规定标识符是由字母开头，后接若干个字母或数字，我们可以这样来表示： L={a-z A-Z} N={0-9}，那么标识符就是 L(L U N)*


2) 正规式
正规式又叫正规表达式，正规式是模式得一种规范的表达形式，正规式描述了一个集合，这个集合是由串组成的，其实这个集合就是我们前面说过的语言，不过这里大家喜欢使用正规集这个术语。正规式 r 表示正规集L(r)
正规式的运算：
1. 闭包运算，运算优先级最高，(r)* 表示 (L(r))*
2. 连接运算，运算优先集合低于闭包，(r)(s) 表示 (L(r))(L(s))
3. 或运算，运算优先集合最低，(r) | (s) 表示 (L(r)) U (L(s))
例如：
a | b 表示集合(语言，正规集) {a,b}
(a | b)(a | b) 表示集合(语言，正规集) {aa,ab,ba,bb}
a* 表示由一切a字符组成的集合(语言，正规集)，包括 ε
(a | b) 表示由a,b组成的集合(语言，正规集)，包括 ε
等价的正规式：字符串是什么字符的集合(a | b) = (b | a)
正规式的代数性质：
1. r|s = s|r
2. r|(s|t) = (r|s)|t
3. (rs)t = r(st)
4. r(s|t) = rs|rt

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。