编译原理-3-(1)

参考gpt

词法分析器作用

读入源程序字符流、组成词素，输出词法单元序列
过滤空白、换行、制表符、注释等
将词素添加到符号表中

基本术语

1.词法单元

源代码字符串集的分类 <identifier, count>, <number,80>

2.模式——字符串集$\stackrel{\text{分类为}}{\to }$单词的规则

正则表达式，$[A-Z{]}^{\ast }{.}^{\ast }$

3.词素

程序中实际出现的字符串，与模式匹配，分类为单词

词法单元的类别

1.每个关键字有一个词法单元。一个关键字的模式就是该关键字本身
2. 表示运算符的词法单元。表示单个/一类运算符
3. 表示所有标识符的词法单元
4. 一个或多个表示常量的词法单元，比如数字和字面值字符串
5. 每一个标点符号有一个词法单元

词法单元的属性

词素的更多信息

$二元组<记号，属性值>$；属性一般用符号表的指针表示
$position:=initial+rate\ast 60$

< id，指向符号表中position条目的指针>
< assign _ op >
< id，指向符号表中initial条目的指针>
< add_op>
< id，指向符号表中rate条目的指针>
< mul_ op>
< num，整数值60>

词法错误

较少：词法分析是对源程序极为局部化的视角
$fi(a==f(x))...$词法分析无法发现
什么情况下发生——剩余输入的前缀无法与任何一个模式匹配

修复方法:
删除、插入字符
替换、交换字符
最短编辑距离

输入缓冲

加快程序读入速度的方法
若干个字符$\to$正确的词素 = 或< 可能是 == 或 <=至少向前看一个字符
单字符I/O＋预读和回退$\to$效率低下
$磁盘\stackrel{\text{块I/O}}{\to }缓冲区\stackrel{\text{单字符读取}}{\to }词法分析器$

3种实现方式

1. 自动生成工具——Lex，生成工具提供读取输入和缓冲的函数
2. 高级语言手工编码，利用高级语言提供的I/O函数
3. 汇编语言编程，直接访问磁盘
   $1\to 3:性能\uparrow ,实现难度\uparrow$
   唯一读取文件的阶段，值得优化

方案

1. 双缓冲区方案
2. 哨兵标记

双缓冲技术

双缓冲通常涉及2个缓冲区：一个存储输入文本，另一个存储当前正在处理的词素（lexeme）Current token
lexemeBegin：当前词素的开始位置

哨兵标记

每个缓冲区末端添加标记——哨兵sentinel: eof$\to$减少条件判断

词法单元的描述

正则表达式$\to$正规式：描述词素模式的表示方法

有限的重复 一个给定结构的无限重复
regular expression r——表示语言L(r) 利用一组规则(运算)构造
高效描述在处理词法单元时要用到的模式类型，基本r如何递归构成复杂r

定义规则

归纳基础
字母表Σ上的正则表达式r的定义规则，以及r所表示的语言$L(r)$定义：

1. ε是正则表达式，表示语言{ε}
2. 若a∈Σ，则a是正则表达式，表示语言{a}

归纳步骤

r, s为正则表达式，表示语言$L(r),L(s)$，则
优先级逐渐$\uparrow$
$(r)|(s)是正则\to 表示语言L(r)\cup L(s)$
$(r)(s)是正则，表示语言L(r)L(s)$
$(r)\ast 是正则，表示语言{(L(r))}^{\ast }$
$(r)是正则，表示语言L(r)$
$a|b^{\ast }c=(a)|({(b)}^{\ast }(c))$
$e.g:\Sigma =a,b$
a ∣ b → { a , b } a | b\quad\rightarrow\quad\{ a, b\} a∣b→{a,b}
( a ∣ b ) ( a ∣ b ) → { a a , a b , b a , b b } (a | b)(a | b)\quad\rightarrow\quad\{ aa, ab, ba, bb \} (a∣b)(a∣b)→{aa,ab,ba,bb}
a ∗ → { e , a , a a , a a a , … } a^*\quad\rightarrow\quad\{e, a, aa, aaa, …\} a∗→{e,a,aa,aaa,…}
( a ∣ b ) ∗ → { 空串及所有由 a 、 b 组成的符号串 } (a | b)^*\quad\rightarrow\quad\{ 空串及所有由a、b组成的符号串 \} (a∣b)∗→{空串及所有由a、b组成的符号串}
a ∣ a ∗ b → { a , b , 所有以多个 a 开头，后跟一个 b 的符号串 } a | a^*b\quad\rightarrow\quad\{a, b, 所有以多个a开头，后跟一个b的符号串\} a∣a∗b→{a,b,所有以多个a开头，后跟一个b的符号串}
正则集合：正则表达式定义的语言
正则表达式等价：$r=s\leftarrow \to 表示语言相同，L(r)=L(s)$

正则表达式的代数定律

$交换律:r|s=s|r$
$结合律:r|(s|t)=(r|s)|t$
$连接满足结合律:(rs)t=r(st)$
$连接和|满足分配律:r(s|t)=rs|rt,(s|t)r=sr|tr$
$\epsilon 是连接运算的单位元:\epsilon r=r，r\epsilon =r$
$\epsilon 和\ast 间的关系:r^{\ast }={(r|\epsilon )}^{\ast }$
$\ast 是幂等的:r^{\ast \ast }=r^{\ast }$

正则定义

为正则表达式指定名字
$d1\to r1$
$d2\to r2$
$\dots$
$dn\to rn$
di是不同的名字，并且不在Σ 中
ri是$\Sigma \cup d_1,d_2,\dots ,d_{i-1}基本符号与前面定义的名字$上的正则

e.g1:C语言标识符

${(\_|A|\dots |Z|a|\dots |z)(\_|A|\dots |Z|a|\dots |z|0|\dots |9)}^{\ast }$
$letter\_\to A|B|C|\dots |Z|a|b|\dots |z|\_$
$digit\to 0|1|2|\dots |9$
$id\to lette{r}_{(}lette{r}_{|}digit)\ast$
简化：
$letter\_\to [A-Za-z\_]$
$digit\to [0-9]$
$id\to letter\_(letter\_|digit)\ast$

e.g2:C语言无符号数$\to$上下文无关文法

$digit\to 0|1|2|\dots |9$
$digits\to digitdigi{t}^{\ast }$
$optional\_fraction\to .digits|\epsilon$
$optional\_exponent\to (E(+|-|\epsilon )digits)|\epsilon$
$num\to digitsoptional\_fractionoptional\_exponent$
简化:
$digit\to [0-9]$
$digits\to digit+$
$number\to digits(.digits)?(E(+|-)?digits)?$

符号简写

$R^{+}一个或多个字符串从L(R)中匹配L(R):R(R^{\ast })$
$R?R是可选的:(R|\epsilon )$
[abce] 从列表中选择一个字符: (a|b|c|e)$\to$[a-z] :(a|b|c|d|e|…|y|z)
[^ab] 除了列表中的字符之外的任意字符$\to$[^a-z]
$0^{\ast }10^{\ast }10^{\ast }10^{\ast }:{(\epsilon 1^{\ast }|01^{\ast })}^{\ast }包含3个1的01串$
${((\epsilon |0)1^{\ast })}^{\ast }：{(1^{\ast }|01^{\ast })}^{\ast }所有01串\to (1|0{)}^{\ast }$
被5整除的10进制整数$[1-9][0-9{]}^{\ast }(0|5)|0|5$
不包含连续的0的01串:
$(1|0{)}^{\ast }:\epsilon ，0，1，01，10，11，010，101，110，111，\dots$

非正则表达式集——正则无法描述的语言

{wcw | w是a、b组成的符号串}
正规式无法描述平衡或嵌套的结构