《编译技术：第04章01 文法语法》由会员分享，可在线阅读，更多相关《编译技术：第04章01 文法语法（53页珍藏版）》请在金锄头文库上搜索。
1、第四章(01) (01) 文法和语法的定义语言的定义语言语言 语法语法规则规则 语义语义规则规则语法、语义都是语法、语义都是规则的集合规则的集合语法语法: : 用来用来构造构造程序及语法成分程序及语法成分 如表达式、语句如表达式、语句语义语义: : 用来用来规定规定语法单位的含义语法单位的含义Zhou, Erqiang2School of Information and Software Engineering基本概念：基本概念：1 1）字母表字母表: :语言允许使用字符的集合语言允许使用字符的集合2 2）词汇词汇: :由字符组成的有限串由字符组成的有限串( (字符串字符串) )3 3）词法规
2、则词法规则: : 哪些字符串合法或者不合法哪些字符串合法或者不合法 标识符：函数名，变量名等标识符：函数名，变量名等Zhou, Erqiang3语法School of Information and Software Engineering4 4）语法规则语法规则: : 句子：一个句子：一个“词汇序列词汇序列” 确定句子在确定句子在形式上形式上是否合法是否合法 提供句子的结构提供句子的结构 ifif ( ( 表达式表达式 ) ) 语句语句 elseelse 语句语句Zhou, Erqiang4School of Information and Software Engineering语法自然语
3、言描述自然语言描述 FORTRANFORTRAN形式化描述（形式化描述（BNFBNF） ALGOL60ALGOL60转换图（语法图）转换图（语法图） PASCALPASCALZhou, Erqiang5语法的表示School of Information and Software Engineering重点！重点！自然语言描述自然语言描述 FORTRANFORTRAN形式化描述（形式化描述（BNFBNF） ALGOL60ALGOL60转换图（语法图）转换图（语法图） PASCALPASCALZhou, Erqiang6语法的表示School of Information and Softwar
4、e Engineering构造规则构造规则语法图的构造语法图的构造 N 1| 2| n对应一个语法图对应一个语法图Zhou, Erqiang7转换图定义语言School of Information and Software Engineering 终结符终结符x x 非终结符非终结符N NN 1| 2| nxN2n1Zhou, Erqiang8构造规则School of Information and Software Engineering12m 12mZhou, Erqiang9构造规则 |School of Information and Software Engineering生成的
5、串是哪种形式？生成的串是哪种形式？一个一个合法的合法的终结符序列：终结符序列： 从从入口边入口边 通过语法图通过语法图 到到出口边出口边 通过时恰恰能识别该终结符序列通过时恰恰能识别该终结符序列语言：语言： 语法图语法图能识别能识别的的 所有所有终结符序列终结符序列的集合的集合Zhou, Erqiang10识别原则School of Information and Software Engineering标识符标识符Zhou, Erqiang11表达式语法图(表达式表达式运算符运算符表达式表达式表达式表达式)School of Information and Software Engineer
6、ing数字数字Zhou, Erqiang12语义语义（规则）语义（规则） 定义语言定义语言合法合法句子的句子的含义含义 即句子的作用和意义的规则组合即句子的作用和意义的规则组合例：例：if(ab) then max=a else max=b if(ab) then max=a else max=b 先计算先计算ifif后的表达式后的表达式 再按照再按照所得值决定所得值决定maxmax的值的值School of Information and Software Engineering描述语法描述语法 文法和语法图文法和语法图描述语义描述语义 尚尚无无普遍接受的描述工具普遍接受的描述工具 许多语言
7、仍采用许多语言仍采用自然语言自然语言描述语义描述语义Zhou, Erqiang13语义的表示School of Information and Software Engineering自然语言描述自然语言描述 FORTRAN形式化描述（形式化描述（BNFBNF） ALGOL60转换图（语法图）转换图（语法图） PASCALZhou, Erqiang14语法的表示School of Information and Software Engineeringstmt if ( expr ) stmt else stmtif, (, ), else 都不能进一步分解都不能进一步分解 终结符终结符，词法
8、单元，词法单元stmt， expr 可以进一步分解可以进一步分解 非终结符非终结符，语言变量，语言变量非终结符非终结符, , 箭头箭头, , 终结符和非终结符序列终结符和非终结符序列 产生式产生式，productionZhou, Erqiang15形式化描述School of Information and Software Engineering指定一个非终结符为指定一个非终结符为开始符号开始符号定义：定义： 终结符集合：终结符集合：V VT T 非终结符集合：非终结符集合：V VN N 产生式集合：产生式集合：P P 开始符号：开始符号：S SG = (VG = (VT T, V, VN
9、N, S, P), S, P) G G称为一个称为一个文法文法 文法文法是对是对语法语法的形式化描述的形式化描述Zhou, Erqiang16形式化描述School of Information and Software Engineering历史背景历史背景 乔姆斯基乔姆斯基( (ChomskyChomsky) ) 于于19561956年建立语言的形式描述年建立语言的形式描述深远影响深远影响 语言学、计算机科学语言学、计算机科学 程序语言的设计程序语言的设计、编译方法编译方法、 计算复杂性计算复杂性等等Zhou, Erqiang17文法School of Information and So
10、ftware Engineering历史回顾历史回顾 取得了大量的成果取得了大量的成果 理论工作走在计算机发展的前面理论工作走在计算机发展的前面现状展望现状展望 计算机及其应用的迅速发展计算机及其应用的迅速发展 今天的理论远远落后今天的理论远远落后Zhou, Erqiang18School of Information and Software Engineering文法产生式非终结符非终结符, , 箭头箭头, , 终结符和非终结符序列终结符和非终结符序列stmt if ( expr ) stmt else stmt产生式是一个产生式是一个有序偶对有序偶对( ( ， ) )记为记为 := 或或
11、 Zhou, Erqiang19School of Information and Software Engineering关于关于 和和 和和 是由是由终结符终结符、非终结符非终结符组成的串组成的串 至少应含有一个至少应含有一个非终结符非终结符即即 V*VNV* V* 其中其中 V= VT VN Zhou, Erqiang20产生式School of Information and Software Engineering几点说明几点说明* 表示任意多次（表示任意多次（0 0次或次或0 0次以上）次以上）+ 表示至少表示至少1 1次次V* 表示表示 V V中的元素中的元素 可出现任意多次可出
12、现任意多次V+ 表示表示 V V中的元素中的元素 至少出现至少出现1 1次次Zhou, Erqiang21产生式School of Information and Software Engineering产生式的简化 1 2 n n 称为称为候选式候选式 1 | 2 |nZhou, Erqiang22其中其中| |表示表示“或者或者” School of Information and Software Engineering非终结符非终结符 英文英文大写字母大写字母表示表示开始符号开始符号 仅有仅有1 1个个 第一个产生式的第一个产生式的左边左边符号符号Zhou, Erqiang23产生式的
13、约定School of Information and Software Engineering文法的表示描述文法描述文法 直接给出产生式集合直接给出产生式集合例如算术表达式文法例如算术表达式文法G G0 0: : E E E+T E+T | | T T T T*F T T*F | | F F F F (E) (E) | | i iZhou, Erqiang24School of Information and Software Engineering1 1） 0 0型文法（无限制文法）型文法（无限制文法） V V* * V VN N V V* * ， V V* * 2 2） 1 1型文法型文
14、法( (上下文上下文有关有关文法文法) ) | | | = | 0Zhou, Erqiang41文法实例School of Information and Software Engineering文法的重要性文法的重要性 有限有限规则描述规则描述无穷无穷语言语言文法等价文法等价 两个文法两个文法G G和和G G, ,如果有如果有L(G)=L(G) 则称则称G G和和G G等价等价Zhou, Erqiang42文法实例小结School of Information and Software Engineering用图展示一个句型（句子）的推导过程用图展示一个句型（句子）的推导过程 推导树、语法树
15、推导树、语法树倒立的树倒立的树 根在上、叶在下根在上、叶在下 开始符号为开始符号为“树根树根”Zhou, Erqiang43推导树（语法树）School of Information and Software Engineering对于文法对于文法 E E+EE*E(E)i 句子句子 (i+i*i) 的推导树的推导树Zhou, Erqiang44推导树实例E（E）EE*EE+iiiE（E）EE+EEiii*School of Information and Software Engineering一棵一棵有序有序的标记树的标记树结点是文法的结点是文法的非终结非终结符或符或终结终结符符当当非终结
16、符非终结符 被被 其其候选式候选式替代替代 该非终结符产生下一代枝叶该非终结符产生下一代枝叶结点结点A A从左到右有子结点从左到右有子结点X X1 1，X X2 2，, X, Xn n, ,则则AXAX1 1X Xn n是一个产生式是一个产生式; ;Zhou, Erqiang45推导树总结School of Information and Software Engineering推导树的边缘：推导树的边缘： 推导树所有叶结点推导树所有叶结点从左到右从左到右的连接。的连接。文法的二义性：文法的二义性： 一个句子有两棵不同的推导树。一个句子有两棵不同的推导树。Zhou, Erqiang46推导树总
17、结School of Information and Software Engineering文法与语法图关系文法文法和和语法图语法图是语法的是语法的等价表示等价表示文法文法 从从产生的观点产生的观点定义语言定义语言 更通用、更准确地给出语法结构更通用、更准确地给出语法结构语法图语法图 从从识别的观点识别的观点定义语言定义语言 更直观、更清晰地给出语法结构更直观、更清晰地给出语法结构Zhou, Erqiang47School of Information and Software Engineering由语言的由语言的设计者确定设计者确定1)1)设计者设计者 表达意图和设计目标表达意图和设计目
18、标2)2)使用者使用者 指导如何编写正确的程序指导如何编写正确的程序3)3)实现者实现者 指导如何指导如何编写语法检查程序编写语法检查程序Zhou, Erqiang48语法描述的用途School of Information and Software EngineeringZhou, ErqiangTHE ENDQUESTIONS49School of Information and Software Engineering考虑文法考虑文法： E T | E+T | E-T T F | T*F | T/F F ( E ) | i给出给出i+i*i， i*(i+i)的的最左最左推导和推导和最右最
19、右推导推导给出给出i+i+i，i+i*i 和和 i-i-i的语法树的语法树Zhou, Erqiang50习题School of Information and Software Engineering给出下面语言的相应文法给出下面语言的相应文法 L1 = anbncin = 1, i = 0 L2 = aibncn | n = 1, i = 0 L3 = anbnambm | n, m = 0 L4 = 1n0m1m0n | n, m = 0 Zhou, Erqiang51文法实例School of Information and Software EngineeringL1: G(S): SAC AaAb|ab CcC|L2: G(S): SAB AaA| BbBc|bcZhou, Erqiang52文法实例School of Information and Software EngineeringL3: G(S): SAB AaAb| BaAb|L4: G(S): S1S0|A A0A1| 或者或者: : SA|B A0A1| B1B0|AZhou, Erqiang53文法实例School of Information and Software Engineering
