LL(1)分析

一、实验任务

存储文法；

• 计算给定文法所有非终结符的 FIRST 集合；

• 计算给定文法所有非终结符的 FOLLOW 集合；

• 构造该文法的 LL(1) 文法的分析表

• 根据 LL(1) 分析表判断文法是否 LL(1) 文法；

• 完成完整的 LL(1) 分析过程。

二、实验内容

确定文法的文件存储格式，存储文法的非终结符集合、开始符号、终结符集合和产生式规则集合。

要求为 3 个以上测试文法准备好相应的存储文件。

计算给定文法所有非终结符的 FIRST 集合。

计算给定文法所有非终结符的 FOLLOW 集合；

确定 LL(1) 分析表的文件存储格式。

要求为 3 个以上测试文法准备好相应 LL(1) 分析表的存储文件。

根据 LL(1) 分析表判断文法是否 LL(1) 文法。

看每个表项是否最多只有一条候选式，如是该文法是 LL(1) 文法。

实现 LL(1) 分析过程。

当 5. 判断出该文法是 LL(1) 文法时，要求给出 3 个以上输入串的 LL(1) 分析过程，并判断输入串是否该文法的合法句子。

完成完整的 LL(1) 分析过程。

三、存储格式

• 文法

E->TE`
E`->+TE`|e
T->FT`
T`->*FT`|e
F->(E)|id

1
2
3
4
5
6

• 改变

E`用Y代替
T`用X代替

1
2
3

• 非终结符号

EYTXF

1
2

• 文法改写存储

E,TY
Y,+TY
Y,e
T,FX
X,*FX
X,e
F,(E)
F,i

1
2
3
4
5
6
7
8
9

• 分析表用一个结构体的二维数组存储，会很复杂，看代码理解。

---

四、程序设计

• 结构体类 struct.h
  注意理清里面的结构体嵌套。

# include 
# ifndef MAXNUM
# define MAXNUM 100
# endif
# ifndef _STRUCT_H
# define _STRUCT_H

/******数据定义******/
struct rule
{                       //一个文法
    std::string startSymbol; //开始符号
    std::string tuidao;      //推导式
};

struct record{      //记录一个终结符号由那些产生式得出的
    int num=0;      //数量
    int gramNum[MAXNUM];    //产生式的编号
};

struct set
{                     //集合
    char startSymbol; //非终结符
    char set[MAXNUM]; //frist or follow集合
    record gramNum[MAXNUM]; //记录一个终结符号是由哪些文法推导出的
    int num = 0;
    bool isExistE = false; //是否存在空串
};

struct tableCell{   //预测分析表的一个单元
    int num=0;
    rule cell[MAXNUM];
    bool error=true;
};

# endif


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

• 获得 first 和 follow 集文法类 getFirFol.h

# include "getFirFol.h"
# include "struct.h"

# ifndef _LL_H
# define _LL_H

class LL{
public:
    LL(getFirst_Follow *ff,std::string ts, std::string nts, std::string rl);
    /***构造分析表***/
    void fillInTheTable();
    /***分析字符串***/
    void analyzeChars(std::string path);
    /***在对应的分析表单元格加入文法***/
    bool addInTableCell(int h,int l,int gramNum);
private:
    getFirst_Follow *getff;
    std::string terSymbol;      //终结符号集合
    int tsLength=0;             //终结符号数量
    std::string nonTerSymbol;   //非终结符号集合
    int ntsLength=0;            //非终结符号数量
    rule *grammer = NULL;       //文法
    int gramNum = 0;            //文法公式数目
    tableCell **analyzeTable;   //预测分析表
    bool isLLGrammer=true;      //判断是为LL(1)文法      
};

# endif


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 主函数 main.cpp

# include"getFirFol.h"
# include"LL.h"
# include
# include
# include
# include
using namespace std;

int main(){
    string ts="test1\\terminalSymbol.ll";
    string nts="test1\\nonTerminalSymbol.ll";
    string rl = "test1\\rule.ll";
    string path="test1\\input1.ll";
    getFirst_Follow gff(ts,nts,rl);
    gff.getFirst();
    gff.getFollow();
    LL ll(&gff,ts,nts,rl);
    ll.fillInTheTable();
    ll.analyzeChars(path);
    system("pause");
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

五、实验测试

• 文法分析结果

• LL(1) 分析结果

1）输入串

i+i*i

1
2

2） 分析