第三章__词法分析及词法分析程序.pptVIP

第三章 词法分析及词法 分析程序; 第三章 词法分析及词法分析程序;§3.1 词法分析(lexical analysis)程序的设计;2、词法分析过程 逐个读入源程序字符，然后按照构词规则切分成一列单词，再转换成单词序列。 单词是语言中具有独立意义的最小单位。词标(token）是单词类型的机内表示，其格式由实现系统规定。;3、词法分析程序的输出（二元组）; 在词法分析阶段，对词标确定一种属性。 如常数词标的值即为其属性； 标识符词标，除值外，还需要记载其类别、层次及其他属性，均收集在符号表中。因此，标识符单词的二元式为: (标识符，标识符所在符号表中位置指针) 通常，单词的词标可用整数编码表示。 例：标识符为1，常数为2，保留字为3，运算符为4等。;§3.2 正规文法和状态转换图;1、状态转换图;2、状态图识别符号串;3、由文法构造状态图;b;G［S］： S→aA|bB A→bB|aD|a B→aA|bD|b D→aD|bD|a|b; 注意：若文法中含有ε产生式，则对G中的所有ε产生式A→ε，都从节点A引一条矢线到终态节点，且标记为ε。; 对符号串W=a1a2a3……an，ai∈ VT 识别过程： 从初态S出发，自左至右逐个扫描W中的字符，在S状态下扫视的符号为a1； 在节点S所射出诸矢线中寻找标记为a1的矢线(若不存在，则说明W有错)； 读入a1，沿矢线方向到下一状态，在此状态时扫描a2，……， 直至W中全部字符读完且进入终态F，则W已被接受。;b;结 论;3) 左线性文法向状态图转换方法 构造状态集：设G=（VN，VT，P，S）是一左线性文法，|VN|=k,共有k+1个节点（状态）。其中，k个状态是非终结符号（或是其编号），另一个状态引入一个F∈V,作为初态，终态为S。 构造状态间弧：P中每个产生式，对于 形如A→Ba的产生式,从节点B引一条矢线到节点A,矢线标记为a； 形如A→a的产生式，从初态F引一条矢线到A，并用符号a标记此矢线;例：S→Ua|Vb U→Vb|a V→Ua|b; 对于符号串W=a1a2a3……an，ai∈VT 可对W识别。 从初态F出发，自左至右逐个扫视W中的各个字符，在F下扫视的符号为a1； 在节点F所射出诸矢线中寻找标记为a1的矢线（若不存在，则说明W有错）； 读入a1沿矢线所指方???到下一状态，在从此状态扫描a2，……， 直到W中全部字符读完且进入终态S，则W已被接受。;A;结 论;4、状态转换图的实现—状态矩阵; a1 a2 …… am ;§3.3 有限自动机;一、确定的有限自动机—DFA;1、定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中 K是一个有穷集，它的每个元素称为一个状态； Σ是一个有穷字母表，它的每个元素称为一个输入字符，所以也称Σ为输入符号字母表； f是转换函数，是在K×Σ→K上的映像，即：如果f（ki，a）=kj，（ki，kj∈K）意味着，当前状态为ki，输入字符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态； S∈K是唯一的一个初态； Z? K是一个终态集，终态也称可接受状态或结束状态。;DFA M=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为： f（S，a）=U f（V，a）=U f（S，b）=V f（V，b）=Q f（U，a）=Q f（U，b）=V ;有穷自动机DFA M 构造： ∑= VT; K= VN ∪{N}, N为一个新状态,它不在VN中; q0 =S; F={N},终态集; 对G中的形如 D→tB的产生式,t为终结符或ε,有f(D,t)=B； 对G中形如D→t的产生式， t为终结符或ε,有f(D,t)=N;?; 假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出； 整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”，终态结点用双圈表示； 若 ? (ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；; 矩阵行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。 用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。;4、DFA识别符号串;例1：证明t=baab被下面的DFA所接受。;例2：根据如下状态图，写出DFA，证明baab可为此DFA接受。;算法：模拟DFA。