会计学4.1词法(cífǎ)分析程序的设计2、词法(cífǎ)分析程序单词符号一般可分为下列五种：1、基本字（关键字）：if,while,等2、标识符：如常量(chángliàng)名、变量名、过程名等3、常数（量）：25,3.1415,TRUE,“ABC”等4、运算符：如+-*/<<=等5、界符：逗号，分号，括号等词法分析工作独立的原因：简化设计：词法分析比语法分析简单，如果与语法分析一起，会导致程序结构复杂。改进编译效率：编译的大部分时间花在扫描(sǎomiáo)字符区分单词上，专门的词法分析可加快编译速度。增加编译系统的可移植性。4.2单词(dāncí)的描述工具2、程序设计(chénɡxùshèjì)语言几类单词的描述无符号实数(shìshù)：（其中s表示正或负号)〈无符号实数(shìshù)〉→d〈余留无符号数〉|.〈十进小数〉|e〈指数部分〉〈余留无符号数〉→d〈余留无符号数〉|.〈十进小数〉|e〈指数部分〉|ε〈十进小数〉→d〈余留十进小数〉〈余留十进小数〉→e〈指数部分〉|d〈余留十进小数〉|ε〈指数部分〉→d〈余留整指数〉|s〈整指数〉〈整指数〉→d〈余留整指数〉〈余留整指数〉→d〈余留整指数〉|ε如25.55e+5和2.1思考：以上文法为几型文法？二、正规(zhèngguī)式和正规(zhèngguī)集程序设计语言中的单词都可由正规(zhèngguī)式来定义：例={l，d}，r=l(ld)定义的正规(zhèngguī)集:{l,ll,ld,ldd,……}（标识符）例4.3={d，.，e，+，-},则上的正规(zhèngguī)式dd(.dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。如：2，12.59,3.6e2,4.71e-1（参考P49）2、若两个正规(zhèngguī)式e1和e2所表示的正规(zhèngguī)集相同,则说e1和e2等价,写作e1=e2。例如：e1=(a|b)，e2=b|a又如：e1=b(a|b)*,e2=b(b|a)*3、正规(zhèngguī)式的运算律4、正规文法正规语言正规式正规集：由正规文法产生的语言称正规集（正规语言）正规集是一个有穷或者无穷的集合，可用正规式(RegularExpression,Re)来描述。正规式也称正则表达式,正规表达式是说明单词的模式(pattern)的一种重要的表示法(记号(jìhɑo))，是定义正规集的数学工具。正规式描述的集合称作正规集。正规文法与正规式具有等价性。单词更适合用正规式（直观）来定义。对上的正规式r,存在一个(yīɡè)G=(VN,VT,P,S)使得L(G)=L(r)，反之亦然。例：文法G[S]S→aAS→aA→aAA→dAA→aA→d转换(zhuǎnhuàn)过程如下：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利用以下(yǐxià)规则做变换产生：正规式rS→r正规式xyA→xBB→yB新引进VN？正规式x*yA→xA|y正规式x|yA→xA→y直到每个产生式最多含有一个终结符为止。例：将r=a(ad)转换成相应(xiāngyīng)的正规文法。4.3有穷自动机自动机相关(xiāngguān)概念1、DFA定义：一个确定的有穷自动机（DFA）M是一个五元(wǔyuán)组：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的状态图表示(biǎoshì)2-2、DFA的矩阵(jǔzhèn)表示3、DFAＭ接受的字符串为了说明DFA如何作为一种(yīzhǒnɡ)识别机制,我们还要理解下面的定义3-1、∑*上的符号串t在M上运行一个输入符号串t，（我们将它表示成at1的形式，其中a∈∑，t1∈∑*）在DFAM上运行的定义为：f（A，at1）=f（f（A，a），t1）其中A∈K扩充转换函数f，是K×Σ*→K上的映射，且：