石河子大学：《编译原理》课程教学资源（PPT课件）第六、七章 语法分析——自下而上分析

第六、七章语法分析一一 自下而上分析 本章内容 ●自下而上分析基本问题 ●直观算符优先分析法 ●算符优先分析 ●LR分析法

第六、七章 语法分析——自下而上分析 本章内容 ⚫自下而上分析基本问题 ⚫直观算符优先分析法 ⚫算符优先分析 ⚫ LR分析法

>自下而上分析法 从输入串开始，逐步进行“归约”，直至 归约到文法的开始符号； 一、自下而上分析基本问题 1、归约 利用栈，输入符号移进栈，当栈顶形成P的 候选式时，就归约为它的左P符号

➢自下而上分析法 从输入串开始，逐步进行“归约”，直至 归约到文法的开始符号； 一、自下而上分析基本问题 1 、归约 利用栈，输入符号移进栈，当栈顶形成P的 候选式时，就归约为它的左P符号

2、自下而上分析法的基本思想： 自左向右逐个扫描输入串，一边把输入符号移入分 析栈内，一边检查位于栈顶部的一串待号是否与某个产生 式的右部相同。 若相同，则执行“归约”； 若不相同，就继续向栈内移进输入符号，并继续进行 判断。 分析成功：上述过程一直重复到输入串结束，而栈内恰好 为给定文法的开始符号为止

2 、自下而上分析法的基本思想： 自左向右逐个扫描输入串，一边把输入符号移入分 析栈内，一边检查位于栈顶部的一串符号是否与某个产生 式的右部相同。 若相同，则执行“归约” ； 若不相同，就继续向栈内移进输入符号，并继续进行 判断。 分析成功：上述过程一直重复到输入串结束，而栈内恰好 为给定文法的开始符号为止

>自下而上法，即“移进-归约”法 例6.1文法G2: S->aAcBe A->b A->Ab B->d 输入串：abbcde

例6.1 文法G2: S->aAcBe A->b A->Ab B->d 输入串：abbcde ➢自下而上法，即“移进-归约”法

最右推导：S=)aAcBe=>aAcde=>aAbcde=>a bb c d e 栈 2 3 4 5 6 7 8 9 10 e dB B S->aAcBe A->Ab A- A A A A A->b B->d bA A a a a 8 a a a 输入串：abbcde

最右推导： a a b a A a A b a A a A c a A c d a A c B a A c B e S 1 2 3 4 5 6 7 8 9 10 栈 S => aAcBe => aAcde =>aAbcde => a b b c d e S->aAcBe 输入串：abbcde A->Ab A->b B->d

最左归约：a bb cde=)aAbcde=)aAcde=〉aAcBe=>S e d S->aAcBe A->Ab A->b B->d 分析树 输入串：abbcde

S a A c B e A b d b 分 析 树 最左归约： => aAcBe => S a b b c d e => aAbcde => aAcde S->aAcBe 输入串：abbcde A->Ab A->b B->d

规范推导：即最右推导， 规范句型：由规范推导所得的句型称为规范 包型， 规范归约：是关于句型心的一个最右推导的 逆过程，也称最左归约

规范推导：即最右推导； 规范句型：由规范推导所得的句型称为规范 句型； 规范归约：是关于句型α的一个最右推导的 逆过程，也称最左归约

E 例6.2文法6 E一>TIE+T T->FT*F F->i(E) 的一个句型11*12+i3 ●短语： i1,i2,i3 i1*i2,i*i2tis ●直接短语：i1,12,i3 ●句柄：i 语 法树

例6.2 文法G E — ＞ T | E +T T — ＞ F | T * F F — ＞ i | （E ） 的一个句型 i 1*i 2+i 3 语 法 树 TF E E F F + T * i i i T TF E E F F + T * i1 i2 i3 T i1 , i2 , i3 , i 1*i2 , i 1*i 2+i 3 i1 , i2 , i3 i1 ⚫短语 : ⚫直接短语 : ⚫句柄:

3将号栈的使用 规范归约用来作语法分析鼎要解决的问题8 ①如何在句型中找出句柄？ ②在相同的右部有不止一个产生式时，选哪一个？ ①实现移进-归约分析的一个方便途径是用一个栈和一个输 入缓冲区，用#表示栈底和输入的结束 栈 输入 # W

3 符号栈的使用 规范归约用来作语法分析需要解决的问题： ①如何在句型中找出句柄? ②在相同的右部有不止一个产生式时,选哪一个? ①实现移进-归约分析的一个方便途径是用一个栈和一个输 入缓冲区,用#表示栈底和输入的结束 栈 输 入 # w#

②分析程序的动作 ●移进：下一输入符号移进栈顶 。归约：把句柄按产生式的右部进行归约 ●接收：分析程序报告成功 ●出错：发现了一个语法错，调用出错处理程序 注意8可归约的串在浅顶不会在内部

② 分析程序的动作 ⚫移进: 下一输入符号移进栈顶 ⚫归约: 把句柄按产生式的右部进行归约 ⚫接收: 分析程序报告成功 ⚫出错: 发现了一个语法错,调用出错处理程序 注意: 可归约的串在栈顶,不会在内部