编译原理2.3.1-34-文法直观概念-形式定义.ppt

2.3 程序语言的语法描述 2.3.1 上下文无关文法 2.3.2 语法分析树与二义性 2.3.3 形式语言鸟瞰 2.3.1 上下文无关文法 一、文法引入 二、符号和符号串 三、文法的直观概念 四、文法和语言的形式定义 三、文法的直观概念 采用EBNF来表示英语中一种句子的构成规则: = = = = wolf | goat | rabbit | tiger = the |a |an = gray | red = will = eat | like 补充例补充例 用规则产生句子. (推导 ) 使用一条规则,把左边的部分替换成右边的部分。 用规则判别句子的合法性 ：方括号 表示其内的成 分为任选项 判断一个符号串是否为语法上正确的 运用规则, 把左边的部分替换成右边的部分, 如果可以推导出(产生) 该符号串, 则该符号串 是正确的句子 可以图示化表示这种推导, 得到语法分析树 参考p27 做练习: 画出 “The gray wolf will eat the goat.“ 的语法树 有关文法概念的给出 = = = wolf | goat | rabbit | tiger 产生式 产生式 产生式 非终结符 终结符 开始符号(识别符号) 文法G : 一组非终结符, 一组终结符, 一个开始符号, 一组产生式 终结符 终结符是组成语言的基本符号, 不可再分 割，不能由其它文法符号定义 词法规则 终结符是字母, 数字, 其他合法符 号 语法规则 从语法分析的角度, 终结符指单词 符号, 基本字,标识符,常数,算符,界符等 非终结符 非终结符: 语法成分, 语法短语，语法单位 ，语法变量，语法范畴，语法实体 非终结符可由其它文法符号定义。不是用 户自己写的 非终结符给语言强加了一种层次结构 每个非终结符表示一定符号串的集合 开始符号 (识别符号) 开始符号是我们最终感兴趣的语法范畴 是文法最终要定义 的语法结构 四、文法和语言的形式定义 产生式 (规则) 文法 直接推导, 直接归约 推导, 归约 句型, 句子 语言 文法等价 (补充) 最左推导, 最右推导 1. 文法 (a) 文法的形式定义: G = (VT，VN，P，S) VNVT = V: 文法符号的集合 (文法G的字母表 ) V = VNVT (补充 ) 语言L VT* 终结符号集合 非终结符号集合 产生式集合 开始符号 2. 产生式 重写规则、产生式 、生成式 a production rule 、a rewriting rule 有序对 (，) (书上 A) = ：规则的左部 V+ ：规则的右部 V* 产生式可以递归 产生式左部的符号可以在右部出现. 例: 表达式的定义 Ei EE+E EE*E E(E) p28p28 (b) 文法 举例 文法G = (VN，VT，P，S)， VN= S ， VT= 0，1， P= S0S1，S01 补 充 例 文 法 1 补 充 例 文 法 2 文法G = (VN，VT，P，S)， VN = 标识符，字母，数字， VT = a,b,c,，x,y,z,0,1,，9 P = 标识符字母 标识符标识符字母 标识符标识符数字 字母a 字母b 字母z 数字0 数字1 数字9 S =标识符 (c) 文法的写法 VN A, B, C , , VT a, b, c, , 1, 2, 3, V , , G = ( S,A，a,b，P，S)， P SaAb， Aab， AaAb， A 补充: 文法的写 法 1 VNVT G = ( S,A，a,b，P，S)， P ：SaAb， Aab， AaAb， A 补充: 文法的写法 2 G ：SaAb， Aab， AaAb， A GS： Aab，AaAb， A， S aAb 补充: 文法的写 法 3 开始符号:第一条产 生式的左部 开始符号 A1， A2 ， An 缩写为： A1 | 2 | | n GS ： Aab | aAb |， SaAb 补充: 文法的写法 4 候选式 思考题 文法的形式定义对编译器有何作用 ? 如何用文法阐明语言的语法? 一个上下文无关文法如何定义语言 ? 29 举例 G: EE+E | E*E | (E) | i E E+E E+i i+i 从E到i+i的一个推导证明 i+i是上述文法定义的一个表达式 3. 直接推导, 直接归约 文法G = (VT， VN， P，S) 是一产生式 , v =，w = 即:v w w 是v的 直接推导， v 直接推出 w, w 直接归约 到v 补充定义 A 直接推出 即: A , 仅当A 是一个产生式, 且 , V* 书上定义 p29 思考题 是否正确? 直接推导 举例 G1: S0S1 S01 G2: 标识符字母 标识符标识符字母 标识符标识符数字 字母a|b|z|A|B|Z 数字0|1|9 4. 推导出, 归约到 序列1 2 n称为为 1 到 n 的一个推导导 或 1 推导导出 n n 2 一步或多步1n n 1 零步或多步1n * 等价于: =或 * 推导 举例 G1: S0S1 S01 G2: 标识符字母 标识符标识符字母 标识符标识符数字 字母a|b|z|A|B|Z 数字0|1|9 5.句型, 句子 设文法GS , 如果 S ,V* 称是文法GS的句型。 若仅由终结符号组成, VT* 称为GS的句子。 例: G1:S0S1 | 01 * 判断对错 句子一定是句型。 从识别符号推导出的所有符号串都是句 型 从识别符号推导出的所有由终结符组成 的符号串都是句子。 由终结符组成的字符串不一定是文法的 句子。 6. 语言 L(G) L(G) = | S ，且VT* L(G) = | S ，且VT* 判断对错：判断对错： 1. 语言是文法G从开始符号出发， 推导出的所有句子的集合。 2. 语言是文法G所有句子的集合。 * + 文法和语言 题型 给文法, 写语言 给语言, 写文法 文法和语言 举例 G1: S0S1 S01 L(G1) = 0n1n | n1 补充例 文法和语 言1 补充例 文法和语 言2 G = (VN，VT，P，S)， VN=S, B, E，VT=a, b, e， P:(1) SaSBE (2) SaBE (3) EBBE (4) aBab (5) bBbb (6) bEbe (7) eEee L(G)= anbnen|n1 例2.1 G1: SbA, AaA | a L(G1)= ban | n1 文法和语言 举例 p30p30 例2.2 G2: SAB, AaA | a, BbB | b L(G2)= am bn | m, n1 例2.3构造一个文法G3, 使 L(G3)= an bn | n1 G3: SaSb | ab 请写出描述以下语言的文法 L(G1) = an ban | n1 G1: SaAa, AaAa, Ab L2 = an bam | n,m1 G2: SaS, SaB, BbC, CaC, Ca