词法分析与语法分析程序设计.doc

实验三 词法分析与语法分析程序设计 一．实验目的 基本掌握计算机语言的词法分析程序和语法分析程序的设计方法。 二．实验要求、内容及步骤 实验要求： 1.根据以下的正规式，画出状态图； 标识符：字母(字母|数字字符)* 关键字：if then else while do 十进制整数：0 | （1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）* 运算符和分隔符：+ - * / = ( ) 。 2.根据状态图，设计词法分析函数int scan( )，从键盘读入数据，分析出一个单词。 3.对于只含有+、*运算的算术表达式的如下文法，编写相应的语法分析程序，要求用LL(1)分析表实现，并以id+id*id为例进行测试： E —＞ TE′ E′—＞ +TE′|ε T —＞ FT′ T′—＞ *FT′|ε F —＞（E）| id 实验步骤： 1.根据状态图，设计词法分析算法； 2.采用C++语言，实现该算法； 3.调试程序：输入一组单词，检查输出结果； 4.编制给定文法的非递归的预测分析程序，并加以测试。 ? 三．实验设备 计算机、Windows 操作系统、Visual C++ 程序集成环境。 实验原理 1. 词法分析器读入输入串，将其转换成将被语法分析器分析的词法单元序列。产生下述小语言的单词序列。这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号 种别编码 助记符 内码值 DIM IF DO STOP END标识符 常数（整） = + * ** ， （ ） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR - - - - - - 内部字符串 标准二进形式 - - - - - - 对于这个小语言，有几点重要的限制： 首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的：IF（5）=x。 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。 再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为IF i0 i= 1;而绝对不要写成IFi0 i=1;因为对于后者，我们的分析器将无条件地将IFI看成一个标识符。 这个小语言的单词符号的状态转换图，如下图： 2.语法分析是决定如何使用一个文法生成一个终结符串的过程。 语法分析器 能识别由加+ 减- 乘* 除/ 乘方^ 括号（）操作数所组成的算术表达式，其文法如下： E→E+T|E-T|T T→T*F|T/F|F F→P^F|P p→(E)|i 使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法等。 分析表格式： id + * ( ) $ E E —＞ TE′ E —＞ TE′ E′ E′—＞ +TE′ E′—＞ ε E′—＞ ε T T —＞ FT′ T —＞ FT′ T′ T′—＞ ε T′—＞ *FT′ T′—＞ ε T′—＞ ε F F —＞id F —＞(E) 3.中间代码生成器 产生上述算术表达式的中间代码（四元式序列）。 五．实验代码及结果 词法分析代码： #includestring.h #includeiostream using namespace std; char prog[100],token[10]; char ch; int syn,p,m=0,n,row,sum=0; char *rwtab[20]={dim,if,do,stop,end ,and,begin,bool,case,char, false,for,int,not,or,set,then,true,until,while }; void scaner() { for(n=0;n9;n++) token[n]=NULL; ch=prog[p++]; while(ch== ) { ch=prog[p]