词法分析及词法分析程序

编译原理词法分析与语法分析的核心算法编译原理是计算机科学与技术领域中的一门重要课程。

在编程中，我们常常需要将高级语言编写的程序翻译成机器语言，使计算机能够理解并执行我们编写的程序。

而编译原理中的词法分析和语法分析是编译器的两个核心算法。

一、词法分析词法分析是编译器的第一个阶段，它负责将输入的字符序列（源代码）划分为一个个的有意义的词素（Token），并生成相应的词法单元（Lexeme）。

词法分析的核心算法主要包括以下两个步骤：1. 正则表达式到有限自动机的转换：正则表达式是一种描述字符串匹配模式的表达式，它可以用来描述词法分析中各种词素的规则。

而有限自动机则是一种用来识别或匹配正则表达式所描述的模式的计算模型。

将正则表达式转换为有限自动机是词法分析的关键步骤之一。

2. 词法分析器的生成：在将正则表达式转换为有限自动机后，我们可以使用生成器工具（如Lex、Flex等）来生成词法分析器。

词法分析器可以按照预定的规则扫描源代码，并将识别出的词素转换成相应的词法单元，供后续的语法分析使用。

二、语法分析语法分析是编译器的第二个阶段，它负责分析和处理词法分析阶段生成的词法单元序列，并根据预定的语法规则确定语法正确的序列。

语法分析的核心算法主要包括以下两个步骤：1. 上下文无关文法的定义：上下文无关文法（Context-Free Grammar，简称CFG）是一种用于描述形式语言的文法。

它由一组产生式和终结符号组成，可以用于描述语法分析中的语法规则。

在语法分析中，我们需要根据具体编程语言的语法规则，编写相应的上下文无关文法。

2. 语法分析器的生成：通过使用生成器工具（如Yacc、Bison等），我们可以根据上下文无关文法生成语法分析器。

语法分析器可以根据预先定义的文法规则，对词法单元序列进行分析，并构建出语法树（Parse Tree）供后续的语义分析和代码生成使用。

综上所述，词法分析与语法分析是编译原理中的两个重要阶段，也是实现编译器的核心算法。

词法分析程序⼀、词法分析程序功能：词法分析器的功能为输⼊源程序，按照构词规则分解成⼀系列单词符号。

单词是语⾔中具有独⽴意义的最⼩单位，包括关键字、标识符、运算符、界符和常量等(1) 关键字是由程序语⾔定义的具有固定意义的标识符。

例如，Pascal 中的begin，end，if，while都是保留字。

这些字通常不⽤作⼀般标识符。

(2) 标识符⽤来表⽰各种名字，如变量名，数组名，过程名等等。

(3) 常数常数的类型⼀般有整型、实型、布尔型、⽂字型等。

(4) 运算符如+、-、*、/等等。

(5) 界符如逗号、分号、括号、等等。

⼆、符号与种别码对照表三、代码实现：#include <stdio.h>#include <stdlib.h>#include <string.h>#define SIZE 100char prog[SIZE],ch,token[8];int p=0,syn,n,i;char *keyword[6]={"begin","then","if","while","do","end"};//定义关键字数组void scaner();void main(){int select=-1;p=0;printf("请输⼊源程序字符串（以'#'结束）：\n");do{ch=getchar();prog[p++]=ch;}while(ch!='#');p=0;do{scaner();switch(syn){case -1:printf("词法分析出错\n");break;default :printf("<%d,%s>\n",syn,token);break;}}while(syn!=0);printf("词法分析成功\n");getchar();}void scaner(){for(n=0;n<8;n++){token[n]='\0';}n=0;ch=prog[p++];while(ch==''){ch=prog[p++];}if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){do{token[n++]=ch;ch=prog[p++];}while((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'));syn=10;for(n=0;n<6;n++)//在六个关键字中对⽐{if(strcmp(token,keyword[n])==0)syn=n+1;}p--;}else if(ch>='0'&&ch<='9')//判断输⼊的是否为整数常数{p--;do{token[n++]=prog[p++];ch=prog[p];}while(ch>='0'&&ch<='9');syn=11;return;}else{switch(ch){case'+':syn=13;token[0]=ch;break;case'-':syn=14;token[0]=ch;break;case'*':syn=15;token[0]=ch;break;case'/':syn=16;token[0]=ch;break;case':':syn=17;token[0]=ch;ch=prog[p++];if(ch=='='){token[1]=ch;syn++;}else p--;break;case'<':syn=20;token[0]=ch;ch=prog[p++];if(ch=='>'){token[1]=ch;syn++;}else if(ch=='='){token[1]=ch;syn=syn+2;}else p--;break;case'>':syn=23;token[0]=ch;ch=prog[p++];if(ch=='='){token[1]=ch;syn++;}else p--;break;case'=':syn=25;token[0]=ch;break;case';':syn=26;token[0]=ch;break;case'(':syn=27;token[0]=ch;break;case')':syn=28;token[0]=ch;break;case'#':syn=0;token[0]=ch;break;default: printf("词法分析出错! 请检查是否输⼊⾮法字符\n");syn=-1;break; }}}四、程序运⾏结果截图：。

实验1 词法分析程序一、实验目的与要求1.复习正规文法、正规式、有限自动机之间的相互转换的原理及技术；2.学会使用Visual C++等高级语言编程实现上述转换，并能合理显示结果；3.以C++的一个真子集为案例，具体分析词法分析程序的设计步骤、基本架构及代码编制，并通过一定实例验证其可行性，以加深对词法分析原理的理解；4.通过本次实验，使学生理解模块化程序设计的思想，从而从全局角度领会一个完整软件的设计精髓，为后续试验的顺利完成奠定坚实的基础。

二、实验仪器及设备1.微型电子计算机80台2.配置Windows 2000及以上版本操作系统3.安装Visual C++6.0/Visual C#2000/Delphi6.0等以上版本的开发环境三、实验内容及步骤（一）正规文法与有限自动机的相互转换1．正规文法⇒有限自动机已知某正规文法G[S]如下：S→aAS→bBS→εA→aBA→bAB→aSB→bAB→ε请编程实现：（1）将G[S]转换为NFA；（2）将上述得到的NFA确定化为DFA；（3）再将DFA最简化为MFA。

2．有限自动机⇒正规文法已知某有限自动机NFA M=（Q,∑,f,q0,Z）如下：状态集：Q={1,2,3,4,5,6,7,8,9}字母表：∑={a,b}转移函数：f(1,a)=5f(1,ε)=2f(1,a)=4f(5,ε)=6f(2,b)=3f(4,ε)=7f(6,ε)=2f(6,b)=9f(3,ε)=8f(8,a)=9f(7,b)=9初态：q0=1终态集：Z={6,7,9}请编程实现：（1）首先将此NFA确定化为DFA；（2）再将得到的DFA最简化为MFA；（3）最后，将MFA转化为正规文法（左线性或右线性均可）。

（二）编程实现MiniC++的词法分析这里的MiniC++为C++语言的一个真子集，其语法结构与C++类似。

基本组成如下：（1）关键字有18个，分别为：void、int、char、bool、float、double、if、else、switch、case、default、break、continue、do、while、for、return以及struct等。

编译原理中的词法分析与语法分析原理解析编译原理是计算机科学中的重要课程，它研究的是如何将源程序翻译成目标程序的过程。

而词法分析和语法分析则是编译过程中的两个重要阶段，它们负责将源程序转换成抽象语法树，为接下来的语义分析和代码生成阶段做准备。

本文将从词法分析和语法分析的原理、方法和实现技术角度进行详细解析，以期对读者有所帮助。

一、词法分析的原理1.词法分析的定义词法分析（Lexical Analysis）是编译过程中的第一个阶段，它负责将源程序中的字符流转换成标记流的过程。

源程序中的字符流是没有结构的，而编程语言是有一定结构的，因此需要通过词法分析将源程序中的字符流转换成有意义的标记流，以便之后的语法分析和语义分析的进行。

在词法分析的过程中，会将源程序中的字符划分成一系列的标记（Token），每个标记都包含了一定的语义信息，比如关键字、标识符、常量等等。

2.词法分析的原理词法分析的原理主要是通过有限状态自动机（Finite State Automaton，FSA）来实现的。

有限状态自动机是一个数学模型，它描述了一个自动机可以处于的所有可能的状态以及状态之间的转移关系。

在词法分析过程中，会将源程序中的字符逐个读取，并根据当前的状态和字符的输入来确定下一个状态。

最终，当字符读取完毕时，自动机会处于某一状态，这个状态就代表了当前的标记。

3.词法分析的实现技术词法分析的实现技术主要有两种，一种是手工实现，另一种是使用词法分析器生成工具。

手工实现词法分析器的过程通常需要编写一系列的正则表达式来描述不同类型的标记，并通过有限状态自动机来实现这些正则表达式的匹配过程。

这个过程需要大量的人力和时间，而且容易出错。

而使用词法分析器生成工具则可以自动生成词法分析器的代码，开发者只需要定义好源程序中的各种标记，然后通过这些工具自动生成对应的词法分析器。

常见的词法分析器生成工具有Lex和Flex等。

二、语法分析的原理1.语法分析的定义语法分析（Syntax Analysis）是编译过程中的第二个阶段，它负责将词法分析得到的标记流转换成抽象语法树的过程。

编译原理词法分析与语法分析的过程与方法编译原理是计算机科学领域中的重要内容之一，它研究如何将高级语言程序转化为机器语言的过程。

其中，词法分析和语法分析是编译原理中的两个重要阶段。

本文将详细介绍词法分析与语法分析的过程与方法。

一、词法分析的过程与方法词法分析是编译器的第一个阶段，其主要任务是将源程序的字符序列划分成有意义的语言单元，也就是词法单元。

以下是词法分析的过程与方法：1. 扫描：词法分析器从源程序中读取字符序列，并按照事先定义的规则进行扫描。

2. 划分词法单元：根据事先定义的规则，词法分析器将字符序列划分为不同的词法单元，如关键字、标识符、常量、运算符等。

3. 生成词法单元流：将划分好的词法单元按照顺序生成词法单元流，方便后续的语法分析阶段使用。

4. 错误处理：在词法分析过程中，如果发现了不符合规则的字符序列，词法分析器会进行错误处理，并向用户报告错误信息。

二、语法分析的过程与方法语法分析是编译器的第二个阶段，其主要任务是分析词法单元流，并判断是否符合语法规则。

以下是语法分析的过程与方法：1. 构建语法树：语法分析器根据语法规则构建抽象语法树（AST），用于表示源程序的语法结构。

2. 自顶向下分析：自顶向下分析是一种常用的语法分析方法，它从根节点开始，按照语法规则向下递归分析，直到生成叶子节点对应的词法单元。

3. 底部向上分析：底部向上分析是另一种常用的语法分析方法，它从词法单元开始，逐步合并为更高级的语法结构，直到生成抽象语法树的根节点。

4. 错误处理：在语法分析过程中，如果发现了不符合语法规则的词法单元流，语法分析器会进行错误处理，并向用户报告错误信息。

三、词法分析与语法分析的关系与区别词法分析和语法分析在编译原理中起着不同的作用：1. 关系：词法分析是语法分析的前置阶段，它为语法分析提供了有意义的词法单元流。

语法分析基于词法单元流构建语法树，判断源程序是否满足语法规则。

2. 区别：词法分析主要关注词法单元的划分和分类，它是基于字符序列的处理；而语法分析主要关注词法单元之间的组合和语法结构的判断，它是基于语法规则的处理。

编译原理实验词法分析程序实验一：词法分析程序1、实验目的从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号形式的中间程序。

2、实验内容表C语言子集的单词符号及内码值单词符号种别编码助记符内码值while 1 while --if 2 if --else 3 else --switch 4 switch --case 5 case --标识符 6 id id在符号表中的位置常数7 num num在常数表中的位置+ 8 + --- 9 - --* 10 * --<= 11 relop LE< 11 relop LT== 11 relop LQ= 12 = --; 13 ; --输入源程序如下if a==1 a=a+1;else a=a+2;输出对应的单词符号形式的中间程序3、实验过程实验上机程序如下：#include "stdio.h"#include "string.h"int i,j,k;char s ,a[20],token[20];int letter(){if((s>=97)&&(s<=122))return 1;else return 0;}int Digit(){if((s>=48)&&(s<=57))return 1;else return 0;}void get(){s=a[i];i=i+1;}void retract(){i=i-1;}int lookup(){if(strcmp(token, "while")==0)return 1;else if(strcmp(token, "if")==0)return 2;else if(strcmp(token,"else")==0)return 3;else if(strcmp(token,"switch")==0)return 4;else if(strcmp(token,"case")==0)return 5;else return 0;}void main(){printf("please input you source program,end('#'):\n");i=0;do{i=i+1;scanf("%c",&a[i]);}while(a[i]!='#');i=1;memset(token,0,sizeof(char)*10);j=0;get();while(s!='#'){if(s==' '||s==10||s==13)get();else{switch(s){case'a':case'b':case'c':case'd':case'e':case'f':case'g':case'h':case'i':case'j':case'k':case'l':case'm':case'n':case'o':case'p':case'q':case'r':case's':case't':case'u':case'v':case'w':case'x':case'y':case'z':while(Digit()||letter()){token[j]=s;j=j+1;get();}retract();k=lookup();if(k==0)printf("(6,%s)\n",token); elseprintf("(%d,null)\n",k); break;case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':while(Digit()){token[j]=s;j=j+1;get();}retract();printf("(%d,%s)\n",7,token); break;case'+':printf("(+,null)\n"); break;case'-':printf("(-,null)\n"); break;case'*':printf("(*,null)\n"); break;case'<':get();if(s=='=')printf("(relop,LE)\n"); else{retract();printf("(relop,LT)\n");}break;case'=':get();if(s=='=')printf("(relop,EQ)\n"); else{retract();printf("(=,null)\n");}break;case';':printf("(;,null)\n"); break;default:printf("(%c,error)\n",s);break;}memset(token,0,sizeof(char)*10);j=0;get();}}}4、实验结果实验结果分析：if是关键字，对应种别编码为2，输出（2，null）a是标识符，对应种别编码为6，值为a，输出（6，a）==的助记符是relop，内码值为LE，输出（relop，LE）1是常数，对应种别编码为7，值为1，输出（7，1）a是标识符，对应种别编码为6，值为a，输出（6，a）=是赋值符号，直接输出，（=，null）a是标识符，对应种别编码为6，值为a，输出（6，a）+是运算符，直接输出（=，null）1是常数，对应种别编码为7，值为1，输出（7，1）；是语句结束符号，直接输出（；，null）else是关键字，对应种别编码为3，输出（3，null）a是标识符，对应种别编码为6，值为a，输出（6，a）=是赋值符号，直接输出，（=，null）a是标识符，对应种别编码为6，值为a，输出（6，a）+是运算符，直接输出（=，null）2是常数，对应种别编码为7，值为2，输出（7，2）；是语句结束符号，直接输出（；，null）#是输入结束标志编译原理实验语法分析程序实验二：语法分析程序1、实验目的：将单词组成各类语法单位，讨论给类语法的形成规则，判断源程序是否符合语法规则3、实验内容：给定文法：G[E]:E→E+E|E-E|E*E|E/E|(E)E→0|1|2|3|4|5|6|7|8|9首先把G[E]构造为算符优先文法，即：G’[E]:E→E+T|TT→T-F|FF→F*G|GG→G/H|HH→(E)|i得到优先关系表如下：+ - * / i ( ) # + ·><·<·<·<·<··>·> - ·>·><·<·<·<··>·> * ·>·>·><·<·<··>·> / ·>·>·>·><·<··>·>i ·>·>·>·>·>·>( <·<·<·<·<·<·=) ·>·>·>·>·>·> # <·<·<·<·<·<·=构造出优先函数+ - * / i ( ) #f 6 8 10 12 12 2 12 2g 5 7 9 11 13 13 2 2要求输入算术表达式：（1+2）*3+2*（1+2）-4/2输出其对应的语法分析结果4、实验过程：上机程序如下：#include "stdio.h"#include "string.h"char a[20],optr[10],s,op;int i,j,k,opnd[10],x1,x2,x3;int operand(char s){if((s>=48)&&(s<=57))return 1;else return 0;}int f(char s){switch(s){case'+':return 6;case'-':return 8;case'*':return 10;case'/':return 12;case'(':return 2;case')':return 12;case'#':return 2;default:printf("error");}}int g(char s){switch(s){case'+':return 5;case'-':return 7;case'*':return 9;case'/':return 11;case'(':return 13;case')':return 2;case'#':return 2;default:printf("error");}}void get(){s=a[i];i=i+1;}void main(){printf("请输入算数表达式，并以‘#’结束:\n");i=0;do{scanf("%c",&a[i]);i++;}while(a[i-1]!='#');i=0;j=0;k=0;optr[j]='#';get();while((optr[j]!='#')||(s!='#')){if(operand(s)){opnd[k]=s-48;k=k+1;get();}else if(f(optr[j])<g(s)){j=j+1;optr[j]=s;get();}else if(f(optr[j])==g(s)){if(optr[j]=='('&&s==')'){j=j-1;get();}else if(optr[j]=='('&&s=='#'){printf("error\n");break;}else if(optr[j]=='#'&&s==')'){printf("error\n");break;}}else if(f(optr[j])>g(s)){op=optr[j];j=j-1;x2=opnd[k-1];x1=opnd[k-2];k=k-2;switch(op){case'+':x3=x1+x2;break;case'-':x3=x1-x2;break;case'*':x3=x1*x2;break;case'/':x3=x1/x2;break;}opnd[k]=x3;k=k+1;printf("(%c,%d,%d,%d)\n",op,x1,x2,x3);}else{printf("error\n");break;}}if(j!=0||k!=1)printf("error\n");}5、实验结果：实验结果分析：（1+2）*3+2*（1+2）-4/2#因为‘）’优先级大于‘*’，先计算1+2=3，并输出（+，1，2，3）原式变为：3*3+2*（1+2）-4/2#因为‘*’优先级大于‘+’，先计算3*3=9，并输出（*，3，3，9）原式变为：9+2*（1+2）-4/2#因为‘）’优先级大于‘-’，先计算1+2=3，并输出（+，1，2，3）原式变为：9+2*3-4/2#因为‘*’优先级大于‘-’，先计算2*3=6，并输出（*，2，3，6）原式变为：9+6-4/2#因为‘/’优先级大于‘#’，先计算4/2=2，并输出（/，4，2，2）原式变为：9+6-2#因为‘-’优先级大于‘#’，先计算6-2=4，并输出（-，6，2，4）原式变为：9+4#因为‘+’优先级大于‘#’，计算9+4=13，并输出（+，9，4，13）原式变为13#优先级等于#，跳出while循环，运算结束！。