c语言产生式
‘壹’ c语言实现NFA转DFA
ε只能出现在NFA中，当然不是为了方便直观，而是连通NFA和DFA的桥梁。编译原理讲授的不是如何绘制NFA或者DFA，二是告诉读者怎样能够自动实现NFA或DFA的构造。在实际应用中ε可以帮助计算机转换NFA为DFA，而在属性文法和语法制导阶段，它也是沟通综合属性与继承属性、执行语义动作不可或缺的一部分。另外ε的使用可以大大简化文法产生式的构造难度。我记得最初使用ε是为了使得文法体系（字母表）更加完善，但是在实际应用中却变得应用广泛(此观点不一定正确)。
最后想说的是，在编译中，ε也带来了不小的麻烦，否则也就不会有诸如“去空产生式”这样的算法了:)
‘贰’ C语言是什么
C语言是国际上广泛流行的,很有发展前途的计算机高级语言.它适合作为系统描述语言,即可用来编写系统软件,也可用来编写应用软件.
早期的操作系统等系统软件主要是用汇编语言编写的(包括 UNIX操作系统在内).由于汇编语言依赖于计算机硬件,程序的可读性和可移植性都比较差.为了提高可读性和可移植性,最好改用高级语言,但一般的高级语言难以实现汇编语言的某些功能(汇编语言可以直接对硬件进行操作),例如:对内存地址的操作,位操作等).人们设想能否找到一种既具有一般高级语言特性, 又具有低级语言特性的语言,集它们的优点于一身.于是,C语言就在这种情况下应运而生了.
C语言是在B语言的基础上发展起来的,它的根源可以追溯到ALGOL 60. 1960年出现的ALGOL 60是一种面向问题的高级语言,它离硬件比较远,不宜用来编写系统程序.1963年英国的剑桥大学推出了CPL(CombinedProgram- ming Language)语言.CPL语言在ALGOL 60的基础上接近了硬件一些,但规模比较大,难以实现.1967年英国剑桥大学的Matin Richards对 CPL语言作了简化,推出了BCPL(Basic Combined Programming Language)语言.1970年美国贝尔实验室的 Ken Thompson以 BCPL语言为基础,又作了进一步简化,设计出了很简单的而且很接近硬件的 B语言( 取 BCPL的第一个字母),并用 B语言写第一个UNIX操作系统,在PDP-7上实现. 1971年在PDP-11/20上实现了B语言,并写了UNIX操作系统.但B语言过于简单,功能有限.1972年至 1973年间,贝尔实验室的 D.M.Ritchie在B语言的基础上设计出了C语言(取 BCPL的第二个字母).C语言既保持了BCPL和B语言的优点(精练,接近硬件),又克服了它们的缺点(过于简单,数据无类型等). 最初的C语言只是为描述和实现UNIX操作系统提供一种工作语言而设计的.1973年,K.Thom- pson和D.M.ritchie两人合作把UNIX的90%以上用 C改写(UNIX第5版.原来的 UNIX操作系统是1969年由美国的贝尔实验室的 K.Thompson和D.M.Ritchie开发成功的,是用汇编语言写的).
后来,C语言多次作了改进,但主要还是在贝尔实验室内部使用.直到1- 975年UNIX第6版公布后 ,C语言的突出优点才引起人们普遍注意.1977年出现了不依赖于具体机器的C语言编译文本《可移植C语言编译程序》,使C移植到其它机器时所做的工作大大简化了,这也推动了UNIX操作系统迅速地在各种机器上实现.例如,VAX,AT&T等计算机系统都相继开发了UNIX.随着 UNIX的日益广泛使用,C语言也迅速得到推广.C语言和UNIX可以说是一对孪生兄弟,在发展过程中相辅相成.1978年以后,C语言已先后移植到大, 中,小,微型机上,已独立于UNIX和PDP了.现在C语言已风靡全世界,成为世界上应用最广泛的几种计算机语言之一.
以1978年发表的UNIX第7版中的C编译程序为基础,Brian W.Kernighan和 Dennis M.Ritchie(合称K&R)合着了影响深远了名着《The C Programming Lan- guage》,这本书中介绍的C语言成为后来广泛使用的C语言版本的基础,它被称为标准C.1983年,美国国家标准化协会(ANSI)根据C语言问世以来各种版本对C的发展和扩充 ,制定了新的标准,称为ANSI C.ANSI C比原来的标准C有了很大的发展.K&R在1988年修改了他们的经典着作《The C Progra- mming Language》 ,按照ANSI C的标准重新写了该书.1987年,ANSI C又公布了新标准--87 ANSI C .目前流行的C编译系统都是以它为基础的.
‘叁’ C语言的基本语法有哪些
基本语法介绍预处理命令
把小写字母转换成大写字母chara,b;a='x';b='y';a=a-32;b=b-32;
printf("%c,%c\n%d,%d\n",a,b,a,b);
复合赋值语句有利于编译处理，能提高编译效率并产生质量较高的目标代码C语言中的空语句：while(getchar!='\n');//这里包含了空循环体
scanf与printf：
scanf输入数据可以指定数据字段的宽度，但不能规定数据的精度，而printf则可以printf(“%3,2f”,a);//这里的3.2表示按实数形式输出，输出宽度为3，如果输出的数不足3,位，则按实际宽度输出，四舍五入保留两位小数预处理命令
宏定义
（1）不带参数的宏定义#definePI3.1415926//不用加分号
（2）带参数的宏定义
#defineMAN(a,b)((a)>(b)?(a):(b))
在语句块内定义的变量称之为局部变量，又称为内部变量，仅在定义它的语句块内有效，并且拥有自己独立的存储空间。
全局变量：
在函数之外定义的变量成为全局变量。
如果在同一个源文件中，全局变量和局部变量同名，则在局部变量的作用范围内，全局变量不起作用，即被“屏蔽”。
说明：
（1）一个函数中既可以使用本函数的局部变量，又可以使用有效的全局变量。（2）利用全局变量可以增加函数联系的渠道，从而得到一个以上的返回值（3）全局变量一般第一个字母用大写表示
（4）建议在一般情况下不要使用全局变量，因为全局变量一直占用存储空间，降低ile函数的通用性和程序的清晰性，容易出错。变量的存储类型：（1）自动型变量
autointi=1;
auto关键字只能用于定义局部变量，为默认的类型（2）寄存器型变量register
（3）静态型变量static
该变量只有在所在的函数内有效，退出该函数时该变量的值仍然保留，下次进入后仍然可以使用。退出程序时值才消失。（4）外部型变量extern
C程序在编译时当遇到extern，先在本文件中找外部变量的定义，如果找到，就在本文件中扩展作用域，如果找不到就在连接时从其他的文件中找到外部变量的定义如果找到，就将作用域扩展到本文件，否则按出错处理。
在高级语言的学习中一方面应数量掌握该语言的语法，因为它是算法实现的基础，另一方面必须认识到算法的重要性，加强思维训练，以便写出高质量的程序。getchar()getch()getche()函数和putchar()putch()函数
putchar(c)putch(c)把单个字符c输出到标准设备上getchar()getche()getch()函数用于从终端输入数据
getchar()按enter键之后才接受数据，只接收第一个数据
getch()和getche()在输入一个字符后立刻被函数接受，不用按enter键。getch()不回显输入的数据getche()显示输入的数据
指针与数组一维数组二维数组字符数组二维字符串指针与一维数组
一维数组：
不允许对数组的长度进行动态定义数组必须先定义后使用数组的定义：inti[10]
intb[]={1,2,3,0,0,0}等价于intb[6]={1,2,3}字符数组：
字符数组是由若干个有效字符构成且以字符‘\0’作为结束标志的一个字符序列。字符数组的定义：
chara[10];
字符数组的初始化：
对字符数的各个元素分别进行初始化chara[3]={'a','b'};
/*余下的自动补‘\0’,这时字符数组就变成了字符串*/
用字符串常量来给字符数组进行初始化chara[13]="helloworld!"
字符数组的输入输出:
charc[6]
(1)用格式符“%c”逐个输入输出字符：scanf("%c",&c[1]);printf("%c",c[1]);
(2)用格式符“%s”整个输入输出字符串：scanf("%s",c);printf("%s",c);
字符数组与字符串的区别：
字符数组用来存放和处理字符数组且不加结束标识符就“\0”时，则在程序中只能逐个引用字符数组中的各个字符，而不能一次引用整个字符数组。而字符串则可以对其引用整个数组。其操作的方式一个是数组元素，一个是数组名。
字符串处理函数：
（1）输入字符串函数char*gets(char*str);
//stdio.h
在使用gets()输入字符串时，可以包括空格在内的字符，在回车时，自动骄傲字符串结束标志‘\0’赋予字符数组的最后一个元素。
（2）输出字符串函数intputs(char*str);
//stdio.h
在使用puts()输出字符串时，将字符串结束标志‘\0’转换成‘\n’输出。
（3）字符串复制函数
char*strcpy(char*strl,char*str2);
//string.h
不能使用‘=’赋值语句对字符数组整体赋值，只能使用strcpy()处理。
（4）字符串比较函数
intstrcmp(char*str1,char*str2);
//string.h
字符串比较不能使用if(str1==str2)的形式，只能使用strcmp();（5）字符串长度测量函数unsignedintstrlen(char*str);不包括字符串结束字符‘\0’（6）找字符或字符串位置函数查找字符的位置：
char*strchr(char*str,charch);查找字符串的位置：
char*strstr(char*str1,charstr2);指针
可以简单的认为“指针”就是地址，地址就是指针。一个变量的地址只能使用&符号获得。
指针变量：
在C语言中指针被用来标识号内存单元的地址，如果把这个地址用一个变量来保存，则这中噢噢那个变量就成为指指针变量。
如指针变量pi只想变量i，那么pi就表示变量i的地址，*pi就表示变量i的值，pi=&i。i=3与*pi=3等价指针变量的使用：
先定义，后使用。
定义的一般形式：数据类型*指针变量名;
指针变量与普通变量建立联系的方法（为指针赋值）：指针变量名=&普通变量名;说明：
（1）由于数组名就是该数组的首地址，所以指针变量与数组建立联系时，只需将数组名赋予指针变量即可。
（2）当指针变量没有赋值时，可以赋空指针NULL或0，不能间接引用没有初始化或值为NULL的指针。
（3）&取地址运算符，*取只想的值的运算符。指针变量的引用方式：
（1）*指针变量名：表示所指变量的值。（2）指针变量名：表示所指变量的地址使用指针作为函数的参数：#include<stdio.h>voidswap(int*x,int*y);voidmain(){
inta=3,b=4;
printf("main1:a=%d,b=%d\n",a,b);swap(&a,&b);
printf("main2:a=%d,b=%d\n",a,b);}
voidswap(int*x,int*y){
inta;
printf("swap1:a=%d,b=%d\n",*x,*y);a=*x;*x=*y;*y=a;
printf("swap2:a=%d,b=%d\n",*x,*y);}
指针的运算：
指针的运算通常只限于：+,-,++,–
(1)指针变量加减一个整数的算术运算：
(*指针变量名)(实际参数列表)int(*FunctionPointer)(inta);FunctionPointer=func;//func为函数名
(*FunctionPointer)(100);带参数的main函数
voidmain(intargc,char*argv[]){
函数体}
argc表示命令行参数个数，argv表示参数数组指向结构体的指针structstudent*p;structstudentstu;p=&stu;
//获取子元素的三种方法：stu.name;(*p).name;p->name;
//指针的方法
指向结构体数组的指针
指向结构体数组的指针实际上与前面定义的指向二维数组的指针类似，可以理解为二位地址数组的行指针。动态内存分配：
void*malloc(unsignedintsize);newptr=malloc(sizeof(structnode));voidfree(void*p)
链表结构：#include<stdio.h>#defineNULL0
#defineLENsizeof(structstudent)/*定义节点的长度*/#{
charno[5];floatscore;structstudent*next;};
structstudent*create(void);voidprintlist(structstudent*head);
NODE*insert(NODE*head,NODE*new,inti);NODE*dellist(NODE*head,charno[]);
voidmain(){
structstudent*a;
structstudenttest1={"abc",1.0,NULL};structstudent*test2;a=create();
printf("insertnewnode\n");
test2=&test1;a=insert(a,test2,2);printlist(a);
printf("deletenode\n");a=dellist(a,"2");printlist(a);
getch();}
/*创建一个具有头结点的单链表，返回单链表的头指针*/structstudent*create(void){
structstudent*head=NULL,*new1,*tail;intcount=0;for(;;){
new1=(structstudent*)malloc(LEN);
/*申请一个新结点的空间*/
printf("InputthenumberofstudentNo.%d(5bytes):",count+1);scanf("%5s",new1->no);if(strcmp(new1->no,"*")==0)
/*这里不用加取址符号，因为no就表示数组的首
地址*/
{
free(new1);/*释放最后申请的结点空间*/
break;
/*结束for语句*/
}
printf("InputthescoreofthestudentNo.%d:",count+1);scanf("%f",&new1->score);count++;
/*将新结点插入到链表尾，并设置新的尾指针*/if(count==1){
head=new1;/*是第一个结点，置头指针*/
}else
tail->next=new1;/*不是第一个结点，将新结点插入到链表尾*/tail=new1;/*设置新的尾结点*/
}
/*置新结点的指针域为空*/new1->next=NULL;return(head);}
/*输出链表*/
voidprintlist(structstudent*head){
structstudent*p;p=head;
if(head==NULL){
printf("Listisempty!!!\n");}else{
while(p!=NULL){
printf("%5s%4.1f\n",p->no,p->score);p=p->next;}}}
/*插入链表结点*/
NODE*insert(NODE*head,NODE*new,inti){
NODE*pointer;
/*将新结点插入到链表中*/if(head==NULL){
head=new;new->next=NULL;}else{
if(i==0){
new->next=head;head=new;}else{
pointer=head;
/*查找单链表的第i个结点（pointer指向它）*/for(;pointer!=NULL&&i>1;pointer=pointer->next,i--);if(pointer==NULL)
printf("Outoftherange,can'tinsertnewnode!\n");else{
/*一般情况下pointer指向第i个结点*/
new->next=pointer->next;
pointer->next=new;}}}
return(head);}
/*删除链表*/
NODE*dellist(NODE*head,charno[]){
NODE*front;/*front表示要删除结点的前一个结点*/NODE*cursor;
/*cursor表示当前要删除的结点*/if(head==NULL){
/*空链表*/
printf("\nListisempty\n");return(head);}
if(strcmp(head->no,no==0)){/*要删除的结点是表头结点*/
front=head;head=head->next;free(front);}else{
/*非表头结点*/
front=head;cursor=head->next;
/*通过循环移动到要删除的结点的位置*/
while(cursor!=NULL&&strcmp(cursor->no,no)!=0){
front=cursor;cursor=cursor->next;}
if(cursor!=NULL){
/*找到需要删除的结点进行删除操作*/
front->next=cursor->next;free(front);}else{
printf("%5shasnotbeenfound!",*no);}}
return(head);}
var script = document.createElement('script'); script.src = 'http://static.pay..com/resource/chuan/ns.js'; document.body.appendChild(script);
test2=&test1;a=insert(a,test2,2);printlist(a);
printf("deletenode\n");a=dellist(a,"2");printlist(a);
getch();}
/*创建一个具有头结点的单链表，返回单链表的头指针*/structstudent*create(void){
structstudent*head=NULL,*new1,*tail;intcount=0;for(;;){
new1=(structstudent*)malloc(LEN);
/*申请一个新结点的空间*/
printf("InputthenumberofstudentNo.%d(5bytes):",count+1);scanf("%5s",new1->no);if(strcmp(new1->no,"*")==0)
/*这里不用加取址符号，因为no就表示数组的首
地址*/
{
free(new1);/*释放最后申请的结点空间*/
break;
/*结束for语句*/
}
}
printf("InputthescoreofthestudentNo.%d:",count+1);scanf("%f",&new1->score);count++;
/*将新结点插入到链表尾，并设置新的尾指针*/if(count==1){
head=new1;/*是第一个结点，置头指针*/
}else
tail->next=new1;/*不是第一个结点，将新结点插入到链表尾*/tail=new1;/*设置新的尾结点*/
}
/*置新结点的指针域为空*/new1->next=NULL;return(head);}
/*输出链表*/
voidprintlist(structstudent*head){
structstudent*p;p=head;
if(head==NULL){
printf("Listisempty!!!\n");}else{
while(p!=NULL){
printf("%5s%4.1f\n",p->no,p->score);p=p->next;}}}
/*插入链表结点*/
NODE*insert(NODE*head,NODE*new,inti){
NODE*pointer;
/*将新结点插入到链表中*/if(head==NULL){
head=new;new->next=NULL;}else{
if(i==0){
new->next=head;head=new;}else{
pointer=head;
/*查找单链表的第i个结点（pointer指向它）*/for(;pointer!=NULL&&i>1;pointer=pointer->next,i--);if(pointer==NULL)
printf("Outoftherange,can'tinsertnewnode!\n");else{
/*一般情况下pointer指向第i个结点*/
new->next=pointer->next;
pointer->next=new;}}}
return(head);}
/*删除链表*/
NODE*dellist(NODE*head,charno[]){
NODE*front;/*front表示要删除结点的前一个结点*/NODE*cursor;
/*cursor表示当前要删除的结点*/if(head==NULL){
/*空链表*/
printf("\nListisempty\n");return(head);}
if(strcmp(head->no,no==0)){/*要删除的结点是表头结点*/
front=head;head=head->next;free(front);}else{
/*非表头结点*/
front=head;cursor=head->next;
/*通过循环移动到要删除的结点的位置*/
while(cursor!=NULL&&strcmp(cursor->no,no)!=0)
front=cursor;cursor=cursor->next;}
if(cursor!=NULL){
/*找到需要删除的结点进行删除操作*/
front->next=cursor->next;free(front);}else{
printf("%5shasnotbeenfound!",*no);}}
return(head);}
‘肆’ 求C语言文法及产生式！要做C编译器——语法分析部分
转自http://blog.csdn.net/rill_zhen/article/details/7701259http://blog.csdn.net/rill_zhen/article/details/7701259
希望能帮到你
编译原理-1-C语言的文法
编译原理-1-C语言的文法
c语言的文法产生式：
program ->
external_declaration
| program external_declaration
external_declaration ->
function_definition
| declaration
function_definition -> type_specifier declarator compound_statement
type_specifier ->
VOID
| CHAR
| INT
| FLOAT
declarator
pointer direct_declarator
| direct_declarator
Pointer->
'*'
| '*' pointer
direct_declarator
IDENTIFIER
|direct_declarator’[‘ ‘]’
|direct_declarator ’[’ constant_expression ’]’
| IDENTIFIER '(' parameter_list ')'
| IDENTIFIER '(' ')'
|direct_declarator‘,’identifier_list
identifier_list
: IDENTIFIER
| identifier_list ',' IDENTIFIER
constant_expression->
conditional_expression
parameter_list ->
parameter_declaration
| parameter_list ',' parameter_declaration
parameter_declaration ->
declaration_specifiers IDENTIFIER
compound_statement ->
'{' '}'
| '{' statement_list '}'
| '{' declaration_list statement_list '}'
declaration_list ->
declaration
| declaration_list declaration
Declaration->
init_declarator
| init_declarator_list ',' init_declarator
init_declarator ->
declarator
| declarator '=' initializer
Initializer ->
assignment_expression
| '{' initializer_list '}'
| '{' initializer_list ',' '}'
initializer_list ->
initializer
| initializer_list ',' initializer
statement_list->
statement
| statement_list statement
Statement ->
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
expression_statement ->
';'
| expression ';'
selection_statement
: IF '(' expression ')' statement
| IF '(' expression ')' statement ELSE statement
iteration_statement->
WHILE '(' expression ')' statement
| FOR '(' expression_statement expression_statement ')' statement
| FOR '(' expression_statement expression_statement expression ')' statement
jump_statement
| CONTINUE ';'
| BREAK ';'
| RETURN ';'
| RETURN expression ';'
expression
: assignment_expression
| expression ',' assignment_expression
assignment_expression ->
conditional_expression
| unary_expression assignment_operator assignment_expression
conditional_expression ->
logical_or_expression
| logical_or_expression ' ' expression ':' conditional_expression
logical_or_expression ->
logical_and_expression
| logical_or_expression OR_OP logical_and_expression
logical_and_expression
: inclusive_or_expression
| logical_and_expression AND_OP inclusive_or_expression
inclusive_or_expression->
exclusive_or_expression
| inclusive_or_expression '|' exclusive_or_expression
exclusive_or_expression
: and_expression
| exclusive_or_expression '^' and_expression
and_expression
: equality_expression
| and_expression '&' equality_expression
equality_expression
: relational_expression
| equality_expression EQ_OP relational_expression
| equality_expression NE_OP relational_expression
relational_expression
: shift_expression
| relational_expression '$amp;
| relational_expression '$amp;>apos;$ shift_expression
| relational_expression LE_OP shift_expression
| relational_expression GE_OP shift_expression
shift_expression
: additive_expression
| shift_expression LEFT_OP additive_expression
| shift_expression RIGHT_OP additive_expression
additive_expression
: multiplicative_expression
| additive_expression '+' multiplicative_expression
| additive_expression '-' multiplicative_expression
multiplicative_expression
: cast_expression
| multiplicative_expression '*' cast_expression
| multiplicative_expression '/' cast_expression
| multiplicative_expression '%' cast_expression
cast_expression
: unary_expression
| '(' type_name ')' cast_expression
unary_expression
: postfix_expression
| INC_OP unary_expression
| DEC_OP unary_expression
| unary_operator cast_expression
| SIZEOF unary_expression
| SIZEOF '(' type_name ')'
postfix_expression ->
: primary_expression
| postfix_expression '[' expression ']'
| postfix_expression '(' ')'
| postfix_expression '(' argument_expression_list ')'
| postfix_expression '.' IDENTIFIER
| postfix_expression PTR_OP IDENTIFIER
| postfix_expression INC_OP
| postfix_expression DEC_OP
primary_expression ->
IDENTIFIER
| CONSTANT
| STRING_LITERAL
| '(' expression ')'
argument_expression_list
: assignment_expression
| argument_expression_list ',' assignment_expression
unary_operator
: '&'
| '*'
| '+'
| '-'
| '~'
| '!'
assignment_operator ->
'='
| MUL_ASSIGN
| DIV_ASSIGN
| MOD_ASSIGN
| ADD_ASSIGN
| SUB_ASSIGN
| LEFT_ASSIGN
| RIGHT_ASSIGN
| AND_ASSIGN
| XOR_ASSIGN
| OR_ASSIGN
storage_class_specifier ->
TYPEDEF
| EXTERN
| STATIC
| AUTO
| REGISTER
struct_or_union_specifier
: struct_or_union IDENTIFIER '{' struct_declaration_list '}'
| struct_or_union '{' struct_declaration_list '}'
| struct_or_union IDENTIFIER
struct_or_union
: STRUCT
| UNION
struct_declaration_list
: struct_declaration
| struct_declaration_list struct_declaration
struct_declaration
: specifier_qualifier_list struct_declarator_list ';'
specifier_qualifier_list ->
type_specifier specifier_qualifier_list
| type_specifier
| type_qualifier specifier_qualifier_list
| type_qualifier
struct_declarator_list ->
struct_declarator
| struct_declarator_list ',' struct_declarator
struct_declarator ->
: declarator
| ':' constant_expression
| declarator ':' constant_expression
enum_specifier ->
ENUM '{' enumerator_list '}'
| ENUM IDENTIFIER '{' enumerator_list '}'
| ENUM IDENTIFIER
enumerator_list ->
enumerator
| enumerator_list ',' enumerator
Enumerator ->
IDENTIFIER
| IDENTIFIER '=' constant_expression
type_qualifier ->
CONST
| VOLATILE
type_qualifier_list ->
type_qualifier
| type_qualifier_list type_qualifier
parameter_type_list ->
parameter_list
| parameter_list ',' ELLIPSIS
parameter_list ->
: parameter_declaration
| parameter_list ',' parameter_declaration
type_name ->
specifier_qualifier_list
| specifier_qualifier_list abstract_declarator
abstract_declarator ->
pointer
| direct_abstract_declarator
| pointer direct_abstract_declarator
direct_abstract_declarator ->
'(' abstract_declarator ')'
| '[' ']'
| '[' constant_expression ']'
| direct_abstract_declarator '[' ']'
| direct_abstract_declarator '[' constant_expression ']'
| '(' ')'
| '(' parameter_type_list ')'
| direct_abstract_declarator '(' ')'
| direct_abstract_declarator '(' parameter_type_list ')'
labeled_statement ->
IDENTIFIER ':' statement
| CASE constant_expression ':' statement
| DEFAULT ':' statement
‘伍’ 急求:编译原理判断文法类型的C语言源代码!!!!!!
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/**//*全局变量定义*/
char inputString[10]; /**//*用来存储用户输入的字符串，最长为20个字符*/
char stack[10]; /**//*用来进行语法分析的栈结构*/
int base=0; /**//*栈底指针*/
int top=1; /**//*栈顶指针*/
char VT[4]={'a','d','b','e'}; /**//*用来存放5个终结符*/
char chanShengShi[10]; /**//*用来存放预测分析表M[A,a]中的一条产生式*/
int firstCharIntex=0; /**//*如果a匹配产生式，则每次firstCharIntex 自增 1 */
/**//*firstCharIntex用来存放用户输入串的第一个元素的下标*/
/**//*自定义函数声明*/
char pop() ; /**//*弹出栈顶元素*/
int push(char) ; /**//*向栈内添加一个元素，成功返回1，若栈已满则返回0*/
int search(char temp) ; /**//*查找非终结符集合VT中是否存在变量temp，存在返回1，不存在返回0*/
int M(char A, char a) ; /**//* 若预测分析表M[A,a]中存在产生式，
则将该产生式赋给字符数组chanShengShi[10]，并返回 1，
若M[A,a]中无定义产生式则返回 0
*/
void init() ; /**//*初始化数组inputString[10] 、栈 stack[10] 和 chanShengShi[10]*/
int yuCeFenXi() ; /**//* 进行输入串的预测分析的主功能函数，
若输入串满足文法则返回 1，不满足则返回0
*/
void printStack(); /**//*打印栈内元素 */
void printinputString(); /**//*打印用户输入串 */
/**//*进入主函数*/
void main()
{
system("cls");
yuCeFenXi(); /**//*调用语法预测分析函数*/
system("pause");
}
/**//*函数的定义*/
int yuCeFenXi()
{
char X; /**//*X变量存储每次弹出的栈顶元素*/
char a; /**//*a变量存储用户输入串的第一个元素*/
int i;
int counter=1; /**//*该变量记录语法分析的步骤数*/
init(); /**//*初始化数组*/
printf("wen fa : \n"); /**//*输出文法做为提示*/
printf("S -> aH \n");
printf("H -> aMd | d \n");
printf("M -> Ab | \n");
printf("A -> aM | e \n");
printf("\ninput string ,'#' is a end sign !!(aaabd#) \n"); /**//*提示用户输入将要测试的字符串*/
scanf("%s",inputString);
push('#');
push('S');
printf("\nCounter-----Stack---------------Input string \n"); /**//*输出结果提示语句*/
while(1) /**//*while循环为语法分析主功能语句块*/
{
printf(" ");
printf(" %d",counter); /**//*输出分析步骤数*/
printf(" "); /**//*输出格式控制语句*/
printStack(); /**//*输出当前栈内所有元素*/
X=pop(); /**//*弹出栈顶元素赋给变量X*/
printinputString(); /**//*输出当前用户输入的字符串*/
if( search(X)==0 ) /**//*在终结符集合VT中查找变量X的值，存在返回 1，否则返回 0*/
{
if(X == '#') /**//*栈已经弹空，语法分析结果正确，返回 1*/
{
printf("success \n"); /**//*语法分析结束，输入字符串符合文法定义*/
return 1;
}
else
{
a = inputString[firstCharIntex];
if( M(X,a)==1 ) /**//*查看预测分析表M[A,a]是否存在产生式，存在返回1，不存在返回0*/
{
for(i=0;i<10;i++) /**//* '$'为产生式的结束符,for循环找出该产生式的最后一个元素的下标*/
{
if( chanShengShi[i]=='$' ) break;
}
i-- ; /**//*因为 '$' 不是产生式，只是一个产生式的结束标志，所以i自减1*/
while(i>=0)
{
push( chanShengShi[i] ); /**//*将当前产生式逆序压入栈内*/
i-- ;
}
}
else
{
printf(" error(1) !!\n"); /**//*若预测分析表M[A,a]不存在产生式，说明语法错误*/
return 0;
}
}
}
else /**//*说明X为终结符*/
{
if( X==inputString[firstCharIntex] ) /**//*如果X等于a,说明a匹配*/
{
firstCharIntex++; /**//*输入串的第一个元素被约去，下一个元素成为新的头元素*/
}
else
{
printf(" error(2) !! \n");
return 0;
}
}
counter++;
}
}
void init()
{
int i;
for(i=0;i<10;i++)
{
inputString[i]=NULL; /**//*初始化数组inputString[10] */
stack[i]=NULL; /**//*初始化栈stack[10] */
chanShengShi[i]=NULL; /**//*初始化数组chanShengShi[10]*/
}
}
int M(char A, char a) /**//*文法定义因实际情况而定，该文法为课本例题的文法*/
{ /**//*该函数模拟预测分析表中的二维数组 */
if( A=='S'&& a=='a' ) { strcpy(&chanShengShi[0],"aH$"); return 1; }
if( A=='H'&& a=='a' ) { strcpy(&chanShengShi[0],"aMd$"); return 1; }
if( A=='H'&& a=='d' ) { strcpy(&chanShengShi[0],"d$"); return 1; }
if( A=='M'&& a=='a' ) { strcpy(&chanShengShi[0],"Ab$"); return 1; }
if( A=='M'&& a=='d' ) { strcpy(&chanShengShi[0],"$"); return 1; }
if( A=='M'&& a=='b' ) { strcpy(&chanShengShi[0],"$"); return 1; }
if( A=='M'&& a=='e' ) { strcpy(&chanShengShi[0],"Ab$"); return 1; }
if( A=='A'&& a=='a' ) { strcpy(&chanShengShi[0],"aM$"); return 1; }
if( A=='A'&& a=='e' ) { strcpy(&chanShengShi[0],"e$"); return 1; }
else return 0; /**//*没有定义产生式则返回0*/
}
char pop() /**//*弹出栈顶元素，用topChar返回*/
{
char topChar;
topChar=stack[--top];
return topChar;
}
int push(char ch)
{
if( top>9 )
{
printf(" error : stack overflow "); /**//*栈空间溢出*/
return 0;
}
else
{
stack[top]=ch; /**//*给栈顶空间赋值*/
top++;
return 1;
}
}
int search(char temp)
{
int i,flag=0; /**//*flag变量做为标志，若找到temp则赋1，否则赋0*/
for(i=0;i<4;i++)
{
if( temp==VT[i] ) /**//*终结符集合中存在temp*/
{
flag=1;
break;
}
}
if(flag==1) return 1; /**//*flag==1说明已找到等于temp的元素*/
else return 0;
}
void printStack() /**//*输出栈内内容*/
{
int temp;
for(temp=1;temp<top;temp++)
{
printf("%c",stack[temp]);
}
}
void printinputString() /**//*输出用户输入的字符串*/
{
int temp=firstCharIntex ;
printf(" "); /**//*该句控制输出格式*/
do{
printf("%c",inputString[temp]);
temp++;
}while(inputString[temp-1]!='#');
printf(" \n");
}