计算机词法分析与总结.pptx

（1 1）文法的终结符号集为）文法的终结符号集为NFANFA的字母表；的字母表；（2 2）文法的非终结符号集为）文法的非终结符号集为NFANFA的状态集；的状态集；（3 3）文法的开始符号作为）文法的开始符号作为NFANFA的初态；的初态；（4 4）对文法中形如）对文法中形如AtBAtB的产生式，其中的产生式，其中t t为终结符或为终结符或，A A和和B B为非终结符，构造为非终结符，构造NFANFA的一个转换函数的一个转换函数f(A,t)=Bf(A,t)=B；（5 5）对文法中形如）对文法中形如AtAt的产生式，构造的产生式，构造NFANFA的一个转换函数的一个转换函数 f(A,t)=Zf(A,t)=Z。2.正规文法正规文法NFA3.5 3.5 正规文法与正规文法与有穷自动机的等价性有穷自动机的等价性例例:求与文法求与文法GSGS等价的等价的NFANFA GS:SaA|bB|GS:SaA|bB|AaB|bA AaB|bA BaS|bA|BaS|bA|SZABaaabbb求得：求得：3.5 3.5 正规文法与正规文法与有穷自动机的等价性有穷自动机的等价性3.5 3.5 正规文法与正规文法与有穷自动机的等价性有穷自动机的等价性课堂练习课堂练习求求GS:SaS|bS|aA|bBGS:SaS|bS|aA|bB AaC|a,BbC|b AaC|a,BbC|b CaC|bC CaC|bC的等价的的等价的NFANFABASaaaabbbbC课堂练习课堂练习(词法分析)阶段总结与复习阶段总结与复习1.1.词法：构词（字符串）规则词法：构词（字符串）规则定义字符串的文法。定义字符串的文法。右文法：右文法：AaB 左文法：左文法：ABa 2.2.正规式（正则式）：正规式（正则式）：三个运算符：三个运算符：|.*|.*正规式的全部字符是字母表正规式的全部字符是字母表 连接符：连接符：a.b a.b 或或 abab 练习练习构造正规式构造正规式 字母表（字母表（0 0，1 1）上含偶数个）上含偶数个0 0的串的串 (1|(01*0)*3.3.有限自动机有限自动机 确定的确定的DFADFA和非确定的和非确定的NFANFA DFA DFA NFA NFA4.DFA4.DFA的化简的化简5.5.自动机自动机 正规式正规式6.6.正规文法正规文法 自动机自动机正规文法正规文法NFA正规式正规式654312DFA最小化最小化转换方法转换方法87 做一做做一做 正规式正规式=NFA(a|b)*(a*bc)*再见！