第二章 文法和形式语言

第二章基础知识1 第二章文法和形式语言 第二章基础知识2 程序设计语言 语法 语义 语用 语言的构成规律 语言所代表的含义 语言的实际应用 如 x a b c 形式化方法是用一整套带有严格规定的符号体系来描述问题的理论和方法 形式语言是不考虑含义的符号语言 主要研究组成这种符号串的集合 它们的表示法 结构及特性 第二章基础知识3 2 1字母表与符号串 一 相关概念1 字母表是符号的非空有穷集合 用 V表示 a b c V 0 1 2 符号 字母表中的元素称为符号或称为字符 如 a b c即为符号 第二章基础知识4 3 符号串 符号串是字母表中符号组成的有穷序列 如 a b c 则有符号串a b c aa ab ac aaa 若符号串中符号出现的顺序不同 符号串也不同空串 不含有任何符号的串称作空串 记作 4 符号串集合 字母表 上若干个符号串组成的集合称为符号串集合 如 有符号串集合A ab bc A a ab abc 第二章基础知识5 5 句子 字母表上符合某种规则构成的串 6 语言 字母表上句子的集合 注 约定用a b c r表示符号 用s t u z表示符号串 用A B C Z表示符号串集合 第二章基础知识6 a b c 字母表 上的两个符号串x y 若x y的各个符号依次相等 则该两符号串相等 记x y 1符号串相等 x abbc y abbc x y x ab y ba x y 2 1字母表与符号串二 符号串的运算 第二章基础知识7 2符号串长度 符号串中包含符号的个数 用 x 表示 abcd 4 0 3符号串连接 设字母表 上的两个符号串x y 把y的所有符号相继写在x的符号之后所得到的符号串称为x与y的连接 用xy表示 x ab y ba xy abba xy x y x x x xy yx 第二章基础知识8 4符号串的逆 符号串x的倒置 x abc 符号串x的逆 cba 5符号串的前缀 后缀 子串 后缀 符号串任意尾部 包括空串 前缀 符号串任意首部 包括空串 如 符号串abc 前缀 a ab abc 后缀 c bc abc 子串 a b c ab abc bc 第二章基础知识9 6符号串的幂符号串x自身连接n次得到的如 x ab 则有x0 x1 abx2 abab xn abab ab n个ab相连 而不是相乘 注 用an表示n个a相连接的符号串 而不是n个a相乘 第二章基础知识10 2 1字母表与符号串三 符号串集合的运算 1 符号串集合的乘积 定义 若串集A 1 2 串集B 1 2 则乘积AB Aand B 例如 A ab bc B ac cb 则AB abac abcb bcac bccb 注 1 由于 x x x所以 A A A2 串集的自身乘积称作串集的方幂 第二章基础知识11 2 符号串集合的幂 例如 串集A的各次方幂定义为 A0 A1 AA2 AA An AAn 1 An 1A n 0 为符号串集合A的自身乘积 若A ab bc 则有A0 A1 ab bc A2 abab abbc bcab bcbc 第二章基础知识12 3集合的闭包与正闭包 正闭包A A1 A2 An 闭包A A0 A1 A2 An A A0 A 证明A AA A A 若A a b 则有A a b aa ab ba bb aaa A a b aa ab ba bb aaa 若A为字母表 第二章基础知识13 2 2文法和语言 当我们表述一种语言时 无非是说明这种语言的句子 如果语言只含有有穷多个句子 则只需列出句子的有穷集就行了 但对于含有无穷句子的语言来讲 存在着如何给出它的有穷表示的问题 语言的有穷表示 生成方式 文法 识别方式 自动机 第二章基础知识14 1 文法文法是描述语言的语法结构的形式规则 例如 我们写这样一个句子 Youngmenlikepopmusic 其语法规则如下 Young pop men music like 一 文法的概念 第二章基础知识15 1 非终结符出现在规则的左部 用括起来 表示一定语法概念的词 非终结符集合用VN表示 2 终结符语言中不可再分割的字符串 包括单个字符组成的串 注 终结符是组成句子的基本单位 终结符集合用VT表示 此文法包括四个组成部分 第二章基础知识16 3 开始符号表示所定义的语法范畴的非终结符 注 开始符号又称为识别符号 4 产生式是用来定义符号串之间关系的一组 语法 规则 形式 A A A产生 第二章基础知识17 文法是四元组G VN VT P S 其中 VN是一个非空有穷非终结符号集合 VT是一个非空有穷终结符号集合 且VT VN 字汇表 词汇表 V VT VNS属于VN 称为开始符号或识别符号 P是一个产生式 规则 的非空有穷集合 每个产生式的形式是 或 其中 V V 开始符号S至少必须在某个产生式的左部出现一次 1 2缩写形式 1 2 第二章基础知识18 例文法G 0 1 9 开始符号 Vt 0 1 2 9 Vn 字汇表VV Vt Vn 文法的BNF表示法 0 1 9 文法的BNF表示 0 1 9 文法的优点 1 文法给出了精确的易于理解的语法说明2 可以给语言定义出层次结构3 以文法为基础的语言的实现便于语言的修改 第二章基础知识19 二 直接推导与推导的定义 推导与归约 推导是使用产生式的右部取代左部的过程称为推导 归约是将左部取代右部的过程称为归约 推导的分类 直接推导 推导 广义推导 最左推导 最右推导 1 直接推导与直接归约 定义 对于文法G 字汇表V x y V 称xUy直接推导出xuy 仅当存在有规则U u 记为xUy xuy xuy可直接归约到xUy xuy xUy 直接推导就是在推导过程中每次只替换一个规则 例 设有文法G E E T T E T F T 2 推导与归约 定义 对于文法G 如果存在一直接推导序列 v u0 u1 u2 un w n 0 称v推导出w 或称w归约到v v w w v 推导长度 若v w则 v w w v 广义推导 例 设有文法G E 对i i i和i i i 进行直接推导 E E T T T F T i T i T F i F F i i F i i i 从开始符号推导 E T T F F F i F i E i E T i T T i F T i i T i i F i i i n 8 n 11 3 规范推导 对于文法G 现讨论推导数25是否唯一 替换最左边 2 2 5 替换最右边 5 5 2 5 规范推导 xUy xuy 文法的BNF表示 0 1 9 第二章基础知识24 课堂练习 文法为E E T TT T F FF E a给出句子a a a的最左推导和最右推导的过程 最左推导过程 E F F F F F 最右推导过程 E F F F 课堂练习 P542 作业 P542 5 3 三 文法和语言 1 句型 句子 语言 定义 如果Zx x Vt 即仅含有终结符的句型是一个句子 设G z 是字汇表V上的一个文法 Z x x V 则称x是G的一个句型 文法G Z 产生的所有句子的集合称为文法G Z 所定义的语言L G Z 第二章基础知识26 例考虑一个文法G 0 1 S S P 其中P S 0S1 01 2 文法与语言的关系 给定一个文法 能从结构上唯一地确定其语言 例1 文法G Z Z aZb ab Z aZb aaZbb an 1Zbn 1 anbn L G Z anbn n 1 例2 L G S aibjakcjbi i 0 j 1 k 1 S推出的字符串的形式是aiPbi i 0 而P推出的字符串的形式是bjQcj j 1 Q推出的字符串的形式是ak k 1 课堂练习 P552 82 11 给定一种语言 能确定其文法 但这种文法不唯一 例 L G Z abna n 1 abaabbaabbba 文法G1 Z Z aBaB b Bb 文法G2 Z Z aBB ba bB 文法G3 Z Z BaB ab Bb 等价文法 L G1 Z L G2 Z 课堂练习 P552 7 例1 写一个文法 使其语言是奇数集 且每个奇数不以0开头 D 1 3 5 7 9 D 2 4 6 8 D D 0 D A AD D N AD D G N 例2 写一个文法 使其语言L G anbman n m 0 考形式抽象能力 应当仔细研究语言的结构特点 通常是这些语言具有形式上的对称性和字符数目上的相关性等特点 S aSa B B bB G S 作业 P552 92 10 四 递归规则和递归文法 递归规则 左 右部具有相同的非终结符号的规则 U xUy 若x U Uy 左递归规则 若y U xU 右递归规则 若x y U xUy 自嵌入规则 递归文法 至少含有一条递归规则的文法 文法G Z Z aBaB b Bb 文法中使用递归规则后 可以用有限的规则刻划无限语言 但不利是对于具有左递归性的文法 不能采用自顶向下的分析算法 五 短语 简单短语 句柄 短语与简单短语 定义 设有文法G Z xuy是其一个句型 若有Z xUy 且U u 则u是句型xuy相对于U的短语 若有Z xUy 且U u 则u是句型xuy相对于U的简单短语或直接短语 理解定义 U u xUy xuy Z xUy xuy 短语须满足两个条件 A 可以归约 B 原句型归约后仍为一个句型 简单短语须满足两个条件 A 可以直接归约 B 原句型归约后仍为一个句型 句柄 句型的最左简单短语为该句型的句柄 例 T i为句型T i相对于E的短语 i为句型T i相对于T的短语 i为句型T i相对于F的短语 且为简单短语 T i T为句型T i相对于E的短语 且为简单短语 句柄 E F i为句型E F i相对于E的短语 F i为句型E F i相对于T的短语 i为句型E F i相对于F的短语 且为简单短语 F为句型E F i相对于T的短语 且为简单短语 句柄 2 3语法树和二义性 一 语法树和推导 1 语法树 定义 树根是文法的开始符号 每个结点都是文法的终结符或非终结符 非终结符结点一定有子结点 若结点A有n个分枝结点为B1B2 Bn 则有A B1B2 Bn为一规则 设有文法G S S a B A a B b d S a A B a b d 则下面两棵树都是G的语法树 2 推导过程和语法树的生成 例 文法G N N ND DD 0 1 2 9 句子25的推导过程和语法树 最左推导 N N D D 2 5 最右推导 N N D 5 D 2 3 子树与短语 子树 语法树的某一结点连同它向下射出的部分组成了语法树的子树 简单子树 只含有单层分枝的子树称为简单子树 子树与短语的关系 子树末端结点组成的符号串是相对于子树根的短语 简单子树末端结点组成的符号串是相对于简单子树根的简单短语 最左简单子树末端结点组成的符号串是句柄 例 短语 T i T i 简单短语 T i 句柄 T E E T T F F i 短语 E F i F i F i 简单短语 F i 句柄 F 设有文法G A 求 C C a 的所有短语 简单短语和句柄 A B B C C C a 短语 C C a C C a C C a 简单短语 C C a 句柄 C 课堂练习 P552 15 作业 P552 14 例 ifBthenifBthenSelseS理解一ifBthenifBthenSelseS理解二ifBthenifBthenSelseS 二 文法的二义性 二 文法的二义性 设有文法G E 句子i i i的语法树 最左推导 最左推导 E E E i E E i i E E E i E E i i 不同 1 定义 一个文法的某个句子存在两棵不同的语法树 则称该文法是二义性文法 文法G S S ifBthenS ifBthenSelseS A 句型ifBthenifBthenSelseS的语法树 S if B then S if B then S else S S if B then S else S if B then S 文法的二义性和语言的二义性是两个不同的概念 可能有两个不同的文法G和G 其中一个是二义的而另一个是无二义的 但是却有L G L G 即这两个文法所产生的语言是相同的 对于一个程序语言来说 通常希望它的文法是无二义的 注意 二义性问题是不可判定的 即不存在一个算法 它能在有限步骤内 确切的判定一个文法是否为二义的 2 二义性的解决办法 修改编译算法 i i i只有最右推导 G E 规定 的优先级大于 优先级高的先归约优先级相同的 先左后右进行归 G S 规定 else与最近的未匹配的then相匹配 句型ifBthenifBthenSelseS的语法树也只有一棵 通常不说语言本身的二义性 句子或句型的不确定性是由文法的二义性带来的 我们不可以改变句子的集合 但能改变其二义性文法 尽量避免规则左部的符号在规则右部同时出现两次或两次以上 修改文法 作业 P562 16 如文法G E 修改后为 例 文法G E E E E E E i E 对于输入串i i i 1 给出一个推导 2 画出一棵语法树 3 文法G E 是否是二义性的 请证明你的结论 2 4 文法的实用限制 一 文法的实用限制 1 有害规则 形如U U的规则为有害规则 如G N N NN ND DD 0 1 9 句子25的语法树 2 多余规则 则称U为活的非终结符号 Z xUy U Vnxy Vt 活的非终结符号 可推出符号 在某句型中出现的符号称为可推出符号 活的非终结符号亦为可推出符号 例 文法G S S aAB aA aAb bB dC aBf S S aAB aaAbB aaAbd 可推出符号集 S a A B b d 活的非终结符号集 S A B 多余规则 所谓多余规则是指 在推导文法的所有句子时 始终用不到的规则 在推导过程中 一旦用了此规则 则无法推出句子来 某规则的左部符号U 若不满足下列条件 则该规则为多余规则 U为可推出符号 活的非终结符号 必须能从U推出句子 终结符号串 例 文法G Z Z BeA Ae eB Ce AfC CfD f D为不可推出符号 D f为多余规则 不能从C推出句子 C Cf为多余规则 不能从B Ce推出句子 B Ce为多余规则 可推出符号集 ZBACef 3 文法的实用限制 两点 不能有多余规则 不能有有害规则 如果文法G中所有规则均满足实用限制条件 则称文法G是压缩或化简过的 例 文法G Z Z BeA Ae eB Ce AfC CfD f 经过压缩化简后的文法G Z Z BeA Ae eB Af 课堂练习 P562 19 第二章基础知识60 1文法的开始符号不出现在规则的右部 二 文法的变换 2每个非终结符号均能导出终结符号串 3每个非终结符号都出现在任意句型中 4没有特殊规则 文法的六种假定 5没有空规则 6没有直接左递归规则 等价变换 第二章基础知识61 1文法的开始符号不出现在规则的右部 即在文法中拓充一条规则S S 例G N N ND DD 0 1 9 N N 拓广文法 第二章基础知识62 算法 1构造非终结符号集 I首先令 A A t G1 t Vt II递归扩充 W W x G1 x Vt 从文法G1中删除那些左部或右部含有不属于 中的符号的规则 2每个非终结符号均能导出终结符号串 第二章基础知识63 例文法G1 S S aABS bDADdA bAB dsA dDDB bAB dSBD dS d I首先令 D D d D II递归扩充 D A A dDD A D A D S S bDADd S A D 等价文法G2 S S bDADdA dsA dDDD ds d 第二章基础知识64 先利用2 找出不能推导出终结符号串的非终结符号 并删除相应的规则 得等价文法G2 S S adD bD e 再利用3 找出不在任意句型中出现的非终结符号 并删除相应的规则 得等价文法G3 S S ad 例 文法G1 S S ad bAA dBDB asAD bD e 3每个非终结符号都出现在任意句型中 算法 1构造非终结符号集 对文法中的每一个非终结符号A 求其 B AB G1 B Vn 若有AB 并且文法中有Bx 则在文法中扩充规则Ax 删除AB和无用规则 4没有特殊规则 A B AB Vn 例 文法G1 A A B dEB A D bD B dE Ea e A A dE A A B D b d B A dE B B b B D d D A dE D B b D D d A B D A B D 等价文法G2 A A b dE dB d dE bD dE d bE Ea e A b dE dE Ea e 第二章基础知识67 5没有空规则 例G1 A A aBbDB DDD b 与G1等价的文法G2为 A ab abD aBb aBbDB D DDD b 第二章基础知识68 算法 1构造非终结符号集 I首先令 A A G1 II递归扩充 W W x G1 x 2从文法中删除空规则 3从规则中删除只能导出空串的非终结符 4扩充新的规则对于规则A xByDB D x y V 则令下列规则为文法G2的规则A xy xyD xBy xByD 第二章基础知识69 例 G1 A A aBbDB DDD b 解 D D D B B DD B D 删除空规则后 A aBbDB DDD b 扩充新规则 A ab abD aBbB D 与G1等价的文法G2为 A ab abD aBb aBbDB D DDD b 第二章基础知识70 6消除左递归规则 若文法中有规则A Ay x x不以A开头 可用A xA A yA 来代替 这两种形式是等价的 一般而言 A Ay1 Ay2 Ayn x1 x2 xn 消除其左递归 A x1A x2A xnA A y1A y2A ynA 第二章基础知识71 例 E E T E T TT T F T F FF E i 消除左递归后的等价文法G2 E 文法G1 E E TE E TE TE T FT T FT FT F E i 第二章基础知识72 2 5扩充的BNF表示法 在BNF表示法中引进6个专用符号 1 花括号 t 表示t可重复多次如 N ND DD 0 1 9利用花括号 文法表示为N D D D 0 1 9 第二章基础知识73 2 方括号 t 表示t可有可无 即可以出现0次或1次 如 E T T ET F F TF i E 利用方括号 文法表示为E T E T F T F i E 第二章基础知识74 3 园括号 表示提因子 A ax ay awA a x y w 扩充的BNF表示法的用途如 E T E TT F T FF i E E T T T F F F i E BNF表示法的最大用途就是消除了文法的左递归 从而使文法在自顶向下的分析方法中能够进行分析处理 第二章基础知识75 2 6文法和语言分类 1 Chomsky对文法的定义从形式上说文法G是一个四元式 VN VT P S 2 Chomsky对文法的分类根据对产生式施加的限制 可分为0型文法1型文法2型文法3型文法 四种类型的文法分别对应着四种类型的语言 第二章基础知识76 0型文法 短语文法或无限制文法 文法G中的每个规则若为 V V 则称G为0型文法 0型文法确定的语言为0型语言 注 a 识别0型语言的自动机称为图灵机 TM b 0型文法是对产生式限制最少的文法 c 任何0型语言都是递归可枚举的 d 对0型文法产生式的形式作某些限制 可得到其他类型文法的定义 第二章基础知识77 0型文法举例 设文法G VN VT S P VN S A B C D E VT a 其中P为 0 S ACaB 1 Ca aaC 2 CB E 3 aD Da 4 AD AC 5 aE Ea 6 AE 第二章基础知识78 2 1型文法 上下文有关文法 文法G中的每个规则若为xUy xuy U Vn x y V u V 则称G为1型文法 1型文法确定的语言为1型语言或上下文有关语言 注 a 1型文法又称为长度增加文法 上下文有关文法 b 识别1型语言的自动机称为线性界限自动机 LBA c 1型文法意味着 对非终结符进行替换时务必考虑上下文 并且 一般不允许替换成 除非是开始符号产生 第二章基础知识79 1型文法举例 设文法G VN VT P S VN S B C D VT a b c 其中P为 0 S aSBC aBC 1 CB DB 2 DB DC 3 DC BC 4 aB ab 5 bB bb 4 bC bc 5 cC cc 第二章基础知识80 3 2型文法 上下文无关文法 文法G中的每个规则若为A 其中A VN V 则称G为2型文法 2型文法确定的语言为2型语言或上下文无关语言 注 a 2型文法对产生式的要求是 产生式左部一定是非终结符 产生式右部可以是VN VT或 非终结符的替换不必考虑上下文 b 识别2型语言的自动机称为下推自动机 PDA c 2型文法也称为上下文无关文法 第二章基础知识81 2型文法举例 设文法G VN VT P S VN S A B VT a b 其中P为 0 S aB 1 S bA 2 A a 3 A aS bAA 4 B b 5 B bS aBB 第二章基础知识82 4 3型文法 正则文法 文法G中的每个规则若为A B A B 或者A 其中A B VN VT 则称G为3型文法 3型文法确定的语言为3型语言或正则语言 注 a 3型文法也称为正规文法RG 右线性文法或左线性文法 b 3型文法中的产生式要么均是右线性产生式 要么是左线性产生式 不能既有左线性产生式 又有右线性产生式 若所有产生式均是左线性 则称为左线性文法 若所有产生式均是右线性 则称为右线性文法 c 识别3型语言的自动机称为有限状态自动机 第二章基础知识83 3型文法举例 设文法G VN VT P S VN S A B VT 0 1 其中P为 0 S 0A 1B 0 1 A 0A 1B 0S 2 B 1B 1 0 第二章基础知识84 四种文法之间的逐级 包含 关系 第二章基础知识85 正则文法与正则表达式的关系 程序设计语言的单词可由正则文法产生 如 标识符可以由正则文法描述如下 标识符 字母 标识符 字母 标识符 数字 现用字母表 字母 数字 上的正则表达式表示为 字母 字母 数字 2 7正则表达式与正则集 正则文法与正则表达式的关系 除了正则文法以外 正则表达式也是描述单词的重要工具 由正则文法或正则式