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