《编译原理课程教案》第2章：文法基础

《《编译原理课程教案》第2章：文法基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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、子程序或分程序、过程、函数

5、语句

6、表达式

7、数据引用算符函数调用程序语言每个组成成分的逻辑和实现意义抽象的逻辑的意义数学意义计算机实现的意义具体实现与机器语言或汇编语言比较，高级语言的优点：较接近于数学语言和工程语言，比较直观、自然和易于理解;便于验证其正确性，易于改错;编写效率高;易于移植.语法词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文

8、无关文法程序语言的语法描述基础几个概念:考虑一个有穷字母表∑上的字符集，其中每一个元素称为一个字符，∑上的字(也叫字符串、符号串)是指由∑中的字符所构成的一个有穷序列。不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε例如:设∑={a，b}，则∑*={ε,a,b,aa,ab,ba,bb,aaa,...}符号串的长度:符号串中符号的个数，例如:某符号串中有m个符号,则称其长度为m，表示为｜x｜=m，如001110的长度是6。空符号串:即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0。∑*的子集U和V

9、的连接（积）定义为UV＝{

10、U&V}设：U＝{a,aa}V＝{b,bb}那么：UV={ab,abb,aab,aabb}∑*的子集U和V的连接（积）定义为UV＝{

11、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上下文无关文法及其语言文法是描述语言的语法结构的形式规则。文法是一种工具，它可用于严格定义

12、句子的结构；用有穷的规则刻划无穷的集合。文法是被用来精确而无歧义地描述语言的句子的构成方式。文法描述语言的时候不考虑语言的含义。Hegavemeabook.<句子><主语><谓语><间接宾语><直接宾语><主语><代词><谓语><动词><间接宾语><代词><直接宾语><冠词><名词><代词>He<代词>me<名词>book<冠词>a<动词>gave引例<句子><主语><谓语><间接宾语><直接宾语><主语><代词><谓语><动词><间接宾语><代词><直接宾语><冠词><名词><代词>He<代词>me

13、<名词>book<冠词>a<动词>gave<句子><主语><谓语><间接宾语><直接宾语><代词><谓语><间接宾语><直接宾语>He<谓语><间接宾语><直接宾语>He<动词><间接宾语><直接宾语>Hegave<间接宾语><直接宾语>Hegave<代词><直接宾语>Hegaveme<直接宾语>Hegaveme<冠词><名词>Hegavemea<名词>Hegavemeabook文法的形式定义由四部分组成：终结符号：是组成该语言的最基本的符号，是不可再分的基本符号,如保留字、标识符等。非终结符号：规则中用尖括

14、号括起来的符号，表示一些语法成分，可以推导出其他的语法成分,表示一定符号串的集合，是一个类，如表达式。开始符号：规则中的一个特殊的非终结符号，语言中的句子都从它开始推导,如程序、句子产生式：定义语法成分的规则，其中：一个