第2章 程序语言基本知识.ppt

第一章：编译概述 编 译 原 理 杭州电子科技大学 第 2 章 程序语言的基本知识 符号串的集合 文法和语言 分析树和二义性 形式语言概观 2.1 符号串的集合 2.1 符号串的集合 2.1 符号串的集合 符号串的长度 符号串中包含符号的个数 符号串 s 的长度记为 |s| 2.1 符号串的集合 符号串的前缀、后缀、子串 2.1 符号串的集合 2.1 符号串的集合 符号串的运算： 连接：符号串α、β的连接，是把 β 的符号写在α 的符号之后得到的符号串 αβ 2.1 符号串的集合 2.1 符号串的集合 语言的运算： 2.1 符号串的集合 连接 两个符号串集合 L 和 M 的乘积定义为： LM = { st | s ? L 且 t ? M } 2.1 符号串的集合 2.1 符号串的集合 2.1 符号串的集合 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.2 文法和语言 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.3 分析树和二义性 2.4 形式语言概观 2.4 形式语言概观 2.4 形式语言概观 2.4 形式语言概观 2.4 形式语言概观 2.4 形式语言概观 2.4 形式语言概观 2.4 形式语言概观 0 型文法— | α | ≠ 0，即 α ≠ ε （ α→β ） 1 型（上下文有关）文法— | α | ≤ | β | （ α→β ） 2 型（上下文无关）文法— A ∈ VN， β ∈（VT∪VN）* （ A→β ） 3 型（正规）文法 A→a 或 A→aB（右线性） A→a 或 A→Ba（左线性） 例：1 型（上下文有关）文法 文法 G ： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD L(G)={ww|w∈{a,b}*} 例：2 型（上下文无关）文法 文法 G1 ： S→aB|bA A→a|aS|bAA B→b|bS|aBB 文法 G2 ： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 最左推导 最右推导 对α中的最左非终结符进行展开 对α中的最右非终结符进行展开 例子：表达式文法 E → E + T E → T T → T * F T → F F → （E） F → a 最左推导：E T T*F F*F a*F a*a ** 最右推导又称为规范推导 最右推导：E T T*F T*a F*a a*a 最右归约 最左归约 最左推导的逆过程是最右归约，即对最右边的可归约串进行归约 最右推导的逆过程是最左归约，即对最左边的可归约串进行归约 a*a = a*F = F*F = T*F = T = E a*a = F*a = T*a = T*F =T = E ** 最左归约称为规范归约 句型 句子 只包含终结符号的句型称为句子。句子是一种特殊的句型。 从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串（S α）。句型可以既包含终结符号又包含非终结符号。 例：在推导 E ? T ? T*F ? F*F ? a*F ? a*a 中， 句型有： E 、T、T*F 、F*F 、a*F 、a*a 句子是： a*a E