你好,欢迎来到电脑编程技巧与维护杂志社! [免费注册][请登录 杂志社简介广告服务读者反馈编程社区  
合订本订阅
 
 
您的位置:技术专栏 / C专栏
深入浅出编译原理-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();             /*读下一个单词符号*/ 
        factor();              /*调用函数factor(); */ 
    } 
     
    return; 

 
void factor(void) 
{  
    if((syn==10)||(syn==11)) 
    { 
        scaner(); 
    } 
    else if(syn==27) 
    {  
        scaner();           /*读下一个单词符号*/ 
        expression();        /*调用函数statement();*/ 
 
        if(syn==28) 
        { 
            scaner();          /*读下一个单词符号*/ 
        } 
        else  
        { 
            printf("the error on '('\n"); 
            kk=1; 
        } 
    } 
    else 
    {  
        printf("the expression error!\n"); 
        kk=1; 
    } 
     
    return; 

void scaner(void) 

    sum=0; 
 
    for(m=0;m<8;m++) 
        token[m++]=NULL; 
     
    m=0; 
    ch=prog[p++]; 
     
    while(ch==' ') 
        ch=prog[p++]; 
     
    if(((ch<='z')&&(ch>='a'))||((ch<='Z')&&(ch>='A'))) 
    {  
        while(((ch<='z')&&(ch>='a'))||((ch<='Z')&&(ch>='A'))||((ch>='0')&&(ch<='9'))) 
        { 
            token[m++]=ch; 
            ch=prog[p++]; 
        } 
        p--; 
        syn=10; 
        token[m++]='\0'; 
        for(n=0;n<6;n++) 
        if(strcmp(token,rwtab[n])==0) 
        { 
            syn=n+1; 
            break; 
        } 
    } 
    else if((ch>='0')&&(ch<='9')) 
    { 
        while((ch>='0')&&(ch<='9')) 
        {  
            sum=sum*10+ch-'0'; 
            ch=prog[p++]; 
        } 
        p--; 
        syn=11; 
    } 
    else 
    switch(ch) 
    { 
        case '<': 
            m=0; 
            ch=prog[p++]; 
            if(ch=='>') 
            {  
                syn=21; 
            } 
            else if(ch=='=') 
            {  
                syn=22; 
            } 
            else 
            {  
                syn=20; 
                p--; 
            } 
        break; 
         
        case '>': 
            m=0; 
            ch=prog[p++]; 
            if(ch=='=') 
            {  
                syn=24; 
            } 
            else 
            { 
                syn=23; 
                p--; 
            } 
        break; 
         
        case ':': 
            m=0; 
            ch=prog[p++]; 
            if(ch=='=') 
            { 
                syn=18; 
            } 
            else 
            { 
                syn=17; 
                p--; 
            } 
            break; 
             
        case '+': 
            syn=13; 
        break; 
         
        case '-':  
            syn=14; 
        break; 
         
        case '*': 
            syn=15; 
        break; 
         
        case '/':  
            syn=16; 
        break; 
         
        case '(':  
            syn=27; 
        break; 
         
        case ')':  
            syn=28; 
        break; 
         
        case '=': 
            syn=25; 
        break; 
         
        case ';':  
            syn=26; 
        break; 
         
        case '#': 
            syn=0; 
        break; 
         
        default: 
            syn=-1; 
        break; 
    } 

  推荐精品文章

·2019年12月目录 
·2019年11月目录 
·2019年10月目录
·2019年9月目录 
·2019年8月目录
·2019年7月目录
·2019年6月目录
·2019年5月目录
·2019年4月目录    
·2019年3月目录   
·2019年2月目录   
·2019年1月目录  
·探析云计算下应用软件用户数据安全问题
·地理空间集束线可视化表达

  联系方式
TEL:010-82561037
Fax: 010-82561614
QQ: 100164630
Mail:gaojian@comprg.com.cn

  友情链接
 
Copyright 2001-2010, www.comprg.com.cn, All Rights Reserved
京ICP备14022230号-1,电话/传真:010-82561037 82561614 ,Mail:gaojian@comprg.com.cn
地址:北京市海淀区长春桥路5号6号楼1209室,邮编:100089