[工学]第2章高级语言及其文法.ppt

第2章 高级语言及其文法 本章主要内容 2.1 语言概述 2.2 基本定义 2.3 文法(Grammar)的定义 2.4 CFG的语法(分析)树(Parse Tree) 2.5 文法的分类 2.6 文法的构造 2.1 语言概述 什么是语言 自然语言(Natural Language) 是人与人的通讯工具 语义(Semantics):环境、背景知识、语气、二义性——难以形式化 计算机语言(Computer Language) 计算机系统间、人机间通讯工具 严格的语法(Grammar)、语义(Semantics) ——易于形式化：严格 语言是用来交换信息的工具——功能性描述 2.1语言概述 语言的描述方法——现状 自然语言：自然、方便-非形式化 数学语言（符号）：严格、准确-形式化 形式化描述 高度的抽象，严格的理论基础和方便的计算机表示。 2.1 语言概述 语言——形式化的内容提取 单词(Token)：满足一定规则字符(Character)串 句子(Sentence)：满足一定规则单词序列 语言(Language)：满足一定条件的句子集合 语言是字和组合字的规则——结构性描述 例：一译开天第课今始编节上 今天开始上第一节编译课 2.1 语言概述 程序设计语言——形式化的内容提取 程序设计语言(Programming Language)：组成程序的所有语句的集合 程序(Program)：满足语法规则的语句序列 语句(Sentence) ：满足语法规则的单词序列 单词(Token) ：满足词法规则的字符串 例 变量=表达式 if 条件 then 语句 while条件 do 语句 call 过程名(参数表) 2.1 语言概述 描述形式——文法 语法——语句 语句的组成规则 描述方法：BNF范式、语法(描述)图 词法——单词 单词的组成规则 描述方法：BNF范式、正规式 2.2 基本定义 字母表（Alphabet）是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character） 例 以下是不同的字母表 ⑴ {a，b，c，d} ⑵ { a，b，c，……，z} ⑶ {0，1} 相当于高级语言的字符集 2.2 基本定义 字母表上符号串(String)的定义 (1) ε是∑上的一个符号串，叫做空串。 (2) 若x是∑上的符号串，而a是∑的元素, 则xa是∑上的符号串。 (3) y是∑上的符号串,当且仅当它由(1)和(2)导出。 由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”(Word)。 2.2 基本定义 定义 1 设∑1、∑2是两个字母表，∑1与∑2 的乘积(Product)∑1∑2={ab|a∈∑1，b∈∑2} 例:∑1={0,1}, ∑2={a,b}, ∑1∑2 ={0a,0b,1a,1b} 定义 2 设∑是一个字母表，∑的n次幂(Power)递归地定义为： ⑴ ∑0={ε} ⑵ ∑n=∑n-1∑ n≥1 例： ∑13 ={000,001,010,011,100,101,110,111} 2.2 基本定义 定义 3 设∑是一个字母表，∑的正闭包(Positive Closure)： ∑+=∑∪∑2∪∑3∪∑4∪…… ∑的克林闭包(Kleene Closure)： ∑*=∑0∪∑+ =∑0∪∑∪∑2∪∑3∪…… 2.2 基本定义 例 {0,1}+={0，1，00，01，11，000，001，010，011，100，……} {a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc……} 2.2 基本定义 例 {0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…} {a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…} 2.2 基本定义 定义 5 设∑是一个字母表，?L ? ∑*，L称为字母表∑上的一个语言（Language），?x∈L，x叫做L的一个句子。 例： 字母表{0，1}上的语言 {0，1} {00，11} {0，1，00，11} {0，1，00，11，01，10} {00，11}* {01，10}* 2.2 基本定义 设s是符号串前缀：移走s的尾部的零个或多于零个符号 后缀：删去s的头部的零个或多于零个符号 子串：从s中删去一个前缀和一个后缀 子序列: 从s中删去零个或多于零个符号(这些符号不要求是连续的） 长度：是该符号串中的符号的数目。例如|aab|