第二章文法和语言ppt课件

第二章文法和语言 学习目标 掌握 自上而下与自下而上的分析思想理解 文法的形式定义 推导 归约 句型 句子 语言 上下文无关文法 规范句型 语法树 短语 直接短语 句柄了解 文法的类型 文法实用中的限制 文法的二义性 2 1语言和文法的直观概念2 2符号和符号串2 3文法和语言的形式定义2 4文法的类型2 5上下文无关文法及其语法树2 6句型的分析 2 1语言和文法的直观概念 程序设计语言的直观定义程序设计语言是一个记号系统 它的定义包括语法和语义 语法 syntax 定义 是一组规则 用它可以形成和产生一个合适的程序描述工具 文法作用 定义什么样的符号序列是合法的 与符号的含义无关 语义 semantics 分类 静态语义 一系列限定规则 确定哪些合乎语法的程序是合适的动态语义 表明程序要做什么描述工具 指称语义 操作语义等作用 检查类型匹配 变量作用域等 文法的直观概念 如何来描述一种语言 如果语言是有穷的 只含有有穷多个句子 可以将句子逐一列出来表示如果语言是无穷的 要找出语言的有穷表示 有两个途经 生成方式 文法 语言中的每个句子可以用严格定义的规则来构造识别方式 自动机 用一个过程 当输入的一任意串属于语言时 该过程经有限次计算后就会停止并回答 是 若不属于 要么能停止并回答 不是 要么永远继续下去 文法 是语言语法的描述工具 实现用有穷的规则把语言的无穷句子集描述出来 例 我是大学生 是汉语的一个句子汉语句子的构成规则表示如下 句子 主语 谓语 主语 代词 名词 代词 我 你 他 名词 王明 大学生 工人 英语 谓语 动词 直接宾语 动词 是 学习 直接宾语 代词 名词 例 34 3 42 是一个表达式表达式的构成规则表示如下 Exp ExpopExp Exp NumberOp 由规则推导句子 方法 用一条规则 的右端符号串代替 的左端 表示 用 表示推导 含义是 使用一条规则 代替 左边的某个符号 产生 右端的符号串 例如 句子 我是大学生 的推导过程如下 句子 主语 谓语 代词 谓语 我 谓语 我 动词 直接宾语 我是 直接宾语 我是 名词 我是大学生 文法的作用严格定义句子的结构 是判断句子结构合法与否的依据用有穷的规则把无穷的句子集合描述出来 2 2符号和符号串 字母表定义 元素的非空有穷集合例 0 1 a b c 元素也称为符号 字母表也称符号集 程序语言的字母表由字母数字和若干专用符号组成 符号串定义 由字母表中的符号组成的任何有穷序列例 0 00 10是字母表 0 1 上的符号串a ab aaca是 a b c 上的符号串在符号串中 符号是有顺序的 顺序不同 代表不同的符号串 如 ab和ba不同不含任何符号的符号串称为空串 用 表示注意 并不等于空集合 符号串长度 符号串中含有符号的个数如 abc 3 0 符号串的运算符号串的连接 设x y是符号串 它们的连接是把y的符号写在x的符号之后得到的符号串xy例如x ST y abu则xy STabu显然 x x x符号串的方幂 把符号串a自身连接n次得到的符号串an aa aa例如a1 aa2 aaa0 符号串集合 定义 若集合A中所有元素都是某字母表 上的符号串 则称A为字母表 上的符号串集合 符号串集合的乘积 符号串集合A和B的乘积定义为 AB xy x A且y B 即AB是由A中的串x和B中的串y连接而成的串xy组成的集合 若集合A ab cde B 0 1 则AB ab0 ab1 cde0 cde1 显然 A A A 符号串集合的方幂 设A是符号串的集合 则称Ai为符号串集A的方幂 其中i是非负整数 具体定义如下 A0 A1 A A2 AAAK AA A k个 集合的闭包闭包集合 的闭包 定义如下 0 1 2 3 例 设有字母表 0 1 则 0 1 2 0 1 00 01 10 11 000 即 表示 上所有有穷长的串的集合 正闭包 1 2 3 称为 的正闭包 表示 上的除 外的所有用穷长串的集合 0 字母表 上的一个语言是 上的一些符号串的集合即是 的一个子集例如 a b a b aa ab ba bb aaa aab 集合 ab aabb aaabbb anbn 或 w w 且w anbn n 1 为字母表 上的一个语言 集合 a aa aaa 或 w w 且w an n 1 为字母表 上的一个语言 是一个语言 即 是一个语言 2 3文法和语言的形式定义 1 文法的定义2 文法的简化表示法3 推导与归约4 句型 句子 语言的定义5 文法的等价 1 文法的定义 产生式 规则 产生式是一个有序对 通常写作 或 文法定义 文法G Grammar 定义为四元组 VN VT P S VN Nonternimal 非终结符集VT Terminal 终结符集P Production 产生式 规则 集合S StartSymbol 开始符号或识别符号 说明 V VN VT V称为文法G的字母表P中产生式形如 其中 V 且至少含一个非终结符 V VN VT和P是非空有穷集VN VT S是一个非终结符 且至少要在一条产生式的左部出现 汉语句子的构成规则表示如下 句子 主语 谓语 主语 代词 名词 代词 我 你 他 名词 王明 大学生 工人 英语 谓语 动词 直接宾语 动词 是 学习 直接宾语 代词 名词 例1 文法G VN VT P S 其中VN S VT 0 1 P S 0S1 S 01 开始符为S例2 文法G VN VT P S VN 标识符 字母 数字 VT a b c x y z 0 1 9 P a z 0 9 S 2 文法的简化表示法 简化 通常不用将文法的四元组表示出来 只写出产生式约定 第一条产生式的左部是开始符号或用G S 表示S是开始符号用大写字母 或用尖括号括起来 表示非终结符用小写字母表示终结符左部相同的产生式A A 可以记为A 其中 是 或 的意思 分别称为侯选式 例如 文法G S S A SA SDA a b zD 0 1 9 3 推导 Derivation 与归约 Reduction 直接推导和直接归约 是文法G的产生式 若有v w满足 v w 其中 V 则称v直接推导到w 也称w直接归约到v 记作v w直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程 例文法G S 0S1 S 01有直接推导 0S1 00S11 S 0S1 00S11 000S111 S 0S1 000S111 00001111 S 01 S 0S1 S 0S1 推导和归约若存在v w0 w1 wn w n 0 则称v推导出w 或w归约到v 记为v w若有v w 或v w 则记作v w 例文法G S 0S1 S 01S 0S1 00S11 000S111 00001111S 00001111S 00001111S S 规范推导如果在推导的任何一步 都是对 中的最左 最右 非终结符进行替换 则称这种推导为最左 最右 推导最右推导被称为规范推导 例如 句子 我是大学生 的推导过程如下 句子 主语 谓语 代词 谓语 我 谓语 我 动词 直接宾语 我是 直接宾语 我是 名词 我是大学生 例文法G E E T TT T F FF E i i i i 的推导过程如下 最左推导 E E T T T F T i T i T F i F F i i F i i i最右推导 E E T E T F E T i E F i E i i T i i F i i i i i 4 句型 句子 语言的定义 句型和句子设有文法G S 若符号串x是从开始符推导出来的 即S x 则称x是文法G的句型若x仅由终结符组成 即S x 且x VT 则称x是文法G的句子由规范推导所得的句型称为规范句型例文法G S S 0S1 S 01S 0S1 00S11 000S111 00001111S 0S1 00S11 000S111 00001111都是G的句型00001111是G的句子 提问 以下哪个符号串是文法的句子 语言的定义由文法G生成的语言记为L G 它是文法G的一切句子的集合 即L G x S x 其中S为文法的开始符号 且x VT 例文法G S 0S1 S 01S 0S1 00S11 03S13 0n 1S1n 1 0n1nL G 0n1n n 1 根据文法 可以通过推导得到该文法相应的语言 例 G E E E T TT T F FF E aE E T T T F T a T a T F a F F a a F a a a表示一切能用符号a 和 构成的算术表达式有了语言的要求 也可以为该语言设计文法例 若语言由0 1符号串组成 串中0和1的个数相同 构造其文法为 A 0B 1CB 1 1A 0BBC 0 0A 1CC 提问根据文法 可以通过推导得到该文法相应的语言 S S a a有了语言的要求 也可以为该语言设计文法L G a a a a 5 文法的等价 若L G1 L G2 则称文法G1和G2是等价的 例如文法G1 A A 0RA 01R A1G2 S S 0S1S 01所定义的语言都是0n1n两文法等价 2 4文法的类型 通过对产生式施加不同的限制 NoamChomsky将文法分为四种类型 0型文法 短语文法 对任一产生式 都有 VN VT 且至少含有一个非终结符 VN VT 1型文法 上下文有关 它是0型文法的特例 设文法G VN VT P S 对P中的任一产生式 都有 仅仅S 除外例文法G S S aSBAAA ABBA BA S abBbA bbBA AA 1型文法产生式的一般形式是 A V A VN V 它表示当A的上文为 且下文为 时可把A替换成 因此称1型文法为上下文有关文法 2型文法 上下文无关文法 它是1型文法的特例 对任一产生式 都有 VN VN VT 例文法G S S ABA BS 0B SA 12型文法产生式的一般形式是 A 它表示不管A的上下文如何即可把A替换成 因此被称为上下文无关文法 产生式A 称为 规则通常程序设计语言的文法 可用2型文法来描述 因此我们重点研究2型文法 3型文法 正规文法 它是2型文法的特例 任一产生式 的形式都为A aB或A a 其中A B VN a VT例如文法G S S 0A 1B 0A 0A 1B 0SB 1B 1 0在程序设计语言中 3型文法通常用来描述单词的结构 四种文法之间的逐级 包含 关系 2 5上下文无关文法及其语法树 1 上下文无关文法 Context FreeGrammar 上下文无关文法有足够的能力描述现今程序设计语言的语法结构例 算术表达式 E i E E E E E i E ifthen ifthenelse所以我们只关心上下文无关文法形成的语言的句子的分析和分析方法 2 语法树 推导树ParseTree 作用 直观地描述上下文无关文法的句型推导过程 给定文法G VN VT P S 对于G的任何句型都能构造与之关联的语法树 例 文法G E E T TT T F FF E i句型T T F的推导过程与语法树 E E T E E T E T F T T F T T T T F 从语法树中看不出句型中的符号被替代的顺序 从左到右读出叶子结点得到的符号串 为文法的句型 也把该语法树称为该句型的语法树 语法树定义 给定文法G VN VT P S 若一棵树满足下列4个条件 则称此树为G的语法树 每个结点都有一个标记 此标记是V的一个符号根的标记是S若一结点n至少有一个它自己除外的子孙 并且有标记A 则肯定A VN如果结点n有标记A 其直接子孙结点从左到右的次序是n1 n2 nk 其标记分别为A1 A2 Ak 那么A A1A2 Ak一定是P中的一个产生式 语法树和推导的关系句型的每个推导都产生相应的一棵语法树一个句型的不同推导产生相同的语法树每棵语法树对应唯一的最左推导或最右推导通常 一个句型有唯一的语法树 最左推导和最右推导 它们代表了句型的语法结构 但是一个句型可以有多个不同的推导 它不能代表句型的语法结构 3 文法的二义性 Ambiguity 通常 一个句型对应一棵语法树 它表示该句型的不同推导过程 句型 T T F 对应的语法树 文法G E E E E E E i句子i i i对应的语法树 两个不同的最左推导 推导1 E E E E E E i E E i i E i i i推导2 E E E i E i E E i i E i i i 二义性 如果一个文法存在某个句子对应两棵不同的语法树 则说这个文法是二义的二义性文法存在某个句子 它有两个不同的最左 右 推导对于一个程序设计语言来说 希望它的文法是无二义的 因为希望对它的每个语句的分析是唯一的 构造无二义性文法 文法G E E E E E E i 文法G E T E TT F T FF E i 句子i i i对应的语法树 2 6句型的分析 任务 句型分析就是识别一个符号串是否为某文法的句型 是某个推导的构造过程 对于程序设计语言来说 句型分析就是一个识别输入符号串是否为语法上正确的程序的过程 从左到右的分析算法 即总是从左到右地识别输入符号串 句型分析算法采用从左到右的分析算法句型的分析算法分类自上而下分析法 Top Downparsing 自下而上分析法 Bottom Upparsing 2 6 1自上而下的分析方法 定义 从文法的开始符号出发 反复使用文法的产生式 寻找与输入符号串匹配的推导 语法树的构造 将文法的开始符号作为语法树的根 向下逐步建立语法树 使语法树的末端结点符号串正好是输入符号串 例文法G S cAdA abA a识别输入串w cabd是否为该文法的句子 S 推导过程 cabd S cAd 自上而下方法的主要问题对输入串cabd自上而下构造语法树的另一过程 不成功 不成功的原因是选错产生式A a 自上而下分析的主要问题是选择产生式 假定要被代换的最左非终结符号是B 且有n条规则 B A1 A2 An 那么如何确定用哪个右部去替代B S 2 6 2自下而上的分析方法 定义 从输入符号串开始 利用文法的产生式逐步进行归约 试图归约到文法的开始符号 语法树的构造 从输入符号串开始 以它作为语法树的末端结点符号串 自底向上的构造语法树 使文法开始符正好是该语法树的根 如果最终根结点是开始符 则输入符号串是语言的一个句子 否则不是 例文法G S cAdA abA a识别输入串w cabd是否为该文法的句子 归约过程 用 表示归约 下划线部分为被归约符号 cabd cAd S 自下而上分析的主要问题对输入串cabd的两种归约过程 1 cabd cAd S归约到开始符 2 cabd cAbd不能归约到开始符在自下而上的分析方法中 每一步都是从当前串中选择一个子串加以归约 该子串暂称 可归约串 如何确定 可归约串 是自下而上分析的主要问题 不同的确定 可归约串 的方法 形成了不同的自下而上分析方法在一种 规范归约 方法中 可归约串 被称为 句柄 短语 直接短语和句柄定义 设 是文法G S 中的一个句型 如果有S A 且A 则称 是句型 相对于非终结符A的短语 特别的如有A 则称 是句型 相对于规则A 的直接短语 一个句型的最左直接短语称为该句型的句柄 Handle 对定义的分析 在短语的定义中包括了三个条件 是文法的一个句型 S A A 这三个条件都必须满足 1 2 说明 A 都必须是句型 2 3 说明 将 中的 归约称A后 得到的 A