第二章语言概述

《第二章语言概述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章主要内容¢2.1语言概述高级语言及其文法¢2.2基本定义¢2.3文法(Grammar)的定义¢2.4CFG的分析树（ParseTree）¢2.5文法的分类¢2.6文法的构造2.1语言概述2.1语言概述¢语言特征¢自然语言(NaturalLanguage)什么是语言？¢是人与人的通讯工具¢语义(semantics):环境、背景知识、语气、二义性——难以形式化¢计算机语言(ComputerLanguage)¢计算机系统间、人机间通讯工具¢严格的语法(Grammar)、语义(semantics)——

2、易于形式化：严格2.1语言概述2.1语言概述¢语言的描述方法——现状¢语言——形式化的内容提取¢自然语言：自然、方便-非形式化¢语言(Language)：满足一定条件的句子集合¢句子(Sentence)：满足一定规则的单词序列¢数学语言（符号）：严格、准确-形式化¢单词(Token)：满足一定规则的字符¢形式化描述(Character)串¢高度的抽象，严格的理论基础和方便的计¢语言是字和组合字的规则算机表示。¢例（自然语言：第译始一天课今开编上节）¢今天开始上第一节编译课12.1语言概述2.1语言

3、概述¢程序设计语言——形式化的内容提取¢程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合。¢程序(Program)：满足语法规则的语句序列。¢语句(Sentence)：满足语法规则的单词序列。¢单词(Token)：满足词法规则的字符串。¢例：变量:=表达式¢if条件then语句¢while条件do语句¢call过程名(参数表)语言是字及其组合规则的统一体2.1语言概述形式语言于自动机理论的产生与作用¢描述形式——文法¢语言学家Chomsky最初从产生语言的角度研究语

4、言。¢1956年，通过抽象，他将语言形式地定义为是由一个字母表¢语法——语句中的字母组成的一些串的集合。可以在字母表上按照一定的¢语句的组成规则规则定义一个文法（Grammar），该文法所能产生的所有句子组成的集合就是该文法产生的语言。¢描述方法：BNF范式、语法(描述)图¢克林（Kleene）在1951年到1956年间，从识别语言的¢词法——单词角度研究语言，给出了语言的另一种描述。¢单词的组成规则¢克林是在研究神经细胞中，建立了自动机，他用这种自动机来识别语言：对于按照一定的规则构造的任一个自

5、动机，该¢描述方法：BNF范式、正规式自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成。形式语言于自动机理论的产生与作用形式语言于自动机理论的产生与作用¢1959年，Chomsky通过深入研究，将他本人的研究成果¢形式语言与自动机理论除了在计算机科学领域中的直与克林的研究成果结合了起来，不仅确定了文法和自接应用外，更在计算学科人才的计算思维的培养中占动机分别从生成和识别的角度去表达语言，而且证明有极其重要的地位了文法与自动机的等价性。¢计算思维能力的培养，主要是由基础理论系列课程实

6、¢20世纪50年代，人们用巴科斯范式（BackusNour现的，该系列主要由从数学分析开始到形式语言结束Form或BackusNormalForm，简记为BNF）成功地对的一些数学和抽象程度比较高的内容的课程组成。高级语言ALGOL-60进行了描述。实际上，巴科斯范式¢它们构成的是一个梯级训练系统。在此系统中，连续数学、就是上下文无关文法（ContextFreeGrammar）的一离散数学、计算模型等三部分内容要按阶段分开，三个阶段种表示形式。这一成功，使得形式语言在20世纪60年对应与本学科的学

7、生在大学学习期间的思维方式和能力的变化与提高过程的三个步骤。代得到了大力的发展。2计算思维能力的培养过程2.2基本定义形式语言与中学数学数学分析离散数学自动机理论¢字母表（Alphabet）∑是一个非空有穷集合，字母表中的元素称为该字母表的一个字具体.静止变量.运动离散.抽象形式.模型母（Letter），也叫字符（Character）。(基本运算系统)(计算系统)¢例以下是不同的字母表：运算⑴{a，b，c，d}实数抽象集合范围⑵{a，b，c，……，z}单一、具体的计算一般、形式化的计算⑶{0，1}

8、特征（实例计算）（模型化计算）(4)ASCII字母表高水平计算专业人才的计算思维能力的渐进培养2.2基本定义2.2基本定义设s是符号串，则s的¢符号串的定义(1)ε是∑上的一个符号串。前缀：移走s的尾部的零个或多于零个符号(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。后缀：删去s的头部的零个或多于零个符号(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。子串:从s中删去一个前缀和一个后缀由字母表中的符号所组成的任何有穷序列被称子序列:从s中删去零或多于零个符