深入浅出编译原理-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语言代码实现

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

#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;}elseswitch(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;}}

5.3小结

语法分析的核心工作就是：从开始状态开始，利用有限状态机理论，根据语言的文法展开式，进行状态分析，得到语法树。然后进而生成中间代码（三地址码），为后面的汇编做好准备。本小节的内容只是进行状态分析。但对理解语法分析器有很大帮助。代码的具体流程图，读者可自己画一下，其中味道，可意不可言......