实验一 编写法分析程序.doc

实验一 编写词法分析程序 1 实验类型 设计型实验 2 实验目的 通过设计、调试词法分析程序，掌握词法分析程序的设计工具，即有穷自动机，进一步理解自动机理论；掌握文法转换成自动机的技术及有穷自动机实现的方法；会确定词法分析器的输出形式及标识符与关键字的区分方法；加深对课堂教学的理解，提高词法分析方法的实践能力。 3 背景知识 词法分析作为相对独立的阶段来完成（对源程序或中间结果从头到尾扫描一次，并作相应的加工处理，生成新的中间结果或目标程序）。在词法分析过程中，编译程序从外部介质中读取源程序文件中的各个字符，为正确地识别单词，有时还需进行超前有哪些信誉好的足球投注网站和回退字符等操作。因此，为了提高读盘效率和便于扫描器进行工作，通常可采用缓冲输入的方案，即在内存中设置一个适当大小的输入缓冲区，将磁盘上的源程序字符串分批送入该缓冲区中，供扫描器进行处理。 词法分析程序的一般设计方案是： 1、程序设计语言词法规则?正则文法? FA； 或：词法规则?正则表达式? FANFA确定化? DFA； 3、DFA最小化； 4、确定单词符号输出形式； 5、化简后的DFA＋单词符号输出形式?构造词法分析程序。 从设计方案可知，要构造词法分析程序，必须掌握以下三个知识点：文法、正则表达式FA。 文法与语言的形式定义如下： 一个形式文法 G 是下述元素构成的一个元组(VN ，VT ，PS )。其中： 1、 VT —非空有限的终结符号集，即 Σ； 终结符：一个语言不可再分的基本符号。 2、VN—非空有限的非终结符号集； 非终结符：也称语法变量，用来代表语法范畴。一个非终结符代表一个一定的语法概念，是一个类（集合）记号，而不是一个体记号。 3、S —开始符号/识别符号，S∈ VN ； 4、P —产生式规则集（或叫规则或生成式或重写规则）； 产生式：形如α → β或α ::= β的表达式，其中α为左部，β为右部。α∈(VT∪VN)+且至少含一个VN；β∈(VT∪VN)*。 5、VT∪VN =Ф。 仅由字母表A={ai i=1，2，…，k}上的正则表达式α所组成的语言称为正则集，记为L(α )。正则集的形式化描述式称为正则表达式。字母表S上的正则表达式和正则集递归定义如下： 1、S 中的a{a}； 2、空串e是S上的正则表达式，其正则集为{e}； 3、空集F是S上的正则表达式，其正则集为F ； 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)*。 而确定有限自动机(DFA)理论定义DFA M=（Q ，S ，t ，q0 ，F）。其中： 1、Q —有穷非空状态集； 2、S —有穷输入字母表； 3、t — 映射Q ′ S → Q(单值映射，下态确定)； 4、q0 —q0∈Q,称为开始状态(唯一)； 5、F —非空终止状态集； 非确定有限自动机(NFA M) 定义与DFA M的比较可知： NFA可有多个初态，并可能含ε弧或字符串弧；在NFA中，t是多值的，即t（s, a）无法唯一地确定下一状态。 对于FA，最重要的是给出其映射。可以由状态转换表，状态转换图或者直接给出。 1、直接给出：t(q ,a)=q’； 2、状态转换表：状态为表列，字母为表行； 3、状态转换图：是由一组矢线连接的有限个结点所组成的有向图。每一结点均代表在识别或分析过程中扫描器所处的状态。它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示。下面是标识符的状态图： 图1：标识符状态图 （正则表达式与有限自动机的等价性）定义：对任何两个有限的自动机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) = S0∪Sε Sε= {s| 从S0的某一状态出发经过任意条ε弧可达s} 3、 把I填入P的I列 4、计算Ia，Ib，IC，…，并填入相应的列。 Ia = ε－CLOSURE(Ja) Ja = {s | 从I的某一状态出发经过一条a弧可到s} 5、若J∈{ Ia，Ib，IC，…}未在I列出现，则令I = J。 并重复3~5直列所有的J均在I列中出现过。 6、把