编译原理第一章.ppt

1、第一章 语言结构与文法1.1 计算机语言的组成结构,计算机语言的结构特征,语法： 语句的组成规则 描述方法：BNF范式、语法描述图 词法： 单词的组成规则 描述方法：BNF范式、正规式 单词： 具有语义的最小字符串（可区分的）,自然语言和计算机语言的比较,自然语言 是人与人的通信工具 环境、背景知识、语气、二义性 自动翻译很困难 计算机语言 计算机软件使用的通信工具 严格的语法、语义 必须支持自动翻译,语言的描述方法,叙述性方法 自然语言（非形式化描述） 记号方法 数学方法（形式化描述） 保证描述清晰准确 形式化描述的作用 理论基础和抽象分析方法,1.2 文法,语言结构的形式化描述 语言结构的

2、分析 语言是句子的集合 句子是按一定规则构成的符号串 语言的基本符号,例1-1 语言结构,范式,描述句子的组成规则 （简写为产生式 ） 、表示若干个终结符或非终结符 终结符：基本符号集 非终结符：某个语言结构,文法G 的形式定义, = (T，N，) Chomsky 定义文法为一个四元组 T：终结符集 N：非终结符集 ：有穷的产生式集合 ：开始符号 N 至少在产生式左侧出现一次,例1-2 运算表达式的文法 G,考虑所有运算表达式组成的语言 G =(i，+，*，(，)，E，P，E) P: E E + E E E * E E ( E ) E i 简写： E E + E | E * E | ( E )

3、 | i,直接推导,产生式右部代替左部 当是文法的一个产生式， 且、（TN）*， 称是的直接推导， 记为 = 例： i + E = i + E * E,推导：,0 = 1 = 2 = = n 记为 0 =+ n （一步或多步） 0 =* n （零步或多步） 合法句子的生成 从出发反复推导，每次得到一个句型，最终得到句子 （完全由终结符组成句型）,语言：所有合法句子,G 描述的所有合法运算表达式 例: 表达式 i + i * i 的生成 E = E + E = i + E 句型 = i + E * E = i + i * E = i + i * i 句子,语言 L 的形式定义,()+ and T

4、* 由文法 产生的所有句子的集合 文法G 的作用 以有限的规则描述无限的语言现象 有限： 产生式集合 终结符集合 非终结符集合 无限： 由开始符号导出的句子,1.3 分析树,Parse Tree 用树的形式表示句子的结构 树根： 开始符号 中间结点： 非终结符 叶结点： 终结符 每个推导对应一个中间结点及其儿子,推导过程（从开始符号到句子）,E = E + E = i + E = i + E * E = i + i * E = i + i * I 是最左推导(每次替换最左非终结符) 自顶向上构造分析树,例1-3 表达式 i+i*i 的分析树 (按照例1-2的文法）,归约过程（从句子到开始符号）

5、,归约：每次用产生式的左部替换右部 i + i * i=i + i * E =i + E * E =i + E =E + E =E 是最右归约 从底向上构造分析树,二义性文法,对同一句子存在两棵语法分析树 在理论上不可判定,1.4 文法的分类( Chomsky ),语言结构的复杂程度 涉及文法的复杂程度、分析方法的选择 文法 的每个产生式 中： 若(NT)* 且|0, (NT)* 则 是 型文法。,上下文有关文法,若产生式集合中所有， 除(空串)外（S不出现在中）， 则 是 型文法 即：上下文有关文法,上下文无关文法,若 N，(NT)* 则 是型文法 即：上下文无关文法 例：程序设计语言的多数

6、语法特征,正规文法,右线性文法（、N，T或） 若产生式为或 左线性文法 若产生式为 或 都是 型文法（即：正规文法） 例：程序设计语言的多数词法特性,1.5 文法的应用,明确描述对象语言 合法的语言结构 确定基本符号集T 引入非终结符 各种句子结构 定义句子的组成规则 BNF范式或产生式,例1-3 描述电话号码的格式,常用： 67391742(010)67391742 1）描述对象： 电话号码（开始符号) 包括地区代码、局代码、本机代码 不包括分机、呼机、手机、国际代码,形式化过程,2）基本符号集（终结符）： 数字字符 DIG、分割符 -、（、） 3）引入非终结符： 各种代码,定义组成规则, - ( ) DIG DIG DIG DIG DIG DIG DIG DIG DIG DIG DIG DIG DIG,应用要点,文法描述 描述句子的组成规则，不涉及语义 文法正确不能保证语义正确 明确目标 作为目标的语言结构 确认基本符号集 合理引入非终结符（语义明确）,形式语言小结：,计算机语言的描述需借助形式语言 如：用 2型文法描述高级语言的语法规则 文法的用途 以有限的规则和符号，说明无穷的句子 成为语言设计和实现的依据 文法特征（0, 1, 2, 3 型) 反映语言结构的复杂性、决定分