第五章作业10.ppt

1文法G S S a T T T S S 2 给出 a a a 和 a a a a 的最左推导 S T T S S S a S a T a T S a S S a a S a a a S T T S S S T S T S S T S S S S S S S T S S S T S S S S S S S S S a S S S S a a S S S a a S S a a T S a a S S a a a S a a a a 2 对文法G进行改写 然后对每个非终结符写出不带回溯的递归子程序 文法中含有左递归 一定不是LL 1 文法 不能应用递归子程序法 所以a 消除左递归 改写后的文法是 S a T T ST T ST b 判断文法是否为LL 1 文法S aS S T T ST T ST T LL 1 文法的充分必要条件是 对每个非终结符A的任意两个产生式 A A 满足select A select A LL 1 文法的判别 1求出能推出 非终结符 T S aS S T T ST T ST T 3计算FOLLOW集 a a 2计算FIRST集 由S T 得Follow T 由T ST 得由于T 能推出 所以Follow S First T Follow T 由T ST 得Follow T Follow T select S a 和select S 和select S T 两两不相交Select T ST select T 因为具有相同左部的产生式的SELECT集两两交集为空 所以此文法是LL 1 文法 4计算SELECT集 SELECT S a a SELECT S SELECT S T SELECT T ST First ST a SELECT T ST SELECT T Follow T 用到的一些子过程 过程GETNEXT负责读入下一个TOKEN字过程ERROR负责报告语法错误约定 全局变量TOKEN存放已读入的TOKEN字过程进入时变量TOKEN存放了一个待匹配的TOKEN字退出过程时 变量TOKEN中仍存放着一个待匹配的TOKEN字 c 对每个非终结符写出不带回溯的递归子程序 递归子程序的写法 若关于一个非终结符的产生式只有一条 直接按产生式右部写程序 右部是终结符就进行匹配 是非终结符就调用相应的子程序 如T ST 若关于一个非终结符的产生式不只一条 按select集合写成if条件语句 如 S a S S T SELECT S a a SELECT S SELECT S T 若产生式右部为空串可以不生成任何语句 或者按select集合 生成一条判断语句如 SELECT T 生成 ifToken thenError procedureS S a T 对应的程序 beginIfTOKEN a thenGETNEXT TOKEN elseifTOKEN thenGETNEXT TOKEN elseifTOKEN thenbeginGETNEXT TOKEN T ifTOKEN thenGETNEXT TOKEN elseERROR endelseERROR end IfToken thenERROR 错误 没有被读掉 变量Token S后续的过程处理的第一个字为 导致出错 procedureT T ST 对应的程序 beginifTOKEN thenbeginGETNEXT TOKEN 容易出错 S T endelseifTOKEN thenERROR end 可以不写 但写成elseERROR 是错误的也可以写成 elseifTOKEN thenreturnelseERROR 但是不能写成elseifTOKEN thenGetNext Token elseERROR procedureT T ST 对应的程序 beginS T end 3 经改写后的文法是否是LL 1 的 给出它的预测分析表 已求得产生式的SELECT集 SELECT S a a SELECT S SELECT