5.1.3符号栈的使用和分析树的表示 ■栈是语法分析的一种基本数据结构。’#作 为栈底符号 ■考虑文法G(E): E→T|E+T T→F|T*F F→(E)|i 输入串为i1*i2+i3,分析步骤为： 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 5.1.3 符号栈的使用和分析树的表示 ◼ 栈是语法分析的一种基本数据结构。’#’作 为栈底符号 ◼ 考虑文法G(E)： E → T | E+T T → F | T*F F → (E) | i 输入串为i1 *i2+i3 ，分析步骤为：
G(E): E→T|E+T T→FIT*F F→(E)Ii 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #1 *i2+i3# 进 2 #℉ *i2+i3# 归，用F川 3 #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i 3 #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 ◼ G(E)： E → T | E+T T → F | T*F F → (E) | i
G(E): E→TIE+T T→FIT*F F→(E)|i 步骤 符号栈 输入串 动作 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归， 用Fi 7 #T +i3# 归， 用TT*F 8 #E +i3# 归，用E→T 9 #E+ i3# 进 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 步骤 符号栈 输入串 动作 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归，用F→i 7 #T +i3# 归，用T→T*F 8 #E +i3# 归，用E→T 9 #E+ i3# 进 ◼ G(E)： E → T | E+T T → F | T*F F → (E) | i
G(E): E→T|E+T T→F|T*F F→(E)Ii 步骤 符号栈 输入串 动作 9 #E+ i3# 10 #E+i3 # 进 11 #E+F # 归，用Fi 12 #E+T # 归，用T→F 13 #E # 归，用E→E+T 14 #E # 接受 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 步骤 符号栈 输入串 动作 9 #E+ i3# 进 10 #E+i3 # 进 11 #E+F # 归，用F→i 12 #E+T # 归，用T→F 13 #E # 归，用E→E+T 14 #E # 接受 ◼ G(E)： E → T | E+T T → F | T*F F → (E) | i
回顾 ■语法分析的方法： 口自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“ 约”，直到文法的开始符号。即从树末端开始， 构造语法树。所谓归，是指根据文法的产 生式规则，把产生式的右部替换成左部符号。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼语法分析的方法： 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归 约”，直到文法的开始符号。即从树末端开始， 构造语法树。所谓 归约 ，是指根据文法的产 生式规则，把产生式的右部替换成左部符号。 回顾