第三章文法和语言介绍.ppt

3型文法?2型文法?1型文法?0型文法 上面分析得出四种文法间的关系: 3型文法必是2型文法，2型文法必是1型文法，1型文法必是0型文法。即： 文法的递归性：说A是直接左递归的，其 规则式为：A→ A… 说A是直接右递归的，其规则式为： A→ … A 若有推导式：A ?+ A…，说A是左递归的 若有推导式：A ?+ …A，说A是右递归的 文法的递归性 表达式 项 因子 §3.4 语法树与句型的分析 1.语法树 语法树：按推导过程，画出一棵树型结构称为语 法树。 语法树：设G=（VN ，VT，P，S）是给定文法，则满足下面条件的树称为G的一棵语法树，也叫推导树。 ⑴每个结点都有标记，该标记是G中的某一终极符 或非终极符。 ⑵树根的标记是文法的开始符S。 ⑶若结点的标记为A，并且它至少有一个从它出来的分枝，则A一定是非终极符。 子树：由某一结点及其所有分枝组成的部分称为原树的一棵子树。 简单子树：只有单层分枝的子树称为简单子树。 ⑷如果标记为A的结点有n个从它出来的分枝，并且这些分枝结点的标记从左至右分别为A1，A 2，… An，则A→A1，A 2，… An一定是G的一个文法规则式。 规范推导：设xUy ? xuy 是一个直接推导。如果y是终极符串或空，即U是句型xUy中的最右非终极符，则称这种推导为规范直接推导。记为： xUy ?r右 xuy （XUy ?r右 Xuy ） 若推导x ?+ y中的每步都是规范直接推导， 则称该推导为规范推导。 并记为x ? +r右 y，也称为最右推导。 短语：设G为给定文法，S是开始符，W= xuy是一个句型，如果满足下面两个条件： ① S ?*xUy ② U?+u 则称句型xuy中的子串u为句型xuy相对于非终极符U的短语。 直接短语（简单短语）：如果满足条件 ① S ?* xUy ② U ? u 则称u为句型xuy的直接短语（简单短语）。 第二个条件表示有文法规则式U?u存在。 句柄：一个句型多个简单短语中最左边的直接短语称为该句型的句柄。 2、句型的分析 自上而下的分析 从根符号开始的对句型构造的语法树的方法是从上向下分析的方法。 自下而上的分析 从输入串开始，逐步进行“归约”，直至归到文法的开始符号。或者说，从语法树的末端开始，步步向上“归约”直到根部。 3、文法的二义性 二义性：如果文法G的一个句子有两棵以上语法树，则称该句子有二义性。 例如，对于例3．6的文法G,句型 i*i+i 就有两个不同的最左推导，它们所对应的语法树分别如图3．2和图3．3所示。 有害规则：指形如U→U的产生式，该种产生式对描述语言是没有必要的，只会引起文法的二义性 多余规则：指文法中连一个句子的推导都用不到的规则，分为不可达到和不可终止两种情况 有关文法的说明: 重新审视例: if i=5 then x=y 词法分析器 （3，‘if’） （1，指向I的符号表入口） （4，‘=’） （2，‘5’） （3，‘then’） （1，指向x的符号表入口） （4，‘=’） （1，指向y的符号表入口） 1）结果用二元式表示 2）二元式形式是： （单词种别，单词自身的值） 3）定义单词种别为： 1：标识符 2：常数 3：保留字 4：运算符 5：界符 词法例子的结论 单词归根结底是一个符号串 这些符号处在一个基本符号集中 基本符号集是一非空有穷集合 单词符号是基本符号按一定规则构成的基本符号串，是定义在基本符号集上的 标识符 单词 表达式 语句 语言 标识符 的文法 单词的 文法 表达式 的文法 语句的 文法 语言的 文法 形式文法 文法规律 集合 集合的 描述规 则 结论 集合中的各元素归根结底都是符号串 这些符号处在一个基本符号集中 基本符号集是一非空有穷集合 集合中的任一元素都是基本符号按一定规则构成的基本符号串，是定义在基本符号集上的 词法、语法分析问题实际是判断所给符号串是否是集合中的元素的问题 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 第三章?文法和语言 —文法的目的在于描述程序设计语言 本章主要内容： 3.1 形式语言简介 3.2 文法及语言的形式定义 3.3 文法的类型 3.4 语法树与句型的分析 几个基本定义： 语言 语法 语义 文法 字母表 符号 符号串