编译原理 第三章上 :词法分析 状态图的画法与检验

第三章 词法分析

写在最前，本节把握重点是状态图的画法及检验句子的合法性

3.1 词法分析的功能

扫描源程序字符流，按照源语言的词法规则识别出各类单词符号，并产生用于语法分析的符号序列。

即字符串源程序➡️通过词法分析➡️符号串源程序

词法分析的功能是识别出具有独立意义的单词，输出的就是这些单词的符号。

功能：

1.识别单词和值

2.删去空格，换行，制表符及注释。

错误检查：

1.非法字符检查

2.关键字拼写错误检查

3.不封闭错误检查

3.2.1 状态图

什么样的图是状态图？

状态图的画法 :

1. 添加开始符号S S是我们手动额外添加的，作为状态图的开始，注意在它的左边画上箭头
2. 所有非终结符号对应一个状态，文法的识别符号作为终结符号，要画两个圈。
3. 形如U→a的规则，从S出发画线指向U，线上标记a
4. 形如U→Wa的歌则，从W出发画线指向U，标记为a在前述章节中，学习了正则文法的结构，就是U→a和U→Wa这两种规则，故而状态图的画法也围绕着这两种方式。

手把手题目代练：

1.有正则文法GZ:

Z::=Ua|Vb

U::Zb|B

V::Za|a

画出文法的状态图

2.已知状态图写出正则文法

3.2.2 状态图的用法

状态图是用来识别句子的，检验句子的合法性。

图片说明：

1.状态是当前要出发的状态，即上一步的结果状态

2.从左往右扫描

3.3 正则表达式

正则表达式可简要描述的内容不多，建议翻书

正则表达式表示相同的语言，则称这两个表达式等价。

正则表示式的部分运算满足结合律，交换律和分配律。

3.3.1 正则文法到正则表达式的转换

补充一个无关的小考点：

test语言的词法分析器