编译原理实验报告(预测分析表方法)

1 预测分析表方法预测分析表方法 一 实验目的一 实验目的 理解预测分析表方法的实现原理 二 实验内容 二 实验内容 编写一通用的预测法分析程序 要求有一定的错误处理能力 出错后能够使程序继续运 行下去 直到分析过程结束 可通过不同的文法 通过数据表现 进行测试 三 实验步骤三 实验步骤 1 算法数据构造 构造终结符数组 char Vt 10 5 id 构造非终结符数组 char Vn 10 构造 follow 集数组 char follow 10 10 可将 follow 集与预测分析表合 并存放 数据构造示例 使用的预测分析表构造方法 1 data1 h简单算术表达式数据 char VN 10 5 E E T T F 非终结符表 intlength vn 5 非终结符的个数 char VT 15 5 id 终结符表 intlength vt 6 终结符的个数 char Fa 15 10 TE TE FT FT E id 产生式表 0 E TE 1 E TE 2 E 空 3 T FT 4 T FT 5 T 空 6 F E 7 F id intanalysis table 10 11 0 1 1 0 2 2 0 0 0 0 0 1 1 1 1 2 2 0 0 0 0 0 3 2 1 3 2 2 0 0 0 0 0 1 5 4 1 5 5 0 0 0 0 0 7 2 2 6 2 2 0 0 0 0 0 预测分析表 1表示出错 2表示该行终结符的follow集合 用于错误处理 正数表示产生式在数组Fa 中的编号 0表示多余的列 1 预测分析表的构造方法 1 给文法的正规式编号 存放在字符数组中 从 0 开始编号 正规式的编号即为该正规 式在数组中对应的下标 如上述 Fa 数组表示存储产生式 构造正规式数组 char P 10 10 E TE E TE 正规式可只存储右 半部分 如 E TE 可存储为 TE 正规式中的符号可替换 如可将 E 改为 M 构造预测分析表 int analyze table 10 10 数组元素值存放正规式的编号 1 表示出错 2 预测分析表的构造方法 2 可使用三维数组 Char analyze table 10 10 10 2 或 Char analyze table 10 10 2 针对预测分析表构造方法 1 的查预测分析表的方法提示 1 查非终结符表得到非终结符的序号 no1 2 查终结符表得到终结符的序号 no2 3 根据 no1 和 no2 查预测分析表得到对应正规式的序号 no3 analyze table no1 no2 如果 no3 1 表示出错 4 根据 no3 查找对应的正规式 Fa no3 5 对正规式进行处理 3 错误处理机制 紧急方式的错误恢复方法 抛弃某些符号 继续向下分析 1 栈顶为非终结符 A 串中当前单词属于 FOLLOW A 则从栈中弹出 A 此 时可认为输入串中缺少 A 表示的结构 继续分析 错误编号为 1 2 栈顶为非终结符 A 串中当前单词不属于 FOLLOW A 则可使串指针下移 一个位置 认为输入串中当前单词多余 继续分析 错误编号为 2 3 栈顶为终结符 且不等于串中当前单词 则从栈中弹出此终结符 认为输入串 中缺少当前单词 或者将串指针下移一个位置 认为串中当前单词多余 在程序中可选择 上述两种 观点中的一种进行处理 错误编号 3 因此 error 函数的编写方式可按如下方式处理 Error int errornum If errornum 1 Else if errornum 2 Else 或者可用 choose case 语句处理 4 增加了错误处理的预测分析程序预测分析程序的算法 将 和文法开始符依次压入栈中 把第一个输入符号读入 a do 把栈顶符号弹出并放入 x 中 if x VT if x a 将下一输入符号读入 a else error 3 else if M x a x y1y2 yk 按逆序依次把 yk yk 1 y1 压入栈中 输出 x y1y2 yk 3 else if a follow x error 1 else error 2 在前述的数据定义中查表为 2 表示 a follow x while x 给定算术表达式文法 编写程序 测试数据 1 算术表达式文法 E TE E TE TE T FT T FT FT FT F E id num 给定一符合该文法的句子 如 id id id 运行预测分析程序 给出分析过程和每一步 的分析结果 输出形式参考下图 为结束符 4 include include include define TT 0 char aa 20 int pp 0 if TT char VN 5 E e T t F 非终结符表 intlength vn 5 非终结符的个数 char VT 10 l m i n 终结符表 l m i id n num intlength vt 10 终结符的个数 char Fa 12 6 Te Te Te NULL Ft Ft nFt mFt NULL E i n 产生式表 0 E Te 1 e Te 2 e Te 3 e 空 char F 12 6 E e e e T t t t t F F F intanalysis table 5 10 2 2 2 2 2 0 1 0 0 1 2 2 2 1 2 2 3 2 2 3 2 2 2 1 1 4 1 4 4 1 5 6 7 8 8 2 8 2 2 8 1 1 1 1 1 9 1 10 11 1 else char VN 4 A Z B Y 非终结符表 intlength vn 4 非终结符的个数 char VT 5 a l d b 终结符表 intlength vt 5 终结符的个数 5 char Fa 6 6 aZ ABl NULL dY bY NULL char F 6 6 A Z B Y intanalysis table 4 5 0 2 1 2 1 1 2 2 2 2 2 1 3 2 2 2 5 2 4 2 endif char stack 50 int top 1 void initscanner 程序初始化 输入并打开源程序文件 int i 0 FILE fp if fp fopen a txt r NULL printf Open error exit 0 char ch fgetc fp while ch EOF aa i ch i ch fgetc fp fclose fp void push char a top stack top a char pop return stack top int includevt char x for int i 0 i length vt i if VT i x return 1 6 return 0 int includean char x char a int i j for i 0 i length vn i if VN i x break for j 0 j 0 int h includean x a printf 展开非终结符 s s n F h Fa h int k for k 0 k 10 k if Fa h k 0 break if k 4 printf pop c n x else while k 0 按逆序依次把 yk yk 1 y1 压入栈中 k push Fa h k else if includean x a 1 flag 1 printf 出错 从栈顶弹出 c n x x pop else flag 1 printf 出错 跳过 c n a pp a aa pp else flag 1 printf 出错 跳过 c n a pp a aa pp 8 while x if flagg 0 printf c t t t c t x a printf 结束 n int main printf 请输入 1 or 0 n scanf d TT printf 语法分析工程如下 n initscanner printf 要分析的语句是 s n aa pri