软件代码开发三文法和语言.pptVIP

第三章 文法和语言 本章内容 引言和预备知识 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 3.1 文法的直观概念和语言描述 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则： “我是大学生”。是否是汉语的一个句子? 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷=我｜你｜他｜她 〈名词〉∷=王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉 有了一组规则以后，按照如下方式用它们导出句子： 如句子：“我是大学生”的全部动作过程是： 〈句子〉 ? 〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉  ?我〈谓语〉 ?我〈动词〉〈直接宾语〉  ? 我是〈直接宾语〉 ?我是〈名词〉 ?我是大学生 由此可见：“我是大学生”的构成符合上述规则， 而“我大学生是”不符合上述规则，我们说它不是句子。 这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中这种描述元语言称为文法。 语言描述 语言是由句子组成的集合，是由一组符号所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 每个句子构成的规律（语法） 研究语言 每个句子的含义（语义） 每个句子和使用者的关系（语用） 语法 -- 表示构成语言句子的各个记号之间的组合规律 语义 -- 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 --表示在各个记号所出现的行为中，它们的来源、使用和影响。 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。 “形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言是程序设计语言语法分析研究的基础。 例:标识符文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={ 标识符→字母 标识符→标识符字母 标识符→标识符数字 字母→a,…, 字母→z 数字→0,…, 数字→9 } S=标识符 文法的写法:一般不用将G的四元组显式地表示出来,而只将产生式写出。 例1 G：S→aAb A→ab A→aAb A→ε 例2 G[S]： S→aAb A→ab A→aAb A→ε 例3 G[S]： S→aAb A→ab |aAb |ε 习惯表示 用尖括号括起来的为非终结符,否则为终结符 或:大写字母：非终结符 小写字母：终结符 S – AB A – Ax | y B – z 通常，用 表示：从?1出发，经过一步或若干步，可以推出?n。 例：G[E]： E→E+T|T T→T*F|F F→(E)|aE?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a句子：用符号a，+，*，(和)构成的算术表达式 例 文法G[S]： （1）S→aSBE （2）S→aBE （3）EB→BE （4）aB→ab （5）bB→bb （6）bE→be （7）eE→ee判断aabbee是否是该文法的句子？并写出该文法所表示的语言。  S ?a S BE (S→aSBE) ?a aBEBE (S→aBE) ?aabEBE (