《编译原理》复习纲要河南工业大学.pptVIP

练习：判断文法是否LL(1)文法，写出原因 SELECT(F→(E))={( } SELECT(E→TE’)={（，i} SELECT(E’→+TE’)={+} SELECT(E’→ε)={),#} SELECT(T→FT’)={ (，i} SELECT(T’→*FT’)={*} SELECT(T’→ε)={+,),#} SELECT(F→i)={i} i + * ( ) # E E’ T T’ F →ε →+TE →TE →TE →ε →ε →ε →ε →FT →FT →*FT →(E) →i 因为上面的分析表中每一项没有冲突，所以，该文法是LL（1）文法。 * X∈VN ‘#’‘S’进栈，当前输入符送a 上托栈顶符号放入X 若产生式为 X?X1X2…Xn按逆序即Xn…X2X1 入栈 出错 X=‘#’ X∈VT X=a M[X,a]是 产生式吗 出错 X=a 读入下一个符号 结束 是 是 是 是 否 否 否 否 否 是 3.LL(1)分析程序的控制程序 初始格局： (#S，输入串#) 终止格局：(#，#) 图中符号说明如下： “#”句子括号即输入串的括号 “S”文法的开始符号 “X”存放当前栈顶符号的工作单元 a存放当前输入符号a的工作单元 1 #E 2 3 T’F 4 E→TE’ T→FT’ i F→i i匹配 5 T’→ε 6 #E’ 7 8 E’T+ E’→+TE’ +匹配 #E’T 9 T’F T→FT’ F→i 10 #E’T’ i匹配 11 i 12 #E’ T’→*FT’ *匹配 13 14 15 16 #E’T’F F→i #E’T’ i匹配 #E’ #E’T’ T’→ε E’→ε 17 # 接受 对输入串i+i*i#进行分析 # E’T i+i*i# i+i*i# i+i*i# i+i*i# +i*i# +i*i# +i*i# i*i# i*i# i*i# *i# * i# i# i# # # # #E’ #E’T’ #E’T’ # #E’ #E’T’ T’F* i →ε →+TE →TE →TE →ε →ε →ε →ε →FT →FT →*FT →(E) →i →ε →+TE →TE →TE →ε →ε →ε →ε →FT →FT →*FT →(E) →i 注意：红色部分为易出错部分 练习 以作业题为主，练习完整的过程 1、能推出ε的非终结符集。 2、求非终结符的FIRST、FOLLOW集。 3、构造分析表。 4、判断是否LL（1）文法。 5、若是LL(1)文法，则写出句子的分析过程。 VN 推出ε? FIRST FOLLOW VN a b … … 步骤 分析栈 剩余输入串 推导所用产生式或匹配 VN 推出ε? FIRST FOLLOW VN 步骤 分析栈 剩余输入串 推导所用产生式或匹配 第六章 算符优先文法 1、会写表达式的逆波兰式 练习：求下述表达式的逆波兰式： (a+b/d)*e , a b d / + e * 注 根据逆波兰式特点： ⑴ 运算对象顺序不变； ⑵ 运算符紧跟运算对象之后。 ※ 可直接写出： 练习以下公式的逆波兰式 a+(b-c)*d+e/f a*b/c↑e*d a+(-b) * FIRSTVT计算如下：P111 ①初值：若有产生式A?a…或A?Ba… 则a?FIRSTVT(A) ②迭代：若a?FIRSTVT(B)且有产生式A?B… 则a?FIRSTVT(A) LASTVT计算如下：P111 ①初值：若有产生式A?…a或A?…aB 则a?LASTVT(A) ②迭代：若a?LASTVT(B)且有产生式A?…B 则a?LASTVT(A) 根据定义直观计算FIRSTVT集、LASTVT集 2. 会构造算符优先分析表 * 例如：求下面文法的每个非终结符的FIRSTVT和LASTVT。 准备工作：增加E’?#E# E’?#E# E?E+T E?T T?T*F T?F F?P?F F?P P?(E) P?i FIRSTVT LASTVT E’ { } { } E { } { } T {