第二章文法和语言.ppt

第二章 文法和语言 一个程序设计语言的确切定义是构造编译程序的重要前提。 本章目的为语言的语法描述寻求工具，以便： 对源程序给出精确无二义的语法描述。 根据语言文法的特点来指导语法分析的过程。 从描述语言的文法可以自动构造出可用的分析程序。 内容安排 文法的直观概念 符号和符号串 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 句型的分析 有关文法实用中的一些说明 2.1 语言和文法的直观概念 语言：由句子组成的集合。 汉语--符合汉语语法的句子的全体 英语--符合英语语法的句子的全体 程序设计语言--该语言的程序的全体 一个程序设计语言就是一个记号系统，其定义包含语法和语义两方面。 阐明语法的主要工具是文法 。 语法(syntax) 定义: 是一组规则，用它可以形成和产生一个合适的程序 描述语法的工具就是文法，这是形式化语言理论的基本概念。 作用: 定义什么样的符号序列是合法的，与符号的含义无关。 例如： A：= B+C A：= B+ 语义(semantics) 分类: 静态语义：限定规则，确定哪些合乎语法  的程序是合适的。 动态语义：执行语义，表明程序要做什么 描述工具：无公认的较好工具 作用: 检查类型匹配，变量作用域等。 文法 文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合 以自然语言为例，人们无法列出全部句子，但可以给出一些规则来说明句子的组成结构，例如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语， 〈句子〉∷＝〈主语〉〈谓语〉 〈主语〉∷＝〈代词〉|〈名词〉 〈代词〉∷＝我|你|他 〈名词〉∷＝王明|大学生|工人|英语 〈谓语〉∷＝〈动词〉〈直接宾语〉 〈直接宾语〉∷＝〈代词〉|〈名词〉 〈动词〉∷＝是|学习 〈句子〉 ? 〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉 ?我〈谓语〉 ?我〈动词〉〈直接宾语〉 ?我是〈直接宾语〉 ?我是〈名词〉 ?我是大学生 按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。 小结：文法的直观概念 补充概念：形式描述语言 Chomsky于1956年提出了一种用来描述语言的数学系统。人们把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。 2.2 符号串和符号串集合 符号：字母表中的元素称为符号 字母表?：符号（元素）的非空有穷集合 符号串：由字母表?中的符号组成的任何有穷序列称为该字母表上的符号串。 在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同 不含任何符号的符号串称为空串，用ε表示 例如：Σ={0,1} 则ε,0,1,01,11,10都是?上的符号串 符号串s的前缀：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀。 号串s的后缀：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana的一个后缀。 符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如：ana是符号串banana的一个子串。 符号和符号串相等 ： X＝Y当且仅当组成X的诸符号与组成Y的诸符号依次相等 1. 符号串的长度：符号串中符号的个数.符号 串s的长度记为|s|。如：|ε|=0， |abc|=3 2.连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy。 如 x=ab ,y=cd 则 xy=abcd，有εa = aε 3.幂：符号串自身连接n次得到的符号串 。 an 定义为 aa…aa a1=a, a2=aa， a0=ε 4. 两个符号串集合A和B的乘积定义为 AB =?xy|x?A且y?B? 例如： 若 集合A=?ab,cde? B = ?0,1? 则 AB =?ab1,ab0,cde0,cde1? A＝{a，b} B＝{c，d} 则 AB＝{ac，ad，bc，bd} 5.集合∑的闭包∑*和集合∑的正闭包∑+ 使用 ∑* 表示∑上的一切符号串