资源描述：
《编译原理课件chap02(陈火旺)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章文法和语言编译原理第一章编译程序引论第二章文法和语言第三章词法分析第四章自顶向下语法分析方法第五章自底向上优先分析方法第六章LR分析方法第七章语法制导翻译和中间代码生成第八章运行时存储空间分配第九章代码生成第二章文法和语言文法和语言编译程序研究如何将源语言程序翻译为目标语言程序；让计算机熟悉和掌握源语言和目标语言；让计算机掌握语言的语法和语义对语法和语义进行形式化描述文法是对语法进行形式化描述的工具对文法和语言进行形式化定义第二章文法和语言文法和语言构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。程序设计
2、语言包括语法和语义两方面。语法是一组规则，可用来产生合乎语法的程序，也可用来分析一个程序是否合乎语法。A:=B+C程序设计语言的语义包括静态语义和动态语义。静态语义是一系列限定规则，用来确定哪些合乎语法的程序是正确的；动态语义称为运行语义或执行语义，表示程序要做什么，要计算什么。第二章文法和语言一、文法的概念二、符号和符号串三、文法和语言的定义四、文法的类型五、上下文无关文法及其语法树六、句型的分析七、有关文法的一些限制文法和语言第二章文法和语言语言语法：是一组规则，定义符号如何排列，排列与符号含义无关。语义：研究语法的含义静态语义动态语义一、文法的概念描述语言的语法结构的形式
3、规则（写出以下语言的文法）“你是大学生”对“我是教师”对“我大学生是”错“我学习大学生”对文法是阐述语法的一个工具1.文法的概念第二章文法和语言〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉
4、〈名词〉〈代词〉∷=我
5、你
6、他〈名词〉∷=王明
7、大学生
8、教师
9、英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是
10、学习〈直接宾语〉∷=〈代词〉
11、<名词>第二章文法和语言推导：我是教师〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈名词〉我是教师文法的概念第二章文法和语言2.符号和符号串C、PASCAL等程序设计语言是由所有C、PASCAL程序组成
12、的集合；程序是由一些基本符号组成的；从字面上看，每个程序都是一个基本符号串；设有一个基本符号集，C、PASCAL等程序设计语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。第二章文法和语言先讨论一些有关概念：1、字母表—符号集：是字母的有穷非空集合。汉语字母表包括：汉字、数字、标点符号等Pascal语言字母表包括：字母、数字、若干专用符号以及Begin、if等保留字。符号和符号串第二章文法和语言符号和符号串2、符号串—字母表的符号组成的任何有穷序列。例：∑={0，1}—符号集符号串有：0，1，00，01，10，11例：∑={a，b，c}—符号集符号
13、串有：a，b，c，ab，aaca第二章文法和语言3、符号串的长度：符号串x有m个符号，则长度就为m，表示
14、x
15、=m如：ababa则长度是54、空符号串：用ε表示，长度为0（不含任何符号）若符号串x,则有εx=xε=x5、符号串的运算：(1)符号串的头和尾若z=xy,则x是z的头，y是z的尾。第二章文法和语言例：设z=abc,则z的头是ε，a，ab，abc则z的尾是ε，c，bc，abc（2）符号串的固有头和固有尾若z=xy符号串，x非空，则y是固有尾；若y非空，则x是固有头。例：设z=abc，则z的固有头是ε，a，ab则z的固有尾是ε，c，bc第二章文法和语言（3）符号串的连接：
16、设x，y是符号串，连接xy是y符号写在x符号之后。例：x=ab,y=MN则xy=abMN显然：εx=xε=x（4）符号串的方幂：设x是符号串，则z=xx……xx，称z为x的方幂,记z=xn。因此x0=ε,x1=x,x2=xx,x3=xxx显然n>0时,有xn=x·xn-1＝xn-1·xN个第二章文法和语言（5）符号串的集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。两个符号串集合A、B乘积定义：AB={xy
17、x∈A且y∈b}例：A={a,b}，B={c,d}则AB={ac，ad，bc，bd}第二章文法和语言（6）闭包（∑*）字母表∑，用∑*表示
18、∑上所有有穷长的串集合，∑*称为∑的闭包。例：字母表∑={0,1}则∑*={ε,0,1,00,01,10,11,000,001,010……}=∑0∪∑1∪∑2∪.…∪∑n长度为1的符号串…与语言的关系：有的构成单词句子，有的不构成第二章文法和语言〈7〉正闭包(∑+)∑+=∑1∪∑2∪.…∪∑n∑+称∑的正闭包。显然：∑*＝∑0∪∑+∑+＝∑∑*＝∑*∑第二章文法和语言3.文法和语言的形式定义（用以上术语对文法的概念进行形式化）1、规则（重写规则、产生式、生成式）形如→β或::=β(称：定
