资源描述：
《第3章 词法分析(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章词法分析词法分析词法分析程序概述正规文法与正规式有穷自动机正规式与有穷自动机的等价性正规文法与有穷自动机的等价性一个简单的词法分析器示例状态图的形式化描述3.3有穷自动机S1非字母数字字母字母、数字2非数字数字数字3其他字符+*，（）出口4其他字符<5=非=出错其他标识符无符号整数单界符双界符读字符返回S有穷自动机是一种数学模型，具有离散的输入与输出，系统可处于有穷状态中的任何一个；它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合；引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类
2、：确定的有穷自动机（DFA）(DeterministicFiniteAutomata)不确定的有穷自动机（NFA）(NondeterministicFiniteAutomata)3.3有穷自动机2型文法（不确定的下推自动机）1型文法（不确定的界限自动机）0型文法（图灵机）3型文法（有限自动机）3.3有穷自动机1.确定的有穷自动机（DFA）M=(Σ,Q,f,S,Z)Σ：有穷字母表，它的每个元素称为一个输入符号；Q：有穷集，它的每个元素称为一个状态；S∈K，是唯一的初态；ZK是一个终态集，终态也称可接受状态或结束状态；f是转换函数，是Q×Σ→Q上的
3、单值映射：f（q1，a）=q23.3有穷自动机状态转移函数f可用一矩阵来表示：输入字符状态ab012132213333例如:M:（{0,1,2,3},{a,b},f，0，{3}）f（0，a）=1f（0，b）=2f（1，a）=3f（1，b）=2f（2，a）=1f（2，b）=3f（3，a）=3f（3，b）=3所谓确定的状态机，其确定性表现在状态转移函数是单值函数！M=(Σ,Q,f,S,Z)3.3有穷自动机一个DFA也可以用一状态转换图表示：DFA的状态图表示：1032aabba,bba3.3有穷自动机输入字符状态ab012132213333字母表Σ含
4、有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串α，则称α为DFAM（接受）识别。DFAM所接受的语言为：L(M)={α
5、f(S,α)=Sn,Sn∈Z}DFAM所能接受的符号串的全体记为L(M)若M的初态结点同时为终态，或者存在一条从初态到某个终态结点的ε通路，则ε为M所识别。3.3有穷自动机δ（0，abaab）=δ（1，baab）=δ（2，aab）=δ（1，ab）=δ（3，b）=3(接受)δ（0，abab）=δ（1，b
6、ab）=δ（2，ab）=δ（1，b）=2(拒绝)对于符号串abaab对于符号串abab3.3有穷自动机DFA的状态图表示：1032aabba,bbaf是一个多值函数，是从Q×Σ*到Q的子集的映射：f：Q×Σ→2Q其中2Q是Q的幂集，即Q中所有子集组成的集合。2.不确定的有穷自动机（NFA）M=(Σ,Q,f,S,Z)有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的。3.3有穷自动机例：NFAN=({a,b,c},{1,2,3,4},f,{1},{4})符号状态εabc1{4}{2，3}ΦΦ2Φ{2}{
7、4}Φ3ΦΦΦ{3，4}4ΦΦΦΦ3.3有穷自动机对于Σ*上的任何符号串，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接成的串等于，则称可以被NFAN所识别或接受。若N的初态结点同时为终态，或者存在一条从初态到某个终态结点的通路，则为N所识别。NFAN所能识别的符号串的全体记为L(N)，称为NFAN所识别的语言。3.3有穷自动机上例题相应的状态图为：1234abacacεN所接受的语言（正规式）R=aa*b
8、ac*c
9、ε3.3有穷自动机例：NFAN=({a,b,c},{1,2,3,4},f,{1},{4})符号状
10、态εabc1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦ能接受0001111010001110000001(0
11、1)*(000
12、111)(0
13、1)*不能接受00011003.3有穷自动机画出能够识别C语言注释/**/的DFA3.3有穷自动机12453othersothers/***/6othersothersall状态1：注释开始状态。状态2：进入注释体前的中间状态。状态3：表明目前正在注释体中的状态。状态4：离开注释前的中间状态。状态5：注释结束状态，即接受状态。3.3有穷自动机12453othersothers/***/用
14、于某些重要软件的设计和构造设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件;验
