《编译原理课程教案》第二章-文法基础.pptVIP

形式语言基本知识;本章要求;问题： 1. 程序语言的定义主要包括哪两个方面？ 2. 什么是语言的语法？ 3. 什么是语言的语法规则？一般程序语言的语法单位有哪些？ 4. 什么是语言的语义？ 5. 什么是名字的作用域？说明名字的作用域规则－－“最近嵌套原则”。;6. 什么是名字的左值、右值？ 7. 描述程序语言中表达式的形成规则。 8. 什么是符号串的闭包、正则闭包？ 9. 什么是文法？什么是上下文无关文法？ 10. 什么是终结符号、非终结符号、开始符号、产生式？ 11. 描述上下文无关文法的形式定义。 12. 和 两个符号的含义及区别。 13. 和 两个符号的含义及区别。 14. 什么是句型、句子、语言？ ;15. 什么是句型的最左推导，最右推导？ 16. 什么是语法树？ 17. 什么是二义性文法？ 18. 可否用算法确切地判定一个文法是二义性的？ 19. 描述程序设计语言时，对于上下文无关文法有哪些限制？ 20. 什么是左线性文法，右线性文法？;2.1 程序语言定义的基本概念;高级程序语言的基本功能和层次结构;程序的层次结构;程序语言每个组成成分的逻辑和实现意义 ;与机器语言或汇编语言比较，高级语言的优点： 较接近于数学语言和工程语言，比较直观、自然和易于理解; 便于验证其正确性，易于改错; 编写效率高; 易于移植.;语 法;程序语言的语法描述基础;符号串的长度 :符号串中符号的个数，例如: 某符号串中有m个符号,则称其长度为m，表示为｜x｜=m，如001110的长度是6。 空符号串: 即不包含任何符号的符号串，用ε表示，其长度为0， 即｜ε｜=0。 ;∑*的子集U和V的连接（积）定义为 UV＝{ ?? | ??U ??V } 设： U＝{ a, aa } V＝ { b, bb } 那么： UV= { ab, abb, aab, aabb} ;∑*的子集U和V的连接（积）定义为 UV＝{ ?? | ??U ??V } V自身的 n次积记为 Vn=VV…V 规定V0={?}，令 V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; 记 V＋＝VV* ，称V+是V的正规闭包。 ;设： U＝{ a, aa } 那么： U* = { ? , 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;文法的形式定义;一个文法G抽象地表示为四元组? G=（Vn,Vt,P,S）? 其中Vn表示非终结符号 Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ S是开始符号， P是产生式，形如：α?β(α∈V+且至少含有一个非终结符号，β∈V*) ;产生式的形式为：A? α;《形式语言与自动机理论》（蒋宗礼等，清华大学出版社）对文法的定义：;上下文无关文法的定义 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT ? VN=? S：文法的开始符号，S?VN P：产生式集合(有限)，每个产生式形式为 P??， P?VN， ? ? (VT ? VN)* 开始符S至少必须在某个产生式的左部出现一次。;上下文无关文法所定义的语法成分独立于它可能出现的环境，即不考虑上下文。 ;算术表达式的文法定义;上下文无关文法产生句子的方法:从文法的开始符号出发,反复连续使用产生式,对左边的非终结符进行替换和展开 例：表达式定义规则;例，定义只含+，*的算术表达式的文法 G={i，+，*，(，)}，{E}，E， P， 其中，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);定义：称?A?直接推