实验一编写词法分析程序

实验一 编写词法分析程序1 实验类型设计型实验，4学时（2学时完成DFA的设计；2学时完成程序的编写、调试、测试）2 实验目的通过设计、调试词法分析程序，掌握词法分析程序的设计工具，即有穷自动机，进一步理解自动机理论；掌握正则文法和正则表达式转换成有穷自动机的方法及有穷自动机实现的方法；会确定词法分析程序的输出形式及标识符与关键字的区分方法；加深对课堂教学的理解，提高词法分析方法的实践能力。3 背景知识词法分析对源程序从头到尾扫描一次，识别符合程序设计语言词法规则的单词并输出，为后续的语法分析和语义提供输入。词法分析程序的一般设计方案如下：1、用正则表达式或正则文法描述程序设计语言的词法规则，通常采用正则表达式；一个正则表达式对应一条词法规则。2、为每个正则表达式构造一个NFA，用来识别正则表达式描述的单词。3、将多个NFA合并为一个NFA。4、将NFA转换成等价的DFA。5、最小化DFA。6、确定单词的输出形式。7、化简后的DFA单词输出形式构造词法分析程序从上述设计方案可知，要构造词法分析程序，必须掌握以下三个知识点：文法、正则表达式和有穷自动机FA。3.1文法的形式定义 一个形式文法 G 是下述元素构成的一个四元组(VN ，VT ，P，S )。其中：1、 VT：非空有限的终结符号集；终结符：一个语言不可再分的基本符号。2、 VN: 非空有限的非终结符号集；非终结符：一个非终结符是一个类（集合）记号，而不是一个体记号。3、S:开始符号或识别符号，S VN ；4、P：产生式规则集；产生式形如 或 := 的表达式，其中为左部，为右部。(VTVN)+且至少含一个VN；(VTVN)*。5、VTVN =。3.2 正则表达式的形式定义仅由字母表A=ai i=1，2，k上的正则表达式所组成的语言称为正则集，记为L( )。正则集的形式化描述式称为正则表达式。字母表S上的正则表达式和正则集递归定义如下：1、S 中的a是正则表达式，其正则集为a；2、空串e是S上的正则表达式，其正则集为e；3、空集F是S上的正则表达式，其正则集为F ；4、如果e1和e2是S上的正则表达式，它们所表示的正则集分别为L(e1)与L(e2) ，则：e1|e2也是S上的正则表达式，其正则集为L(e1|e2)=L(e1) L(e2)。e1e2也是S上的正则表达式，其正则集为L(e1e2)=L(e1) L(e2)。(e1)* 也是S上的正则表达式，其正则集为L(e1)* )=L(e1)*。3.3有穷自动机定义确定的有穷自动机DFA M=（Q ，S ，t ，q0 ，F），其中：1、Q 有穷非空状态集；2、S 有穷输入字母表；3、t 映射Q S Q(单值映射，下态确定)； 4、q0 q0Q,称为开始状态(唯一)；5、F 非空终止状态集；非确定有穷自动机(NFA M) 定义与DFA M相比可以：允许弧；t多值的，即t（s, a）无法唯一地确定下一状态。对于FA，最重要的是给出其映射。可以由状态转换矩阵，状态图或者直接给出。1、直接给出：t(q ,a)=q；2、状态转换矩阵：状态为表列，字母为表行；3、状态图：是由一组矢线连接的有穷个结点所组成的有向图。每一结点均代表在识别或分析过程中扫描器所处的状态。它是设计和实现扫描器的一种有效工具，是有穷自动机的直观图示。对任何两个有穷的自动机M1和M2，若有L(M1)=L(M2)，则称M1与M2等价。可通过造表法求解NFA的等价DFA（NFA的确定化方法）。NFA的确定化方法算法（表格法）：1、画一张具有n+1列的矩阵表P，n = NFA中出现的符号个数。各应列的名字分别为I，Ia，Ib，IC，其中，a，b，c是NFA中出的所有字符。2、令I = CLOSURE（S0）。S0：NFA的初态；CLOSURE(S0) = S0S，S= s| 从S0出发经过任意条弧可达s3、 把I填入P的I列4、计算Ia，Ib，IC，并填入相应的列。Ia = CLOSURE(Ja)，Ja = s | 从I的某一状态出发经过一条a弧可到s5、若J Ia，Ib，IC，未在I列出现，则令I = J。并重复35直列所有的J均在I列中出现过。6、把P中的各子集作为状态，并重新命名。7、确定终态和初态：初态：I列的第一个元素。终态：含有原NFA任一终态的子集。8、画出相应的DFA3.4 正则文法到有穷自动机的转换步骤：1、VT ；2、VN Q，其中Sq0；3、A中增加新状态Z作为终态；4、U aV t(U，a)=V；l aVT或 a=，VVN 。5、U a (aVT) t(U,a)=Z。3.5 正则表达式到有穷自动机的转换步骤：对于任意的一个正则表达式e，从 开始，按照变换规则，逐步扩弧、扩结，直到转换图上所有的弧上都是中的单个符号为止。对于引入的每一个新状态，应该赋予一个独有的名字。其变换规则如下：3.6 单词输出对于一个语言来说，如何对其单词进行分类和编码并没有一个原则性的规定，而主要取决于处理上的方便。4 实验内容编写TEST语言的词法分析程序，并完成词法分析程序的编程与调试。TEST 语言的词法规则如下：TEST语言的词法规则如下：1、标识符：字母打头，后接任意字母或数字，2、保留字：标识符的子集，包括：if,else,for,while,do, int,write,read，3、无符号整数：由数字组成，但最高位不能为0，允许一位的0，4、分界符：(、)、;、5、运算符：+、-、*、/、=、=、=、!=、=6、注释符：/* */5 实验要求1. 根据TEST语言的词法规则，分别写出每条规则的正则文法或者正则表达式；2. 将每一个正则文法或者正则表达式转换为NFA；3. 将多个NFA合并后进行确定化并化简；4. 根据化简后的DFA画出流程图；5. 确定单词分类、单词输出方案；6. 编写词法分析程序；7. 对下面的TEST语言源程序进行词法分析，将合法单词存入lex.txt，并报告词法错误及其位置。注：不能修改源程序/*This a test program.*/int abc;int 123;int A$;int i;int n;int b,c;int 2a;int a2;read n;n = 012345;for (i=1;i=n; i= i+1) abc=abc+i;if (!n) b = b+c;/*The loop endedwrite abc;以上内容写入实验报告。6 实验思考1、 你的编写词法分析程序满足最长匹配原则吗？如果满足请给出你的实现方案。如果不满足请给出改进方案。2、 给出你的单词分类方案，并说明理由。3、 构建词法分析程序一般过程是怎样的？