非递归预测分析器1.doc

预测分析法 1．实验目的与任务 设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。 2．实验要求 建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。 3．实验内容 （1）文法描述及其LL(1)分析表 表达式语言（XL）’ 8 term → factor term’ prgm’ → prgm 9 term’ → *factor term’ prgm’ →ε 10 term’ →ε expr → term expr’ 11 factor → (expr) expr →ε 12 factor → num expr’ → +term expr’ 13 system_goal → prgm expr’ →ε 该LL(1)文法的LL(1)分析表如下： T N Num + * ( ) ; # prgm 1 1 1 prgm’ 2 2 2 3 expr 4 4 5 5 expr’ 6 7 7 term 8 8 term’ 10 9 10 10 factor 12 11 system_goal 13 13 13 对文法中每个文法符号指定一个常数值，符号编码表如下： 文法符号 常数值 备注 （ Num + ) ; * # 4 6 2 5 1 3 0 终结符 （#为输入结束标志） Expr expr’ term term’ factor prgm prgm’ system_goal 258 260 259 262 261 256 257 263 非终结符 （2）文法及其LL(1)分析表的数据结构 文法的产生式可用数组Yy_pushtab[]存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d[]存放。第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0（表示接受），1（表示产生式号），-1（表示语法错）。 数组Yy_d[]的具体内容及表示如下： 0 1 2 3 4 5 6 # ； + * （ ） Num -1 0 -1 -1 0 -1 0 2 1 -1 -1 1 -1 1 -1 4 -1 -1 3 4 3 -1 -1 -1 -1 7 -1 7 -1 6 5 -1 -1 6 -1 -1 -1 -1 -1 10 -1 11 -1 9 9 8 -1 9 -1 -1 12 -1 -1 12 -1 12 prgm 256 prgm’ 257 expr 258 term 259 expr’ 260 factor 261 term’ 262 system_goal 263 数组Yy_pushtab[]的具体内容及表示如下： （3）预测分析器总控程序结构 预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈（元素类型为int）’ ; expr prgm’ ; expr’ term prgm’ ; expr’ term’ factor prgm’ ; expr’ term’ Num prgm’ ; expr’ term’ prgm’ ; expr’ prgm’ ; expr’ term + prgm’ ; expr’ term prgm’ ; expr’ term’ factor prgm’ ; expr’ term’ Num prgm’ ; expr’ term’ prgm’ ; expr’ prgm’ ; prgm’ 263 256 257 1 258 257 1 260 259 257 1 260 262 261 257 1 260 262 6 257 1 260 262 257 1 260 257 1 260 259 2 257 1 260 259 257 1 260 262 261 257 1 260 262 6 257 1 260 262 257 1