② 若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等。让X出stack栈，并输入下一个单词二元式。 ③ 若X是非终结符，则查预测分析表。若M[X][t.code]存放着关于X的一个产生式，那么，让X出stack栈，然后把产生式右部符号串按反序一一推进stack栈。若右部符号串为空字ε，则意味着无任何文法符号进栈。 实验步骤：

（1）熟悉习教材关于预测分析法的原理。

（2）依照教材关于基于预测分析的语法分析算法，使用C/C++语言实现该算法。

（3）调试、编译、运行程序。 实验要求：

在下次实验时提交本次实验的实验报告（实验报告包括实验目的、实验内容、实验实现过程、源程序、实验结果、实验体会）。

15

实现代码：

void LL1() {

struct code_val {

Char code; char var[20]; }t;

ifstream cinf(“lex_r.txt”,ios::in);

char stack[20]={?#?,?S?}; char X; int top=1; cinf>>t.code>>t.val; while(1) do {

x=stack[top--]; switch(X) of { case ?#?:

if(x==t.code) {

cout>>”Acc”; break; }

case X∈VT:

if(X= =t.code) {

cout>>t.code>>t.val; }

case X∈VN:

if(M[X][t.code]=X→X1X2?Xk) { X1X2?Xk按反序进栈; top=top+k; } } }

}

16

实验五 LR语法分析

实验学时：2学时 实验目的：

掌握

LR语法分析的基本原理

基本原理：把每个句柄的识别（产生式右部的符号串）过程划分为若干状态，每个状态只识别句柄的一个符号，若干个状态就可识别句柄左端的一部分符号。

利用高级语言实现LR语法分析器 实验内容： 文法：（0）S→E

（1）E→E+T （2）E→T （3）T→T*F （4）T→F （5）F→(E) （6）F →i

假设分析表用二维数组M存储，栈顶状态用Stop表示，当前输入符号用t.code表示，控制程序的算法可归纳如下：

(1) 移进。若M[Stop][t.code]=sj，说明句柄尚未完成，应执行移进

操作。S表示移进，j为状态号，将j移入状态栈，将t.code移入符号栈，j成为新的栈顶状态Stop。读下一个单词。

17

(2) 归约。若M[Stop][t.code]=rk，说明句柄已出现在栈顶，应该用

编号为k的产生式A→B进行归约。假设LEN(β)=r，M[Stop-r][t.code]=j。首先将栈顶r个元素出栈，然后将j和A分别移入状态栈和符号栈，j成为新的栈顶状态Stop。当前处理单词不变。

(3) 接受。M[Stop][t.code]=Acc，表示输入串是一个合法句子，程

序终止运行。

(4) 出错。M[Stop][t.code]=空白，表示出错，最简单处理为程序终

止运行。

18