第二章 形式语言基础(1).ppt

编译原理 如何让计算机认识 理解和执行高级程序设计语言 2007年2月 内容提要 第2章形式语言基础 2 1语言是符号串集合2 2文法是定义语言的规则集2 3怎样用文法定义语言2 4各种语法成分定义与求解 形式语言是真实语言 程序设计语言 自然语言 的一种数学模型 很适合于计算机处理 形式语言的基本观点是 语言是符号串之集合 2 1语言是符号串集合 例2 1 L1 00 01 10 11 例2 2 L2 abnc bn n 0 句型1abnc 有句子 ac abc abbc abbbc 句型2bn 有句子 b bb bbb 注 符号串的方幂运算 b0 空符号串 b1 b b2 bb b3 bbb 有限语言 无限语言 仅有四个句子 00 01 10 11 2 1 1字母表 字母表是语言的基本符号集 是语言的第一要素 其内容随着语言的研究范畴不同而不同 例2 3 机器语言字符集 1 0 1 例2 4 高级语言字符集 2 a b 例2 5 汉语字符集 3 啊 吃 饭 我 例2 6 汉语单词集 4 毕业 吃 打击 新华社 注 字母表是符号的有限集 而由字母表中符号通过规则组成的句子的集合 语言 则可能是无限集 规则集是语言中句子的组成的规律和法则 它可以通过某种运算 把该语言中的句子产生出来 故而 规则集又称为产生式集 S A 定义的对象 S句子 最大的定义对象 又称为开始符号 A为句型aAc的一个短语 a b c 为字母表 中的符号 空符号串 为描述符号 定义为 或者是 例2 7 L abnc bn n 0 字母表 a b c 展开 L ac abc abbc b bb 规则集 其中 2 1 2规则集 S aAc a c ac S aAc abAc ab c abc S aAc abAc abbAc abbc 一个句子 又一个句子 Sabnc n 0 再一个句子 句子的产生过程 从开始符号出发 对符号串中的定义对象 用其规则右部替换之 称为推导 产生的新符号串仍如此进行 直到新符号串中不再出现定义的对象为止 则最终的符号串就是一个句子 用规则产生句子的过程 同理Sbn n 0 2 1 3怎样利用规则产生句子 G S A 或者A 2 2文法是定义语言的规则集 2 2 1文法的形式定义 每一种形式语言 都能由相应的有限规则集来描述 称为该语言的文法 grammar 注 描述符号 定义为 或者是 文法符号 Z A VN VN VT 规则形式 闭包 由VN VT中符号组成的全部符号串集合 文法应用示例 G N 例2 8 无符号整数文法 其中 d 泛指0 9的任意数字 标识符 指字母开头的字母 数字序列 例2 9 标识符文法 则 则 G I 其中 泛指a z的任一字母 d 泛指0 9的任一数字 注 上述两个文法的四元组 请自行确认之 其中VN E 算术表达式 T 项 F 因式 VT i 变量或常数 Z E P 例2 10 简单算术表达式文法 E T E T E T T F T F T F F i E 令G Z VN VT Z P 注 此文法定义了算术表达式的层次嵌套结构 利用文法求解算术表达式示例 证明i i i i 是一个算术表达式 T T F T E T E T T E T T F E T T i E T T 观察推导过程 可以看到 一旦产生式选择错了 会导致失败 i i i i 我们从两个方面讨论该文法的应用 随意产生出一个算术表达式 E E T T T F T i T i F i i E 2 2 2文法的基本运算 文法有两种基本运算 推导 归约 星推导 直接推导 xAy x y 加推导算符 加推导 设x y VN VT A P 当且仅当 1 2 当且仅当 或 1 2 直接推导算符 星推导算符 即 指一步或一步以上的直接推导运算 即 指零步或零步以上的直接推导运算 即 指用产生式的右部符号串替换左部非终结符 实用中最常见的两种运算 加归约 直接归约 x yxAy 即 直接归约是直接推导的逆运算 用产生式的左部符号串替换右部非终结符 即 指零步或零步以上的直接归约运算 即 指一步或一步以上的直接归约运算 直接归约算符 加归约算符 星归约算符 这是相应的算符 最左推导 最左归约 每次推导皆最左非终结符优先 每次归约皆最左可归约串优先 2 3怎样用文法求解语言 设有文法G Z L G 为G所定义的语言 则有 2 1 通过文法运算 可以求解该文法所定义的语言及其各种语言成分 2 3 1什么是一个文法所定义的语言 G N 例2 11 无符号整数文法 Z dN ddN dn n 1 dn n 0 即 i i i 2 3 2上下文无关语言求解 例2 12 已知文法 最左归约 从符号串出发 过程 E E T T T F T i T i T F i F F i i F i i i F i i T i i E i i E F i E T i E T F E T E 1 最左推导 从开始符号出发 过程 最左非终结符 最左可归约串 按指定的运算法则 证明符号串i i i是算数表达式 得 I d n n 0 令 I A 例2 13 标识符文法 迭代求解法 先求解A A d A A d 2A A d nA 代入A 得 A d n n 0 I A 代入A d n n 0 正规方程式 标识符 字母开头的字母 数字序列 2 3 3正规语言求解 A d A 该文法所定义的语言 可通过构造正规方程式解之 属正规文法类 产生式形式为 xAy x y 产生式形式为 A aB A a A 产生式形式为 A chomsky把形式语言分为四类 分别由四类文法定义 四类文法的区别在于产生式的形式不同 2型语言由2型文法定义 1型语言由1型文法定义 0型语言由0型文法定义 产生式形式为 3型语言由3型文法定义 又称无限制文法 语言 又称上下文有关文法 语言 又称上下文无关文法 语言 又称正规文法 语言 注 四类语言为包含关系 且有L0 L1 L2 L3 编译处理中 主要应用后两种文法 2 4形式语言的分类问题 习题 习题2 1 解释下列词语 形式语言 文法 文法所定义的语言 习题2 2 试构造下述语言L的文法 L ambn m 0 n 1 习题2 3 试求下述文法G Z 所定义的语言 G Z Z b bB B bZ 1 连接 如a b ab 附注2 符号串 集合 的运算问题 3 方幂 n n 1 n 1 4 闭包 n个 符号串的运算 设 为两个符号串 则 的正闭包 1 2 n 的星闭包 0 1 2 n 0 空符号串 什麽符号也没有的符号串 1 2 或 或者 这是一种泛指 2 1 乘积 AB xy x A且y B 4 闭包 A的正闭包 A A1 A2 An A的星闭包 A A0 A1 A2 An 设A和B为两个符号串集合 则 3 方幂 An AA A AAn 1 An 1A n个 A0 A1 A A2 AA A3 AAA 符号串集合的运算 例1 ab cd ab或cd abc de abcde a b 1 a b a b a b a b 0 a b 1 a b 2 a b 2 a b a b aa ab ba bb 即 a b a b n n 0 同理 a b a b n n 0 符号串运算示例 包含空串 不包含空串 符号串集合运算示例 例2 设A a b B c d 则A B a b c d 则AB xy x A y B ac ad bc bd 例3 设A a 则A A0 A1 A2 An a aa aaa a aa aaa an n 0 例4 设A a b A A A0 A1 A2 An A0 A1 A a b A2 A A a b a b aa ab ba bb A3 A A2 a b aa ab ba bb aaa aab aba abb baa bab bba bbb A x x a b n n 0 符号串集合运算示例 续 推论 若A为任一字母表 则A 就是该字母表上的所有符号串 包括空串 的集合 例5 设A a b A A A0 A1 A2 An A0 A1 A