知识

词汇分析（扫描）

  • 基本概念与正则表达式

    • 词法分析器做什么？

    • 它是如何工作的？

    • 形式化单词定义与识别

  • 词法分析器生成器
词汇分析器的作用
  • 词法分析器(词法分析器) 是编译器的第一阶段，它逐字符读取源程序以生成用于语法分析的标记。
  • 通常，词法分析器不会一次返回标记列表，而是在解析器向其请求标记时返回标记。
  • 词法分析器=扫描+词法分析
词汇分析

alt

  • 将源程序作为字符文件读取。
  • 将文件划分为单词。
  • 单词: 表示源程序中的一个信息单元。
  • 例如：关键词/保留字, 标识符、算术符号、多字符符号（>=，<>）。
  • 重点：
    • 单词的规范和识别-正规/正则表达式
    • 如何识别单词——有限自动机
    • 用C或LEX编程的词法分析器的设计
图 词法分析器与语法分析器的交互

alt

词汇分析中的几个问题
  • 词法分析和句法分析的分离提供了一个更简单的概念模型
  • 从软件工程的角度来看，该部门强调
  • 高内聚低耦合
  • 意味着明确的→并行实现
  • 分离可以提高编译器效率（I/O技术可以增强词法分析）
  • 分离促进了可移植性.
  • 在平台（操作系统和硬件）众多且多样的今天，这一点至关重要！
  • 平台独立性的出现——Java
透视中的词汇分析器
词法分析器
  • 扫描输入
  • 删除WS，NL…
  • 识别单词
  • 创建符号表
  • 将单词插入ST
  • 产生错误
  • 向解析器发送单词
解析器
  • 执行语法分析
  • 由象征性命令决定的行动
  • 更新符号表条目
  • 创建源代码的抽象代表
  • 产生错误
  • 还有更多…。（我们稍后再看）
介绍基本术语

词汇分析的主要术语是什么？

  • 代币
    • 一组常用字符串的分类
    • 例如，等。
  • 图案
    • 表征单词字符串集的规则
    • 调用文件和操作系统通配符（[A−Z]∗.∗）（[A-Z]*.*）
  • 词素
    • 与模式匹配并由标记分类的字符的实际序列
    • 标识符：x、计数、名称等…
标记、模式、词素
  • 由于一个标记可以代表多个词素，因此应该为该特定词素保留其他信息。此附加信息称为属性(属性)象征性的。
  • 为简单起见，单词可以有一个属性，该属性保存该单词所需的信息。
  • 对于标识符，该属性是指向符号表的指针，符号表保存该标记的实际属性。
  • 标记类型及其属性唯一标识词素。
  • 正则表达式(正规表达式）广泛用于指定模式。
  • 单词是扫描仪中的逻辑单元。
  • 词素是单词的一个实例。
图 单词示例

alt

单词的属性
  • 单词的属性：与单词关联的任何值
  • 词法分析器将有关标记的信息收集到它们的相关属性中。
  • 标记影响解析决策；这些属性会影响标记的翻译。
  • 通常一个单词只有一个属性——一个指向符号表条目的指针，其中保存着关于单词的信息。
  • 一些属性：（参见示例3.1）
    • <id，attr>其中attr是指向符号表的指针
    • <assgop，不需要属性（如果只有一个赋值运算符）
    • <num，val>其中val是数字的实际值。
扫描过程
  • 单词：扫描仪生成的逻辑单元。
  • 单词分为几类：
    • 保留词：如果，那么
    • 标识符：ID
    • 操作符号：正、负
    • 数字：NUM
    • 字符和字符串：STR
    • 其他：{，}，（，），；，，“，'，/*
  • Lexeme（字符串值）：由标记表示的字符串。
  • 标记一个词素或多个词素
  • 单词的属性：与单词关联的任何值
  • 标记许多属性
  • 扫描器需要计算一个单词的至少相同数量的属性。
  • 单词记录： 类型定义结构
Typedef struct 
{ TokenType tokenval;
char *stringval;
int numval;
} TokenRecord

  • 一种更常见的安排是：扫描器只返回标记值，并将其他属性放入变量中（例如在LEX和YACC中）。

  • 输入字符字符串保存在缓冲区中，或由系统输入设备提供。

输入缓冲

  • 每次字符输入/输出（getc、UNG等）

  • 块/缓冲I/O

    • 利用内存块
    • 一次将数据从源转移到缓冲块
    • 维护两个模块-为什么（召回操作系统）？
      • 异步I/O-用于1个数据块
      • 在第二块进行词汇分析时

    alt

算法：带哨兵的缓冲I/O
图 带有哨兵的前瞻代码。

alt

forward : = forward + 1 ;
if forward ↑ = eof then begin
	if forward at end of first half then begin
		reload second half ;//← Block I/O
		forward : = forward + 1
	end
	else if forward at end of second half then begin
		reload first half ;//← Block I/O
		move forward to beginning of first half
	end
else / * eof within buffer signifying end of input * /
	terminate lexical analysis
end//2nd eof → no more input !

算法执行I/O。我们仍然可以使用get&ungetchar

现在这些工作在真正的内存缓冲区！

一次字符输入/输出
图 词法分析构词原理的示意图

alt

词法分析程序是调用标准库函数来实现字符的读取和放回的，读取的字符是放在单词的缓冲区中，直至组成一个合法的单词。词法分析程序返回单词的值（整型），其属性值通过结构变量yyvalue带回的。

单词规范

语言概念：

语言L就是固定字母表上的任意一组字符串。 alt

语言术语
  • 字母表：一组有限的符号（ASCII字符）
  • 字符串：
    • 字母表上的有限符号序列
    • 句子和单词也用于表示字符串
    • ε是空字符串
    • |s |是字符串s的长度。
  • 语言：固定字母表上的字符串集
    • Φ空集是一种语言。
    • {ε} 包含空字符串的集合是一种语言
    • 所有可能的标识符集都是一种语言。
  • 字符串上的运算符：
    • 连接：xy表示字符串x和y的连接。s ε = s | ε s = s
    • sn^n=s。。s（n次）s0^0=ε
示例和其他概念：

假设：S是banana

  • 前缀：ban，banana
  • 后缀：ana, banana
  • 子串：nan, ban, ana, banana
  • 子序列：bnan，nn

正确的前缀、子前缀或子字符串不能都是S

语言操作
语言操作的定义

alt

Ex3.2

L = {A, B, C, D } D = {1, 2, 3} alt

语言与正则表达式

  • 正则表达式是从字母表中构造符号（字符串）序列的一组规则/技术。
  • 允许∑ 是字母表，r是正则表达式。那么L（r）就是语言，以r的规则为特征。
正则表达式
  • 我们使用正则表达式来描述编程语言的符号。
  • 正则表达式由使用一组定义规则的简单正则表达式组成。
  • 每个正则表达式r表示一种语言L（r）。
  • 用正则表达式r表示的语言L（r）称为正则集。
  • 正则表达式r：由它匹配的字符串集定义。
  • L（r）：由正则表达式生成的语言。
  • 字符集：是ASCII字符集或其子集
  • ∑: 法律符号，称为字母表。
  • 规则的压制符号表示模式、元字符（元符号）。
  • 反斜杠和引号（转义字符）：关闭元字符的特殊含义。
指定正则表达式的规则

固定字母表∑

  • ∈ 是一个正则表达式，表示{∈}
  • 如果a在∑, a是表示{a}的正则表达式
  • 设r和s是语言为L（r）和L（s）的正则表达式。

然后

  • （r） |（s）是一个正则表达式→ L（r）∪ L（s）
  • （r） （s）是正则表达式→ L（r）L（s）
  • （r） 是正则表达式→ （L（r））
  • （r） 是正则表达式→ L（r）

所有这些都是左关联的。优先规则允许删除括号。 字母表上的正则表达式∑ alt

Ex1
  • ∑ = {0,1}
  • 0|1 => {0,1}
  • (0|1)(0|1) => {00,01,10,11}
  • 0* => {ε ,0,00,000,0000,....}
  • (0|1)* => all strings with 0 and 1, including the empty string
Ex2

L = {A, B, C, D } D = {1, 2, 3} alt

正则表达式的代数性质

alt

Ex1

∑＝{A,…,Z, a,…,z} 所有以“tab”开头或以“bat”结尾的字符串：

tab[A,…,Z,a,...,z]*|[A,…,Z,a,....,z]*bat

Ex2

∑＝{A,…,Z} 数字1,2,3以升序存在的所有字符串：

[A,…,Z]*1 [A,…,Z]*2 [A,…,Z]*3 [A,…,Z]*ε

正则定义
  • 为某些语言编写正则表达式可能很困难，因为它们的正则表达式可能非常复杂。在这些情况下，我们可以使用正则定义。
  • 我们可以给正则表达式命名，我们可以用这些名称作为符号来定义其他正则表达式。
  • 正则定义是形式定义的一个序列： alt

正则定义：将名称与正则表达式关联

PASCAL IDs

alt

课堂练习

1

鉴于：∑={a，b，c}，用正则表达式描述最多包含一个b的所有字符串集。

参考答案

∑={a，b，c}

最多包含一个b的所有字符串的集合。

(a|c)*(b|ε)(a|c)*     (a|c)*|(a|c)*b(a|c)*

同一种语言可能由许多不同的正则表达式生成。

2

给出：字母→ A | B |……|Z | a | b |……|Z

数字→ 0 | 1 | ... | 9

用正则表达式描述Pascal或C语言中的标识符和数字。

参考答案

Pascal或C语言的标识符

字母→ A | B |……|Z | a | b |……|Z

数字→ 0 | 1 | ... | 9

身份证件→ 字母（字母|数字）*

如果我们试图在不使用正则定义的情况下编写表示标识符的正则表达式，那么该正则表达式将非常复杂。

（A |…| Z | A |…| Z）（A |…| Z |…| Z）|（0 |…| 9））*

3 Pascal或C中的无符号数

digit → 0 | 1 | ... | 9

参考答案
digits → digit +
opt-fraction → ( . digits ) ？
opt-exponent → ( E (+|-)？ digits ) ？
unsigned-num → digits opt-fraction opt-exponent

回顾

  • 有限自动机概念述评
    • 非确定性和确定性FA
    • 转换过程
      • NFA的正则表达式
      • NFA至DFA
      • DFA的正则表达式
  • 将NFAs/DFAs/转换与词汇分析联系起来
  • 结束语/展望未来

作业

1
  1. 描述下列正规式（正则）定义的语言（请用汉语直白地描述该语言）
a) 0(0 | 1)*0
b) ((e | 0)1*)*
c) (0|1)*0(0|1)(0|1)
d) 0*10*10*10*
e) (00| 11)*((01 | 10)(00 | 11)*(01 | 10)(00 | 11)*)*
2
  1. 为下列语言写出正规定义(或正规式)
a) 包含五个元音，且按顺序排列的所有字母串（RE）
b) 字母按字典升序排列的所有字母串（RE）
c)以/*开始，*/结束的注释，中间不能包含*/，除非包含在"和"中（RE） 
d) 不包含重复数字的数字串（正规定义） 
e) 包含至多一个重复数字的数字串（正规定义） 
f) 包含偶数个0和奇数个1的0、1串 （正规定义）