山东理工大学-编译原理内部课件-第三章：短语直接短语句柄.ppt

*1 相关概念 短语 p44 例例 E E E+T E+T E+T*F E+T*F E+T*i E+T*i 句型句型E+T*iE+T*i的短语有的短语有3 3个：个： (1)E+T*i(1)E+T*i是句型是句型E+T*iE+T*i相对于相对于E E的短语的短语 (2)T*i(2)T*i是句型是句型E+T*iE+T*i相对于相对于T T的短语的短语 (3)i(3)i是句型是句型E+T*iE+T*i相对于相对于F F的短语的短语 E =E = 0 0 E E且且 E=E= + + E+T*iE+T*i E =E = * * E+E+T T 且且 T=T= + + T*iT*i E =E = * * E+T*E+T*F F 且且 F=F=i i E E E E E+T*iE+T*i E E E+ E+ T T T*iT*i E E E+T* E+T* F F i i n短语 若=*，且A=+，则称 是句型相对于非终结符号A的短语 不是不是 短语短语 *2 直接短语 句柄 p44 一个句型的直接短语可能一个句型的直接短语可能不唯一不唯一 句型句型E+T*iE+T*i的句柄是：的句柄是：i i E =E = 0 0 E E 且且 E=E= + + E+T*iE+T*i E =E = * * E+T E+T 且且 T=T= + + T*iT*i E =E = * * E+T*F E+T*F 且且 F F=i=i i i是句型是句型E+T*iE+T*i相对于相对于F F的直接短语的直接短语 （句型有（句型有唯一唯一句柄）句柄） n直接短语 若* 且 A ，则称是句型 相对于非终结符号A的直接短语 n n 句柄句柄 一个句型的一个句型的最左直接短语最左直接短语 称为该句型的句柄称为该句型的句柄 *3 利用语法树寻找句型的短语、句柄等 句型句型=E+T*i=E+T*i E E E + TE + T T * FT * F i i n n寻找方法寻找方法 句型句型的语法树有：的语法树有： uun n棵子树棵子树n n个短语个短语 uum m棵直接子树棵直接子树m m个直接短个直接短 语语 uu最左直接子树最左直接子树句柄句柄 3 3个短语个短语 1 1个直接短语个直接短语 i i 句柄句柄 i i E+T*iE+T*i T*i T*i i i 只有父子两代只有父子两代 uun n个内部节点个内部节点n n棵子树棵子树 每颗子树的叶结点从左至右排每颗子树的叶结点从左至右排 列组成一个短语列组成一个短语 *4 利用语法树寻找短语、句柄等方法总结 n n 句型句型 的语法树有若干个内部节点（包括根节点的语法树有若干个内部节点（包括根节点 ）每个内部节点对应一棵以该内部节点为根的子）每个内部节点对应一棵以该内部节点为根的子 树树 n n 如果一棵子树只有父子两代（两层节点），则称如果一棵子树只有父子两代（两层节点），则称 该子树为直接子树该子树为直接子树 n n 如果一棵子树的根标记为如果一棵子树的根标记为A A，且将此子树的叶节，且将此子树的叶节 点点 标记自左至右排列来所形成的符号串为标记自左至右排列来所形成的符号串为 ， 则则 是句型是句型 相对于相对于A A的一个短语的一个短语 n n 如果子树是一棵直接子树，如果子树是一棵直接子树，则则 是句型是句型 相对于相对于 A A的一个直接短语的一个直接短语 n n 最左直接子树对应该句型的句柄最左直接子树对应该句型的句柄 *5 利用语法树寻找短语、句柄举例 句型句型 =T=T+T*F+i +T*F+i 的语法树的语法树 例 文法GE： E EE+T|T TT*F|F F(E)|iE+T|T TT*F|F F(E)|i E E E + TE + T F F i i E + TE + T T * F T * F T T 句型句型有有6 6个短语：个短语： T+T*F+i T+T*F+i 是句型是句型相对于相对于E E 1 1 的短语的短语 T+T*F T+T*F 是句型是句型相对于相对于E E 2 2 的短语的短语 T T 是句型是句型相对于相对于E E 4 4 的短语的短语 T*F T*F 是句型是句型相对于相对于T T 5 5 的短语的短语 i i，i i 是句型是句型相对于相对于T T 3 3 ，F F 6 6 的短语的短语 3 3个直接短语：个直接短语： T T ,T*F,T*F，i i 句柄：句柄：T T 6 6个内部节点个内部节点6 6棵子树棵子树 *6 利用语法树寻找短语、句柄课堂练习 句型句型 =i=i 1 1 *i*i 2 2 + +i i 3 3 的语法树的语法树 8 8个内部节点个内部节点 8 8棵子树棵子树 句型句型有有8 8个短语：个短语： i i1 1 *i*i 2 2 + +i i 3 3 是句型是句型相对于相对于E E 1 1 的短语的短语 i i1 1 *i*i 2 2 是句型是句型相对于相对于E E2 2 ,T ,T 4 4 的短语的短语 i i1 1 是句型是句型相对于相对于T T6 6 ， ，F F 8 8 的短语的短语 i i2 2 是句型是句型相对于相对于F F 7 7 的短语的短语 i i3 3 是句型是句型相对于相对于T T 3 3 ,F,F 5 5 的短语的短语 例 文法GE： E EE+T|T TT*F|F F(E)|iE+T|T TT*F|F F(E)|i 直接短语直接短语 3 3个：个： i i 1 1 , , i i 2 2 ，i i