精华内容
下载资源
问答
  • 编译原理词法分析

    2019-10-26 22:25:08
    编译原理词法分析 要求:对如下工作进行展开描述 (1) 给出语言的词法规则描述 • 标识符、关键字、整常数、字符常数、浮点常数 • 单界符:+,-,×,:,… • 双界符:/*,:=,… • 注释 (2) 针对这种单词的...

    编译原理词法分析

    要求:对如下工作进行展开描述
    (1) 给出语言的词法规则描述
    • 标识符、关键字、整常数、字符常数、浮点常数
    • 单界符:+,-,×,:,…
    • 双界符:/*,:=,…
    • 注释
    (2) 针对这种单词的状态转换图和程序框图
    (3) 核心数据结构的设计
    如符号表、关键字等
    (4) 错误处理
    错误的位置及类型等

    #include<iostream>
    #include<fstream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cstdlib>
    
    using namespace std;
    
    int aa;// fseek的时候用来接着的
    string  word = "";
    string  reserved_word[28];//保留
    char buffer;//每次读进来的一个字符
    int num = 0;//每个单词中当前字符的位置
    int line = 1; //行数
    int row = 1; //列数,就是每行的第几个
    bool flag; //文件是否结束了
    int flag2;//单词的类型
    
    //设置保留字
    void set_reserve()
    {
    	reserved_word[1] = "procedure";
    	reserved_word[2] = "def";
    	reserved_word[3] = "if";
    	reserved_word[4] = "else";
    	reserved_word[5] = "while";
    	reserved_word[6] = "call";
    	reserved_word[7] = "begin";
    	reserved_word[8] = "end";
    	reserved_word[9] = "and";
    	reserved_word[10] = "or";
    
    	reserved_word[11] = "return";
    	reserved_word[12] = "float";
    	reserved_word[13] = "double";
    	reserved_word[14] = "void";
    	reserved_word[15] = "cin";
    	reserved_word[16] = "cout";
    	reserved_word[17] = "char";
    	reserved_word[18] = "for";
    	reserved_word[19] = "true";
    	reserved_word[20] = "false";
    	reserved_word[21] = "int";
    	reserved_word[22] = "bool";
    	reserved_word[23] = "main";
    	reserved_word[24] = "#";
    	reserved_word[25] = "include";
    }
    
    //看这个字是不是字母
    bool judge_word(char x)
    {
    	if (x >= 'a' && x <= 'z' || x >= 'A' && x <= 'Z') {
    		return true;
    	}
    	else return false;
    }
    
    //看这个字是不是数字
    bool judge_number(char x)
    {
    	if (x >= '0' && x <= '9') {
    		return true;
    	}
    	else return false;
    }
    
    //看这个字符是不是界符
    bool judge_jiefu(char x)
    {
    	if (x == '(' || x == ')' || x == ',' || x == ';' || x == '{' || x == '}' || x == '"' || x == '\'') {
    		return true;
    	}
    	else return false;
    }
    
    
    //加减乘
    bool judge_yunsuanfu1(char x)
    {
    	if (x == '+' || x == '-' || x == '*')
    	{
    		return true;
    	}
    	else return false;
    }
    
    //等于 赋值,大于小于 大于等于,小于等于,大于小于
    bool judge_yunsuannfu2(char x)
    {
    	if (x == '=' || x == '>' || x == '<') {
    		return true;
    	}
    	else return false;
    }
    
    
    //这个最大的函数的总体作用是从文件里读一个单词
    int scan(FILE* fp)
    {
    	buffer = fgetc(fp);
    	if (feof(fp)) {
    		flag = 0; return 0;
    	}
    	//cout<<buffer;
    	else if (buffer == ' ')
    	{
    		row++;
    		return 0;
    	}
    	else if (buffer == '\n')
    	{
    		line++;
    		row = 1;
    		return 0;
    	}
    
    	//如果是字母开头或'_' 看关键字还是普通单词
    	else if (judge_word(buffer) || buffer == '_')
    	{
    		word += buffer; row++;
    		while ((buffer = fgetc(fp)) && (judge_word(buffer) || judge_number(buffer) || buffer == '_'))
    		{
    			word += buffer; row++;
    		}
    		if (feof(fp)) {
    			flag = 0; return 1;
    		}
    		//这个函数的意义是 因为保留字不区分大小写 要把大写字母全变成小写再比较
    		string temp = word;
    		for (int j = 0; j < temp.length(); j++)
    		{
    			if (temp[j] >= 'A' && temp[j] <= 'Z')
    			{
    				temp[j] += 32;
    			}
    		}
    		for (int i = 1; i <= 25; i++) {
    			if (temp == reserved_word[i]) {
    				aa = fseek(fp, -1, SEEK_CUR);
    				return 3;
    			}
    		}
    		aa = fseek(fp, -1, SEEK_CUR);
    		return 1;
    	}
    
    	//开始是加减乘 一定是类型4
    	else if (judge_yunsuanfu1(buffer))
    	{
    		word += buffer; row++;
    		return 4;
    	}
    
    	//开始是数字就一定是数字 2
    	else if (judge_number(buffer))
    	{
    		int flagp = 0;
    		word += buffer; row++;
    		while ((buffer = fgetc(fp)) && (judge_number(buffer)||buffer == '.'))
    		{
    			word += buffer; row++;
    			if (buffer == '.')
    			{
    				flagp = 1;
    			}
    			/*
    			if (buffer = fgetc(fp))
    			{
    				if (buffer == '.')
    				{
    					word += buffer; row++;
    				}
    				else
    				{
    					fseek(fp, -1, SEEK_CUR);
    				}
    			}
    			*/
    		}
    		if (feof(fp)) {
    			if (flagp == 0)
    			{
    				flag = 0; return 2;
    			}
    			else
    			{
    				flag = 0; return 7;
    			}
    			
    		}
    		aa = fseek(fp, -1, SEEK_CUR);
    		if (flagp == 0)
    		{
    			return 2;
    		}
    		else
    		{
    			return 7;
    		}
    	}
    
    	//检验界符
    	else if (judge_jiefu(buffer))
    	{
    		word += buffer; row++;
    		return 6;
    	}
    
    	//检验 <=、  >=、  <>、  == =、 <、>
    	else if (judge_yunsuannfu2(buffer))
    	{
    		row++;
    		word += buffer;
    		if (buffer == '<')   //为了检验题目中的<> <=
    		{
    			buffer = fgetc(fp);
    			if (buffer == '>' || buffer == '=')
    			{
    				word += buffer;
    				row++;
    				return 5;
    			}
    		}
    		//检验  >= ==
    		else {
    			buffer = fgetc(fp);
    			if (buffer == '=')
    			{
    				word += buffer;
    				row++;
    				return 5;
    			}
    		}
    		if (feof(fp)) {
    			flag = 0;
    		}
    		aa = fseek(fp, -1, SEEK_CUR);
    		return 4;
    	}
    
    	//首字符是/ 有可能是除号 也有可能是注释
    	else if (buffer == '/')
    	{
    		row++; word += buffer;
    		buffer = fgetc(fp);
    		//这种情况是除号
    		if (buffer != '*' && buffer != '/')
    		{
    			aa = fseek(fp, -1, SEEK_CUR);
    			return 4;
    		}
    		// 这一行剩下的全被注释了
    		if (buffer == '/')
    		{
    			word.clear();
    			while ((buffer = fgetc(fp)) && buffer != '\n' && !feof(fp))
    			{
    				//真的什么也没有做
    			}
    			if (feof(fp)) {
    				flag = 0; return 0;
    			}
    			else {
    				aa = fseek(fp, -1, SEEK_CUR);
    			}
    			//line++; row = 1;
    			return 0;
    		}
    		if (buffer == '*')
    		{
    			bool flag5 = 1;
    			while (flag5)
    			{
    				word.clear();
    				buffer = fgetc(fp);
    				row++;
    				if (buffer == '\n') { line++; row = 1; }
    				if (buffer != '*')continue;
    				else {
    					buffer = fgetc(fp);
    					row++; if (buffer == '\n') { line++; row = 1; }
    					if (buffer == '/') {
    						flag5 = 0;
    					}
    					else continue;
    				}
    				if (feof(fp)) { flag = 0; return 0; }
    			}
    
    		}
    
    	}
    
    	else {
    		word += buffer;
    		row++;
    		return -1;
    	}
    }
    
    int main()
    {
    	set_reserve();//设置保留字
    	cout << "introduction" << endl;
    	cout << "open " << "code.txt" << endl;
    
    	cout << "press any key" << endl;
    	system("pause");
    
    	flag = 1;
    	//ifstream a("需要解析的源代码.txt");
    	FILE* fp;
    	if (!(fp = fopen("code.txt", "r")))
    	{
    		cout << "not found the file or other error " << endl;
    		flag = 0;
    	}
    
    	while (flag == 1)
    	{
    		//flag2 返回的类型
    		flag2 = scan(fp);//反复调用函数提取单词
    
    		if (flag2 == 1)
    		{
    			cout << "type:1 标识符       " << "line " << line << " row " << row - word.length() << "  " << word << endl;
    			if (word.length() > 20)
    				cout << "ERROR Identifier length cannot exceed 20 characters" << endl;
    			word.clear();
    		}
    		else if (flag2 == 3)
    		{
    			cout << "type:3 关键字       " << "line " << line << " row " << row - word.length() << "  " << word << endl;
    			word.clear();
    		}
    		else if (flag2 == 4)
    		{
    			cout << "type:4 操作数       " << "line " << line << " row " << row - 1 << "  " << word << endl;
    			word.clear();
    		}
    		else if (flag2 == 2)
    		{
    			cout << "type:2 常整形       " << "line " << line << " row " << row - word.length() << "  " << word << endl;
    			//if (word[0] == '0')
    			//	cout << "ERROR: The first digit cannot be 0!" << endl;
    			word.clear();
    		}
    		else if (flag2 == 7)
    		{
    			cout << "type:7 浮点数       " << "line " << line << " row " << row - word.length() << "  " << word << endl;
    
    			word.clear();
    		}
    		else if (flag2 == 6)
    		{
    			cout << "type:6 分隔符       " << "line " << line << " row " << row - 1 << "  " << word << endl;
    			word.clear();
    		}
    		else if (flag2 == 5)
    		{
    			cout << "type:5 二元操作数   " << "line " << line << " row " << row - 2 << "  " << word << endl;
    			word.clear();
    		}
    		//非法字符
    		else if (flag2 == -1)
    		{
    			cout << "Illegal character      " << "line " << line << " row " << row - 1 << "  " << word << endl;
    			word.clear();
    		}
    	}
    
    	int a = fclose(fp);
    	cout << "press e to close" << endl;
    	char end;
    	while (cin >> end && end != 'e') {
    		cout << "只有e可以关闭" << endl;
    	}
    	return 0;
    }
    
    展开全文
  • 编译原理 词法分析

    千次阅读 2016-04-20 17:45:50
    编译原理词法分析词法分析的主要任务是从左至右逐个字符地对源程序进行扫描,产生一个个单词序列,用于语法分析。 1.正则表达式对给定的字符集∑={c1,c2,...,cn},归纳定义: 1.空串ε是正则表达式 2.对于任意c∈∑,...

    原文地址:编译原理 词法分析
    2345%E6%88%AA%E5%9B%BE20160416170725.jpg

    编译原理
    
    词法分析
    
    词法分析的主要任务是从左至右逐个字符地对源程序进行扫描,产生一个个单词序列,用于语法分析。
    

    1.正则表达式

    对给定的字符集∑={c1,c2,...,cn},归纳定义:
    1.空串ε是正则表达式
    2.对于任意c∈∑,c是正则表达式
    3.如果M和N是正则表达式,则下列表达式也是正则表达式
    (1)选择 M|N={M,N}
    (2)连接 MN={mn|m∈M,n∈N}
    (3)闭包 M*={ε,M,MM,MMM,...}
    

    1.jpg

    2.正则表达式的扩展

    (1)[c1-cn]==c1|c2|c3|...|cn
    (2)e+==一个或多个e
    (3)e?==零个或一个e
    (4)"a*"==a*自身,不是a的Kleen闭包
    (5)e{i,j}==i到j个e的连接
    

    3.状态转换图

    状态转换图有一组被称为“状态”的结点或圆圈。词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素,而
    转换图中的每个状态代表一个可能在这个过程中出现的情况。
    

    对于

    的状态转换图为

    4.有穷自动机

    有穷自动机是识别器,只能对每个可能的输入串简单地回答“是”或“否”。
    

    (1)有穷自动机分两种

    1)不确定的有穷自动机(NFA):对其边上的标号没有任何限制。一个符号标记离开同一状态的多条边,
    并且空串ε也可以作为标号。
    2)确定的有穷自动机(DFA):对于每个状态及自动机输入字母表中的每个符号,有且只有一条离开该状态、以该符
    号为标号的边。
    

    (2)不确定的有穷自动机(NFA)

    一个不确定的有穷自动机(NFA)由以下几个部分组成:
    1)一个有穷的状态集合S。
    2)一个输入符号集合∑,即输入字母表。(ε∉∑)
    3)一个转换函数,它为每个状态和∑∪{ε}中的每个符号都给出了相应的后继状态的集合。
    4)S中的一个状态s0被指定为开始状态,或者初始状态。
    6)S的一个子集F被指定为接受状态(或终止状态)的集合。
    

    (3)确定的有穷自动机(DFA)

    确定的有穷自动机是不确定有穷自动机的一个特例。其中:
    1)没有输入ε之上的转换动作。
    2)对于每个状态s和每个输入符号a,有且只有一条标号为a的边离开s。
    

    5.从正则表达式构造NFA(Thompson算法)

    输入:字母表∑上的一个正则表达式r.
    输出:一个接受L(r)的NFA N.
    方法:首先对r进行语法分析,分解出组成它的子表达式。构造一个NFA的规则分为基本规则和归纳规则两组。
    基本规则处理不包含运算符的子表达式,而归纳规则根据一个给定表达式的直接子表达式的NFA构造出这个表达式的NFA。
    

    (1)基本规则:

    1)对于表达式ε,构造下面的NFA
    

    2)对于字母表中的子表达式a,构造下面的NFA
    

    (2)归纳规则:假设正则表达式s和t的NFA分别为N(s)和N(t)

    3)假设r=s|t,构造下面的NFA,这里i和f是新状态,分别是N(r)的开始状态和接受状态。从i到N(s)和N(t)的开始状态各
    有一个ε转换,从N(s)和N(t)到接受状态f也各有一个ε转换。
    

    4)假设r=st,构造下面的NFA,N(s)的开始状态变成了N(r)的开始状态。N(t)的接受状态成为N(r)的唯一接受状态。N(s)的
    接受状态和N(t)的开始状态合并为一个状态,合并后的状态拥有原来进入和离开合并前的两个状态的全部转换。
    

    5)假设r=s*,构造下面的NFA,i和f是两个新状态,分别是N(r)的开始状态和唯一的接受状态。要从i到达f,我们可以沿着新引入
    的标号为ε的路径前进,这个路径对应于L(s)的一个串。我们也可以到达N(s)的开始状态,然后经过该NFA,再零次或多次从它的
    接受状态回到它的开始状态并重复上述过程。
    

    (3)利用Thompson算法为正则表达式r=(a|b)*abb构造一个NFA

    1)首先画出语法分析树
    

    2)对于表达式r1=a,r2=b构造NFA
    

    3)对于表达式r3=r1|r2构造NFA
    

    4)对于表达式r5=r3*构造NFA
    

    5)对于表达式r6=r1r2构造NFA
    

    6)对于表达式r7=r5r6构造NFA
    

    7)同理最后可以得到NFA
    

    6.由NFA构造DFA的子集构造算法(subset construction)

    输入:一个NFA N.
    输出:一个接受同样语言的DFA D.
    方法:我们为D构造一个转换表Dtran,D的每个状态是一个NFA状态集合,我们将构造Dtran,使得D"并行地"模拟N在遇到一个
    给定输入串时可能执行的所有动作。我们面对的第一个问题是正确处理N的ε转换。
    

    下面给定了一些函数的定义,这些函数描述了一些需要在这个算法中执行的N的状态集上的基本操作,s表示N的单个状态,T代表N的一个状态集。

    我们需要找出当N读入了某个输入串之后可能位于的所有状态集合。
    首先,在读入第一个输入符号之前,N可以位于集合ε-closure(s0)中的任何状态上,其中s0是N的开始状态。下面进行归纳定义,
    假定N在读入输入串x之后可以位于集合T中的状态上。如果下一个输入符号是a,那么N可以立即移动到move(T,a)中的任何状态。
    然而,N可以在读入a后再执行几个ε转换,因此N在读入xa之后可位于ε-closure(move(T,a))中的任何状态上。
    

    ε-closure(T)的计算:从一个状态集合开始,所有只存在标号为ε的边都加入T
    

    对于上面由Thompson算法为正则表达式r=(a|b)*abb构造一个NFA,我们将这个NFA转换成一个DFA

    首先,NFA的开始状态A是ε-closure(0),即A={0,1,2,4,7},NFA的输入字母表是{a,b},则
    Dtran[A,a]=ε-closure(move(A,a))=ε-closure({3,8})={1,2,3,4,6,7,8},令B=Dtran[A,a]
    Dtran[A,b]=ε-closure(move(A,b))=ε-closure({5})={1,2,4,6,7},令C=Dtran[A,b]
    Dtran[B,a]=ε-closure(move(B,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=B
    Dtran[B,b]=ε-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9},令D=Dtran[B,b]
    Dtran[C,a]=ε-closure(move(C,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=B
    Dtran[C,b]=ε-closure(move(C,b))=ε-closure({5})={1,2,4,6,7}=C
    Dtran[D,a]=ε-closure(move(D,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=B
    Dtran[D,b]=ε-closure(move(D,b))=ε-closure({5,10})={1,2,4,5,6,7,10},令E=Dtran[D,b]
    Dtran[E,a]=ε-closure(move(E,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=B
    Dtran[E,b]=ε-closure(move(E,b))=ε-closure({5})={1,2,4,6,7}=C
    

    所有DFA的转换表Dtran

    根据转换表可以得到DFA

    7.最小化一个DFA的状态数量

    输入:一个DFA D,其状态集合为S,输入字母表为∑,开始状态为s0,接受状态为F。
    输出:一个DFA D',它和D接受同样的语言,且状态数最少。
    方法:
    1)首先构造包含两个组F和S-F的初始划分II,这两个组分别是D的接受状态组和非接受状态组。
    2)用下面的构造新的分划IInew
    

    3)如果IInew=II,令IIfinal=II并接着执行步骤4),否则,用IInew替换II并重复步骤2)。
    4)在分划IIfinal的每个组中选取一个状态作为该组的代表。这些代表构成了状态最少DFA D'的状态。
    D'的其他部分按如下步骤构建:
    (a)D'的开始状态是包含了D的开始状态的组的代表。
    (b)D'的接受状态是那些包含了D的接受状态的组的代表。
    (c)令s是IIfinal中某个组G的代表,并令DFA D中在输入a上离开s的转换到达状态t。令r为t所在组H的代表。
    那么在D'中存在一个从s到r在输入a上的转换。
    

    对上面的DFA最小化

    首先初始划分包括两个组{A,B,C,D},{E},分别是非接受状态组和接受状态组。构造IInew时,考虑这两个组
    和输入符号a和b,因为组{E}只包含一个状态,不能再被分割,所以{E}被原封不动的保留在IInew中。对于
    {A,B,C,D},是可以被分割的,因此我们必须考虑各个输入符号的作用,在输入a上,这些状态中的每一个都
    转到B,因此使用以a开头的串无法区分这些状态。但对于输入b,状态A、B、C都转换到{A,B,C,D}的某个成
    员上,而D转到另一组中的成员E上,因此在IInew中,{A,B,C,D}被分割成{A,B,C},{D},现在IInew中有
    {A,B,C},{D},{E}。对于{A,B,C},在输入b上,A和C都到达{A,B,C}中的元素,B却到达D上,所有IInew
    有{A,C},{B},{D},{E},对于{A,C}无法在分割。
    所有最后有{A,C},{B},{D},{E},构造如下的DFA
    

    展开全文
  • 编译原理 词法分析
  • 编译原理词法分析、语法分析程序代码
  • 编译原理词法分析.rar

    2020-04-02 10:17:12
    这是编译原理词法分析部分,这部分难度比较大,代码量也很大,大家有需要的拿去参考参考,希望对你们有用。
  • 编译原理词法分析程序设计实验报告 实验目的 了解词法分析的主要任务 熟悉编译程序的编制 实验内容 根据某文法构造一基本词法分析程序找出该语言的关键字标识符整数以及其他一些特殊符号给出单词的种类和值 实验...
  • 编译原理词法分析.zip

    2020-03-17 13:56:18
    编译原理词法分析实验,C语言编写,代码500+行。包含源代码、实验报告、状态迁移图、输入输出文档,最终成绩90+。 题目:C语言词法分析程序的设计与实现  实验内容及要求: 1. 可以识别出用C语言编写的源程序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,657
精华内容 1,462
关键字:

编译原理词法分析