词法分析

词法分析器

作用

读入字符流, 组成词素, 输出词法单元序列.

将词素添加到 符号表 中

过滤空白, 换行, 制表符, 注释等

概念

词法单元(token)

通常是 <词法单元名, 属性值>

词法单元名是表示词法单位种类的抽象符号, 语法分析器通过单元名即可确定词法单元序列的结构
属性值通常用于语义分析之后的阶段

模式(Pattern)

描述了一类词法单元的词素可能具有的形式

词素(Lexeme)

源程序中的字符序列

它和某个词法单元的模式匹配, 被词法分析器识别为该词法单元的实例

eg

printf("Total = %d\n", score);

printf和score与标识符id的模式匹配
"Total = %d\n"与literal的模式匹配

词法单元	非正式描述	词素示例
if	字符i,f	if
comparison	<或>,<=,=>,==,!=	<=,!=
id	字母开头的字母/数字串	Pi,score,D2
number	任何数字常量	123
literal	在两个"之间,除"以外的任何字符	"Hello, World!\n"

词法单元

属性

一个模式匹配多个词素时, 必须通过属性来传递附加的信息

属性值将被用于语义分析, 代码生成等

不同的目的需要不同的属性

属性值通常是一个结构化数据
如词法单元id的属性: id内容, 类型, 第一次出现的位置...

词法错误

词法分析器本身很难发现源代码的错误, 如fi(true)无法判断fi是if写错了, 还是有fi这个函数.

词法分析器会返回id词法单元给语法分析器处理.

当所有模式都无法和剩余输入的某个前缀匹配时:

词法分析器不能继续处理输入
错误恢复策略
- 从剩余的输入中删除一个字符
- 向生育的输入中插入一个遗漏的字符
- 用一个字符来替换另一个字符
- 交换两个相邻的字符

规约 - 正则表达式

正则表达式可以高校处理词法单元的模式

串和语言

字母表: 一个有穷的符号集合
- eg: 字母, 数字, 标点符号
- {0, 1}, Unicode
- 理论上, 任意的有限集合都可以看作是字母表
字母表上的串(string)是该表中符号的有穷序列
- 串s的长度是指s中符号出现的次数
- 空串ε的长度为0
语言是某个给定字母表上的串的可数集合
前缀: 从串的尾部删除任意个符号后得到的串
后缀: 从串的开始处删除任意个符号后得到的串
子串: 删除串中的某个前缀和某个后缀后得到的串
真前缀/真后缀/真字串: 不等于原串或空串的前缀/后缀/子串
子序列: 从串中删除任意个符号后得到的串
串的运算
- 连接: x和y的连接是把y附加到x的后面, 记作xy.
x=dog, y=house, 则xy=doghouse
- 指数运算: x^n表示n个x连接在一起, x^0=ε
x=ha, 则x^3=hahaha
语言的运算
- 并: $L \cup M = {s | s \in L or s \in M}$
- 连接: $L M = {x y | x \in L and y \in M}$
- 克林闭包: $L^{*} = ⋃_{n \geq 0} L^{n}$
- 正闭包: $L^{+} = ⋃_{n \geq 1} L^{n}$

词法分析 ​

词法分析器 ​

作用 ​

概念 ​

词法单元(token) ​

模式(Pattern) ​

词素(Lexeme) ​

eg ​

词法单元 ​

属性 ​

词法错误 ​

规约 - 正则表达式 ​

串和语言 ​