《《编译原理课程教案》第2章：文法基础》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第2章：文法基础（71页珍藏版）》请在金锄头文库上搜索。
1、形式语言基本知识第二章 本章要求 主要内容：符号串，文法的概念及分 类，语言的定义过程 重点掌握：上下文无关文法、推导、 句型、句子、语言，语法树、二义性 文法、文法的语言生成过程 问题：1. 程序语言的定义主要包括哪两个方面？2. 什么是语言的语法？3. 什么是语言的语法规则？一般程序语言的 语法单位有哪些？4. 什么是语言的语义？5. 什么是名字的作用域？说明名字的作用域 规则“最近嵌套原则”。6. 什么是名字的左值、右值？7. 描述程序语言中表达式的形成规则。8. 什么是符号串的闭包、正则闭包？9. 什么是文法？什么是上下文无关文法？10. 什么是终结符号、非终结符号、开始符号 、产生式
2、？11. 描述上下文无关文法的形式定义。12. 和 两个符号的含义及区别。13. 和 两个符号的含义及区别。14. 什么是句型、句子、语言？15. 什么是句型的最左推导，最右推导？ 16. 什么是语法树？ 17. 什么是二义性文法？ 18. 可否用算法确切地判定一个文法是二义性 的？ 19. 描述程序设计语言时，对于上下文无关文 法有哪些限制？ 20. 什么是左线性文法，右线性文法？2.1 程序语言定义的基本概念高级程序语言的基本功能和层次结构 程序语言的基本功能：描述数据和对数据 的运算。 所谓程序，本质上说是描述一定数据的处 理过程。程序的层次结构程序 | 子程序或分程序、过程、函数 |
3、语句 | 表达式 | 数据引用 算符 函数调用程序语言每个组成成分的逻辑和实现意义 抽象的逻辑的意义 数学意义 计算机实现的意义 具体实现 与机器语言或汇编语言比较，高级语言 的优点： 较接近于数学语言和工程语言，比较 直观、自然和易于理解; 便于验证其正确性，易于改错; 编写效率高; 易于移植.语 法 词法规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基本结构 。一般包括：常数、标识符、基本字、算符、 界符等。 描述工具：有限自动机 语法规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、分程序、 过程、函数、程序等; 描述工具：上下文无关文法程序语言的语法描述基础 几
4、个概念:考虑一个有穷 字母表 上的字符集，其中每一个元素称为一个字符，上的字(也叫字符串、符号串) 是指由中 的字符所构成的一个有穷序列。不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字例如: 设 =a， b，则 *=,a,b,aa,ab,ba,bb,aaa,.符号串的长度 :符号串中符号的个数，例如: 某符号串中有m个符号,则称其长度为m，表示 为x=m，如001110的长度是6。空符号串: 即不包含任何符号的符号串，用 表示，其长度为0， 即=0。 *的子集U和V的连接（积）定义为 UV | U 记 VVV* ，称V+是V的正规闭包。 设： U a, aa 那么：U*
5、= , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, 2.2 上下文无关文法及其语言 文法是描述语言的语法结构的形式规则。 文法是一种工具，它可用于严格定义句子 的结构；用有穷的规则刻划无穷的集合。 文法是被用来精确而无歧义地描述语言的 句子的构成方式。 文法描述语言的时候不考虑语言的含义。 He gave me a book. He me book a gave引 例 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book文法的形
6、式定义 由四部分组成： 终结符号：是组成该语言的最基本的符号， 是不可再分的基本符号,如保留字、标识符等 。 非终结符号：规则中用尖括号括起来的符号 ，表示一些语法成分，可以推导出其他的语法 成分,表示一定符号串的集合，是一个类，如 表达式。 开始符号：规则中的一个特殊的非终结符号 ，语言中的句子都从它开始推导,如程序、句 子 产生式：定义语法成分的规则，其中： 一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） 其中Vn表示非终结符号 Vt表示终结符号，VnVt=(字母表)， VnVt= S是开始符号， P是产生式，形如：(V+且至少含有 一个非终结符号，V*) 产生式的形式为：A 左
7、部符号 ，非终结 符右部，可以含有非 终结符和终结符产生式又称为一条规则。有时一个产生式不足以描述该语法范畴，就用多个 产生式，如算术表达式的描述为：(递归定义)E E + E | E * E|iE E + E E E * E E i相同左部的一个右部又称一个候选式。形式语言与自动机理论（蒋宗礼等 ，清华大学出版社）对文法的定义：上下文无关文法的定义一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT VN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须
8、在某个产生式的左部出现 一次。上下文无关文法所定义的语法成分 独立于它可能出现的环境，即不考 虑上下文。算术表达式的文法定义 变量是表达式 表达式 + 表达式是表达式 表达式 * 表达式是表达式 (表达式) 是 表达式E E + E E E * E E ( E ) E iE E+E | E*E | (E) | i 上下文无关文法产生句子的方法:从文法的开始 符号出发,反复连续使用产生式,对左边的非终 结符进行替换和展开 例：表达式定义规则E E + E E E * E E ( E ) E i( i+i )E=( E ) =( E+E ) =( i+E ) =( i + i ) 例，定义只含+，
9、*的算术表达式的文法G=， 其 中，P由下列产生式组成： E i E E+E E E*E E (E) 几点规定： “ ”也可以用“:=“表示， 这种表示称为巴科斯 范式(BNF) P 1 P 2 可缩写为 P 1|2|n P n其中，“|”读成“或”，称为P的一个候选式。 表示一个文法时，通常只给出开始符号和产生式 ，如上例，可表示为： G(E)： E i | E+E | E*E | (E)n例，定义只含+，*的算术表达式的文法G=， 其中 ，P由下列产生式组成： E i E E+E E E*E E (E) 定义：称A直接推出，即 A仅当A 是一个产生式，且， (VT VN)* 。 如果1 2
10、 n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。 对文法G(E)： E i | E+E | E*E | (E) E (E) (E+E) (i+E) (i+i)n通常，用 表示：从1出发，经过 一步或若干步，可以推出n。用 表示：从1出发，经过0步或 若干步，可以推出n。所以 ： 即 或q定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全体 是一个语言，将它记为 L(G)。 文法G所产生的语言定义为：L(G)=x|S=x,其中S为文法的开始符号，xVt* 。 即: 一个文法G
11、可以推导出的所有句子构成的一个集 合, 就确定了一个语言。* 例2.1 (P30) 考虑文法G1:它定义了什么语言。S bAA aA|a推导过程 ：S=bA =baS=bA =baA=baa.S=bA =baA= =baa归纳 得： L(G1) = ban | n1 例2.2(P30) 考虑文法G2: 它定义的语言是：S ABA aA|aB bB|bL(G2) = ambn |m,n1 练习：文法(A,B,S,a,b,c,P,S)S Ac|aBA abB bc 写出(G)的全部元素 L(G) = abc 例： (i*i+i)是文法 G(E)： E i | E+E | E*E | (E) 的一个
12、句子。证明：E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)E，(E)，(E*E+E)，(i*i+i)是句型。q例：文法G1(A)： A c|Ab G1(A)的语言?L(G1)=c，cb，cbb， 以c开头，后继若干个b 例：文法G2(S)： S AB A aA|a B bB|b G2(S)的语言?L(G2)=ambn|m，n0q例：给出产生语言为anbn|n1的文法。G3(S)：S aSbS abq例：给出产生语言为ambn|1nm2n的 文法。G4(S)：S aSb | aaSbS ab | aab 思考：构造一个文法G3使得：L(G3) = anbn
13、 |n1 S aSbS aba,b的个数相同,则文法G3为： 文法等价：若文法G1和文法G2所产生的语言相同，即L(G1) = L(G2)，则称文法G1和文法G2等价。例：有如下两个文法，判断它们是否等价？G1=（S，0，S，S0S，S0）G2=（S，0，S，SS0，S0）S0 S0S00 S0S 00S 0000 L(G1) = 0n | n1 对于G2： 对于G1 ：SS0 S00 0000 L(G2) = 0n | n1 G1G2，但L(G1) = L(G2)，文法G1和G2等价 例3 : G = (E, i, +, *, (, ) , P , E)P： E E + E | E * E
14、| ( E ) | i 表达式 (i+i)*i的推导过程：(1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i(2) E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*il 得到一个语言，是通过利用所有的产生式推导 出所有可能的句子，构成一个集合。l 但是一个句型到另一个句型(句子)的推导过程 不是唯一的。 从一个句型到另一个句型的推导往往不唯 一。E+Ei+Ei+i E+EE+ii+i 最左推导：任何一步 都是对中的最 左非终结符进行替换。最右推导：任何一步 都是对中的最 右非终结符进行替换。 最左推导: 在整个推导过程中,任何一步推导 =都是对中最左边的非终结符进行替换。 最右推导: 在推导之前确定推导的顺序，是对句子进行确 定性分析所必须的例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i(i+i)*i的最左推导过程：E E*E (E)*E (E
