《编译原理》课程教学课件（2023讲稿）cha02-2 文法和语言_短语直接短语句柄

n最左（最右）推导 2.6句型分析 u在推导的任何一步a=*>B(其中α和B是句型)， 都对α中的最左（最右）非终结符进行替换。 n句型分析（句子分析） ū识别一个符号串是否为某文法的句型（句子）的过程。 u也就是某文法的某个推导的构造过程。 n设文法G为： E→E+T|T T→T*F|F F→(E)|i 自顶向下 自底向上 n请问符号串i+ii是 否为该文法的句子？ 可☒

1 n 最左(最右)推导 u 在推导的任何一步α==*>β(其中α和β是句型)， 都对α中的最左(最右)非终结符进行替换。 n 句型分析(句子分析) u 识别一个符号串是否为某文法的句型(句子)的过程。 u 也就是某文法的某个推导的构造过程。 n 设文法G为: E →E+T|T T →T*F|F F →(E)|i n 请问符号串i+i*i是 否为该文法的句子? E E + T T * F F F T i i i 自 顶 向 下 自 底 向 上 2.6 句型分析

常用语法分析方法 n语法分析算法可分为两大类： n自顶向下分析法 山从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导。 n自底向上分析法 ū从输入串开始，逐步进行归约，直至归约到文法 的开始符号。 n两种方法反映了两种不同的语法树的构造过程 ū自顶向下一一从树根推导到树叶。 ū自底向上一一从树叶归约到树根。 ☒D

2 常用语法分析方法 n 语法分析算法可分为两大类: n 自顶向下分析法 u 从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导。 n 自底向上分析法 u 从输入串开始，逐步进行归约，直至归约到文法 的开始符号。 n 两种方法反映了两种不同的语法树的构造过程 u 自顶向下——从树根推导到树叶。 u 自底向上——从树叶归约到树根

短语直接短语句柄 p31 n短语：若S=>aA8,且A=+>B,则称B是 句型aB8相对于非终结符号A的短语。 n直接短语：若S☐*aA8且A☐B S ,则称B是句型αBδ相对于非终结 符号A的直接短语。 A 一个句型的直接短语可能不唯一。 E 句柄：一个句型的最左直接短语 称为该句型的句柄。 E+T米F 句型E+T*i的句柄是：i 一个句型有唯一的句柄。 i 2023/2/28 ☑3

2023/2/28 3 短语 直接短语 句柄 p31 Ｓ α Ａ δ E β ε E ε E+T*i E E+ T ε T*i E E+T* F ε i n 短语:若Ｓ==*>αＡδ，且A==+>β，则称β是 句型αβδ相对于非终结符号A的短语。 n 直接短语：若Ｓ￾ * αＡδ 且 A￾ β ，则称β是句型αβδ 相对于非终结 符号A的直接短语。 一个句型的直接短语可能不唯一。 句型E+T*i的句柄是：i 一个句型有唯一的句柄。 n 句柄：一个句型的最左直接短语 称为该句型的句柄

利用语法树寻找句型的短语、句柄等 句型n=E+T*i n寻找方法 E① 句型n的语法树有： un个内部节点一n棵子树 un棵子树一n个短语 每颗子树的叶结点从左至右排 列组成一个短语 um棵直接子树一m个直接短语 只有父子两代 3个短语E+T*iT*i1 1个直接短语i 最左直接子树一句柄 句柄i 2023/2/28 ☒D4

2023/2/28 4 利用语法树寻找句型的短语、句柄等 句型η=E+T*i E E + T T * F i n寻找方法 句型η的语法树有： un棵子树——n个短语 um棵直接子树——m个直接短语 u最左直接子树——句柄 ① ② ③ 3个短语 1个直接短语 i 句柄 i E+T*i T*i i 只有父子两代 un个内部节点——n棵子树 每颗子树的叶结点从左至右排 列组成一个短语

利用语法树寻找短语、句柄举例 例文法GE:E→E+T|TT→TFFF→(E)|i 句型1=T+TF+i的语法树 6个内部节点6棵子树 E② 句型n有6个短语： T+TF+i是句型n相对于的短语 E④+T⑤ F T+TF是句型n相对于E2的短语 T是句型n相对于E4的短语 T米F TF是句型1相对于T的短语 i,i是句型n相对于T3,6的短语 3个直接短语：T,TP,1 句柄：T 2023/2/28 ☑D6

2023/2/28 6 利用语法树寻找短语、句柄举例 句型 η=T+T*F+i 的语法树 例 文法G[E]： E→E+T|T T→T*F|F F→(E)|i E E + T F i E + T T T * F ① ② ③ ④ ⑤ ⑥ 句型η有6个短语： T+T*F+i 是句型η相对于E 1的短语 T+T*F 是句型η相对于E 2的短语 T 是句型η相对于E 4的短语 T*F 是句型η相对于T 5的短语 i，i 是句型η相对于T 3 ，F 6的短语 3个直接短语： T ,T*F，i 句柄：T 6个内部节点——6棵子树

利用语法树寻找短语、句柄课堂练习 例文法GE]:E→E+T|TT→TFFF→(E)|i 句型n=i1*i2+i3的语法树 BEGIN 8个内部节点一 8棵子树 E2 句型1有8个短语： i1*i2+i3是句型n相对于的短语 T4 F5 i1*i2是句型n相对于E2,T4的短语 i1是句型1相对于T6,F8的短语 米 F7 is 12是句型n相对于F7的短语 F8 i3是句型n相对于T3,F5的短语 32 直接短语3个：i1,12,i3 句柄：i1 2023/2/28 章节目录

2023/2/28 7 利用语法树寻找短语、句柄课堂练习 句型 η=i1*i2+i3 的语法树 8个内部节点—— 8棵子树 句型η有8个短语： i1*i2+i3是句型η相对于E 1的短语 i1*i2是句型η相对于E 2 ,T4的短语 i1是句型η相对于T 6 ，F 8的短语 i2是句型η相对于F 7的短语 i3是句型η相对于T 3,F5的短语 例 文法G[E]： E→E+T|T T→T*F|F F→(E)|i 直接短语 3个： i1, i2，i3 句柄：i1 E1 E 2 + T3 F 5 T 6 * F7 T 4 F 8 i2 i3 i1 BEGIN 章节目录