资源描述：
《《编译原理》实验二.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验二预测分析法设计与实现实验时间：2013.5.7，5.21，6.4实验目的设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。实验内容（1）文法描述及其LL(1)分析表表达式语言（XL）的语法规则如下：1．程序→表达式；2．
2、表达式；程序prgm→expr;prgm’prgm’→prgmprgm’→ε3．表达式→表达式+项4．
3、项ex
4、pr→termexpr’expr’→+termexpr’expr’→ε5．项→项*因式6．
5、因式term→factorterm’term’→*factorterm’term’→ε7．因式→num_or_id8．
6、(表达式)factor→(expr)factor→num将该语言的文法转换为如下的LL(1)文法：1prgm→expr;prgm’7term→factorterm’2prgm’→prgm8term’→*factorterm’3prgm’→ε9term’→ε4expr→termexpr’10factor→(expr)5expr’→+termexpr’11factor→num6expr’
7、→εfirst(prgm)={(,num}first(prgm’)={(,num,ε}first(expr)={(,num}first(expr’)={+,ε}first(term)={(,num}first(term’)={*,ε}first(factor)={(,num}follow(prgm)={#}follow(prgm’)={#}follow(expr)={;,)}follow(expr’)={;,)}follow(term)={+,;,)}follow(term’)={+,;,)}follow(factor)={*,+,;}select(prgm→expr;prgm’)={(,n
8、um}select(prgm’→prgm)={(,num}select(prgm’→ε)={#}select(expr→termexpr’)={(,num}select(expr’→+termexpr’)={+}select(expr’→ε)={;,)}select(term→factorterm’)={(,num}select(term’→*factorterm’)={*}select(term’→ε)={+,;,)}select(factor→(expr))={(}select(factor→num)={num}该LL(1)文法的LL(1)分析表如下：TNNum+*();#prgm11p
9、rgm’223expr44expr’566term77term’9899factor1110对文法中每个文法符号指定一个常数值，符号编码表如下：文法符号常数值备注（Num+);*#4625130终结符（#为输入结束标志）Exprexpr’termterm’factorprgmprgm’258260259262261256257非终结符（2）文法及其LL(1)分析表的数据结构文法的产生式可用数组Yy_pushtab[]存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d[]存放。
10、第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0（表示接受），1（表示产生式号），-1（表示语法错）。数组Yy_pushtab[]的具体内容及表示如下：012345678910Yyp00257,1,258,0prgm’;exprYyp01256,0prgmYyp020Yyp03260,259,0expr’term260,259,2,0expr’term+262,261,2,0term’factor*05,258,4,0)expr(6,0Num0262,261,0term’factorYyp04Yyp05Yyp06Yyp07Yyp08Yyp09Yyp10数组Yy_d[]的具
11、体内容及表示如下：0123456#；+*（）Num-1-1-1-10-102-1-1-11-11-1-1-1-13-13-1-1-1-16-16-154-1-15-1-1-1-1-19-110-1887-18-1prgm256prgm’257expr258term259expr’260factor261term’262（3）预测分析器总控程序结构预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d
