编译原理与技术讲义-第5章.ppt

编译原理与技术主要内容5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.1自底向上语法分析概述5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法算法5.2算符优先分析算法
输入：待分析的输入符号串γ，算符优先文法G及其算符优先表
输出：γ是句子或γ不是句子
声明：S是以数组实现的符号栈，存放还不能归约的符号串；
k是整型下标变量，表示符号栈S的使用深度;
r存放当前输入符号。

γ$；k=1;S[k]=$//S[j]总存放一个终结符，而且对任何终结符t都有$≮t以及t≯$
do{
r=getchar(γ)；//把输入符号串γ的下一个符号送入r
ifS[k]VNthenj=kelsej=k－1;//寻找一个终结符
whileS[j]≯rdo{//栈顶符号和输入符号比较
//S[j]≯r表示S[j]是最左素短语的结尾符号，然后
//在分析栈中回溯地比较两个邻接的终结符来寻找最左素短语的开始符号
do{
t=S[j];
ifS[k]VNthenj=j－1elsej=j－2;//寻找一个邻接的终结符
}untilS[j]≮t//找到最左素短语开始符号的条件

把最左素短语S[j+1]...S[k]归约成P：P是文法G一个产生式P→β的左部，S[j+1]...S[k]和产生式右部β中的符号一一对应：终结符对终结符而且相同，非终结符对非终结符

k=j+1;//把最左素短语从栈顶删除，把归约的非终结符P放在栈顶
S[k]=P;
}endwhile;
ifS[j]≮rORS[j]≌r//此时，栈中的符号串和输入串γ的剩余部分构成一个句型
then{k=k+1;S[k]=r}//而且，最左素短语还没有形成，把当前输入符号压进栈
elseERROR//否则，不能构成最左素短语，调用错误处理程序
}untilr=$//扫描完输入串，而且分析栈S应该是$N，N是一个非终结符5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.2算符优先分析方法5.3.1LR分析方法概述5.3.1LR分析方法概述5.3.1LR分析方法概述5.3.1LR分析方法概述5.3.1LR分析方法概述5.3.1LR分析方法概述算法5.3LR分析算法
输入：待分析的输入符号串γ，LR分析表
输出：γ是句子或γ不是句子
声明：symbol-stack是以数组实现的符号栈，存放还不能归约的符号串；
state-stack是以数组实现的状态栈，每个动作之后和symbol-stack的长度一样；
k是整型下标变量，表示符号栈和状态栈的使用深度;
a存放当前输入符号。
在输入串γ的后面加一个结束标志符$；
k=1;symbol-stack[k]=$；state-stack[k]=s0；//初始化
do{
a=getchar(γ)；//把输入符号串γ的下一个符号送入r
switchACTION[state-stack[k],a]
casesi:{k=k+1;
symbol-stack[k]=i;
state-stack[k]=a}
caserj:{找到文法的第j个产生式A→β；
k=k－length(β)＋1;
symbol-stack[k]=A;
s=state-stack[k];
k=k+1;
state-stack[k]=GOTO[s,A]}
case“acc”:return
default:error();
}untilr=$5.3.1LR分析方法概述5.3.1LR分析方法概述5.3.1LR分析方法概述5.3.1LR分析方法概述5.3.1LR分析方法概述5.3.2LR(0)分析表的构造5.3.2LR(0)分析表的构造5.3.2LR(0)分析表的构造5.3.2LR(0)分析表的构造5.3.2LR(0)分析表的构造5.3.2LR(0)分析表的构造5.3.2LR(0)分析表的构造5.3.2LR(0)分析表的构造5.3.2LR(0)分析表的构造5.3