实验一 编写词法分析程序

《实验一 编写词法分析程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一编写词法分析程序1实验类型设计型实验，4学时（2学时完成DFA的设计；2学时完成程序的编写、调试、测试）2实验目的通过设计、调试词法分析程序，掌握词法分析程序的设计工具，即有穷自动机，进一步理解自动机理论；掌握正则文法和正则表达式转换成有穷自动机的方法及有穷自动机实现的方法；会确定词法分析程序的输出形式及标识符与关键字的区分方法；加深对课堂教学的理解，提高词法分析方法的实践能力。3背景知识词法分析对源程序从头到尾扫描一次，识别符合程序设计语言词法规则的单词并输出，为后续的语法分析和语义提供输入。词法分析程序的一般

2、设计方案如下：1、用正则表达式或正则文法描述程序设计语言的词法规则，通常采用正则表达式；一个正则表达式对应一条词法规则。2、为每个正则表达式构造一个NFA，用来识别正则表达式描述的单词。3、将多个NFA合并为一个NFA。4、将NFA转换成等价的DFA。5、最小化DFA。6、确定单词的输出形式。7、化简后的DFA＋单词输出形式⇒构造词法分析程序从上述设计方案可知，要构造词法分析程序，必须掌握以下三个知识点：文法、正则表达式和有穷自动机FA。3.1文法的形式定义一个形式文法G是下述元素构成的一个四元组(VN，VT，P，S)

3、。其中：1、VT：非空有限的终结符号集；终结符：一个语言不可再分的基本符号。2、VN:非空有限的非终结符号集；非终结符：一个非终结符是一个类（集合）记号，而不是一个体记号。3、S:开始符号或识别符号，S∈VN；4、P：产生式规则集；产生式形如α→β或α::=β的表达式，其中α为左部，β为右部。α∈(VT∪VN)+且至少含一个VN；β∈(VT∪VN)*。5、VT∩VN=Ф。3.2正则表达式的形式定义仅由字母表A={aii=1，2，…，k}上的正则表达式α所组成的语言称为正则集，记为L(α)。正则集的形式化描述式称为正则表

4、达式。字母表S上的正则表达式和正则集递归定义如下：1、S中的a是正则表达式，其正则集为{a}；2、空串e是S上的正则表达式，其正则集为{e}；3、空集F是S上的正则表达式，其正则集为F；4、如果e1和e2是S上的正则表达式，它们所表示的正则集分别为L(e1)与L(e2)，则：e1

5、e2也是S上的正则表达式，其正则集为L(e1

6、e2)=L(e1)∪L(e2)。e1e2也是S上的正则表达式，其正则集为L(e1e2)=L(e1)L(e2)。(e1)*也是S上的正则表达式，其正则集为L((e1)*)=L(e1)*。3.3有穷自

7、动机定义确定的有穷自动机DFAM=（Q，S，t，q0，F），其中：1、Q—有穷非空状态集；2、S—有穷输入字母表；3、t—映射Q´S→Q(单值映射，下态确定)；4、q0—q0∈Q,称为开始状态(唯一)；5、F—非空终止状态集；非确定有穷自动机(NFAM)定义与DFAM相比可以：允许ε弧；t多值的，即t（s,a）无法唯一地确定下一状态。对于FA，最重要的是给出其映射。可以由状态转换矩阵，状态图或者直接给出。1、直接给出：t(q,a)=q’；2、状态转换矩阵：状态为表列，字母为表行；3、状态图：是由一组矢线连接的有穷个结点

8、所组成的有向图。每一结点均代表在识别或分析过程中扫描器所处的状态。它是设计和实现扫描器的一种有效工具，是有穷自动机的直观图示。对任何两个有穷的自动机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

9、(S0)=S0∪Sε，Sε={s

10、从S0出发经过任意条ε弧可达s}3、把I填入P的I列4、计算Ia，Ib，IC，…，并填入相应的列。Ia=ε－CLOSURE(Ja)，Ja={s

11、从I的某一状态出发经过一条a弧可到s}5、若J∈{Ia，Ib，IC，…}未在I列出现，则令I=J。并重复3~5直列所有的J均在I列中出现过。6、把P中的各子集作为状态，并重新命名。7、确定终态和初态：初态：I列的第一个元素。终态：含有原NFA任一终态的子集。8、画出相应的DFA3.4正则文法到有穷自动机的转换步骤：1、VT⇒Σ；2、VN⇒Q，其

12、中S⇒q0；3、A中增加新状态Z作为终态；4、U→aV⇒t(U，a)=V；la∈VT或a=ε，V∈VN。5、U→a(a∈VT)⇒t(U,a)=Z。3.5正则表达式到有穷自动机的转换步骤：对于任意的一个正则表达式e，从开始，按照变换规则，逐步扩弧、扩结，直到转换图上所有的弧上都是∑中的单个符号为止。对于引入的每一个新状态，应该赋予一