语法分析(1)PPT课件.ppt

1 编译原理第4讲语法分析 1 贾西平Email jiaxp 2 内容提纲 基本概念形式语言分类正规表达式与上下文无关文法 3 内容提纲 基本概念形式语言分类正规表达式与上下文无关文法 4 基本概念 1 字母表 元素的有穷非空集合 2 字符 或符号 字母表中的每个元素 不同的语言可以有不同的字母表 例如英文的字母表中26个字母 数字及标点符号等 PASCAL语言的字母表是由字母 数字 若干专用符号组成 字母表也称为符号集 5 基本概念 续 3 字符串 或字 字母表中的字符组成的任何有穷序列 例如001110是字母表 0 1 上的符号串 字母表A a b c 上的一些符号串有 a b c ab aaca等 在字符串中 字符的顺序是很重要的 字符串ab就不同于ba abca和aabc也不同 字符串STR表示 由字符S T和R 并按此顺序组成 6 语言 语言 对字母表 来说 上的任意一个子集都称为 上的一个语言 记为L L 句子 语言L的每一个字符串称为该语言的一个语句或句子 例 字母表 0 1 上的语言 0 1 00 11 0 1 00 11 0 1 00 11 01 10 00 11 01 10 7 文法 文法 描述语言的语法结构的形式规则 文法被用来精确而无歧义地描述语言句子的构成方式 文法描述语言的时候不考虑语言的含义 8 文法的形式定义 文法通常表示成四元组G VT VN S 其中 1 VT为终结符号集 是一个非空有限集 它的每个元素称为终结符号 2 VN为非终结符集 也是一个非空有限集 其每个元素称为非终结符号 且有VT VN 3 S为一文法开始符 是一个特殊的非终结符号 即S VN 4 是产生式的非空有限集 9 文法的形式定义 终结符号 组成该语言的最基本的符号 不可再分 如保留字 标识符等 非终结符号 表示一些语法成分 可以推导出其他的语法成分 表示一定符号串的集合 是一个类 如表达式 开始符号 规则中的一个特殊的非终结符号 语言中的句子都从它开始推导 如程序 句子产生式 定义语法成分的规则 10 产生式 产生式 也称产生规则或规则 是定义语法实体的一种书写规则 每个产生式是一序偶 通常写作 或 读作 是 或 定义为 为产生式的左部 为右部 是由终结符和非终结符组成的符号串 VT VN 且至少有一个非终结符 VT VN 11 产生式的书写 可将有相同左部的产生式合并为一个例 P 1P 2P n可缩写成P 1 2 n每个 i i 1 2 n 称为P的一个候选式直竖 读为 或 与 一样是用来描述文法的元语言符号 即不属于 的字符 12 例 构造产生标识符的文法 解 标识符是以字母开头的字母数字串 用L表示 字母 类非终结符 用D表示 数字 类非终结符 而用T表示 字母或数字 类非终结符 则有 L a b zD 0 1 9T L D如果用S表示 字母数字串 类 则T是一字母或数字 ST也是字母数字串 即有S T ST产生式S T ST是一种左递归形式 由它可以产生一串T 13 例 构造产生标识符的文法 续 作为 标识符 的非终结符I 它或者是一单个字母 或者为一字母后跟字母数字串 即I L LS因此 产生标识符的文法G I 为 G a b z 0 9 I S T L D I I L LSS T STT L DL a b zD 0 1 9 14 例3 2 写一文法 使其语言是奇数集合 但不允许出现以0打头的奇数 解 根据题意 可以将奇数划分为如图所示的三个部分 最高位允许出现1 9 用非终结符B表示 中间部分可以出现任意多位数字0 9 每一位用非终结符D表示 最低位只允许出现1 3 5 7 9等奇数 用A表示 15 例3 2 由于中间部分可出现任意位 所以另引入了一个非终结符M 它包括最高位和中间位部分 假定开始符为N 则可得到文法G N 为 G 0 1 9 N A M B D N N A MA 一位数字 多位数字 M B MD 仅两位数字 无中间位 多于两位数字 A 1 3 5 7 9B 1 2 3 4 5 6 7 8 9D 0 B 16 推导 直接推导 又称一步推导 用符号 表示 就是用某条规则的右部去替换该规则的左部推导 连续使用直接推导 得到的连续序列称为一个推导 17 直接推导 设文法G VT VN S 且 VT VN 如果存在产生式A VT VN 则称 A 可直接推出 即 A 表示直接推导出 是应用产生规则进行推导的记号 与 不同 是产生式中的定义记号直接推导是对文法符号串 A 中的非终结符A用相应的产生式A 的右部 来替换 从而得到 18 通常 用表示 从 1出发 经过一步或若干步 可以推出 n 用表示 从 1出发 经过0步或若干步 可以推出 n 所以 即或 推导符号 19 表达式推导 例如 对下面的文法G E E E E E E E i 3 1 唯一的非终结符E可以看成是代表一类算术表达式 可以从E出发进行一系列的推导 如表达式i i i的推导如下 E E E E E E E E i E i i i i i 注意 每步推导 只能将某个产生式的左部用其右部替换 20 例 G i E E P 1 1 P E E E E E E i表达式 i 和 i i i的推导 E E i E E E E E E E E i E E i i E i i i EE0步推导E i i i6步推导E i i i6步推导E E 直接推导 表达式推导 21 句型 设 s 是一文法 如果符号串x是从开始符号推导出来的 即有s x 则称x是文法G s 的一个句型 即 任何由开始符 推导出来的符号串都是句型 句子 若x仅由终结符号组成 则称x为G S 的句子 练习 文法G S aAcB BdA AaB cB bScA b写出句型aAcbBdcc和句子acabcbbdcc的推导过程 22 文法G产生的语言 定义 文法G S 所产生的所有句子构成的集合 记为L G L G S 其中S为文法的开始符号 Vt 23 文法G产生的语言 例考虑文法G1 它定义了什么语言 S bAA aA a 推导过程 S bA baS bA baA baa S bA baA ba a 归纳得 L G1 ban n 1 24 文法G产生的语言 练习 文法 S a b c A B S S P S Ac aBA abB bc写出 G 的全部元素 答案 L G abc 25 文法G产生的语言 例 考虑文法G2 它定义的语言是 S ABA aA aB bB b L G2 ambn m n 1 26 内容提纲 基本概念形式语言分类正规表达式与上下文无关文法 27 形式语言分类 Chomsky把文法分成四种类型 0 1 2 3型与上下文无关文法一样 它们都由四部分组成 但对产生式的限制有所不同 28 0型文法 如果文法G的每一个产生式具有下列形式 其中 V VNV 注 V VN VT 即至少含有一个非终结符 V 则称文法G为0型文法或短语文法 记为PSG 0型文法相应的语言称为0型语言或称递归可枚举集它的识别系统是图灵 Turing 机 29 1型文法 文法G的每一个产生式 均在0型文法的基础上增加了字符长度上满足限制条件 则称文法G为1型文法或上下文有关文法 记为CSG 1型文法相应的语言称为1型语言或上下文有关语言 它的识别系统是线性界限自动机 1型文法的另一种定义方法 文法G的每一个产生式具有下列形式 A 其中 V A VN V A必须在 的上下文环境中才能被 所替换 30 2型文法 文法G的每一个产生式具有下列形式 A 其中 A VN V 则称文法G为2型文法或上下文无关文法 记为CFG 2型文法相应的语言称为2型语言或上下文无关语言 它的识别系统是下推自动机 31 3型文法 文法G的每个产生式具有下列形式 A a或A aB其中 A B VN a VT 则文法G称为3型文法 正规文法或右线性文法 记为RG3型文法相应的语言为3型语言或正规语言 它的识别系统是有限自动机 3型文法还可以呈左线性形式 A a或A Ba 32 四类文法的关系与区别 从0型文法到3型文法逐渐增加限制1 3型文法都属于0型文法2 3型文法均属于1型文法3型文法属于2型文法 四类文法的区别如下 1 1型文法中不允许有形如 A 的产生式存在 而2 3型文法允许 2 0 1型文法的产生式左部含有终结符或两个以上的非终结符 而2型和3型文法的产生式左部只允许是单个的非终结符号 33 语言的层次 这四种语言可被4种自动机识别 0型 图灵机1型 线性界限自动机2型 下推自动机3型 有限自动机 从外到内 四种文法对产生式的限制越来越多 语言的描述能力越来越弱 34 例3 3 试判断下列产生式集所对应的文法类型和产生的语言 1 S ACaB 2 S aSBC 3 S Ac 4 S aS Ca aaC S aBC S Sc S aA CB DB CB DB A ab A bA CB E DB DC A aAb A bB aD Da DC BC B cB AD AC aB ab B c aE Ea bB bb AE bC bc cC cc 35 解 由四类文法的定义与区别可知 1 4分别为0 3型文法 1 该0型文法产生的0型语言为L0 G a2n n 0 例如 当n 2时 句子a2 2 aaaa 36 2 该1型文法产生的1型语言为L1 G anbncn n 1 例如 当n 2时 句子a2b2c2 aabbcc是通过下列推导得到的 37 3 该2型文法产生的2型语言为L2 G anbncm m n 1 例如当n 2 m 3时 句子a2b2c3 aabbccc是通过下列推导得到的 38 4 该3型文法产生的3型语言为L3 G ambnck m n k 1 例如当m 2 n 3 k 4时 句子a2b3c4 aabbbcccc是通过下列推导得到的 39 几点说明 由例3 3可知 anbncn n 1 anbncm m n 1 ambnck m n k 1 对文法规则定义形式的限制虽然加强了 但相应的语言反而更大了不能主观认定文法限制越大则语言越小下述结论是不成立的 3型语言 2型语言 1型语言 0型语言 40 几点说明 在编译方法中 常用3型文法描述高级程序语言的词法部分 然后用有限自动机FA来识别高级语言的单词 用2型文法描述高级语言的语法部分 然后用下推自动机PDA来识别高级语言的各种语法成分 41 图3 2例3 4的DFA 解 为了构造字母表 a b 上同时只有奇数个a和奇数个b的所有字符串的正规表达式 画出如图3 2所示的DFA 即由开始符S出发 经过奇数个a到达状态A 或经过奇数个b到达状态B 再由状态A出发 经过奇数个b到达状态C 终态 同样 由状态B出发 经过奇数个a到达终态C 例3 4给出字母表 a b 上的同时只有奇数个a和奇数个b的所有字符串集合的正规文法 42 例3 4 由图3 2可直接得到正规文法G S 如下 G S S aA bBA aS bC bB bS aC aC bA aB 43 内容提纲 基本概念形式语言分类正规表达式与上下文无关文法 44 正规表达式与上下文无关文法 正规表达式所描述的语言结构均可以用上下文无关文法描述 反之则不一定 由正规表达式构造上下文无关文法的一种方法如下 1 构造正规表达式的NFA 2 若0为初始状态 则A0为开始符号 3 如果存在映射关系f i a j 则定义产生式Ai aAj 4 如果存在映射关系f i j 则定义产生式Ai Aj 5 若i为终态 则定义产生式Ai 45 例3 5 用上下文无关文法描述正规表达式 a b abb 解 首先构造识别正规表达式 a b abb的NFAM如图由构造上下文无关文法的方法得到上下文无关文法G