编译原理 第三章 part3（上下文无关文法及其语法树、二义性、自下而上、自上而下、有害规则和多余规则） |
您所在的位置：网站首页 › 所有游戏都有规则吗为什么 › 编译原理 第三章 part3（上下文无关文法及其语法树、二义性、自下而上、自上而下、有害规则和多余规则） |
编译原理 第三章 part3（上下文无关文法及其语法树、二义性、自下而上、自上而下、有害规则和多余规则）
|
上下文无关文法及其语法树，句型分析，有害规则和多余规则 文章目录 （1）上下文无关文法1.例子：（2）规范推导和规范句型1.定义：2.注意：3.例子：（一定要再写一次）（3）语法树1.作用：2.例子：3.定义：（应该没用，看一下就好了）(4)文法的二义性1.定义：2.例子:3.例子2（二义性文法变成无二义文法）4.注意：（5）句型的分析（概括）1.定义：2.分类：（看看就好）（6）自上而下的分析方法1.定义：2.例子：（感觉会考）3.自上而下方法的主要问题 : （是选择产生式）（7）自下而上的分析方法1.定义：2.例子：3.自下而上分析的主要问题：（是确定“可归约串”）（8）有害规则和多余规则1.有害规则定义： U->U，无用，且引起文法的二义2.多余规则定义： 所有句子推导都用不到的规则 不可到达：不在任何产生式的右部出现的非终结符 不可终止：不可推导出终结符号串的非终结符3.例子：（重要）4.ε规则 （1）上下文无关文法 1.例子：
如果在推导的任何以部α⇒β，其中α、β是句型，都是对α中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导 2.注意：①最右推导称为规范推导 ②由规范推导所得的句型称为规范句型 3.例子：（一定要再写一次）
直观地描述上下文无关文法的句型推导过程。
如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。二义性文法存在某个句子，它有两个不同的最左（右）推导。 对于一个程序设计语言来说，希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。 2.例子:
如果同一文法，推导过程不同，但结果是两棵相同的语法树，也是无二义的 识别输入符号串是否为语法上正确的程序的过程。（判断是否符合文法） 2.分类：（看看就好）
从文法的开始符号出发，反复使用文法的产生式，寻找与符号串匹配的推导。 语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。 2.例子：（感觉会考）
从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 语法树的构造：从输入符号串开始，以它作为语法树的末端结点符号串，自底向上地构造语法树 2.例子：
表现形式： 不可到达：不在任何产生式的右部出现的非终结符 不可终止：不可推导出终结符号串的非终结符 3.例子：（重要）
定义：上下文无关文法中允许使用A->ε产生式，A->ε称为ε规则 |
从上图中例子得出： ①最左推导是把产生式右部最左边的非终结符推导换掉。 ②最右推导是把产生式右部最右边的非终结符推导换掉。
(推导过程不同，但结果等价)
其中(2)也是不可终止【本文地址】
今日新闻 |
推荐新闻 |