同济大学编译原理第四章语法分析——自上而下分析概要.ppt

总控程序 总控程序根据栈顶符号x和当前输入符a，查表决定分析器的动作 （1）若x＝a＝“#”，即STACK 栈顶符号为“#”，当前输入符号为“#”，则分析成功。 （2）若x＝a≠“#” ，即栈顶符号x与当前输入符a匹配，则将x从栈顶弹出，输入串指针后移，读入下一个符号存入a，继续对下一个字符进行分析。 （3）若x为非终结符A ，则查分析表M[A,a]: 1）若M[A,a]为一产生式，则A自栈顶弹出，M[A, a]中产生式的右部符号逆序压栈; 2）若M[A,a]为A→ε ，则只将A自栈顶弹出。 3）若M[A,a]为空，则发现语法错误，调用出错处理程序进行处理。 总控程序的伪码描述 BEGIN ＃及S 进栈(push(‘#’);push(‘S’);)； 把第一个输入符读入a； FLAG :＝ TRUE； WHILE FLAG DO BEGIN 把STACK栈顶弹出放在X中(X=pop())； IF X∈VT THEN IF X＝a THEN 将下一输入符读入a ELSE ERROR ELSE IF X = “ ＃” THEN IF X = a THEN FLAG := FALSE ELSE ERROR ELSE IF M[X, a] = {X→X1… Xk} THEN 把Xk, Xk-1, … ,X1 逐一进栈 ELSE ERROR END OF WHILE； END # i + i * i # E i + * ( ) # E E→TE E→TE E E→+TE E→? E→? T T→FT T→FT T T →? T →*FT T →? T →? F F→i F→(E) E T 栈 输 入 产生式 0 #E i+i*i# 1 #ET i+i*i# E → TE 2 #ETF i+i*i# T → FT 3 #ETi i+i*i# F → i 4 #ET +i*i# 5 #E +i*i# T → ε 6 #ET+ +i*i# E → +TE 7 #ET i*i# 8 #ETF i*i# T → FT 9 #ETi i*i# F → i 10 #ET *i# 11 #ETF* *i# T → *FT 12 #ETF i# 13 #ETi i# F → i 14 #ET # 15 #E #