编译原理ppt3_2
32页1、3.2 语言和文法,文法为语言给出了精确的、易于理解的语法说明 对于某些文法类,可以自动产生高效的分析器 如果文法设计得恰当,则它赋予语言的结构对于源程序翻译成正确的目标代码和对于错误诊断都是有用的 语言也是逐步完善的,增加新构造以完成新任务的情况时有发生。如果存在以文法为基础的语言的实现,语言新构造的加入就显得方便,文法能够描述程序设计语言的大部分语法成分,但不能描述程序设计语言的全部语法成分,3.2.1正规式和上下文无关文法的比较,正规表达式所描述的每一种结构都可以用上下文无关文法来描述 例如描述正规表达式(a|b)*abb的上下文无关文法A0 aA0 | bA0 | aA1A1 bA2A2 ,NFA -上下文无关文法 对NFA的每个状态i,创建一个非终结符Ai 如果状态i遇到输入符号a转换到状态j,则引入产生式Ai aAj 如果状态i遇到输入符号转换到状态j,则引入产生式Ai Aj 如果状态i是接受状态,则引入产生式Ai 如果状态i是开始状态,则Ai是文法的开始符号,对任何a及A,BS,若有(A,a)=B,则:(a) 当BF时,令AaB,(b) 当BF时,令Aa|aB。,例:设D
2、FA M = 。M的状态转换图如下图所示,求等价的上下文无关文法,G=,其中P由下列产生式组成:A0B|1DB0D| 1C| C0B| 1DD0D|1D,A0| 0B | 1D B0D | 1C C0 | 0B | 1D D0D | 1D,3.2.2 分离词法分析器的理由,为什么用正规式定义语言的词法,而不用上下文无关文法 语言的词法规则简单 正规式给出的描述更简洁且易于理解 从正规式自动构造出的词法分析器更有效,3.2.3验证文法产生的语言,文法G产生语言L:由G产生的每个字符串都在L中;反之,L中的每个字符串都能由G产生 例,下面的文法G能而且仅能产生所有配对的括号串S(S)S | ,文法示例,例1:G1S: S bAA aA | aL(G1)= ban | n1例2:G2S: S aSb | abL(G2)= anbn | n1,例3:构造文法G3,使L(G3)= anbn+1 | n0G3S: S aSb | b例4:构造文法G4,使L(G4)=| 为字符集上的回文,=a,bG4S: S aSa | bSb | a | b |,3.2.4 适当的表达式文法,通过改写文法来消除文
3、法的二义性 例:Gexpr: exprexpr+expr | expr*expr | (expr) | id 可以改写为如下无二义文法 expr expr+term | term term term*factor | factor factor (expr) | id,将相同优先权的算符放在一组,并为每一种优先权规定不同的规则E E+E | TT T*T | FF (E) | i 文法中仍为指定算符的结合性,还具有二义性,用基本情况代替递归,强制重复算符匹配一边的递归,将规则 EE+E | T 替换为 EE+T | T (左结合)ET+E | T (右结合) 最后得到:GEEE+T | TTT*F | FF (E) | i,3.2.5 消除二义性,例 stmt if expr then stmt| if expr then stmt else stmt| other 考虑:if E1 then if E2 then S1 else S2,每个else 和前面最近的没有配对的then配对,基本思想:出现在then和else之间的语句必须是“配对”的,即它不能以一个未配对的then后面跟随
《编译原理ppt3_2》由会员kms****20分享,可在线阅读,更多相关《编译原理ppt3_2》请在金锄头文库上搜索。
高三文科数学(长方体模型1)
高一生物:必修2 1.1孟德尔的豌豆杂交实验
遗传学第1章 绪言
高等代数课件--第三章 线性方程组§3.3 线性相关性
高二数学(1.1-1空间几何体及棱柱、棱锥的结构特征)
递回关系与演算法分析
过程是vb的基本组成单位
营养器官的生长
细菌真菌在生物圈中的作用课件(济南版七年级上)
自动化-ab变频器的原理及其应用
网络操作系统-第16章 windows server 2003安全管理
网络安全+第4讲+防火墙
素材-接触网施工技术-双线隧道吊柱安装
系统结构第5章
计算机体系结构实验2008
计算机系统安全
高考词汇总常用词v
软件测试tmap
电脑文件被删除怎么恢复图文教程
电子教案--第9章
2023-10-12 28页
2022-07-12 126页
2022-06-07 89页
2022-06-07 158页
2022-06-07 60页
2022-06-07 122页
2022-06-07 76页
2022-06-07 79页
2022-06-06 38页
2022-06-06 47页