《语言结构与文法》PPT课件.ppt

第二章 语言结构与文法,目的： 为复杂的语言结构的分析 提供精确、严格的描述方法 用途： 支持语言结构（语法、词法）的抽象分析 指导分析程序的实现 约束假设： 不考虑语义信息及其用途 仅考虑语言的组成结构,计算机语言与自然语言的比较,自然语言 是人与人的通讯工具 环境、背景知识、语气、二义性 计算机语言 计算机软件使用的通讯工具 严格的语法、语义,2.1 计算机语言的组成,计算机语言的共同点,语法： 语句的组成规则 描述方法：BNF范式、语法描述图 词法： 单词的组成规则 描述方法：BNF范式、正规式 单词： 具有语义的最小字符串（可区分的）,语言的描述方法,叙述性方法 自然语言（非形式化描述） 记号方法 数学方法（形式化描述） 保证描述清晰准确 形式化描述的作用 理论基础和抽象分析方法,2.2 文法：,提供语言结构的形式化描述 分析语言组成结构的规律 语言是句子的集合 句子是按一定规则构成的符号串 语言有一组基本符号,例2-1 语言结构,范式,描述句子的组成规则 （简写为产生式 ） 、表示若干个终结符或非终结符 终结符：基本符号集 非终结符：某个语言结构,文法G 的形式定义, = (T，N，) Chomsky 定义文法为一个四元组 T：终结符集 N：非终结符集 ：有穷的产生式集合 ：开始符号 N 至少在产生式左侧出现一次,例2-2 运算表达式的文法 G,考虑所有运算表达式组成的语言 G =(i，+，*，(，)，E，P，E) P: E E + E E E * E E ( E ) E i,运算表达式的描述,简写的文法 E E + E | E * E | ( E ) | i 语义 E 表示表达式 i 表示整数 开始符号表示整个句子 所描述的语言 所有仅包含乘法和加法的整数运算表达式,直接推导的定义,用某个产生式的右部代替左部 当是文法的一个产生式， 且、（TN）*， （表示0个或多个终结符或非终结符组成的符号串） 称符号串是的直接推导， 记为 = 例： i + E = i + E * E E = ( E ),推导的定义：,0 = 1 = 2 = = n 记为 0 =+ n （一步或多步） 0 =* n （零步或多步） 例：E = ( E ) = = ( i + E ) 记为 E =+ ( i + E ) 最左推导、最右推导 每次直接推导中代换最左（右）的非终结符,合法句子的生成,从开始符号出发反复推导，每次得到一个句型，最终得到句子 （完全由终结符组成句型） 合法句子的验证 通过基于文法的推导，可判断出给定的符号串是否是属于该文法描述的语言 文法的作用 提供了严格的抽象分析手段 支持语法错误检查的实现,语言由所有合法句子组成,G 描述的所有合法运算表达式 例: 表达式 i + i * i 的生成 E = E + E = i + E 句型 = i + E * E = i + i * E = i + i * i 句子,语言 L 的形式定义,()+ and T* 由文法 产生的所有句子的集合 文法 G 的作用 以有限的规则描述无限的语言现象 有限： 产生式集合 终结符集合 非终结符集合 无限： 由开始符号导出的句子,2.3 分析树,Parse Tree 用树的形式表示句子的结构 树根： 开始符号 中间结点： 非终结符 叶结点： 终结符 每个推导对应一个中间结点及其儿子 表示精确的文法分析结果,例2-3 表达式 i+i*i 的分析树 (按照例1-2的文法）,二义性文法,对同一句子存在两棵语法分析树 在理论上不可判定,2.4 文法的分类( Chomsky ),表述语言结构的复杂程度 涉及文法的复杂程度、分析方法的选择 文法 的每个产生式 中： 若(NT)* 且至少包含一个非终结符, (NT)* 则 是 型文法。,上下文有关文法,若产生式的集合中 除外所有， 代表空串 表示中符号的个数 并且 S 不出现在中， 则 是 型文法 即：上下文有关文法,上下文无关文法,若 N，(NT)* 则 是型文法 即：上下文无关文法 例： 例1-2中的运算表达式 程序设计语言的多数语法特征,正规文法,右线性文法（、N，T*） 若产生式为或 左线性文法 若产生式为 或 都是 型文法（即：正规文法） 例：程序设计语言的多数词法特性,2.5 文法的应用,明确描述对象语言 合法的语言结构 确定基本符号集T 引入非终结符 各种句子结构 定义句子的组成规则 用 BNF 范式或产生式,例2-3 描述电话号码的格式,常用： 67391742(010)67391742 1）描述对象： 电话号码（开始符号) 包括地区代码、局代码、本机代码 不包括分机、呼机、手机、国际代码,形式化过程,2）基本符号集（终结符）： 数字字符 DIG、分割符 -、（、） 3）引入非终结符： 描述对象及其组成部分： 电话号码 地区代码、局代码、本机代码,定义组成规则, - ( ) DIG DIG DIG DIG DIG DIG DIG DIG DIG DIG DIG DIG DIG,应用要点,文法描述 描述句子的组成规则，不涉及语义 文法正确不能保证语义正确 明确目标 作为目标的语言结构 确认基本符号集 合理引入非终结符（语义明确）,形式语言小结：,计算机语言的描述需借助形式语言 如：用 2型文法描述高级语言的语法规则 文法的用途 以有限的规则和符号，说明无穷