编译原理 - LL(1)文法源代码（实验三）

一、实验目的及要求

1．掌握LL(1)分析法的基本原理； 2．掌握LL(1)分析表的构造方法；

3．用LL（1）分析法分析高级语言表达式。 4、了解LL（1）分析器的工作过程。 文法：无二义性的算术表达式的文法

（1）把词法分析作为语法分析的子程序实现（5分） （2）独立的语法分析程序（4分）

（3）对表达式文法消除左递归、构造LL（1）分析表 （4）LL（1）分析表可以直接输入（4分），也可以用程序实现（5分） （5）给一个表达式，给出分析过程（分析栈、输入串、所用规则）（4分） （6）生成一个棵语法树（5分）用二叉树的形式表示出来

二、实验内容及原理 1、 实验原理

（1）、LL（1）文法的定义

LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。

需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式A??,A??，都要满足下面条件：SELECT(A??)∩SELECT(A??)=?

（2）、预测分析表构造

LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下：

M: VN×VT?P∪{Error}

M(A, t) = A?α，当t?select(A?α) ，否则 M(A, t) = Error

其中P表示所有产生式的集合。 （3）、语法分析程序构造

LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括号即输入串的括号。分析表用一个二位数组M表示，数组元素M[A，a]中的下标A

表示非终结符，a为终结符或句子括号‘#’，二维数组中存放的是一条关于A 的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。

LL(1)分析过程主要包括以下四个动作：

替换：当X?VN时选相应产生式的右部?去替换X。此时X出栈，?逆序入栈。

匹配：当X?VT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。

接受：当格局为（#，空#）时报告分析成功。

报错：出错后，停止分析。并给出相应的错误提示信息。

2、实验内容

根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。

对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG （3）G->ε （4）T->FS （5）S->*FS （6）S->ε （7）F->(E) （8）F->i 程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。

三、实验过程及步骤 1.

总体思路分析及流程图

给定一个正规文法G，在LL(1)预测分析中，必须先求出First集和Follow集， 构造预测分析表。求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析过程。

读取正规文法求文法的First集求文法的Follow集求文法的Select集键盘输入字符串字符串分析 功能模块分解图

（1）主程序流程图

开始输入文法判断文法是否为LL(1)文法Y构造预测分析表N输入要分析的符号串出错处理判断该符号串是否可被该文法识别出错处理NY提示i*i+i#为可接受的字符串结束 （2）核心算法流程图

1.计算非终结符的First集的算法及流程： First集合的构造算法：

（1）若X∈VT，则First（X）={X}。

（2）若X∈VN，且有产生式X→a??，则把a加入到First (X)中；若X→ε也是一条产生式，则把ε也加到First (X)中。

（3）若X→Y??是一个产生式且Y∈VN，则把First (Y)中的所有非ε-元素都加到First (X)中；若X→Y1Y2?Yk是一个产生式，Y1，?，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，First (Yj)都含有ε（即Y1?Yi-1* ε），则把First (Yj)中的所有非ε-元素都加到First (X)中；特别是，若所有的First (Yj)均含有ε，j=1,2,?，k，则把ε加到First (X)中。

连续使用上面的规则，直至每个集合First不再增大为止。

开始读取一个非终结符V遍历所有产生式，查找左部是V的产生式添加一个删除空的标志为 true取出得到的一条产生式V*是不是有推导规则V*->空产生式右部第一个符号V*是终结符？将该终结符V*加入V的First集中空标志为真删除空，得到V的First集剩有非终结符？结束

2.计算非终结符的Follow集： Follow集合的具体构造算法如下：

（1）对于文法的开始符号S，置#于Follow(S)中；

（2）若A→αBβ是一个产生式，则把First(β)|{ε}加至Follow(B)中； （3）若A→αB是一个产生式，或A→αBβ是一个产生式而β ε（即ε∈First(β)），则把Follow(A)加至Follow(B)中。

连续使用上面的规则，直至每个集合Follow不再增大为止。

开始取得一个非终结符V查找产生式的右部含有V的产生式YV是不是最后一个字符NV后一个字符V*是否为终结符YY添加#到V的Follow集中YN是否遍历完所有右部含有V的产生式添加V*到V的Follow中Y将V*的First集加入到V的Follow集中是否有未求解过的非终结符N完成

3.预测分析控制程序的算法流程

输入要分析的字符串Y判断字符串是否正确N‘#’’E’进栈，当前终结符号送入a若产生式为A→A1A2?An,按逆序即[An?A2A1]入栈显示分析步骤读入下一符号显示栈中内容NY显示剩余输入串接受Y产生式右部为空？A∈Vt?YYA=‘a’？N匹配字符串？NNA=‘#’？YN产生式不存在？Y显示产生式NY出错出错

LL（1）文法（源代码） #include \#include \

#define MaxRuleNum 8 #define MaxVnNum 5 #define MaxVtNum 5

#define MaxStackDepth 20 #define MaxPLength 20 #define MaxStLength 50

struct pRNode /*产生式右部结构*/ {

int rCursor;

struct pRNode *next; };

struct pNode {

int lCursor;

int rLength; /*右部长度*/

struct pRNode *rHead; /*右部结点头指针*/ };

char Vn[MaxVnNum + 1]; /*非终结符集*/ int vnNum;

char Vt[MaxVtNum + 1]; /*终结符集*/ int vtNum;

struct pNode P[MaxRuleNum]; int PNum;

char buffer[MaxPLength + 1]; char ch;

char st[MaxStLength]; /*要分析的符号串*/

struct collectNode {

int nVt;

struct collectNode *next; };

struct collectNode* first[MaxVnNum + 1]; /*first集*/ struct collectNode* follow[MaxVnNum + 1]; /*follow集*/

int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];

int analyseStack[MaxStackDepth + 1]; /*分析栈*/ int topAnalyse; /*分析栈顶*/

void Init();/*初始化*/ int IndexCh(char ch);

void InputVt(); /*输入终结符*/ void InputVn();/*输入非终结符*/

void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/ void InputP();/*产生式输入*/

bool CheckP(char * st);/*判断产生式正确性*/ void First(int U);

void AddFirst(int U, int nCh); /*加入first集*/ bool HaveEmpty(int nVn);

void Follow(int V);/*计算follow集*/ void AddFollow(int V, int nCh, int kind);

void ShowCollect(struct collectNode **collect);/*输出first或follow集*/ void FirstFollow();/*计算first和follow*/ void CreateAT();/*构造预测分析表*/ void ShowAT();/*输出分析表*/ void Identify(char *st); void InitStack(); void ShowStack(); void Pop();

void Push(int r);

void main(void) {

char todo,ch;

Init();

InputVn(); InputVt(); InputP();

getchar();

FirstFollow();

printf(\所得first集为：\ ShowCollect(first);

printf(\所得follow集为：\ ShowCollect(follow);

CreateAT(); ShowAT();

todo = 'y';

while('y' == todo) {

printf(\是否继续进行句型分析？(y / n):\ todo = getchar();

while('y' != todo && 'n' != todo) {

printf(\ todo = getchar(); }

if('y' == todo) { int i;

InitStack();

printf(\请输入符号串(以#结束) : \ ch = getchar(); i = 0;

while('#' != ch && i < MaxStLength) {

if(' ' != ch && '\\n' != ch) {

st[i++] = ch; }

ch = getchar(); }

if('#' == ch && i < MaxStLength) {

st[i] = ch; Identify(st); } else

printf(\输入出错！\\n\ } }

getchar(); }

void Init() {

本文来源：https://www.bwwdw.com/article/9wkt.html