《编译概述》PPT课件.ppt

2020 3 24 1 Chapter2GrammarandLanguage 串和语言 StringsandLanguages 文法和语言的定义 DefinitionsofGrammarandLanguage 文法和语言的分类 ClassificationofGrammarandLanguage 分析树与句型 ParseTreeandSententialform 2020 3 24 2 2 1串和语言 字母表 alphabet 字母表是符号 symbols 的非空有穷集合 用 表示符号 可以相互区别的记号 元素 不同的语言有不同的字母表汉语 汉字英语 26个英文字母 2020 3 24 3 2 1串和语言 符号串 String 符号串是由字母表中的符号所组成的有穷序列 在语言理论中 符号串又称为 句子 sentence 字 word 例如 a b a b aa ab aabba 都是 上的符号串 是任何 上的符号串 2020 3 24 4 2 1串和语言 符号串的长度符号串中包含符号的个数符号串s的长度记为 s 例 对于字母表 a b c aab是其上的一个符号串 aab 3注意 空符号串 0 2020 3 24 5 2 1串和语言 符号串的前缀 prefix 后缀 suffix 子串 substring 后缀 删去符号串s头部的零个或多于零个符号得到的符号串例如 nana是符号串banana的一个后缀 前缀 移走符号串s尾部的零个或多于零个符号得到的符号串例如 b是符号串banana的一个前缀 2020 3 24 6 2 1串和语言 符号串的真 proper 前缀 真后缀和真子串 非空 子串 从s中删去一个前缀和一个后缀得到的符号串例如 ana是符号串banana的一个子串 对于每个符号串s s和 两者都是符号串s的前缀 后缀和子串 2020 3 24 7 2 1串和语言 语言 Language 某个字母表上的符号串的集合 例 汉语 所有符合汉语语法的句子构成的集合PASCAL语言 所有合法的PASCAL程序构成的集合 注意 空集 和 的不同 2020 3 24 8 2 1串和语言 符号串的运算 连接 concatenation 符号串x y的连接 是把y的符号写在x的符号之后得到的符号串xy 如x ab y cd则xy abcd注 方幂 exponentiation 符号串自身连接n次得到的符号串 n定义为 n个 1 2 注 0 2020 3 24 9 2 1串和语言 语言的运算 operationsonlanguages 语言是符号串的集合 集合的运算有并 交 差等 并运算 等同于集合的并运算 2020 3 24 10 2 1串和语言 连接 乘积 两个符号串集合A和B的乘积定义为 AB xy x A且y B 例如 集合A ab cde B 0 1 则AB ab1 ab0 cde0 cde1 L L LLL L LnL0 2020 3 24 11 2 1串和语言 闭包 Kleeneclosure L L0 L1 L2 L3 闭包 Positiveclosure L L1 L2 L3 L L 2020 3 24 12 2 1串和语言 注 后面通常是考虑字母表 的 闭包和 闭包例 a b a b aa ab ba bb aaa aab a b aa ab ba bb aaa aab 2020 3 24 13 2 1串和语言 综合性的例子 P93example3 2L A B C Z a b c z D 0 1 9 把L和D两个字母表看作长度为1的符号串集合 即语言 1 L D2 LD3 L44 L 5 L L D 6 D 2020 3 24 14 2 2文法和语言的定义 如何来描述一种语言 如果语言是有穷的 只含有有穷多个句子 可以将句子逐一列出来表示 如果语言是无穷的 找出语言的有穷表示 2020 3 24 15 2 2文法和语言的定义 语言的有穷表示有两个途经 生成方式 文法 语言中的每个句子可以用严格定义的规则来构造 识别方式 自动机 用一个过程 当输入的一任意串属于语言时 该过程经有限次计算后就会停止并回答 是 若不属于 要么能停止并回答 不是 要么永远继续下去 文法即是以生成方式描述语言的 语言中的每个句子可以用严格定义的规则来构造 2020 3 24 16 2 2文法和语言的定义 文法G定义为四元组 VT VN S P VT 终结符 terminals 集 其中的元素一般用小写字母或数字表示 a b c 0 1 代表语言中不可再分的基本符号 如汉语中的汉字 PASCAL语言中的基本字 VN 非终结符 nonterminals 集 其中的元素一般用大写字母表示 A B C 或者用尖括号括起 代表语法单位 如汉语中的语句 段落 PASCAL语言中的语句 表达式 子程序等 2020 3 24 17 2 2文法和语言的定义 S是一个特殊的非终结符号 称为开始符号 startsymbol S至少要在一条产生式中作为左部出现 P是一个产生式 production 的集合产生式 重写规则 生成式 是形如 或 的 有序对 且 V V 其中V VT VN 称为产生式的左部 不能为空 称为产生式的右部 可以为空 如 A 2020 3 24 18 2 2文法和语言的定义 例1 文法G VT VN S P VN S VT 0 1 P S 0S1 S 01 可以只写出产生式 通过产生式可以得到文法的其它部分 左部相同的产生式可以写在一起 如 S 0S1 01 2020 3 24 19 2 2文法和语言的定义 例2 文法G VT VN S P VN VT a b c x y z 0 1 9 P a z 0 9 S 2020 3 24 20 2 2文法和语言的定义 推导 derivation 与归约 reduction 直接推导与直接归约如果A 是G的一条产生式 则称用 代替 A 为一步直接推导 记为 A 称用 A 代替 为一步直接归约 记为 A 推导是用产生式的右部代替左部 归约是用产生式的左部代替右部 归约是推导的逆过程 2020 3 24 21 2 2文法和语言的定义 推导的长度直接推导的次数 长度大于等于1的推导 长度大于等于0的推导 推导的例子 S 0S1 00S11 000111 长度为3记为 S000111SS 2020 3 24 22 2 2文法和语言的定义 最左推导与最右推导 是一步推导 VT VN 最左推导 lm 对 中的最左非终结符进行展开最右推导 rm 对 中的最右非终结符进行展开 2020 3 24 23 2 2文法和语言的定义 例子 表达式文法E E TE TT T FT FF E F a 最左推导 E lm T lm T F lm F F lm a F lm a a 最右推导又称为规范推导 最右推导 E rm T rm T F rm T a rm F a rm a a 2020 3 24 24 2 2文法和语言的定义 最右归约与最左归约最左推导的逆过程是最右归约 即对最右边的可归约串进行归约a a a F F F T F T E 最右推导的逆过程是最左归约 即对最左边的可归约串进行归约a a F a T a T F T E 最左归约称为规范归约 2020 3 24 25 2 2文法和语言的定义 句型 sententialform 与句子 sentence 句型 从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串S 句型可以既包含终结符号又包含非终结符号 只包含终结符号的句型称为句子 句子是一种特殊的句型 2020 3 24 26 2 2文法和语言的定义 例 在推导E T T F F F a F a a中 句型有 E T T F F F a F a a 句子是 a a 2020 3 24 27 2 2文法和语言的定义 语言的形式定义 文法G推导出的所有句子组成的集合 称为语言 记为L G L G S VT 2020 3 24 28 2 2文法和语言的定义 例子 G1 S AA 0A1A 01 是由一个或多个0开头 后跟同样数目的1的符号串构成的集合 语言 可记为 L G 0n1n n 1 2020 3 24 29 2 2文法和语言的定义 G2 E idE E EE E EE E 产生的是表达式的集合 2020 3 24 30 2 2文法和语言的定义 G3 E E TE TT T FT FF E F id 产生的也是表达式的集合 2020 3 24 31 2 2文法和语言的定义 一个文法对应一个语言 但一个语言可能有若干个文法产生它 这若干个文法是等价的 称为等价 equivalent 文法 例G2与G3 2020 3 24 32 2 3文法和语言的分类 乔姆斯基 Chomsky 在1956年提出形式语言理论 他将形式文法分为四类 0 1 2 3 对应四类形式语言 0 1 2 3 分类的方法是对文法的产生式进行不同的限制 2020 3 24 33 2 3文法和语言的分类 0型文法 0 即 1型 上下文有关 文法 2型 上下文无关 文法 A VN VT VN A 3型 正规 文法A a或A aB 右线性 A a或A Ba 左线性 2020 3 24 34 2 3文法和语言的分类 例 1型 上下文有关 文法文法G S CDAb bAC aCABa aBC bCBBb bBAD aDC BD bDD Aa bDL G ww w a b 2020 3 24 35 2 3文法和语言的分类 例 2型 上下文无关 文法文法G1 S aB bAA a aS bAAB b bS aBB文法G2 S 0A 1B 0A 0A 1B 0SB 1B 1 0 2020 3 24 36 2 3文法和语言的分类 例 3型 正规 文法文法G S 0A 1B 0A 0A 1B 0SB 1B 1 0 2020 3 24 37 2 3文法和语言的分类 0型文法产生的语言称为0型语言 1型文法或上下文有关文法 CSG 产生的语言称为1型语言或上下文有关语言 CSL 2型文法或上下文无关文法 CFL 产生的语言称为2型语言或上下文无关语言 CFL 3型文法或正则 正规 文法 RG 产生的语言称为3型语言正则 正规 语言 RL 2020 3 24 38 2 3文法和语言的分类 四种文法 语言 之间的逐级 包含 关系 2型文法 语言 1型文法 语言 0型文法 语言 3型文法 语言 2020 3 24 39 2 3文法和语言的分类 识别各类语言的数学模型 自动机 图灵机 0型语言 有界图灵机 线性有界自动机 1型语言 下推自动机 2型语言 有限自动机 3型语言 2020 3 24 40 2 4分析树与句型 上下文无关文法能够描述现今程序设计语言的大部分语法结构 算术表达式赋值语句条件语句等 2020 3 24 41 2 4分析树与句型 表达式文法 G i E E P P E idE E EE E EE E E表示算术表达式 id表示程序的 变量 该文法定义了由变量 和 组成的算术表达式的语法结构 即 变量是算术表达式 若E1和E2是算术表达式 则E1 E2 E1 E2和 E1 也是算术表达式 2020 3 24 42 2 4分析树与句型 描述一种简单赋值语句的产生式 赋值语句 i E 描述条件语句的产生式 条件语句 if 条件 then 语句 if 条件 then 语句 else 语句 2020 3 24 43 2 4分析树与句型 分析树是描述上下文无关文法句型推导的一种直观方法 也称为推导树 2020 3 24 44 2 4分析树与句型 为句型推导构造分析树例子 E T E E TE TT T FT FF E F a T F F F a F T T F F a a E a a 2020 3 24 45 2 4分析树与句型 分析树的特性 根标识为开始符号 内部结点标识为非终结符号 每一内部结点及其子结点对应一条产生式 该结点是产生式的左部 子结点从左至右排列构成产生式的右部 叶结点从左至右排列构成句型 T T F F a a E 2020 3 24 46 2 4分析树与句型 分析树与句型推导的关系 一次推导 不是一个句型 对应一棵分析树 一棵分析树可能对应若干个推导 例如下面的推导对应的也是上面那棵分析树E T T F T a F a a a T T F F a a E 2020 3 24 47 2 4分析树与句型 说明分析树没有严格反映推导的顺序 但是一棵分析树对应一个最左推导 也只能对应一个最右推导 T T F F a a E 2020 3 24 48 2 4分析树与句型 句型的短语 直接短语和句柄 handle 如果S A 和A 则称 是关于A的 句型 的一个短语 子树的叶子 S A 2020 3 24 49 2 4分析树与句型 例 句型F a的短语 T T F F a E F a F a 2020 3 24 50 2 4分析树与句型 如果S A 和A 则称 是关于A的 句型 的一个直接短语 只有父子两代的子树的叶子 S A 2020 3 24 51 2 4分析树与句型 例 句型F a的直接短语 T T F F a E F a 2020 3 24 52 2 4分析树与句型 最左直接短语称为句柄最左性体现在分析树和句型中 S A 2020 3 24 53 2 4分析树与句型 例 句型F a的句柄 T T F F a E F 2020 3 24 54 2 4分析树与句型 句型的素短语 最左素短语 1 是关于A的 句型