3hh第3章 文法和语言.pptx

第3章文法和语言 3 1文法的直观概念3 2符号和符号串3 3文法和语言的形式定义3 4文法的类型3 5上下文无关文法及其语法树3 6句型的分析 上下文无关文法 3 7有关文法实用中的一些说明 3 3文法和语言的形式定义 如何描述一种语言 若语言是有穷的 则用枚举法将句子逐一列出 若语言是无穷的 则找出语言的有穷表示 语言的有穷表示有两个途经 语言的生成方式 用文法描述 即语言中每个句子用严格定义的规则来构造 语言的识别方式 用自动机描述 即当输入串属于语言时 经有限次计算会停止并回答 是 若不属于 则停止并回答 否 或永远继续下去 1 文法的定义 定义3 1文法G表示为四元组 VN VT P S 其中VN 非终结符的非空有穷集 语法实体或变量 非终结符也称语法变量 它代表语法实体或语法范畴 如算术表达式对应非终结符 如i i i i i VT 终结符的非空有穷集 终结符指语言的不可再分的基本符号 是语法的最小元素 如保留字 变量名 常量 VT VN 令V VT VN V称文法的字母表 通常用大写字母表示非终结符 用小写字母表示终结符 P 规则的非空有穷集 S 开始符 是一个非终结符 它至少要在一条产生式中作为左部出现 规则也称产生式或生成式 形如 或 其中 V 且至少包含一个非终结符 V 称为规则的左部 称为规则的右部 产生式通常有多个 左部相同的产生式可合并 例如 产生式P 1 P 2 P n可写为P 1 2 n其中 i i 1 2 n 称为P的候选式 例3 1文法G VN VT P S 其中VN S VT 0 1 P S 0S1 S 01 S为开始符该文法产生的语言为 0n1n n 1 例3 2产生标识符的文法 分析 令L 字母 即L a b zD 数字 即D 0 1 9T 字母或数字 即T L DS 字母数字串 则ST是字母数字串 即S ST T标识符I为字母后跟字母数字串或单个字母 即I LS L 解 产生标识符的文法为G VN VT P I 其中VN I S T L D VT a b z 0 9 P I LS LS ST TT L DL a b zD 0 1 9I是文法开始符 产生标识符的文法也可写为 G VN VT P S 其中VN 标识符 字母 数字 VT a b c z 0 1 9 P a z 0 9 S 注 用尖括号括起来的是非终结符 没括起来的是终结符 通常不用将文法的四元式显式表示出来 而只写出其产生式 这时约定 第1条产生式的左部为开始符 上述例3 1可以写成 G S 0S1S 01 或G S S 0S1S 01 或G S S 0S1 01 例G S aAbA abA aAbA G S A abA aAbA S aAb 或G S S aAbA abA aAbA 或G S S aAbA ab aAb 例3 3写一文法 使其语言是奇数集 但不允许出现以0打头的奇数 分析 将奇数划分为三个部分 最高位允许出现1 9 用非终结符B表示 中间部分可出现任意多位数字0 9 每一位用非终结符D表示 最低位只出现1 3 5 7 9 用A表示 由于中间部分可出现任意位 故需另外引入一个非终结符M 解 奇数集文法G N 为G N A M B D 0 1 9 P N P N A BMAM D MD A 1 3 5 7 9B 1 2 3 4 5 6 7 8 9D 0 B 解2 奇数集文法G N 也可以写为 G N A M B D 0 1 9 P N P N A MAM B MDA 1 3 5 7 9B 1 2 3 4 5 6 7 8 9D 0 B 2 推导的定义 为了定义文法所产生的语言 引入推导的概念 定义3 2假设 是文法G的一条产生式 若有v w满足 v w 其中 V V 则称v直接推导到w 或w是v的直接推导 记作v w 也称w直接归约到v 例G S 0S1 010S1 00S1100S11 000S111000S111 00001111S 0S1 定义3 3若存在直接推导的序列v w0 w1 wn w n 0 则称为v推导出w 记为w称为w归约到v 定义3 4若有或v w 则记为 例G S 0S1 S 010S1 00S1100S11 000S111000S111 00001111S 0S1 00S11 000S111 00001111记为S00001111 也记为S00001111SS00S1100S11 3 句型 句子 语言的定义 定义3 5假设G S 是一个文法 若Sx 则称x是文法G的句型 假设G S 是一个文法 若Sx x VT 则称x是文法G的句子 例G S 0S1 S 01S 0S1 00S11 000S111 00001111文法的句型 S 0S1 00S11 000S111 00001111 文法的句子 00001111 例G E E E T TT T F FF E aE E T T T F T a T a T F a F F a a F a a a由该推导知 句型 E E T T T 由该推导知 句子 a a a 该文法的句子是由符号a 构成的算术表达式 定义3 6由文法G生成的语言记为L G 它是文法G生成的所有句子的集合 L G x Sx S为开始符且x VT 例G S 0S1 01L G 0n1n n 1 定义3 7若L G1 L G2 则称文法G1和G2等价 例如 下述文法G1 A 和G2 S 等价 G1 A A 0RA 01R A1 G2 S S 0S1S 01 3 4文法的类型 Chomsky于1956年定义了四类文法及相应的形式语言 1 0型文法 短语文法 若文法G的每个产生式都为 的形式 其中 VN VT 且至少含1个非终结符 VN VT 则称该文法G为0型文法 记为PSG 0型文法对应的语言称为0型语言 对应图灵机 2 1型文法若文法G的每个产生式 均满足 则称文法G为1型文法或上下文有关文法 记为CSG 1型文法对应的语言称为1型语言 对应自然语言 1型文法的另一种定义 文法G的每个产生式具有如下形式 A 其中 VT VN A VN VT VN 3 2型文法若文法G的每个产生式具有下列形式 A 其中A VN VT VN 则称文法G为2型文法或上下文无关文法 记为CFG 2型文法对应的语言称为2型语言或上下文无关语言 对应程序设计语言 其识别系统是下推自动机 4 3型文法若文法G的每个产生式具有下列形式 A a或A aB 其中A B VN a VT 则称文法G为3型文法或正规文法 右线性 左线性 记为RG 3型文法对应的语言为3型语言或正规语言 对应正规式 其识别系统是有限自动机 例1型文法 上下文有关 文法G S S CDC aCAC bCBAD aDBD bDAa bDAb bA Ba aBBb bBC aD b 例2型文法 上下文无关 文法G S S ABA BS 0B SA 1 G S S 0A 1B 0A 0A 1B 0SB 1B 1 0 G I I lT lT lT dT l d 例3型文法 四类文法之间的关系 从0型文法到3型文法逐步增加了限制 1 3型文法都属于0型文法 2 3型文法不一定属于1型文法 如A 3型文法都属于2型文法 四类文法之间的区别 1 1型文法不允许有形如A 的产生式 2 3型文法允许 2 0 1型文法的产生式左部可以含终结符或两个以上的非终结符 2 3型文法产生式左部只能是单个非终结符 0型文法 3型文法 四类文法之间的逐级 包含 关系 0型文法 短语文法 的能力相当于图灵机 可以表征任何递归可枚举集 任何0型语言都是递归可枚举的 1型文法 上下文有关文法 产生式形如 1A 2 1 2 即只有A出现在 1和 2的上下文中时 才允许 取代A 其识别系统是线性界限自动机 2型文法 上下文无关文法CFG 产生式形如A 取代A时与A上下文无关 其识别系统是下推自动机 3型文法 正规文法RG 产生的语言是有穷自动机 FA 所接受的集合 文法和识别系统之间的关系 例1写出下列语言对应的文法 正规文法 L G1 ban n 1 L G2 and n 0 解 1 S bAA aA a 2 S AdA aA L G3 cd ef n n 1 对应的文法为 S cdAA efA efL G4 a2n n 1 aa n n 0 对应的文法为 S aaS 例2写出下列语言对应的文法 CFG文法 L G1 ambn m 1 n 0 L G2 anbn n 1 L G3 anbnci n i 1 L G4 anbnambm m n 1 L G5 ambnck m n k 1 解 1 S ABA aA aB bB 2 S aSb ab 3 6 略 例3写出下列语言对应的文法 CFG文法 L G1 1n0m1m0n m n 1 L G2 bnamambn m n 0 解 1 S 1S0 1A0A 0A1 01 2 S bSb AA aAa anbncn n 1 anbncm m n 1 ambnck m n k 1 注意 不能主观认定文法的限制越大则语言越小 即下述结论不成立 3型语言 2型语言 1型语言 0型语言 3型文法 有穷自动机NFAM S VN N N为一个新状态 N VN VT A S Z N 对G中形如A tB的产生式 t为终结符或 有f A t B 对G中形如A t的产生式 t为终结符或 有f A t N 对VT中每个a 有f N a 定理设G VN VT P S 是3型文法 则存在一个有穷自动机M S f A Z 使得L M L G 3型文法与有穷自动机的转换 例3型文法G S S aA bBA bB aD aB aA bD bD aD bD a b 有穷自动机FA 3型文法 例3 4给出 a b 上具有奇数个a和奇数个b的所有字符串集合的正规文法 解 如图 由S经奇数个a到达A 或经奇数个b到达B 再由A经奇数个b到达C或由B经奇数个a到达C 正规文法G S S aA bBA aS bB bS aC bA aB 正规文法G S 也可写为 S aA bBA aS bCB bS aCC bA aB 对 上正规式r 存在一个正规文法G VN VT P S 使得L G L r 初始 VT S VN 生成正规产生式 S r R 1 对形如A r1r2正规产生式 A r1BB r2 B VN R 2 对形如A r r1正规产生式 A rB A r1B rB B r1 B VN R 3 对形如A r1 r2正规产生式 A r1 A r2不断变换 直到每个产生式右端至多有一个VN 正规式 正规文法 正规式与正规文法的转换 1 S a a d 2 S aA A a d 3 A a d B A B a d B B G S S aAA aBA dBA B aBB dBB 例r a a d VT a d VN S A B A xB B y形成正规式A xyA xA y形成正规式A x yA x y形成正规式A x y 对于正规文法G VN VT P S 存在一个 VT上的正规式r 使得L r L G 正规文法 正规式 例G S S aA aA aA a dA dA a d A a d A a d a d S a a d a d a a a d a d a a d a a d R a a d 3 5上下文无关文法及语法树 CFG 能描述程序设计语言的语法结构 语法树 句型推导的直观表示 设G VN VT P S 为CFG 若一棵树满足下述条件 则称为G的语法树 推导树 派生树 1 每个结点用G的一个终结符或非终结符标记 2 根的标记是文法开始符S 3 内部结点一定是非终结符 若某内部结点A有n个分支 且其所有子结点从左至右依次为x1 x2 xn 则A x1x2 xn是G的一条产生式 4 若某结点标记为 则必为叶结点 且是其父结点的唯一子结点 例CFGG E E E E E E E aE E E a E a E E a a E a a a 句子a a a的语法树 最左推导 在推导的任何一步 其中 是句型 都是对 中最左非终结符进行替换 最右推导 在推导的任何一步 其中 是句型 都是对 中最右非终结符进行替换 最右推导也称为规范推导 由规范推导所得的句型称为规范句型 例CFGG E E E E E E E aE E E E E E E E a E a a a a a 句子a a a的语法树 短语 若S A 且A 则称 是句型 关于A的一个短语 简称 是句型 的一个短语 若S A 且A 则称 是句型 的一个直接短语或简单短语 句型E E的短语 E E直接短语 E E句型a E的短语 a a E直接短语 a 例如 考虑下述最左推导 E E E a E a E E a a E a a a 注意 短语的两个条件缺一不可 句型a E E的短语 a E E a E E直接短语 a E E句型a a E的短语 a a E a a E直接短语 a句型a a a的短语 a a a a a a直接短语 a E E E a E a E E a a E a a a 句柄 句型的最左直接短语称为句柄 a a a注意 一个句型的直接短语不唯一 句柄唯一 例如 对S A 若 为终结符串 则句型 的句柄为 把 用A代替 得到新句型 A 该过程为规范归约 是规范推导的逆过程 G S S aASA SbAS aA ba S aAS aSbAS aabAS aabbaS aabbaaS aAS aAa aSbAa aSbbaa aabbaa 例根据下述文法 写出句型aabbaa的最左推导 最右推导和相应的语法树 给定一个文法G VN VT P S 对于G的任何句型都能构造与之对应的语法树 EE EE Eiii EE EiE Eii 句型i i i的两个最左推导 E E E E E E i E E i i E i i iE E E i E i E E i i E i i i 例 G E E iE E EE E EE E 一棵语法树表示了一个句型的多种可能推导过程 未必是所有的 一个句型是否只对应唯一的一棵语法树呢 是否只有唯一的最左 最右 推导 二义文法 若一个文法存在某个句子对应两棵不同的语法树 则称这个文法是二义的 或者说 若一个文法存在某个句子有两个不同的最左 右 推导 则称这个文法是二义的 可能存在文法G和G G是二义的 L G L G 把二义文法改写为无二义文法 G E E iG E E T E TE E ET F T FE E EF E iE E 规定算符优先性和结合性 文法的二义性和语言的二义性 文法的二义性和语言的二义性是两个不同概念 若产生一个上下文无关语言的每个文法都是二义的 则说此语言是二义的 对于一个程序设计语言 希望其文法是无二义的 因为希望对每个语句的分析是唯一的 句型分析 判断一个符号串是否为某文法的句型 句型的分析算法分类 自上而下分析法 从文法开始符出发 反复使用文法的产生式 寻找与输入符号串匹配的推导 即为输入串寻找一个最左推导 自下而上分析法 从输入符号串开始 逐步进行归约 直至归约到文法的开始符 3 6句型的分析 上下文无关文法 SSScAdcAdab 例文法G S cAdA abA a分析输入串cabd是否为该文法的句子 3 6 1自上而下的语法分析 推导过程 S cAdcAd cabd 例文法G S cAdA abA a分析输入串cabd是否该文法的句子 3 6 2自下而上的语法分析 归约过程 cAd cabdS cAd 自上而下语法分析的问题 1 S cAd 2 A ab 3 A a识别输入串w cad是否为该文法的句子 若S cAd后选择 2 扩展A S cAd cabd则w的第二个符号可以与叶子结点a匹配 但第三个符号不能与下一叶子结点d匹配 宣告分析失败 显然是错误的结论 导致失败的原因是在分析中对A的选择不是正确的 这时应回朔 把以A为根的子树剪掉 扫描过的a退回 再试探产生式 3 3 6 3句型分析的有关问题 对cabd的分析中 若不是选择产生式 2 而是选择产生式 3 将a归约到A 则在cAbd中无法找到一个可归约串 最终达不到归约到S的结果 因而无法知道cabd是一个句子 cabdcAbda 自下而上语法分析的问题 1 S cAd 2 A ab 3 A a识别输入串w cabd是否为该文法的句子 1 在自上而下的分析中如何选择使用哪个产生式进行推导 假定要被代换的最左非终结符号是B 且有n条规则 B A1 A2 An 如何确定用哪个右部去替代B 2 在自下而上的分析中如何识别可归约串 在分析的每一步 都从当前串中选择一个子串 将它归约为某非终结符 该子串称为可归约串 问题 3 7有关文法实用中的一些说明 3 7 1有关文法的实用限制实用中 限定文法中不含有害规则和多余规则 有害规则 形如U U的产