《词法分析》讲义.ppt

《词法分析》讲义;4.1 词法分析程序的设计;2、词法分析程序;单词符号一般可分为下列五种： 1、基本字（关键字）：if, while, 等 2、标识符：如常量名、变量名、过程名等 3、常数（量）：25, 3.1415, TRUE, “ABC”等 4、运算符：如 + - * / =等 5、界符：逗号，分号，括号等;词法分析工作独立的原因： 简化设计：词法分析比语法分析简单，如果与语法分析一起，会导致程序结构复杂。 改进编译效率：编译的大部分时间花在扫描字符区分单词上，专门的词法分析可加快编译速度。 增加编译系统的可移植性。 ;4.2 单词的描述工具;2、程序设计语言几类单词的描述;无符号实数：（其中s表示正或负号)  〈无符号实数〉→ d 〈余留无符号数〉| . 〈十进小数〉 | e〈指数部分〉 〈余留无符号数〉→ d 〈余留无符号数〉| . 〈十进小数〉 | e〈指数部分〉|ε 〈十进小数〉 → d 〈余留十进小数〉 〈余留十进小数〉 → e〈指数部分〉| d 〈余留十进小数〉| ε 〈指数部分〉 → d 〈余留整指数〉| s〈整指数〉 〈整指数〉 → d 〈余留整指数〉 〈余留整指数〉 → d 〈余留整指数〉 |ε 如e+5 思考：以上文法为几型文法？ ;二、正规式和正规集; ;;程序设计语言中的单词都可由正规式来定义： 例 ?={l，d}，r=l(l ?d) ?定义的正规集: {l,ll,ld,ldd,……}（标识符） 例4.3 ?={d，.，e，+，-},则?上的正规式 dd?(.dd ?? ? )(e(+?- ??)dd? ??)表示的是无符号数的集合。其中d为0~9的数字。如：2，（参考P49） 2、若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。????????????? 例如： e1= (a|b)， e2 = b|a????????????? 又如： e1= b(a|b)* , e2 =b (b|a)*;3、正规式的运算律;4、正规文法 正规语言 正规式 正规集? ： 由正规文法产生的语言称正规集（正规语言） 正规集是一个有穷或者无穷的集合，可用正规式(Regular Expression,Re)来描述。 正规式也称正则表达式,正规表达式是说明单词的模式(pattern)的一种重要的表示法(记号)，是定义正规集的数学工具。正规式描述的集合称作正规集。 正规文法与正规式具有等价性。 单词更适合用正规式（直观）来定义。;对?上的正规式r ,存在一个G=(VN,VT,P,S)使得L(G)=L(r) ，反之亦然。;例：文法G[S] ???? S→aA??S→a???? A→aA??A→dA??A→a? A→d???? 转换过程如下： ???? S=aA|a = a(A|ε) ???? A=(aA|dA)|(a|d) = (a|d)A|(a|d) A= (a|d)*(a|d)????S= a((a|d)*(a|d)|ε) ????S= a(a|d)* // S= a((a|d)+| ε) ？; 2、将正规式转换成正规文法 引进S作为识别符号, VT=∑?， VN与P利用以下规则做变换产生：?? ????????????? ?? 正规式r????? S→r????正规式xy??? ??A→xB B→y??? B新引进VN？?? 正规式x*y??? A→xA|y  正规式x|y??? A→x A→y 直到每个产生式最多含有一个终结符为止。;例：将 r = a(a?d)?转换成相应的正规文法。;4.3 有穷自动机;自动机相关概念; 1、DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中： K是一个有穷集，它的每个元素称为一个状态； Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表； f是转换函数，是在K×Σ→K上的映射，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；（单值函数） S∈K是唯一的一个初态； Z? K是一个终态集，终态也称可接受状态或结束状态。;DFA 例： M=（{S,U,V,Q}, {a,b}, f, S, {Q}） f 为：;2-1、DFA 的状态图表示;2-2、DFA 的矩阵表示;3、 DFA? Ｍ