【编译原理】LL(1)分析法：C/C++实现

SarPro

发布于 2024-02-20 14:23:47

1.1K0

发布于 2024-02-20 14:23:47

1. 编译原理之LL(1)分析法概念

1.1 编译原理

编译原理是计算机科学领域的一个重要分支，它研究如何将高级编程语言的源代码转化成计算机能够执行的机器代码或中间代码的过程。编译原理涵盖了编译器的设计和实现，其中编译器是一种将源代码翻译成目标代码的软件工具。编译器的主要任务包括语法分析、词法分析、语义分析、优化和代码生成等环节。

1.2 LL(1)分析法

LL(1)分析法是一种常用的自顶向下的语法分析方法，用于分析和解释编程语言或其他形式的文本。LL(1)代表"Left-to-Right, Leftmost derivation, 1 symbol lookahead"，这表示了分析器的工作方式和限制条件，通常用于编程语言的语法分析，编写编译器或解释器。主要步骤包括构建LL(1)文法、构建LL(1)分析表和使用递归下降分析或预测分析器等算法来分析输入文本。

2. LL(1)分析法

2.1 实验目的

（1）加深对预测分析LL(1)分析法的理解；

（2）根据某一文法编制调试LL(1)分析程序，以便对任意输入的符号串分析。

2.2 实验要求

实验规定对下列文法，用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#

则输出：

LL(1)的分析表：

	i	+	*	(	)	#	说明
E	e			e			Select(E→TG)=｛(,i｝
G		g			g1	g1	Select (G→+TG)=｛+｝ Select (G→є)=｛#,)｝
T	t			t			Select (T→FS)=｛(,i｝
S		s1	s		s1	s1	Select (S→FS)=｛｝Select (S→є)=｛#,) +｝
F	f1			F			Select (F→(E))=｛(｝ Select (F→i)=｛i｝

参考代码（不完整）：

do/*读入分析串*/
{
    scanf("%c",&ch);
    if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#'))
    {
        printf("输入串中有非法字符\n");
        exit(1);
    }
    B[j]=ch;
    j++;
}while(ch!='#');

l=j;/*分析串长度*/
ch=B[0];/*当前分析字符*/
A[top]='#'; A[++top]='E';/*'#','E'进栈*/
printf("步骤\t\t分析栈 \t\t剩余字符 \t\t所用产生式 \n");
do
{
    x=A[top--];/*x为当前栈顶字符*/
    printf("%d",k++);
    printf("\t\t");
}   

for(j=0;j<=5;j++)/*判断是否为终结符*/
    if(x==v1[j])
    {   
        flag=1;
        break;
    }
    if(flag==1)/*如果是终结符*/
    {
        if(x=='#')
        {
            finish=1;/*结束标记*/
            printf("acc!\n");/*接受 */
            getchar();
            getchar();
            exit(1);
        }
        if(x==ch)
        {
            print();
            print1();
            printf("%c匹配\n",ch);
            ch=B[++b];/*下一个输入字符*/
            flag=0;/*恢复标记*/
        }
        else/*出错处理*/
        {
            print();
            print1();
            printf("%c出错\n",ch);/*输出出错终结符*/
            exit(1);  
        }
    }
    else/*非终结符处理*/
    {
        for(j=0;j<=4;j++)
            if(x==v2[j])
            {
                m=j;/*行号*/
                break;
            }
        for(j=0;j<=5;j++)
            if(ch==v1[j])
            {
                n=j;/*列号*/
                break;
            }
        cha=C[m][n];
        if(cha.origin!='N')/*判断是否为空*/
        {
            print();
            print1();
            printf("%c->",cha.origin);/*输出产生式*/
            for(j=0;j<cha.length;j++)
                printf("%c",cha.array[j]);
            printf("\n");
            for(j=(cha.length-1);j>=0;j--)/*产生式逆序入栈*/
                A[++top]=cha.array[j];
            if(A[top]=='^')/*为空则不进栈*/
                top--;
        }
    }
}

void print()/*输出分析栈 */
{
    int a;/*指针*/
    for(a=0;a<=top+1;a++)
        printf("%c",A[a]);
    printf("\t\t");
}

void print1()/*输出剩余串*/
{
    int j;
    for(j=0;j<b;j++)/*输出对齐符*/
        printf(" ");
    for(j=b;j<=l;j++)
        printf("%c",B[j]);
    printf("\t\t\t");
}

// 主程序中的各变量定义
char A[20];/*分析栈*/
char B[20];/*剩余串*/
char v1[20]={'i','+','*','(',')','#'};/*终结符 */
char v2[20]={'E','G','T','S','F'};/*非终结符 */

int j=0,b=0,top=0,l;/*L为输入串长度 */
typedef struct type/*产生式类型定义 */
{
    char origin;/*大写字符 */
    char array[5];/*产生式右边字符 */
    int length;/*字符个数 */
}type;

type e,t,g,g1,s,s1,f,f1;/*结构体变量 */
type C[10][10];/*预测分析表 */

/*把文法产生式赋值结构体*/
e.origin='E';
strcpy(e.array,"TG");
t.origin='T';
strcpy(t.array,"FS");
g.origin='G';
strcpy(g.array,"+TG");
g1.origin='G';
g1.array[0]='^';
s.origin='S';
strcpy(s.array,"*FS");
s1.origin='S';
s1.array[0]='^';
f.origin='F';
strcpy(f.array,"(E)");
f1.origin='F';
f1.array[0]='i';

for(m=0;m<=4;m++)/*初始化分析表*/
    for(n=0;n<=5;n++)
        C[m][n].origin='N';/*全部赋为空*/
/*填充分析表*/
C[0][0]=e;C[0][3]=e;
C[1][1]=g;C[1][4]=g1;C[1][5]=g1;
C[2][0]=t;C[2][3]=t;
C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;
C[4][0]=f1;C[4][3]=f;

2.3 实验内容

2.3.1 实验解决代码

根据参考代码修改如下：

do/*读入分析串*/
{
    scanf("%c",&ch);
    if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#'))
    {
        printf("输入串中有非法字符\n");
        exit(1);
    }
    B[j]=ch;
    j++;
}while(ch!='#');
l=j;/*分析串长度*/
ch=B[0];/*当前分析字符*/
A[top]='#'; A[++top]='E';/*'#','E'进栈*/
printf("步骤\t\t分析栈 \t\t剩余字符 \t\t所用产生式 \n");
do
{
    x=A[top--];/*x为当前栈顶字符*/
    printf("%d",k++);
    printf("\t\t");
}

for(j=0;j<=5;j++)/*判断是否为终结符*/
    if(x==v1[j])
    {   
        flag=1;
        break;
    }
    if(flag==1)/*如果是终结符*/
    {
        if(x=='#')
        {
            finish=1;/*结束标记*/
            printf("acc!\n");/*接受 */
            getchar();
            getchar();
            exit(1);
        }
        if(x==ch)
        {
            print();
            print1();
            printf("%c匹配\n",ch);
            ch=B[++b];/*下一个输入字符*/
            flag=0;/*恢复标记*/
        }
        else/*出错处理*/
        {
            print();
            print1();
            printf("%c出错\n",ch);/*输出出错终结符*/
            exit(1);
        }
    }
    else/*非绂
        for(j=0;j<=4;j++)
            if(x==v2[j])
            {
                m=j;/*行号*/
                break;
            }
        for(j=0;j<=5;j++)
            if(ch==v1[j])
            {
                n=j;/*列号*/
                break;
            }
        cha=C[m][n];
        if(cha.origin!='N')/*判断是否为空*/
        {
            print();
            print1();
            printf("%c->",cha.origin);/*输出产生式*/
            for(j=0;j<cha.length;j++)
                printf("%c",cha.array[j]);
            printf("\n");
            for(j=(cha.length-1);j>=0;j--)/*产生式逆序入栈*/
                A[++top]=cha.array[j];
            if(A[top]=='^')/*为空则不进栈*/
                top--;
        }
    }
}

void print()/*输出分析栈 */
{
    int a;/*指针*/
    for(a=0;a<=top+1;a++)
        printf("%c",A[a]);
    printf("\t\t");
}

void print1()/*输出剩余串*/
{
    int j;
    for(j=0;j<b;j++)/*输出对齐符*/
        printf(" ");
    for(j=b;j<=l;j++)
        printf("%c",B[j]);
    printf("\t\t\t");
}

// 主程序中的各变量定义
char A[20];/*分析栈*/
char B[20];/*剩余串*/
char v1[20]={'i','+','*','(',')','#'};/*终结符 */
char v2[20]={'E','G','T','S','F'};/*非绂
int j=0,b=0,top=0,l;/*L为输入串长度 */
typedef struct type/*产生式类型定义 */
{
    char origin;/*大写字符 */
    char array[5];/*产生式右边字符 */
    int length;/*字符个数 */
}type;

type e,t,g,g1,s,s1,f,f1;/*结构体变量 */
type C[10][10];/*预测分析表 */

/*把文法产生式赋值结构体*/
e.origin='E';
strcpy(e.array,"TG");
t.origin='T';
strcpy(t.array,"FS");
g.origin='G';
strcpy(g.array,"+TG");
g1.origin='G';
g1.array[0]='^';
s.origin='S';
strcpy(s.array,"*FS");
s1.origin='S';
s1.array[0]='^';
f.origin='F';
strcpy(f.array,"(E)");
f1.origin='F';
f1.array[0]='i';

for(m=0;m<=4;m++)/*初始化分析表*/
    for(n=0;n<=5;n++)
        C[m][n].origin='N';/*全部赋为空*/
/*填充分析表*/
C[0][0]=e;C[0][3]=e;
C[1][1]=g;C[1][4]=g1;C[1][5]=g1;
C[2][0]=t;C[2][3]=t;
C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;
C[4][0]=f1;C[4][3]=f;

2.3.2 运行结果

输入正确的测试用例

i+i*i

输入错误的测试用例

一>i+i

输入错误的测试用例二

i+i*i)

输入错误的测试用例三

i**i

2.3.3 详细代码分析

1.首先，在程序的开头包含了 <stdio.h> 和 <string.h> 这两个头文件，用于提供输入输出和字符串处理的功能。 2.定义了宏 number_zjfu 和 unnumber_zjfu 分别表示终结符和非终结符的个数。 3.声明了全局变量和结构体 stack1 和 stack2 是字符数组，分别表示分析栈和剩余串。

terminal_array 是一个字符数组，存储终结符。
non_terminal_array 是一个字符数组，存储非终结符。
struct Production 是一个结构体类型，表示产生式，包括产生式的起始符号、右边的字符数组和字符个数。

e、t、g、g1、s、s1、f、f1 是 struct Production 类型的结构体变量，表示相应的产生式。

analyseTable 是一个二维数组，存储预测分析表的内容。

4.定义辅助变量：

frist 表示输入串的指针，初始值为 0。
last 表示分析栈的指针，初始值为 0。
length_of_string 表示输入串的长度。
userF 和 stacktop 分别表示当前处理的输入串中的字符和栈顶的字符。
statue 用于表示分析状态，初始值为 0。
proce 用于记录分析步骤的序号，初始值为 1。

5.定义了一系列函数的原型，包括 init()、analyse()、printStack()、printRemainString() 和 input_string()。 6.main() 函数是程序的主函数。

1. 在 main() 函数中首先调用 init() 函数进行初始化。
2. 接下来通过 input_string() 函数获取用户输入的串，并进行合法性判断。
3. 将结束符号 # 和开始符号 E 分别入栈。
4. 进入一个循环，在循环中调用 analyse() 函数进行分析，直到 statue 变量的值变为 1 表示分析完成。
5. 分析完成后，程序结束并返回 1。

7.input_string() 函数用于获取用户输入的串。

首先打印提示信息，要求用户输入终结符。
使用 getchar() 函数逐个读取用户输入的字符，并将其存储到 stack2 数组中。
判断输入的字符是否合法，如果不是终结符则输出错误信息并返回 false。
将结束符号 # 加入到 stack2 数组中，并将输入串的
长度保存到 length_of_string 变量中，并返回 true 表示输入串合法。

8.init() 函数用于初始化产生式和预测分析表。

初始化了各个产生式的起始符号、右边字符数组和字符个数。
初始化了预测分析表 analyseTable，将非终结符对应的产生式填入表中。

9.analyse() 函数用于执行分析操作。

获取栈顶字符 stacktop 和输入串第一个字符 userF。
判断栈顶字符是否为终结符，如果是则进行终结符匹配操作。
如果栈顶字符为 #，且输入串字符也为 #，表示输入串已经全部匹配完成，打印当前分析栈和剩余串，并输出 "acc!" 表示分析成功，将 statue 设置为 1 表示分析完成。
如果栈顶字符和输入串字符相等，则进行匹配操作，将指针 frist 向后移动一位，将指针 last 向前移动一位，并将终结符标志 logo 设为 0。
如果栈顶字符和输入串字符不相等，表示匹配失败，将 statue 设置为 2 表示错误状态，打印当前分析栈和剩余串，并输出 "error" 表示错误。
如果栈顶字符不是终结符，进行查表操作。
首先根据栈顶字符找到对应的行号 row。
然后根据输入串字符找到对应的列号 column。
根据行号和列号在预测分析表 analyseTable 中找到对应的产生式 cha。
如果产生式不为空（即 cha.origin 不为 'N'），表示可以继续分析。
打印当前分析栈和剩余串。
输出产生式的左边字符 cha.origin 和右边字符数组 cha.array。
将栈顶字符出栈，根据产生式逆序将字符入栈。
如果产生式右边的第一个字符为 '^'，则将其出栈。
如果产生式为空（即 cha.origin 为 'N'），表示无对应的产生式，说明输入串不符合文法规则，将 statue 设置为 2 表示错误状态，打印当前分析栈和剩余串，并输出 "error" 表示错误。

10.printStack() 函数用于打印分析栈。

首先打印当前分析步骤的序号 proce。
然后遍历分析栈数组 stack1，将栈中的字符逐个输出。

11.printRemainString() 函数用于打印剩余串。

首先打印一定数量的空格以对齐输出。
遍历剩余串数组 stack2，从指针 frist 开始输出剩余的字符。

12.在 main() 函数中进行程序的主要逻辑。

首先进行初始化操作调用 init() 函数。
使用循环获取用户输入的分析串，直到输入合法的分析串为止，调用 input_string() 函数。
将结束符 # 和起始符号 E 分别压入分析栈数组 stack1 中。
使用循环进行分析操作，直到 statue 不为 0。
调用 analyse() 函数执行分析操作。
返回 1，表示程序执行完毕。

这段程序实现了基于LL(1)分析法的语法分析器。通过使用预测分析表和栈来进行自顶向下的语法分析，并且比较栈顶符号和输入串的符号，根据预测分析表中的产生式进行匹配和规约操作，直到分析完成或出现错误。在分析过程中，输出每一步的分析栈、剩余串和所使用的产生式。

2.3.3.1 init()函数

void init(){
    e.origin='E';
    strcpy(e.array,"TG");
    e.length = 2;

    t.origin='T';
    strcpy(t.array,"FS");
    t.length = 2;

    g.origin='G';
    strcpy(g.array,"+TG");
    g.length = 3;

    g1.origin='G';
    g1.array[0]='^';
    g1.length = 1;

    s.origin='S';
    strcpy(s.array,"*FS");
    s.length = 3;

    s1.origin='S';
    s1.array[0]='^';
    s1.length = 1;

    f.origin='F';
    strcpy(f.array,"(E)");
    f.length = 3;

    f1.origin='F';
    f1.array[0]='i';
    f1.length = 1;

    for(int m=0; m<unnumber_zjfu; m++) //初始化分析表
        for(int n=0; n<number_zjfu; n++)
            analyseTable[m][n].origin='N';

    analyseTable[0][0]=e;
    analyseTable[0][3]=e;
    analyseTable[1][1]=g;
    analyseTable[1][4]=g1;
    analyseTable[1][5]=g1;
    analyseTable[2][0]=t;
    analyseTable[2][3]=t;
    analyseTable[3][1]=s1;
    analyseTable[3][2]=s;
    analyseTable[3][4]=s1;
    analyseTable[3][5]=s1;
    analyseTable[4][0]=f1;
    analyseTable[4][3]=f;
}

分析如下：

这里的init() 函数用于初始化语法分析器中的产生式和预测分析表。通过定义了一系列的结构体变量来表示产生式，每个产生式包含三个属性：origin 表示产生式的起始符号，array 表示产生式右边的字符序列，length 表示产生式右边字符序列的长度。

然后，根据文法的产生式规则，为每个结构体变量赋值。具体赋值如下：

e 产生式：起始符号为 E，右边字符序列为 "TG"，长度为 2。
t 产生式：起始符号为 T，右边字符序列为 "FS"，长度为 2。
g 产生式：起始符号为 G，右边字符序列为 "+TG"，长度为 3。
g1 产生式：起始符号为 G，右边字符序列为 "^"，长度为 1。
s 产生式：起始符号为 S，右边字符序列为 "*FS"，长度为 3。
s1 产生式：起始符号为 S，右边字符序列为 "^"，长度为 1。
f 产生式：起始符号为 F，右边字符序列为 "(E)"，长度为 3。
f1 产生式：起始符号为 F，右边字符序列为 "i"，长度为 1。

接下来，通过双重循环初始化预测分析表 analyseTable。循环变量 m 遍历非终结符数组的索引，循环变量 n 遍历终结符数组的索引。每个表格项是一个产生式结构体。将所有表格项的 origin 属性设置为 'N'，表示空，再根据预测分析表中的产生式规则，为表格项赋值。具体赋值如下：

analyseTable[0][0] 赋值为 e 产生式。
analyseTable[0][3] 赋值为 e 产生式。
analyseTable[1][1] 赋值为 g 产生式。
analyseTable[1][4] 和 analyseTable[1][5] 赋值为 g1 产生式。
analyseTable[2][0] 赋值为 t 产生式。
analyseTable[2][3] 赋值为 t 产生式。
analyseTable[3][1] 赋值为 s1 产生式。
analyseTable[3][2] 赋值为s产生式。
analyseTable[3][4] 和 analyseTable[3][5] 赋值为 s1 产生式。
analyseTable[4][0] 赋值为 f1 产生式。
analyseTable[4][3] 赋值为 f 产生式。

这样预测分析表 analyseTable 中的每个表格项都被正确赋值，表示了语法分析中的产生式规则。

2.3.3.2 analyse()函数

void analyse(){
    stacktop = stack1[last]; //获取栈顶字符
    userF = stack2[frist]; //获取用户输入串第一个字符

    int logo = 0; //终结符标志

    for(int j=0; j<number_zjfu; j++){ /*判断是否为终结符*/
        if(stacktop==terminal_array[j]){
            logo=1;
            break;
        }
    }

    if(logo==1){ //如果是终结符
        if(stacktop=='#'&&userF=='#'){   //如果该终结符是#，说明输入串已经全部匹配完成。
            printStack();
            printRemainString();
            statue=1;
            printf("acc!\n");
            return ;
        }
        
        if(stacktop==userF){ //相等则匹配
            printStack();
            printRemainString();
            printf("%c匹配\n",userF);
            frist++;
            last--;
            logo = 0;
        }
        else{
            statue = 2;
            printStack();
            printRemainString();
            printf("error"); //输出产生式
            return;
        }
    }
    else{  //查表
        int row,column;
        for(int j=0; j<unnumber_zjfu; j++){
            if(stacktop==non_terminal_array[j]){
                row = j;  //行号 
                break;
            }
        }
        
        for(int j=0; j<=number_zjfu; j++){
            if(userF==terminal_array[j]){
                column = j;  //列号
                break;
            }
        }
        
        Production cha = analyseTable[row][column];
        if(cha.origin!='N'){ //如果对应的产生式不为空，说明可以继续分析
            printStack();
            printRemainString();
            printf("%c->",cha.origin); //输出产生式
            printf("%s\n",cha.array);
            
            //如果为非终结符，则栈顶的非终结符要去掉
            last--;
            
            for(int j=(cha.length-1); j>=0; j--){ /*产生式逆序入栈*/
                last++;
                stack1[last]=cha.array[j];
            }
            
            if(stack1[last]=='^'){
                last--;
            }
        }
        else{
            //如果对应的产生式为N，则报错。
            statue = 2; //状态为报错状态
            printStack();
            printRemainString();
            printf("error"); //输出产生式
        }
    }
    return ;
}

分析如下：

这里实现了语法分析的核心部分，即根据当前的栈顶符号和输入串的首字符进行分析和匹配。代码先通过以下语句获取栈顶字符和输入串的首字符：

stacktop = stack1[last]; //获取栈顶字符
userF = stack2[frist]; //获取用户输入串第一个字符

接着通过一个循环判断栈顶字符是否为终结符：

int logo = 0; //终结符标志
for(int j=0; j<number_zjfu; j++){  /*判断是否为终结符*/
    if(stacktop==terminal_array[j]){
        logo=1;
        break;
    }
}

如果栈顶字符是终结符，执行以下逻辑：

首先，检查栈顶字符是否为终止符号 #，同时输入串的首字符也是 #。如果是，说明输入串已经全部匹配完成，打印分析栈和剩余串，设置状态为1（acc），输出 "acc!"，然后函数返回。如果栈顶字符和输入串的首字符相等，说明匹配成功，打印分析栈和剩余串，输出当前匹配的终结符号，并更新分析栈和剩余串的指针，即 frist++ 和 last--，并将终结符标志 logo 设置为0，表示不是终结符。如果栈顶字符和输入串的首字符不相等，说明匹配失败，将状态设置为2（error），打印分析栈和剩余串，输出 "error"，然后函数返回。如果栈顶字符不是终结符，执行以下逻辑：首先通过循环找到栈顶字符所在的非终结符的行号 row。然后通过循环找到输入串的首字符所在的终结符的列号 column。接着从预测分析表 analyseTable 中获取对应的产生式 cha，根据行号和列号索引到对应的表格项。如果对应的产生式不为空（即 origin 字段不为 'N'），说明可以继续分析。打印分析栈和剩余串，输出产生式的左部和右部，然后更新分析栈，将产生式的右部逆序入栈。如果对应的产生式为空（即 origin 字段为 'N'），说明发生错误。将状态设置为2（error），打印分析栈和剩余串，输出 "error"。最后，函数返回，继续下一步的分析过程。

2.4 实验心得

通过本次实验，我实现了LL(1)分析法进行语法分析，并认识到LL(1)分析法利用预测分析表和栈来进行符号匹配和产生式的选择，从而推导出输入串的语法结构。

首先，我了解到LL(1)分析法的核心是构建预测分析表。预测分析表由非终结符和终结符构成，通过预测分析表我们可以根据当前的栈顶符号和输入串的首符号，快速确定应该选择的产生式，从而进行语法推导。在实验中，我通过定义非终结符和终结符的数组以及预测分析表的初始化，构建了一个完整的预测分析表。

其次，我认识到LL(1)分析法对文法的要求比较严格，文法必须满足LL(1)文法的条件。LL(1)文法要求每个非终结符的每个产生式的选择集与其他产生式的选择集没有交集，这样才能保证在分析过程中不会出现二义性和回溯。在实验中，我针对给定的文法，仔细检查了每个非终结符的产生式，并根据LL(1)文法的条件进行了调整和修改，确保文法满足LL(1)的要求。

在编写代码的过程中，我深入理解了LL(1)分析法的工作原理。通过构建函数analyse()的代码，我实现了循环的语法分析过程。在每次循环中，根据栈顶字符和输入串的首字符进行匹配，并根据预测分析表选择相应的产生式。通过不断地匹配和产生式的选择，逐步推导出输入串的语法结构。

通过实验，我对LL(1)分析法的应用有了更深刻的理解。我意识到LL(1)分析法在编译原理中的重要性，它可以帮助构建抽象语法树或生成中间代码。