重点：状态转换图，有穷自动机。

1. 词法分析的主要任务：从左至右逐个字符地对源程序进行扫描，按照构词规则识别出每个单词，如果识别过程中发现错误或无法识别单词，输出有关错误信息。

2. 词法分析程序的主要任务：扫描源程序，识别单词，查找单词的token值，转换并输出token串，输出相应错误信息。

3. 词法分析程序的输出：与源程序等价的单词的中间形式（称为token串，或单词符号串、单词记号串）。

4. 词法分析的主要工作：

1） 扫描源程序，从源文件中读入字符流到输入缓冲区中

2） 按构词规则识别单词，输出单词本身及其种别码

3） 滤掉源程序中的无用成分，如注释、空格、回车换行等

4） 调用出错处理程序，识别并定位错误

5. 词法分析程序的两种实现方式：

1） 手工编写高级语言程序实现

2） 使用词法分析自动生成工具

6. 常用单词分类：

1） 关键字：具有固定意义的标识符

2） 标识符：标识自己命名的各个对象

3） 运算符：指明进行的运算类型，一般分为三类：算术运算符、逻辑运算特和关系运算符

4） 界符：类似于自然语言中的标点符号，用来分隔单词，可分为单界符和双界符

5） 常数：固定不变的值

7. 种别码（token 值）：对每个单词（或单词类别）进行编码。（对能识别的单词的分类编码）

8. 单词识别方式：超前搜索技术和状态转换图。

9. 状态转换图：是一张有限方向图。有限个状态，用结点表示状态，其中有一个初态（初态用剪头指出），至少有一个终态（终态用双圈表示）。状态之间用带箭头的弧线连接，弧线上标记的字符表示在射出状态下可能出现的输入字符和字符类。

10. 单词识别过程

1） 初始时，状态转换图位于初态，输入指针指向输入缓冲区的开始。

2） 从输入缓冲区中读入一个字符，会使状态发生转换。

3） 当输入指针不断扫描输入缓冲区的字符流时，状态转换图中的状态不断地发生转换，直到状态转换到接受状态。

11. 字母表：一个高级语言程序能够使用的全体字符构成的集合称为字母表，即该语言的合法字符集。是一个有穷非空集合，其中的每个元素称为一个符号。

12. 字母表上的符号串：是指由该字母表中的符号构成的有穷序列，又称为字。

13. 字的前缀：指从字的开头取0个或多个符号得到的符号串。

14. 字的后缀：指从字的末尾取0个活多个符号得到的符号串。

15. 字的子串：从字中删除任意前缀或后缀得到的符号串。字的前缀和后缀本身也是子串。

16. 合并多个状态转换图的方法

1） 将多个状态转换图的开始状态合并为一个开始状态

2） 将各个图中读取相同符号后到达的状态合并

3） 从开始状态（或合并后的状态）出发画多条边，分别标识原来多个状态转换图从开始状态（或合并后的状态）出发的边上标识的符号（类），将相同标识的边进行合并。

4） 检查后并后的状态转换图的状态名字，修改使之互不相同

17. 正则表达式：也称正规式，描述所有通过对某个字母表上的符号串集合应用并、连接和克林闭包运算而得到的语言。

18. 正规表达式由两种基本形式ε和a，以及|、·、*三种运算递归定义而成。

19. 集合的运算

1） 集合U和V的并：U∪V={s|s∈U或s∈V}

2） 集合U和V的连接：UV={αβ|α∈U并且β∈V}

3） 集合V的n次方幂：Vⁿ=Vⁿ⁻¹V（当n＞0），规定V⁰={ε}

4） 集合V的闭包：V*=V⁰∪V¹∪V²∪V³∪……

20. 正规集：一个正则表达式r所描述的符号串值，也称为正则表达式描述的语言，记为L(r)。

21. 有穷自动机：（也称有限自动机）是具有离散输入与输出的系统的一种数学模型，系统可以处于有限个状态中的任何一个，系统的当前状态概括了过去输入的有关信息，这些信息对于确定系统在以后接受了新的输入时的行为是必需的。

22. 有穷自动机分为确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）:

1） 确定的有穷自动机：指在一个状态下输入一个符号，状态转换到唯一的下一个状态（又称后继状态）。

2） 不确定的有穷自动机：指在一个状态下输入一个符号，可能有两个或两个以上的后继状态。

23. 状态转换表的优点：可以快速找到在给定状态下读入给定输入符号时的下一状态。

24. 状态转换表的缺点：当状态较多、输入字母较多、多数转换为空时，会占用大量无用空间。

25. DFA的特点：

1） 状态转换函数是个单值函数；

2） 从状态转换图来看就是从任何状态出发，对于任何输入符号，最多只有一个后继状态，而且从一个状态出发的所有边上标记的字符均不同；

3） 如果在状态转换表中，每个表项最多只有一个状态。

26. NFA的特点：是它的不确定性，即在当前状态下读入同一个符号，可能有多个后继状态。不确定性反映在NFA的定义中，就是δ函数是一对多的；反映在状态转换图中，就是从一个状态出发可能有多于一条的弧转移到不同的后继状态；反映在转换表中，就是M[i,a]的值不是单一状态，而是一个状态集合。DFA其实是NFA的特例。

27. NFA和DFA的区别：

1） DFA任何状态下都沒有ε转换，即没有任何状态可以不进行输入符号的匹配就直接进入下一个状态。

2） DFA对任何状态S和任何输入符号a，最多只有一条标记为a的边离开S，即转换函数δ:S×Σ→S是一个单值部分函数。

3） DFA的初态唯一，NFA的初态为一集合。

28. 两个有穷自动机的等价是指对任何两个有穷自动机M和M’，如果L(M)=L(M’)，则称M和M’是等价的。

29. 子集法从NFA构造等价的DFA的基本思路：DFA的每一个状态对应于NFA的一组状态，用DFA的一个状态去记录在NFA中读入一个输入符号后可能达到的状态集合。

30. 状态集合I的ε-闭包：ε_Closure(I)，是一状态集

1） 任何状态q ∈ I，则q ∈ ε_Closure(I)；

2） 任何状态q ∈ I，则q经任意条 ε 弧而能到达的状态q′ ∈ ε_Closure(I) 。

31. 状态集合I的a弧转换：Iₐ = ε_Closure(move(I,a))，即所有可从I中的某一状态经过一条a弧而到达的状态的全体。move(I,a)表示从I中任一状态出发经过一条a弧到达的状态的集合。

32. 多余状态：是指从开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。

33. 在有穷自动机中，两个状态S和T等价的条件

1） 一致性条件 —— 状态S和T必须同时为可接受状态或不可接受状态。

2） 蔓延性条件 —— 对于所有输入符号，状态S和状态T必须转换到等价的状态里

34. 分割法的基本思想（核心）：把DFA的全部状态划分成一些互不相交的子集，使得任何不同的两子集的状态都是可区别的（不等价），而同一子集中的任何两个状态都是等价的。

35. 正则表达式和有穷自动机是等价的。

36. Lex是一个基于正则表达式的描述来构造词法分析器的工具，已广泛应用于产生各种语言的的词法分析器，也称为Lex编译器。它的输入是用Lex语言编写的源程序，输出是词法分析的C语言程序。

37. Lex源程序包括3个部分：声明、翻译规则和辅助程序。三部分由%%分开。

1） 声明包括变量声明、常量声明和正则表达式定义。

2） 翻译规则是由一组正则表达式以及当每个正则表达式被匹配时所采取的动作，这些动作是C语言的代码。

3） 辅助程序主要包括一些C语言代码。

38. Lex的工作过程

1） 对翻译规则中的每一个正规式，为之构造一个NFA Mi

2） 将各条翻译规则对应的NFA Mi合并为一个新的NFA M；

3） 然后将NFA确定化为DFA D，并生成该DFA D的状态转换矩阵和控制执行程序。

4） 由于各种语言的状态转换矩阵的结构相同，所以控制执行程序对各种语言都是相同的

39. 二义性的解决

1） 最长匹配原则：当有几个规则看来都适用时，总是寻找可能的最长子串与正规式pi相匹配。

2） 优先匹配原则：如果某个子串可与两个或更多的正规式匹配，并且匹配的长度都相同， Lex以出现在最前面的那个pi为准，也就是说，越处于前面的那个pi，匹配的优先级越高。如果没有正规式可与任何非空子串相匹配，则词法分析器应报告输入含有错误，Lex的默认动作就将下一个字符复制到输出中并继续下去。

40. C代码的插入

1） 写在%{和%}之间的任何文本将被直接复制到外置于任意过程的输出程序之中。

2） 辅助过程中的任何文本都将被直接复制到Lex代码末尾的输出程序中。

3） 将任何跟在翻译规则中的正规式之后的代码插入到识别过程yylex的恰当位置，并在与对应的正规式匹配时执行它。代表一个行为的C代码既可以是一个C语句，也可以是一个由任何说明及由位于花括号中的语句组成的复杂的C语句段。

41. 词法分析中常见的错误

1） 非法字符错误。

2） 拼写错误。

3） 注释、字符常数、字符串常数不闭合。

4） 错误的与或运算。

5） 变量声明有重复。

42. 给出错误信息的方式：

1） 将错误类型和错误信息夹在用户源程序中发现错误的地方，一并给出。

① 优点：方便用户对错误进行处理

② 缺点：如果格式组织不会，容易把源程序搞乱

2） 先把错误信息集中起来，仅在源程序的错误之处做个标记，再调用错误处理函数进行统一输出。

#春日生活打卡季##自考#