深入浅出编译原理-5-一个简单语法分析器的C语言实现

引言

前面已经介绍了编译器的预处理，词法分析，词法分析器的实现，也在其中说到了语法分析的任务和过程。

语法分析的输入是词法单元序列，然后根据语言的文法表示（展开式），利用有限状态机理论，生成抽象语法树，然后遍历得到中间代码，即，三地址码。本节就以一个实验的方式，来看一下，语法分析器的内在实现机制。

5.1实验描述

编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。

利用C语言编制递归下降分析程序，并对简单语言进行语法分析。

5.1.1 待分析的简单语言的语法

用扩充的BNF表示如下：

⑴<程序>：：=begin<语句串>end

⑵<语句串>：：=<语句>{；<语句>}

⑶<语句>：：=<赋值语句>

⑷<赋值语句>：：=ID：=<表达式>

⑸<表达式>：：=<项>{+<项> | -<项>}

⑹<项>：：=<因子>{*<因子> | /<因子>

⑺<因子>：：=ID | NUM | （<表达式>）

5.1..2 实验要求说明

输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。

例如：

输入 begin a:=9; x:=2*3; b:=a+x end #

输出 success！

输入 x:=a+b*c end #

输出 error

5.2 C语言代码实现

核心思想就是，从开始状态开始，按照文法展开式，逐级进行状态分析，直到分析完毕，如果在此期间出现状态不匹配，即语法错误，停止分析。当然在实际的语法分析器要有错误恢复机制，以发现其他的语法错误。即，一次报告多个语法错误。这里需要说明的是，要想实现语法分析，必须先有词法分析，所以，这段代码包含了上一节的内容，词法分析部分。

[html]
#include "stdio.h"
#include "string.h"

char prog[100],token[8],ch;
char *rwtab[6]={"begin","if","then","while","do","end"};
int syn,p,m,n,sum;
int kk;

void factor(void);
void expression(void);
void yucu(void);
void term(void);
void statement(void);
void lrparser(void);
void scaner(void);

int main(void)
{
    p=kk=0;
    printf("\nplease input a string (end with '#'): \n");

    do
    {
        scanf("%c",&ch);
        prog[p++]=ch;
    }while(ch!='#');

    p=0;
    scaner();
    lrparser();
    //getch();
}

void lrparser(void)
{
    if(syn==1)
    {
        scaner();       /*读下一个单词符号*/
        yucu();     /*调用yucu()函数；*/

        if(syn==6)
        {
            scaner();
            if((syn==0)&&(kk==0))
            printf("success!\n");
        }
        else
        {
            if(kk!=1) printf("the string haven't got a 'end'!\n");
            kk=1;
        }
    }
    else
    {
        printf("haven't got a 'begin'!\n");
        kk=1;
    }

    return;
}

void yucu(void)
{
    statement();         /*调用函数statement();*/

    while(syn==26)
    {
        scaner();          /*读下一个单词符号*/
        if(syn!=6)
            statement();         /*调用函数statement();*/
    }

    return;
}

void statement(void)
{
    if(syn==10)
    {
        scaner();        /*读下一个单词符号*/
        if(syn==18)
        {
            scaner();      /*读下一个单词符号*/
            expression();      /*调用函数statement();*/
        }
        else
        {
            printf("the sing ':=' is wrong!\n");
            kk=1;
        }
    }
    else
    {
        printf("wrong sentence!\n");
        kk=1;
    }

    return;
}

void expression(void)
{
    term();

    while((syn==13)||(syn==14))
    {
        scaner();             /*读下一个单词符号*/
        term();               /*调用函数term();*/
    }

    return;
}

void term(void)
{
    factor();

    while((syn==15)||(syn==16))
    {
        scaner();             /*读下一个单词符号*/
&nbs

补充：软件开发 , C语言 ,