编译原理文法语言递归兑现

编译原理文法语言递归实现

   今天做了一道题，感觉比较有意思，就是编译原理里面的。刚好也总结回顾一下编译原理方面的知识

   文法语言：一共分为四类,0,1,2,3型

  文法G为一个四元组，G=（Vn,Vt,P,S）,其中Vn,Vt分别为非空有限的非终结符和终结符号集，Vn交Vt为空集

P为产生式集，S为文法识别符号或开始符号

    1     0型文法

      A ->B 其中A为 终结符解和非终结符集组成  B为终结符集和非终结符集和空集组成

                  A，B不做任何限制。又称短语结构文法，它的能力相当于图灵机

    2     1型文法（上下文有关文法）

       如果文法G的产生式具有以下形式

   A->B 其中   A = r1Fr2 ;B=r1Xr2; r1,r2是终结符或非终结符组成的符号， A属于非终结符，X为终结符和非终结符的并集

   上面的例2.2就是一个1型文法

  3    2型文法（上下文无关文法）

       也就是将1型文法中的r1和r2同时去掉，就是不收上下文的影响。

       2型文法产生式的左部是单个非终结符，右部是由终结符和非终结符组成的符号串。

4     3型文法（右线性文法或正规文法）

    是对2型文法添加限制，产生式右部由单一终结符或单一终结符和单一非终结符组成

今天这道题目描述主要是使用递归来解决

#include "stdio.h"#define MAX 1024 int index;int error;void algor(char *str);char scanner(char *str){return str[index];} void U(char *str){char c;c=scanner(str);index+=1;switch(c){case 'd':algor(str);break;case 'b':U(str);break;case 'e':break;default :error=1;break;}}void algor(char *str){char c;c=scanner(str);switch(c){case '(':index+=1;U(str);c=scanner(str);index+=1;if(c!=')'){error=1;}break;case 'a':index+=1;U(str);c=scanner(str);index+=1;if(c!='b'){error=1;} break;default:index+=1;error=1;break;} if(str[index]=='\0'){return;}}int main(){int testCase;char *str;scanf("%d",&testCase);str = (char *)malloc(sizeof(char)*MAX);while(testCase--){scanf("%s",str);index=0;error=0;algor(str);if(error==0){printf("Yes.\n");} else{printf("No.\n");}} free(str);return 0;}
其实如果不了解文法的含义，单纯的通过题目描述使用递归，也是比较容易处理的~