语言极其文法ppt课件

.,1,语言及其文法,.,2,本章主要内容,语言概述基本定义文法(Grammar)的定义CFG的分析树（ParseTree）文法的分类文法的构造,.,3,语言概述,什么是语言？,.,4,语言概述,语言特征自然语言(NaturalLanguage)是人与人的通讯工具环境、背景知识、语气、二义性,.,5,鲁迅对红楼梦的评价,单是命意，就因读者的眼光而有种种：经学家看见易，道学家看见淫，才子看见缠绵，革命家看见排满，流言家看见宫闱秘事。,.,6,计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(semantics),.,7,语言概述,语言的描述方法现状自然语言：自然、方便-不易形式化计算机语言：严格、准确-易于形式化形式化描述高度的抽象，严格的数学理论基础和方便的计算机表示,.,8,语言概述,自然语言形式化的内容提取语言(Language)：满足一定条件的句子集合句子(Sentence)：满足一定规则的单词序列单词(Token)：满足一定规则的字符(Character)串自然语言语言是字和组合字的规则例：第译始一天课今开编上节今天开始上第一节编译课,.,9,语言概述,字,组合规则,无规则使用,不表达意义的串,语言(表达意义的话),.,10,语言概述,程序设计语言形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合。程序(Program)：满足语法规则的语句序列。语句(Sentence)：满足语法规则的单词序列。单词(Token)：满足词法规则的字符串。例：变量=表达式if条件then语句while条件do语句,.,11,语言概述,形式化语言理论用数学方法研究自然语言（如英语）和人工语言（如程序设计语言）的产生方式、一般性质和规则的理论。描述形式文法语法语句语句的组成规则描述方法：BNF范式、语法(描述)图词法单词单词的组成规则描述方法：BNF范式、正规式,.,12,形式化语言,语言学家Chomsky最初从产生语言的角度研究语言。1956年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（Grammar），该文法所能产生的所有句子组成的集合就是该文法产生的语言。克林（Kleene）在1951年到1956年间，从识别语言的角度研究语言，给出了语言的另一种描述。克林是在研究神经细胞中，建立了自动机，他用这种自动机来识别语言：对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成。,.,13,形式化语言,1959年，Chomsky通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。20世纪50年代，人们用巴科斯范式（BackusNourForm或BackusNormalForm，简记为BNF）成功地对高级语言ALGOL-60进行了描述。实际上，巴科斯范式就是上下文无关文法（ContextFreeGrammar）的一种表示形式。这一成功，使得形式语言在20世纪60年代得到了大力的发展。,.,14,形式化语言,形式语言与自动机理论除了在计算机科学领域中的直接应用外，更在计算学科人才的计算思维的培养中占有极其重要的地位。计算思维能力的培养，主要是由基础理论系列课程实现的，该系列主要由从数学分析开始到形式语言结束的一些数学和抽象程度比较高的内容的课程组成。它们构成的是一个梯级训练系统。在此系统中，连续数学、离散数学、计算模型等三部分内容要按阶段分开，三个阶段对应与本学科的学生在大学学习期间的思维方式和能力的变化与提高过程的三个步骤。,.,15,计算思维能力的培养过程,高水平计算专业人才的计算思维能力的渐进培养!,.,16,文法,文法阐明语法的一种工具形式化语言理论的基本概念以有穷的集合刻画无穷的集合,.,17,一个形式化例子,|小张|小王|小李|学生|篮球我|你|他是|打,直观地认识文法例子：我是学生,.,18,文法的定义,如何实现语言结构的形式化描述？,.,19,文法的形式定义,文法为一个四元组:=(T，N，)T：终结符(Terminal)集N：非终结符集，TN=语法成分代表某个语言的各种子结构：开始符号(StartSymbol)，SN代表文法所定义的语言，至少在产生式左侧出现一次,.,20,文法的形式定义,：产生式(Product)集合，被称为产生式（定义式），读作：定义为。其中(TN)+，且中至少有N中元素的一个出现。(TN)*。称为产生式的左部(LeftPart)，称为产生式的右部(RightPart)。产生式定义各个语法成分的结构（组成规则）,.,21,句子结构分析例子,|小张|小王|小李|学生|篮球我|你|他是|打,=(T，N，),.,22,例子：标识符的文法,在程序设计语言中，假设标识符的命名规则为a、b、c开头的，字母a、b、c和数字1、2、3的序列。命名规则：a|b|c1|2|3,.,23,例子：标识符的文法,那么文法是：=(T，N，)N=N,L,DT=a,b,c,1,2,3P:NLNNLNNDLa|b|cD1|2|3N是开始符号,L代表D代表N代表,.,24,例子:简单算术表达式的文法,定义简单算术表达式的文法，要求：只考虑加、减、乘、除的基本运算；考虑括号。,a+b-c1+3/a(a+b)*m-n,.,25,例子:简单算术表达式的文法,递归定义（中缀表示）标识符(id)（常数、变量）是表达式(E)；表达式加一个表达式是表达式；表达式减一个表达式是表达式；表达式乘一个表达式是表达式；表达式除一个表达式是表达式；表达式加上括号后是表达式.,.,26,例子:简单算术表达式的文法,考虑简单算术表达式组成的语言G=(id，+，-，*，/，(，)，E，P，E)P:EE+EEE-EEE*EEE/EE(E)Eid简写(假设约定：只写产生式)EE+E|E-E|E*E|E/E|(E)|id,=(T，N，),.,27,产生式形式为：xAy-xy,产生式形式为：A-aB,A-a,A-,产生式形式为：A-,形式语言的分类,chomsky把形式语言分为四类，分别由四类文法定义；四类文法的区别在于产生式的形式不同：