第六、七章语法分析一一 自下而上分析 本章内容 ●自下而上分析基本问题 ●直观算符优先分析法 ●算符优先分析 ●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