实验一 编写词法分析程序

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

1、实验一编写词法分析程序1实验类型设计型实验2实验目的通过设计、调试词法分析程序，掌握词法分析程序的设计工具，即有穷自动机，进一步理解自动机理论；掌握文法转换成自动机的技术及有穷自动机实现的方法；会确定词法分析器的输出形式及标识符与关键字的区分方法；加深对课堂教学的理解，提高词法分析方法的实践能力。3背景知识词法分析作为相对独立的阶段来完成（对源程序或中间结果从头到尾扫描一次，并作相应的加工处理，生成新的中间结果或目标程序）。在词法分析过程中，编译程序从外部介质中读取源程序文件中的各个字符，为正确地识别单词，有时还需进行超前搜索和

2、回退字符等操作。因此，为了提高读盘效率和便于扫描器进行工作，通常可采用缓冲输入的方案，即在内存中设置一个适当大小的输入缓冲区，将磁盘上的源程序字符串分批送入该缓冲区中，供扫描器进行处理。词法分析程序的一般设计方案是：1、程序设计语言词法规则⇒正则文法⇒FA；或：词法规则⇒正则表达式⇒FA；2、NFA确定化⇒DFA；3、DFA最小化；4、确定单词符号输出形式；5、化简后的DFA＋单词符号输出形式⇒构造词法分析程序。从设计方案可知，要构造词法分析程序，必须掌握以下三个知识点：文法、正则表达式和FA。文法与语言的形式定义如下：一个形式

3、文法G是下述元素构成的一个元组(VN，VT，P，S)。其中：1、VT—非空有限的终结符号集，即Σ；终结符：一个语言不可再分的基本符号。2、VN—非空有限的非终结符号集；非终结符：也称语法变量，用来代表语法范畴。一个非终结符代表一个一定的语法概念，是一个类（集合）记号，而不是一个体记号。3、S—开始符号/识别符号，S∈VN；4、P—产生式规则集（或叫规则或生成式或重写规则）；产生式：形如α→β或α::=β的表达式，其中α为左部，β为右部。α∈(VT∪VN)+且至少含一个VN；β∈(VT∪VN)*。5、VT∪VN=Ф。仅由字母表A=

4、{aii=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

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

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

7、)L(e2)。(e1)*也是S上的正则表达式，其正则集为L((e1)*)=L(e1)*。而确定有限自动机(DFA)理论定义DFAM=（Q，S，t，q0，F）。其中：1、Q—有穷非空状态集；2、S—有穷输入字母表；3、t—映射Q´S→Q(单值映射，下态确定)；4、q0—q0∈Q,称为开始状态(唯一)；5、F—非空终止状态集；非确定有限自动机(NFAM)定义与DFAM的比较可知：NFA可有多个初态，并可能含ε弧或字符串弧；在NFA中，t是多值的，即t（s,a）无法唯一地确定下一状态。对于FA，最重要的是给出其映射。可以由状态转换表，

8、状态转换图或者直接给出。1、直接给出：t(q,a)=q’；2、状态转换表：状态为表列，字母为表行；3、状态转换图：是由一组矢线连接的有限个结点所组成的有向图。每一结点均代表在识别或分析过程中扫描器所处的状态。它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示。下面是标识符的状态图：图1：标识符状态图（正则表达式与有限自动机的等价性）定义：对任何两个有限的自动机M1和M2，若有L(M1)=L(M2)，则称M1与M2等价。可通过子集法或造表法求解NFA的等价DFA（NFA的确定化方法）。NFA的确定化方法算法（表格法）：1、

9、画一张具有n+1列的矩阵表P，n=NFA中出现的符号的个数。各应列的名字分别为I，Ia，Ib，IC，…，其中，a，b，c…是NFA中出的所有字符。2、令I=ε－CLOSURE（S0）。S0：NFA的初态集。ε－CLOSURE(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均在

12、I列中出现过。6、把P中的各子集作为状态，并重新命名。7、确定终态和初态：初态：I列的第一个元素。终态：含有原NFA任一终态的子集。8、画出相应的DFA正则文法到有穷自动机的转换步骤：1、VT⇒Σ；2、VN⇒Q,其中S⇒q0；3、A中增加新状态Z作为终态；4、U