程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 深入淺出編譯原理

深入淺出編譯原理

編輯:關於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; 
    } 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved