三章语法分析.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 在FRIST(T?)中，+, )和$在FOLLOW (T?) 中。 * * * * * * * 例 题 2 设计一个文法:字母表{a, b}上a和b的个数相 等的所有串的集合 二义文法： S ? a S b S | b S a S | ? aabbabab aabbabab S S S S 例 题 2 设计一个文法:字母表{a, b}上a和b的个数相 等的所有串的集合 二义文法： S ? a S b S | b S a S | ? aabbabab aabbabab 二义文法： S ? a B | b A | ? A ? a S | b A A B ? b S | a B B aabbabab aabbabab aabbabab B B B B B B 例 题 2 设计一个文法:字母表{a, b}上a和b的个数相 等的所有串的集合 二义文法： S ? a S b S | b S a S | ? aabbabab aabbabab 二义文法： S ? a B | b A | ? A ? a S | b A A B ? b S | a B B aabbabab aabbabab aabbabab 非二义文法： S ? a B S | b A S | ? A ? a | b A A a abb abab B ? b | a B B a B S 例 题 3 试说明下面文法不是LR(1)的： L ? M L b | a M ? ? M b L L L L a M b M b ? ? ? 句子abbb的分析树 例 题 4 下面的文法不是LR(1)的，对它略做修改，使之成为 一个等价的SLR(1)文法 program ? begin declist ; statement end declist ? d ; declist | d statement ? s ; statement | s 该文法产生的句子的形式是 begin d ; d ; … ; d ; s ; s ; … ; s end 修改后的文法如下： program ? begin declist statement end declist ? d ; declist | d ; statement ? s ; statement | s 例 题 5 一个C语言的文件如下，第四行的if误写成fi： long gcd(p,q) long p,q; { fi (p%q == 0) return q; else return gcd(q, p%q); } 基于LALR（1）方法的一个编译器的报错情况如下： parse error before ‘return’ ( line 5). 是否违反了LR分析的活前缀性质？ 习 题 第一次：3.2, 3.4(b)(c), 3.6(a)(b) 第二次：3.8 第三次：3.15 第四次：3.18(a) 第五次：3.21, 3.23 第六次：3.27, 3.31 * * * * * * * * * * * * * * * * * * * * * * * * * 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例 二义文法 E ? E + E | E ? E | (E) | id 规定： ?优先级高于+，两者都是左结合 LR(0)项目集I7 E ? E + E· E ? E·+ E id + id + id E ? E·? E id