词法分析和有限自动机词法分析器和语法分析器的相互作用.docVIP

第3章 词法分析和有限自动机 1．词法分析器和语法分析器的相互作用 见教科书屠3。1 2．单词符号、词法记号 单词符号是程序设计语言的基本语法符号，它由该程序设计语言的字母表上的字符，按照该语言的词法规则组成的。 3．单词符号的表示 单词符号的输出通常用二元组表示： (单词种别，单词自身的值) 单词种别说明单词所属的类别，单词的值则是单词在类中的属性值，是为了正确区分同一类别中的不同单词所必须的。 4．Token 单词种别又称为token。 5．模式 构成单词的规则称为模式，它用于刻画token。 6．词素 词素是与关于token的模式所匹配的源程序中的一个字符串。 7．词法规则 隶属于语法规则， 8．把词法分析分离出来作为一个独立的阶段来考虑，有如下好处： (使整个编译程序的结构更简洁、更清晰和更有条理化； (提高了编译程序的效率； (增加了编译程序的可移植性； 9．正则表达式 由一些运算对象（符号串）和一些运算符号按照一定的规则组成，类似于算术表达式，它是描述正则集的工具。 10．正规集 正规式表示简单的语言，叫做正规集 11．正则式和正则集的定义 设∑是一字母表，∑上的正则式和正则集定义如下： 1.ε和φ是∑上的正则表达式，所表示的正则集分别为{ε}和φ。 2.任何a∈∑，a是∑上的正则表达式，所表示的正则集为{a}。 3.设e1和e2都是∑上的正则表达式，所表示的正则集分别为L(e1)和L(e2)，那么， (1) (e1)是∑上的正则表达式，所表示的正则集为L(e1); (2) e1|e2是∑上的正则表达式，所表示的正则集为 L(e1)∪L(e2)； (3) e1(e2是∑上的正则表达式，所表示的正则集为L(e1) L(e2)； (4) e1*是∑上的正则表达式，所表示的正则集为(L(e1))*。 4.仅由有限次使用上述三步骤而定义的表达式才是∑上的正则表达式，仅由这些正则式所表示的集合才是∑上的正则集。 12．正则式的等价 若e1和e2都是∑上的正则表达式，它们所表示的正则集分别为L(e1)和L(e2)，且有L(e1)＝ L(e2)，则称e1和e2等价。 13．正则式的运算法则 14．有限状态自动机 它是具有离散输入输出系统的数学模型。它具有有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继行为。它的当前状态概括了过去输入处理的信息。 15．有限状态自动机特点 有限状态自动机作为一种识别装置，它能准确地识别正则集，即识别正则文法所定义的语言和正则式所表示的集合。 16．有限状态自动机分为两类： (确定的有限自动机 (不确定的有限自动机。 17．有限自动机模型 18．不确定的有限自动机（NFA） 定义 一个不确定的有限自动机（NFA）N是一个五元组： N＝（VT,Q,δ, q0, Qf）, 其中每个要素的含义要弄清楚 19．NFA的表示方式 有如下三种： 1．定义式 2．状态转移图 3．状态转移表 20．状态转移图 假定NFA M含有m个状态，n个输入符号，那么这个状态图含有m个结点，每个结点最多有n条弧射出，若δ(qi,a)=qj, 则从状态结点qi到状态结点qj画一标记为a的弧，整个图含有唯一一个初态结点，用“=”标记，含有若干个终态结点，用双圈表示。 21．状态转移表 NFA用转移表表示时，列为矩阵的形式;矩阵的行表示状态，列表示输入字符，矩阵元素表示在相应行状态和相应列输入字符下的NFA可能走向的状态集。 22．NFA接受输入串ω 对于∑*中的任何字符串ω，若存在一条从初态到终态的通路，且这条路上所有弧的标记符连接成的字符串恰好等于ω，则称ω可为NFA M所接受，若M的初态结点同时又是终态结点，则空字ε可为M所识别（接受）。 23．NFA接受的集合 NFA接受的集合称为NFA识别的语言 NFA M所能接受的字符串的全体（字的全体）记为L(M), L(M)＝{ω|ω∈∑* ， (’(q0, ω)=P, 其中 q0 ∈Q为NAF M的开始状态，P(Q, P∩Qf ≠ (， Qf为终态集} 24．确定的有限自动机（DFA） 定义 一个确定的有限自动机（DFA）M是一个五元组： M＝（VT,Q,δ, q0, Qf）,其中 其中每个要素的含义要弄清楚 25．NFA的表示方式 有如下三种： 1．定义式 2．状态转移图 3．状态转移表 26．确定的有限自动机的状态转移图 确定的有限自动机的状态转移图表示与非确定的有限自动机的状态转移图相同; 但是,确定的有限自动机的状态转移图中每个状态关于每个输入符号都有一条唯一的转移弧.而非确定的有限自动机的状态转移图中每个状态关于每个输入符号可能有多条