第三章文法和语言52.ppt

第三章 文法和语言 本章目的为语言的语法描述寻求工具,以便： 对源程序给出精确无二义的语法描述。（严谨、简洁、易读） 根据语言文法的特点来指导语法分析的过程 从描述语言的文法可以自动构造出可用的分析程序 制导语义翻译 文法和语言 预备知识 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明 有关文法的一些关系 预备知识 -----语言概述 语言是由句子组成的集合，是由一组记号所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 每个句子构成的规律 研究语言 每个句子的含义 每个句子和使用者的关系 预备知识 -----语言概述 研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics 预备知识 -----语言概述 语法 -- 表示构成语言句子的各个记号之间的组合规律 语义 -- 表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 --表示在各个记号所出现的行为中，它们的来源、使用和影响。 预备知识 -----语言概述 每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。 语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。 预备知识 -----形式语言 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。 预备知识 -----有关定义和记号 符号：可以相互区别的记号（元素）。 字母表?：符号（元素）的非空有穷集合。 符号串：由字母表?中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是?上的符号串 2.若x是?上的符号串,a是?的元素,则xa是?上的符号串 3. y是?上的符号串,当且仅当它可以由1和2导出。 例如： Σ={a,b} ε,a,b,aa,ab,aabba…都是?上的符号串 预备知识 -----有关定义和记号 符号串s的前缀：移走符号串s尾部的零个或多于零个符号得到的符号串. 如： b是符号串banana的一个前缀. 符号串s的后缀：删去符号串s头部的零个或多于零个符号得到的符号串. 如:nana是符号串banana的一个后缀. 符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串. 如:ana是符号串banana的一个子串. 对于每个符号串s， s和ε两者都是符号串s的前缀，后缀和子串。 符号串s的真前缀，真后缀，真子串：任何非空符号串 x,相应地，是s的前缀，后缀或子串，并且 s ? x 符号串的运算 符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 ε的长度为0 连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有εa = aε 方幂：符号串自身连接n次得到的符号串 an 定义为 aa…aa n个a a1=a, a2=aa则a0=ε 符号串集合：若集合A中所有元素都是某字母表?上的符号串，则称A为字母表?上的符号串集合。 两个符号串集合A和B的乘积定义为 AB =?xy|x?A且y?B? 若 集合A=?ab,cde? B = ?0,1?