如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
会计学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(ld)定义的正规(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(ad)转换成相应(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是唯一的一个初态;ZK是一个终态集,终态也称可接受状态或结束状态。DFA例:M=({S,U,V,Q},{a,b},f,S,{Q})f为:2-1、DFA的状态图表示(biǎoshì)2-2、DFA的矩阵(jǔzhèn)表示3、DFAM接受的字符串为了说明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上的映射,且: