第二章语言概述.ppt

1、高级语言及其语法，2.1语言概要2.2基本定义2.3语法(Grammar )的定义2.4 CFG的解析树2.5语法的分类2.6语法的构造，本章的主要内容，2.1语言概要，语言是2.1语言的概要语言特征自然语言(Natural Language )， 人与人的通讯工具含义(semantics):环境、背景知识、语气、二义性是难以格式化计算机系统之间、人机间通讯工具的严格和易于格式化：严格、2.1语言概述、语言描述方法现状自然语言：自然方便-非形式化数学语言(符号):严格、准确-形式化描述高度抽象、严格的理论基础和方便的计算机显示。2.1语言概要、语言形式化的内容抽取语言(Language ) :

2、满足一定条件的句子集合(Sentence ) :满足一定规则的单词列单词(Token ) :满足一定规则的单词列语言是单词和组合词的规则2.1语言概要、语言是字及其组合规则的统一、2.1语言概要、 软件编程语言形式化的内容提取软件编程语言(Programming Language ) :构成程序计程仪程序的所有语句的集合。 程序计程仪(Program ) :满足语法规则的一系列语句。 句子(Sentence ) :符合语法规则的单词序列。 单词(Token ) :符合词法规则的字符串。 例：变量：=表达式if条件then语句while条件do语句call过程名(残奥仪表)，2.1语言概要，描述

3、形式语法语法语法句子的构成规则描述方法： BNF正规，语法(描述)图字句单词的构成规则描述方法： BNF正规，正规1956年，抽象地说，他字母了语言形式字母表上可以根据一定的规则定义语法(Grammar )，该语法生成的所有句子的集合就是该语法生成的语言。 清洁(Kleene )在1951年到1956年期间，从语言认识的观点研究语言，提出了语言的别的记述。 克林在研究神经元细胞的过程中，对于按照一定规则建构的任何一个自动机，制作了定义由该自动机能认识的所有句子组成的语言的自动机。 形式语言是自动机理论的生成和作用，1959年，Chomsky经过深入研究，将他自身的研究成果和克林的研究成果结合起

4、来，不仅确定了语法和自动机分别从生成和认识的角度来表达语言，还证明了语法和自动机的等价性。 在20世纪50年代，人们成功地使用Backus Nour Form或者Backus Normal Form，缩写为BNF )记述了高级语言ALGOL-60。 实际上，巴科斯范式是上下文无关语法(Context Free Grammar )的表现形式。 由于这项成功，形式语言在六零年代有了很大的发展。 形式语言是自动机理论的生成和作用，形式语言和自动机理论除了在修正机科学领域的直接应用外，在修正学科人才的修正思维培养中占有极其重要地位的修正思维能力的培养，主要在基础理论系列课程中实现，该系列主要从数学分析

5、到形式语言末尾的数学和抽象度正在配置薪级培训系统。 在这个系统中，连续数学、离散数学、修正模型等三个内容要分阶段，三个阶段对应于本学科学生在高等院校学习期间的思维方法和能力变化与提高过程的三个阶段。补正思考能力的培养过程、中学数学分析离散数学具体.静止变量.运动离散.抽象形式.模型(基本运算系统) (补正系统)实数抽象集合单一、具体的补正一般、形式化的补正算(实例补正算) (模型化补正算)、高级补正算专门人才的补正算字母(Alphabet )是非空的贫穷集合， 字母元素有时称为其字母字符(Letter )，有时称为字符(Character )。 以下是不同的字母： a、b、c、d a、b、c、

6、z0、1(4)ascii字母、2.2基本定义、符号串的定义(1)是以上的符号串。 (2)如果x是上面的符号串，a是要素，则xa是上面的符号串。 (3) y是以上的符号串，仅从(1)和(2)导出。 由字母象征符组成的穷序列，又称为其字母上的象征符列，又称为字。2.2若将基本定义、s设为符号串，则删除s的前缀： s末尾的0个以上的符号后缀：删除s开头的0个以上的符号子串3360从s中删除1个前缀和1个后缀子串3360从s中删除0个以上的符号(这些个的符号不连续)反转(用SR表示)，例如| aab 、2.2基本定义、符号串的连结和幂1 .连结：将x和y设为符号串，这些连结xy是将y的符号写在x的符号

7、之后的符号串。 例如，x=ba、y=nana、xy=banana. 2 .幂： x0=； x1=x； x2=xx； xn=xn-1x； 例如，假设x=ba，x1=ba，x2=baba，x3=bababa，2.2基本定义，定义1是1，2是两个字母，以及1和2的乘积(产品)被定义为110的n次方，递归地，0=n=n-1 n1 定义为111，的正闭包为=234的克林闭包为*=0=023，2.2基本定义，例如0、1=0、1 ba、bb、bc、bd、aaa、aab、aac、aad aad，aba，abb，abc，2.2基本定义，定义5为字母，L *，l为字母上的语言(Language )，xL，x为l的

8、句子。例如：字母0，1上的语言0，100，110，1，00，110，1，00，11，01，1000，11 * 01，10 *，2.3语法的定义考虑一个语法要素的提取，分析： The grey wolf will eat the goat，句主语、终止符集VT=the、grey、wolf、will、eat、goat非终止符集VN=句子、主语、谓语、冠词、形容词、名词、动词、直接宾语、助动词、 句主语谓语冠词形容词名词谓语the grey wolf谓语the grey wolf谓语the grey wolf动词直接宾语. the grey wolf will eat the goat，句子的派生(

9、导出) -从生成语言的观点来看句子的归约-从认识语言的观点来看， -根据所有规则，语句thegreywolfwilleatthegoatthegreywolfwilleatthewolfthegreygoatwilleatthegreywolf符合语法，符合意义grey wolf will eat the goat，句子的意思要求，语法g的形式定义，语法g是四组：=(T，n， t :终止符定径套n :非终止符() TN=语法成分代表一种语言的各种子结构：开始符号，SN代表由语法定义的语言，至少出现在生成公式的左侧一次，其中，语法g的形式定义：产生公式(定义式)的集合(TN)*。 被称作生成式的

10、左部(Left Part )，并且被称作生成式的右部(Right Part )。 生成式定义各语法成分的结构(构成规则)，例2-1算术式的语法，在递归定义中，识别符(id ) (常数、变量)是式(e )的式加上式，则成为式。从式中减去一个的式是式。式乘以式，则成为式。除去一个的式是式，在式即式上加括弧，则成为式例2-1算术式的语法考虑由简单的算术式构成的语言G=(id，*，(，)，e，p，E) P: EE E EE * E E(E ) Eid约束：仅写入生成式的简称e将它们称为生成式。 将1，2，n称为候补式(Candidate )。 基于生成表达式的转换-导出或归约，E E E | E *

11、E | (E ) | id E从第一个候选表达式起，E E E E中的前一个e从第二个候选表达式起为E*E，E*E从第四个候选表达式起为E*E，E*E中的所有e都为id: E*E E 根据第四候选方程式，在第三步骤中将e*e转换为id*id id。例如id Eid E * E、(多步)推导、012 n是0 n n (恰好n步)-0 n (至少一步)0* n (多步：零步或多步)、推导/归纳的示例。 在E E E (1)列中包含的变量id E (4)列中包含的变量id E * E (2)列中包含的变量id id * E(4)列中，在该列中没有变量(文法) 1、EE E 2、EE * E 3、E(E ) 4、E(E ) 4 如果E 5 id id * id语句：是S * x、xT*，则x被称为g创建的语句(senteed被称为g产生的句型(Sentential Form )，语法g产生的语句，() S * x和xT*语法EE E|E*E|(E)|id 语法g的作用语言的穷描述有限规则描述无限的语言现象有限：生成式集合、终止符集合、非终止符集合无限：无限多个句子(既有l也有穷)、id id*id的差异可以导出eeeeee*e*ideid*idid*id、ee * ee *。 最右变量右文型/规范文型(canonical ) (最左/规范归约) E id id*id、最左变量左文型