《编译原理》课程教学课件（PPT讲稿，2018）cha2_2 文法和语言_短语直接短语句柄——讲授

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

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

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

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

短语直接短语句柄p31 ■短语 若S==*>aAδ，且A=+>B,则称 B是句型αBδ相对于非终结符号A的短语 ■直接短语 若S→*aAδ且A→B,则 称B是句型aBδ相对于非终结 A 6 符号A的直接短语 一个句型的直接短语可能不唯一 E B I 0 句柄 一个句型的最左直接短语 E+T米F 称为该句型的句柄 句型E+T*i的句柄是：i i (句型有唯一句柄) 2025/4/2 ☒)3

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

利用语法树寻找句型的短语、句柄等 句型n=E+T*i ■寻找方法 E① 句型n的语法树有： 口n个内部节点一n棵子树 0n棵子树一n个短语 每颗子树的叶结点从左至右排 米 列组成一个短语 om棵直接子树 m个直接短语 只有父子两代 3个短语E+T*iT*ii 1个直接短语i 加最左直接子树—句柄 句柄i 2025/4/2 ☑D4

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

利用语法树寻找短语、句柄举例 例文法GE]:E→E+TTT→TFFF→(E)|i 句型n=T+TF+i的语法树 6个内部节点—6棵子树 E② 句型n有6个短语： T+TF+i是句型n相对于的短语 E④+T⑤ R⑥ T+TF是句型1相对于E2的短语 T是句型n相对于E4的短语 ④ T*F是句型n相对于T5的短语 i,i是句型n相对于T3,6的短语 3个直接短语：T,TF,1 句柄：T 2025/4/2 ☒) 6

2025/4/2 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+TTT→TF|FF→(E)i 句型n=i1*i2+i3的语法树BEGIN 8个内部节点一8棵子树 E2 T3 句型n有8个短语： i1*i2+i3是句型n相对于E1的短语 T4 F5 i1*i2是句型1相对于E2,T4的短语 i1是句型n相对于T6,F8的短语 T6 米F7 i3 i2是句型n相对于F7的短语 F8 12 i3是句型n相对于T3,F5的短语 直接短语3个：i1,i2,i3 i1 句柄：i1 2025/4/2 章节目录 D7

2025/4/2 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 章节目录