第06讲-语法分析-I详解.pptx

第三章 语法分析 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 1 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 其余部分 分析器 中间表示 符号表 2 语法分析：词法记号（token）流-〉语法短语（分析树） initial + rate * 60 优秀的大工学子 id + id * num 形容词 名词 非终结符 终结符 语法分析的任务 3 字符 字符串 记号 词法分析器（正规式） 表达式 语句 程序块 程序 语法分析器 语法分析树 （上下文无关文法） 语法分析 目标 线性的词法记号流 = 语法树 实质：无结构的数据转换为有结构的数据 依据 上下文无关语法（描述语法规则） 4 本讲纲要 语法分析概述 上下文无关文法 语言和文法 5 上下文无关文法 主要内容 6 定义 文法推导 二义性 给出上下文无关文法的概念定义 3.1 上下文无关文法 3.1.1 上下文无关文法的定义 正规式来定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复。 例：a (ba)5, a (ba)* 正规式不能用于描述配对或嵌套的结构 例：配对括号串的集合， {wcw | w是a和b的串} 7 3.1 上下文无关文法 3.1.1 上下文无关文法的定义 上下文无关文法是四元组（VT , VN , S, P） VT : 终结符集合(非空有限集合，记号名是其同义词) VN : 非终结符集合（非空有限集合, ） S : 开始符号 P : 产生式集合，产生式形式 : A ? ? 8 3.1 上下文无关文法 例 ( {id, +, *, ?, (, )}, {expr, op}, expr, P ) expr ? expr op expr expr ? (expr) expr ? ? expr expr ? id op ? + op ? * 9 同一个符号可以在多个产生式中出现 每个产生式之间没有强制的顺序关系， 这与正规式不同 终结符 3.1 上下文无关文法 简化表示方法 10 以下符号通常 表示终结符 1)字母表中前面的小写字母，如a,b,c 2)黑体串,如id或while 3)数字 0,1,…,9 4)标点符号，如括号，逗号等 5)运算符号，如+,-等 以下符号通常 表示非终结符 1)字母表中前面的大写字母，如A,B,C 2)字母S, 通常它表示开始符号 3)小写字母的名字，如expr和stmt 另外， 1)字母表中后面的大写字母，如X,Y等，表示非终结符或终结符 2)字母表中后面的小写字母，如u,v,..z,代表终结符串 3)小写希腊字母，代表文法的符号串 4)如果 A—a1，A—a2，记为 A—a1|a2 3.1 上下文无关文法 例 ( {id, +, *, ?, (, )}, {expr, op}, expr, P ) expr ? expr op expr expr? (expr) expr ? ? expr expr ? id op ? + op ? * 简化表示 E ? E A E | (E ) | ?E | id A ? + | * 11 3.1 上下文无关文法 上下文无关文法 E ? E A E | (E ) | ?E | id A ? + | * 12 正规式定义 letter ?[A-Za-z] digit ?[0-9] id ?letter(letter|digit)* 上下文无关文法与正规式比较 上下文无关文法 主要内容 13 推导：是从文法推出文法所描述的语言中 所包含的合法串集合的动作 3.1.2 推导 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。 例 E ? E + E | E * E | (E ) | ? E | id E ? ?E ? ?(E) ? ?(E + E) ? ?(id + E)? ?(id + id) 记号：S ?*?、 S ?+ w 概念：句型、句子、上下文无关语言、等价的文法 14 从开始符号E开始 符合语法的句子 推导的定义 直接推导“?” A→ ? 是文法G的产生式： ? A? ?? ?? 例：G： S→0S1， S→01 0S1 ?00S11 00S11 ?000S111 000S111 S ?0S1 15 等价的文法 (1) G：S→aAb A→ab A→aAb A→ε (2) G[S]： A→ab A→aAb