编译原理课程设计－词法分析器设计（C语言）

词法分析器又称扫描器。词法分析是指将我们编写的文本代码流解析为一个一个的记号，分析得到的记号以供后续语法分析使用。词法分析器的工作是低级别的分析：将字符或者字符序列转化成记号.。在谈论词法分析时，使用术语“词法记号”（简称记号）、“模式”和“词法单元”表示特定的含义。

在分析时，一是把词法分析器当成语法分析的一部分，另一种是把词法分析器当成编译程序的独立部分。在前一种情况下，词法分析器不断地被语法分析器调用，每调用一次词法分析器将从源程序的字符序列拼出一个单词，并将其Token值返回给语法分析器。后一种情况则不同，词法分析器不是被语法分析器不断地调用，而是一次扫描全部单词完成编译器的独立一遍任务。

时间：2012-10-30 晚

要求：输入一串字符串，对其进行词法分析，并且按照（<种别>,<字符串/数字>）格式进行输出

种别编码：

符号 种别 符号 种别 符号 种别

begin 1 + 13 <= 22

if 2 - 14 >23

then 3 * 15 >= 24

while 4 / 16 = 25

do 5 : 17 26

end 6 := 18 ( 27

l(l|d)* 10 <20 ) 28

数字① 11 <>21 # 0

①数字的词法正规式如下：( +|-|ε ) dd*(.dd* | ε)( e ( +|-|ε ) dd*|ε)

ps：输入的字符串以“#”结尾

运行环境：VC++6.0

说明：搜索网上的资源，大部分的“数字”部分都是dd*形式，但这次试验要求的是①形式，因而在数字部分做了很大努力。与dd*形式的不同有三个地方——ch是数字时，ch是+后接着是数字形式，ch是-后接着是数字形式。然而由于水平有限，时间较短，每个“加号”或“减号”后必须要在输入数字正负符号，否则会默认“+”“-”为正负符号而不是“加号”“减号”。希望能有简单方法解决这个问题。

源代码：

#include <stdio.h> //定义I/O库所用的某些宏和变量

#include <string.h> //定义字符串库函数

#include <math.h> //定义数学运算符号库函数

char prog[80],token[8] //prog：缓冲区；token：一个有意义的字符串

char ch//ch：当前处理的字符

int syn,p,m,n,f,e

//syn：类别；p,m,n：计数变量；f，标记数字正负；e，10的次方数

double sum//sum，数字

char *rwtab[6]={"begin","if","then","while","do","end"}

//基本字表置初值

void main(void) //主函数

{

void scaner(void) //声明函数

p=0

printf("\n请输入字符串：\n")

do{ //输入的字符放入缓冲区

ch=getchar()

prog[p++]=ch

}while(ch!='#')

p=0

do{ //分析词法并输出结果

scaner()

switch(syn)

{

case 11:printf("(%2d,%16g)\n",syn,sum)break

case -1:printf("输入错误\n")break

default:printf("(%2d,%16s)\n",syn,token)

}

}while(syn!=0)

}

void scaner(void)

{

for(n=0n<8n++) //token初始化

token[n]=NULL

ch=prog[p++]

while(ch==' ')//如果取消空字符（目前空字符只包括空格）

ch=prog[p++]

if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))

//如果ch是字母字符

{

m=0

while((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'))

//如果ch是字母字符或数字字符

{

token[m++]=ch

ch=prog[p++] //读下一个字符

}

token[m++]='\0'

p--

syn=10

for(n=0n<6n++)

if(strcmp(token,rwtab[n])==0)

{

syn=n+1//给出syn值

break

}

}

else if(ch>='0'&&ch<='9') //数字(1)

{

sum=0

while(ch>='0'&&ch<='9')

{

sum=sum*10+ch-'0'

ch=prog[p++]

}

if(ch=='.') //有小数点

{

e=-1

ch=prog[p++]

if(ch>='0'&&ch<='9')

{

while(ch>='0'&&ch<='9')

{

sum=sum+(ch-'0')*pow(10,e--)

ch=prog[p++]

}

}

}

if(ch=='e'||ch=='E') //有e

{

e=0,f=1

ch=prog[p++]

if(ch=='+')

{

f=1

ch=prog[p++]

}

else if(ch=='-')

{

f=-1

ch=prog[p++]

}

if(ch>='0'&&ch<='9')

{

while(ch>='0'&&ch<='9')

{

e=e*10+ch-'0'

ch=prog[p++]

}

}

e=e*f

sum=sum*pow(10,e)

}

p--

syn=11

}

else switch(ch)

{

case '<':

m=0

token[m++]=ch

ch=prog[p++]

if(ch=='>') //<>

{

syn=21

token[m++]=ch

}

else if(ch=='=') //<=

{

syn=22

token[m++]=ch

}

else//<

{

syn=20

p--

}

break

case '>':

m=0

token[m++]=ch

ch=prog[p++]

if(ch=='=') //>=

{

syn=24

token[m++]=ch

}

else//>

{

syn=23

p--

}

break

case ':':

m=0

token[m++]=ch

ch=prog[p++]

if(ch=='=') //:=

{

syn=18

token[m++]=ch

}

else//:

{

syn=17

p--

}

break

case '+':

ch=prog[p++]

if(ch>='0'&&ch<='9') //数字(2)

{

sum=0

while(ch>='0'&&ch<='9')

{

sum=sum*10+ch-'0'

ch=prog[p++]

}

if(ch=='.') //有小数点

{

e=-1

ch=prog[p++]

if(ch>='0'&&ch<='9')

{

while(ch>='0'&&ch<='9')

{

sum=sum+(ch-'0')*pow(10,e--)

ch=prog[p++]

}

}

}

if(ch=='e'||ch=='E') //有e

{

e=0,f=1

ch=prog[p++]

if(ch=='+')

{

f=1

ch=prog[p++]

}

else if(ch=='-')

{

f=-1

ch=prog[p++]

}

if(ch>='0'&&ch<='9')

{

while(ch>='0'&&ch<='9')

{

e=e*10+ch-'0'

ch=prog[p++]

}

}

e=e*f

sum=sum*pow(10,e)

}

p--

syn=11

}

else//+

{

syn=13

p--

ch=prog[p-1]

token[0]=ch

}

break

case '-':

ch=prog[p++]

if(ch>='0'&&ch<='9') //数字(3)

{

sum=0

while(ch>='0'&&ch<='9')

{

sum=sum*10+ch-'0'

ch=prog[p++]

}

if(ch=='.') //有小数点

{

e=-1

ch=prog[p++]

if(ch>='0'&&ch<='9')

{

while(ch>='0'&&ch<='9')

{

sum=sum+(ch-'0')*pow(10,e--)

ch=prog[p++]

}

}

}

if(ch=='e'||ch=='E') //有e

{

e=0,f=1

ch=prog[p++]

if(ch=='+')

{

f=1

ch=prog[p++]

}

else if(ch=='-')

{

f=-1

ch=prog[p++]

}

if(ch>='0'&&ch<='9')

{

while(ch>='0'&&ch<='9')

{

e=e*10+ch-'0'

ch=prog[p++]

}

}

e=e*f

sum=sum*pow(10,e)

}

sum=-sum

p--

syn=11

}

else//-

{

syn=13

p--

ch=prog[p-1]

token[0]=ch

}

break

case '*': syn=15token[0]=chbreak

case '/': syn=16token[0]=chbreak

case '=': syn=25token[0]=chbreak

case '': syn=26token[0]=chbreak

case '(': syn=27token[0]=chbreak

case ')': syn=28token[0]=chbreak

case '#': syn=0token[0]=chbreak

default: syn=-1

}

}

试试吧

词法分析是把构成源程序的字符串转换成单词符号序列。词法规则可用 3型文法 （正规文法）或正规表达式描述，他产生的集合是语言基本字符集Σ（字母表）上的字符串的一个子集，称为正规集。

正规式是一种表示正规集的工具，正规式是描述程序语言单词的表达式，对于字母表Σ。

正规式（正规表达式）的运算符有3个，优化级从高到低顺序排列为：*（闭包）、·（连接，可省略）、|（或）。

正规式  →  正规集

ab  →  字符串ab构成的集合

a|b  →  字符串a、b构成的集合

a*  →  由0个或多个a构成的字符串集合

(a|b)*  →  所有字符a和b构成的串的集合

a(a|b)*  →  以a为首字符的a、b字符串的集合

(a|b)*abb  →  以abb结尾的a、b字符串的集合

有限自动机可以转换为正规式，正规式也可以转换为有限自动机。

词法分析器的构造步骤：

1）用正规式描述语言中的单词构成规则。

2）为每个正规式构造一个NFA，它识别正规式所表示的正规集。

3）将构造出的NFA转换成等价的DFA。

4）对DFA进行最小化处理，使其最简。

5）从DFA构造词法分析器。

简而言之就是先画一个状态图，然后根据图来编码就行一个简单的xml的词法分析器供参考#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct{char*pintlen}xml_Texttypedefenum{xml_tt_U,xml_tt_H,xml_tt_E,xml_tt_B,xml_tt_BE,xml_tt_T}xml_TokenTypetypedefstruct{xml_Texttextxml_TokenTypetype}xml_Tokenintxml_initText(xml_Text*pText,char*s){pText->p=spText->len=strlen(s)return0}intxml_initToken(xml_Token*pToken,xml_Text*pText){pToken->text.p=pText->ppToken->text.len=0pToken->type=xml_tt_Ureturn0}intxml_print(xml_Text*pText){intifor(i=0i<pText->leni++){putchar(pText->p[i])}return0}intxml_println(xml_Text*pText){xml_print(pText)putchar('\n')return0}intxml_getToken(xml_Text*pText,xml_Token*pToken){char*start=pToken->text.p+pToken->text.lenchar*p=startchar*end=pText->p+pText->lenintstate=0pToken->text.p=ppToken->type=xml_tt_Ufor(p<endp++){switch(state){case0:switch(*p){case'<':state=1breakdefault:state=7break}breakcase1:switch(*p){case'?':state=2breakcase'/':state=4breakdefault:state=5break}breakcase2:switch(*p){case'?':state=3breakdefault:state=2break}breakcase3:switch(*p){case'>':pToken->text.len=p-start+1pToken->type=xml_tt_Hreturn1default:state=-1break}breakcase4:switch(*p){case'>':pToken->text.len=p-start+1pToken->type=xml_tt_Ereturn1default:state=4break}breakcase5:switch(*p){case'>':pToken->text.len=p-start+1pToken->type=xml_tt_Breturn1case'/':state=6breakdefault:state=5break}breakcase6:switch(*p){case'>':pToken->text.len=p-start+1pToken->type=xml_tt_BEreturn1default:state=-1break}breakcase7:switch(*p){case'<':p--pToken->text.len=p-start+1pToken->type=xml_tt_Treturn1default:state=7break}breakdefault:pToken->text.len=p-start+1pToken->type=xml_tt_Treturn1}}return0}intmain(){intret=0xml_Textxmlxml_initText(&xml,"<?xml?><root>ss<haha>hoho</haha></root>")xml_Tokentokenxml_initToken(&token,&xml)ret=xml_getToken(&xml,&token)printf("ret=%dtext=",ret)xml_print(&token.text)printf("type=%d\n\n",token.type)ret=xml_getToken(&xml,&token)printf("ret=%dtext=",ret)xml_print(&token.text)printf("type=%d\n\n",token.type)ret=xml_getToken(&xml,&token)printf("ret=%dtext=",ret)xml_print(&token.text)printf("type=%d\n\n",token.type)ret=xml_getToken(&xml,&token)printf("ret=%dtext=",ret)xml_print(&token.text)printf("type=%d\n\n",token.type)ret=xml_getToken(&xml,&token)printf("ret=%dtext=",ret)xml_print(&token.text)printf("type=%d\n\n",token.type)ret=xml_getToken(&xml,&token)printf("ret=%dtext=",ret)xml_print(&token.text)printf("type=%d\n\n",token.type)ret=xml_getToken(&xml,&token)printf("ret=%dtext=",ret)xml_print(&token.text)printf("type=%d\n\n",token.type)return0}

1.输入是代码文件，输出是一个个的token。这些输出之后是供语法分析器（yacc，bison什么的）用的。

2.做准备的话你可以看看《c专家编程》第3章：分析c语言的声明。这个例子是一个最简单的词法+语法分析器，足够给你一些提示了。当然这还不够，你可能要找一份C语言的标准来看。

3.归类无非是修饰符、类型、关键字、标识符、运算符等等了。

4.在2的基础上。不难解决。

5.这个很简单。就算直接文件处理也解决掉了。依稀记得lex可能更容易做这件事儿。

总体来说，这事儿如果自己做可能比较费劲，用lex应该省事不少。

=========================================================================

上面只是凭印象说的，希望对你有帮助。等等看有没有大牛帮你完成吧。或者等我有空咱们一起研究下。

一般的编译器可能包含下面这些模块:

1, 词法分析器:

输入: 源代码

输出: token

2, 语法分析器:

输入: token

输出: AST

在这个过程中, 可以识别出不符合语法规则的语句, 就可以报syntax错误, 如果有syntax错误, 编译结束

3, 语义分析器:

输入: AST

输出: 无

在这个过程中, 根据语言的语义规则来识别语义错误, 要识别语义错误 就必须编译AST, 因为是树的遍历, 假如你先遍历到了int a 这个节点, 接着又遍历到了一个表达式a = 4这个节点, 你需要检查变量a有没有声明啊, 变量a和4的类型批不匹配呢? 这时你如果没有保存变量a的信息, 那么你怎么检查? 所以就需要符号表来保存这些信息了.

4, 代码优化:

最简单的就是常量折叠优化了, 比如: a = 1 + 2 这个语句可以直接换成: a = 3了, 也就是说在编译阶段就把一些必要的运算先计算完成, 在程序运行的时候就不需要计算这些了, 就提高了程序的运行效率. 这部分是最复杂的了, 还有各种各样各样的优化

5, 代码生成:

输入: AST

输出: 可以是虚拟机代码, 可以是本地汇编代码

编译原理中的词法分析器的输入是源程序，输出是识别的记号流。

词法分析器编制一个读单词的程序，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符和分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。

扩展资料

词法分析器的作用：

1、与符号表进行交互，存储和读取符号表中的标识符的信息。

2、读入源程序的输入字符，将他们组成词素，生成并输出一个词法单元序列，每个词法单元序列对应一个于一个词素。

3、过滤掉程序中的注释和空白。

4、将编译器生成的错误消息与源程序的位置联系起。

参考资料来源：

百度百科-词法分析器

C语言词法分析器

#include<iostream>

#include<stdio.h>

#include<string>

using namespace std

FILE *f //定义一个文件变量

static int line = 1 //表示光标所在的行数

struct ID{ char *nameint count}id[100]//用于存放ID号码

static int I = 0//用于记录ID存放的数量

int Number[100]//用于存放数字

static int P = 0//用于记录存放数字的个数

int error[100] = {0} //用于记录错误所在的行数

static int K = 0//记录错误次数

void Error() //记录错误

void loginID(char *) //注册ID号

void loginNumber(int &)//记录数字

void noteLine(char &)//记录光标所在的行数

void print() //输出分析结果

int same(char *chr) //判断单词是否已经存在

void Error()

{ error[K++] = line}

void loginID(char *chr) //注册ID号

{

int k = 0

int h = 0

for(int i = 0i <Ii++)

{

if(!strcmp(chr,id.name)) //如果单词已经存在

{

id.count++

k = 1

}

}

if(k == 0) //该单词不存在

{

h = I + 1

//I = h

id[h].count++

id[h].name = chr

//strcpy(id[h].name ,chr)

}

}

void loginNumber(int &nu)

{ Number[P++] = nu}

void noteLine(char &ch)

{

if ( ch == ' ' )

++line

}

void print()//输出部分

{

//cout <<"关键字以及变量:" <<endl

//for(int i = 0i <100i++)

//cout <<i <<" " <<id.name <<" " <<id.count <<endl

cout <<"数字：" <<endl

for(int i = 1i <= Pi++)

cout <<i <<": " <<Number[i-1] <<endl

if(error[0] != 0)

{

cout <<"出现的错误！" <<endl

for(int i = 1i <= Ki++)

cout <<"第" <<i <<"个错误： " <<"第" <<error[i-1] <<"行" <<endl

}

else cout <<"没有错误！" <<endl

}

//文件处理部分

void noblank( char &ch) //跳过空格，回车

{

noteLine(ch)

while(ch == ' ' || ch == ' ')

ch = fgetc(f)

}

void identifier(char name[],char &ch)//字母变量

{

int i

for(i = 0i <20i++)

name = ''

i = 0

while (('0'<= ch &&ch <= '9')||('a'<= ch&&ch <= 'z')||('A'<= ch&&ch <='Z'))

{

name = ch

i++

ch = fgetc(f)

}

loginID(name)

//for(int j = 0j <ij++)

//{cout <<name[j]}

// cout <<' '

}

int number(char &ch)//数字

{

int num=0

while('0'<= ch &&ch <= '9')

{

num = num* 10 + (ch-'0')

ch = fgetc(f)

}

if( ('a'<= ch&&ch <= 'z')||('A'<= ch&&ch <='Z'))

{

Error()

}

else if( ch == '.')

{}

loginNumber(num) //记录数字

return num

}

void test(char &ch)//符号

{

char str[2]={'0/'}

if(ch == '*')

{ str[0] = chch = fgetc(f)}

if(ch == '.')

{ str[0] = chch = fgetc(f)}

if(ch == ',')

{ str[0] = chch = fgetc(f)}

if(ch == '"')

{ str[0] = chch = fgetc(f)}

if(ch == '/')

{ str[0] = chch = fgetc(f)}

if(ch == '%')

{ str[0] = chch = fgetc(f)}

if(ch == '^')

{ str[0] = chch = fgetc(f)}

if(ch == '-')

{ str[0] = chch = fgetc(f)}

if(ch == '{')

{ str[0] = chch = fgetc(f)}

if(ch == '}')

{ str[0] = chch = fgetc(f)}

if(ch == '[')

{ str[0] = chch = fgetc(f)}

if(ch == ']')

{ str[0] = chch = fgetc(f)}

if(ch == '')

{str[0] = chch = fgetc(f)}

if(ch == ':')

{ str[0] = chch = fgetc(f)}

if(ch == '?')

{ str[0] = chch = fgetc(f)}

if(ch == '(')

{ str[0] = chch = fgetc(f)}

if(ch == ')')

{str[0] = chch = fgetc(f)}

if(ch =='+')

{

str[0] = ch

if((ch = fgetc(f)) == '+' )

{

str[1] = ch

ch = fgetc(f)

//cout <<str[0] <<str[1] <<endl

}

//cout <<str[0]<<endl

}

if(ch == '-')

{

str[0] = ch

if((ch = fgetc(f)) == '-' )

{

str[1] = ch

ch = fgetc(f)

//cout <<str[0] <<str[1] <<endl

}

//cout <<str[0]<<endl

}

if(ch == '&')

{

str[0] = ch

if((ch = fgetc(f)) == '&' )

{

str[1] = ch

ch = fgetc(f)

//cout <<str[0] <<str[1] <<endl

}

//cout <<str[0]<<endl

}

if(ch == '|')

{

str[0] = ch

if((ch = fgetc(f)) == '|' )

{

str[1] = ch

ch = fgetc(f)

//cout <<str[0] <<str[1] <<endl

}

//cout <<str[0]<<endl

}

if(ch == '!')

{

str[0] = ch

if((ch = fgetc(f)) == '=' )

{

str[1] = ch

ch = fgetc(f)

//cout <<str[0] <<str[1] <<endl

}

//cout <<str[0]<<endl

}

if(ch == '=')

{

str[0] = ch

if((ch = fgetc(f)) == '=' )

{

str[1] = ch

ch = fgetc(f)

//cout <<str[0] <<str[1] <<endl

}

}

if(ch == '>')

{

str[0] = ch

if((ch = fgetc(f)) == '=' )

{

str[1] = ch

ch = fgetc(f)

//cout <<str[0] <<str[1] <<endl

}

else

if(ch == '>' )

{

str[1] = ch

ch = fgetc(f)

//cout <<str[0] <<str[1] <<endl

}

}

if(ch == '<')

{

str[0] = ch

if((ch = fgetc(f)) == '=' )

{

str[1] = ch

ch = fgetc(f)

}

else

if(ch == '<' )

{

str[1] = ch

ch = fgetc(f)

}

}

}

int main()

{

char ch

char name[30]

for(int i = 0i <30i++)

name = '/0'

f = fopen("c.txt","r") //打开指定输入文件

if (f == NULL)

cout<<"文件不存在！"<<endl

ch = fgetc(f)

while(!feof(f))

{

noblank( ch )//跳过回车，空格

if( ( ch >= 'a' &&ch <= 'z' )||( ch >= 'A' &&ch <= 'Z' ))

{ identifier(name,ch)} //处理字母

else if( ch >= '0'&&ch <= '9')

{ number(ch)} //处理数字

else

{ test(ch)} //处理符号

}

print() //打印词法分析结果

fclose(f) //关闭文件

system("pause")

return 0

}