实验1-3 《编译原理》词法分析程序设计方案

实验1-3《编译原理》词法分析程序设计方案一、实验目的1.深入理解词法分析在编译程序中的地位和作用。2.熟练掌握词法分析程序的设计方法，能够运用状态转换图和有限自动机等工具实现词法分析功能。3.通过编写词法分析程序，提高程序设计和调试能力，加深对编译原理中词法分析阶段相关知识的理解和运用。

二、实验内容设计并实现一个词法分析程序，该程序能够对给定的源程序进行扫描，识别出各种单词，并将其分类输出。具体来说，需要实现以下功能：1.能够识别源程序中的关键字、标识符、常量、运算符和界符等单词。2.对识别出的单词进行分类，并输出每个单词的类别和值。3.能够处理源程序中的注释，忽略注释内容。

三、实验环境1.编程语言：C语言2.开发工具：VisualStudio2019（或其他C语言集成开发环境）

四、词法分析概述词法分析是编译的第一个阶段，其主要任务是从左到右逐个字符地对源程序进行扫描，依据词法规则将其识别为一个个单词。词法分析程序的输出通常是一个单词序列，每个单词由单词类别和单词自身的值组成。

单词分类1.关键字：如C语言中的`if`、`else`、`while`、`for`、`int`、`float`等，它们具有固定的语义，是语言的一部分。2.标识符：用于表示程序中的变量、函数、类型等，由字母、数字和下划线组成，且首字符必须为字母或下划线。3.常量：包括整型常量、实型常量、字符常量和字符串常量等。4.运算符：如`+`、``、`*`、`/`、`=`、`>`、`<`等，用于进行各种运算。5.界符：如逗号`，`、分号`;`、括号`(`、`)`、`[`、`]`等，用于界定程序的结构。

词法分析方法常见的词法分析方法有有限自动机（FiniteAutomata,FA）。有限自动机分为确定有限自动机（DeterministicFiniteAutomata,DFA）和非确定有限自动机（NondeterministicFiniteAutomata,NFA）。DFA是一种状态机，它在任何时刻都处于一个确定的状态，对于每个输入符号，都有唯一的转移。NFA则可以在某些情况下有多个转移选择。在词法分析中，通常先将词法规则转换为NFA，然后通过一定的算法将NFA转换为DFA，最后基于DFA实现词法分析程序。

五、设计方案状态转换图设计根据词法规则，设计状态转换图（StateTransitionDiagram,STD）。状态转换图是描述有限自动机的一种图形表示，它由状态和有向边组成。每个状态表示词法分析过程中的一个阶段，有向边表示从一个状态到另一个状态的转换，边上标记的是输入字符。

例如，对于标识符的状态转换图：初始状态为`S0`，表示开始识别标识符。当输入字母或下划线时，进入状态`S1`，继续识别后续字符。在状态`S1`下，若输入字母、数字或下划线，则继续停留在`S1`；若输入其他字符，则识别结束，标识符类别为`ID`，值为当前识别的字符串。

对于关键字的识别，可以在识别出标识符后，通过查找关键字表来确定其是否为关键字。如果是关键字，则将类别标记为相应的关键字类别；否则为标识符类别。

对于常量的识别，以整型常量为例：初始状态为`S0`，若输入数字，则进入状态`S1`。在状态`S1`下，若继续输入数字，则保持在`S1`；若输入非数字字符，则识别结束，常量类别为`INT_CONST`，值为当前识别的数字字符串。

数据结构设计1.状态结构体```ctypedefstruct{intstate;intnext_state[256];intfinal_state;inttoken_type;}State;````state`：当前状态编号。`next_state[256]`：存储针对每个输入字符的下一个状态编号，最多可处理256种不同字符。`final_state`：标记该状态是否为最终状态。`token_type`：如果是最终状态，存储该状态对应的单词类别。2.单词结构体```ctypedefstruct{inttoken_type;chartoken_value[MAX_TOKEN_LEN];}Token;````token_type`：单词类别。`token_value[MAX_TOKEN_LEN]`：存储单词的值，`MAX_TOKEN_LEN`定义了单词值的最大长度。3.关键字表```ctypedefstruct{charkeyword[MAX_KEYWORD_LEN];intkeyword_type;}Keyword;````keyword[MAX_KEYWORD_LEN]`：存储关键字字符串。`keyword_type`：关键字对应的类别。

算法设计1.词法分析主程序初始化词法分析器，设置初始状态。从源程序文件中逐个读取字符。根据当前状态和读取的字符，查找状态转换表，确定下一个状态。如果下一个状态为最终状态，则输出当前单词的类别和值，并更新状态为初始状态，继续读取下一个字符。如果遇到注释，则跳过注释内容。当源程序读取完毕，结束词法分析。2.状态转换表生成算法根据设计的状态转换图，初始化状态转换表。对于每个状态，遍历所有可能的输入字符，确定从该状态出发在该字符输入下的下一个状态。标记最终状态及其对应的单词类别。3.关键字匹配算法在识别出标识符后，遍历关键字表。将标识符与关键字表中的每个关键字进行比较。如果匹配成功，则将单词类别更新为相应的关键字类别；否则为标识符类别。

六、程序实现步骤初始化部分1.初始化状态转换表，根据状态转换图设置每个状态的转移关系和最终状态信息。2.初始化关键字表，将C语言中的关键字及其类别存储到关键字表中。3.打开源程序文件，准备读取字符。

词法分析循环1.从源程序文件中读取一个字符。2.根据当前状态和读取的字符，查找状态转换表，获取下一个状态。3.如果下一个状态为最终状态：判断当前单词是否为关键字，若是则更新单词类别。将单词的类别和值存储到单词结构体中。输出单词的类别和值。重置当前状态为初始状态。4.如果读取到的字符是注释的开始符号（如`/*`）：跳过注释内容，直到遇到注释结束符号（如`*/`）。5.如果读取到文件末尾，结束词法分析。

程序结束关闭源程序文件，释放相关资源。

七、测试用例简单算术表达式```cintmain(){inta=10;intb=20;intc=a+b;return0;}```预期输出：|单词类别|单词值||::|::||关键字|int||标识符|main||界符|(||关键字|int||标识符|a||界符|=||常量|10||关键字|int||标识符|b||界符|=||常量|20||关键字|int||标识符|c||界符|=||标识符|a||运算符|+||标识符|b||界符|)||关键字|return||常量|0||界符|;||界符|)|

包含注释的程序```c/*Thisisament*/intfunc(inta,intb){intc=a*b;returnc;}```预期输出：|单词类别|单词值||::|::||关键字|int||标识符|func||界符|(||关键字|int||标识符|a||界符|,||关键字|int||标识符|b||界符|)||界符|{||关键字|int||标识符|c||界符|=||标识符|a||运算符|*||标识符|b||界符|;||关键字|return||标识符|c||界符|;||界符|}|

八、总结通过本次实验，成功设计并实现了一个词法分析程序。该程序能够准确地识别源程序中的各种单词，并进行分类输出。在设计过程中，深入理解了词法分析的原理和方法，运用状态转换图和有限自动机等工具完成了词