编译原理第3章.pptVIP

编译原理 第3章 词法分析 3.1设计扫描器时应考虑的几个问题 完全独立模式的好处：改进编译程序的效率、增强编译程序的可移植性、结构清晰、简化设计。 相对独立模式的好处：词法分析器和语法分析器被设计在同一趟，省去了存放单词的终结文件 词法分析过程 逐个读入源程序字符，然后按照构词规则切分成一列单词，再转换成单词序列。单词是语言中具有独立意义的最小单位。 词标(token）是单词的机内表示，其格式由实现系统规定。 实现词法分析程序时，首先需要描述单词，其次需要执行某些相关操作识别单词。 描述程序设计语言的词法的机制是3型文法和正规式，识别机制是有穷状态自动机（FA）。 在词法分析过程中，与语法分析无关的单词应处理时可掠过，无需产生相应词标。 3.1.2 单词符号的内部表示 单词的分类 单词符号一般可分为下列五种： 基本字，关键字； 标识符； 常数（量）； 运算符； 分隔符 关键字,运算符和分隔符每字为一类。标识符统一为一类,而常数一般按数据类型进行分类。 至于单词的值,一字一类的符号的类别号已能完全表示相应的符号,故不须再给出单词的值;但一个类别中含有多个单词,则除了类别号,还须按某种编码给出单词的值。 3.1.3 识别标识符的若干约定和策略 3.1.4 源程序的输入及预处理 3.2正规文法和状态转换图 3.2.1 由正规文法构造状态转换图 一个状态转换图是由一组矢线连接的有限个节点所组成的有向图。 每个节点均代表在识别或分析过程中扫描器的状态，其中有一个是开始状态(带箭头)，至少有一个状态是结束状态（双圈）。 状态间用矢线连接，矢线上标记有符号，表示在矢线射出端的状态下，读入矢线上标记的符号可转换到矢线指向的状态。状态图只有有穷个状态。 状态图识别符号串 利用状态转换图可识别相应文法所表示的符号串。 对符号串W=a1a2a3……an，ai∈ VT 识别过程： 从初态S出发，自左至右逐个扫描W中的字符，在S状态下扫视的符号为a1； 在节点S所射出诸矢线中寻找标记为a1的矢线(若不存在，则说明W有错)； 读入a1，沿矢线方向到下一状态，在此状态时扫描a2，……， 直至W中全部字符读完且进入终态F，则W已被接受。 结 论 1、M对符号串识别的方法是自顶向下的分析方法； 2、M初态出发，沿某路径到达状态Ak，则a1a2a3……akAk是G的一个句型，且是规范句型。当A是终态时，a1a2……ak为G的句子。 3、M所识别的任一符号串x，必存在S=*x ，反之，L(G)中的任一句子y，必存在一条从S到F的路径，将此路径上各矢线的标记依次连接起来所组成的符号串即为y。 ∴M能识别出L(G)中的全部句子。 结 论 3.2.2 状态图的一种实现--状态矩阵法 3.3 有限自动机（FA） 3.3 有限自动机（FA） 3.3.1 确定的有限自动机 DFA识别符号串 ∑*上的字符串t在M上运行 输入字符串t，(表示成Tt1的形式，其中T∈∑，t1∈∑*）在DFA M上运行的定义为： ?（Q,Tt1）= ?（ ? （Q,T）,t1） 其中Q∈K ∑*上的字符串t被M接受 若t?∑*，? (S,t)=P，其中S为DFA M的开始状态， P? Z，Z为终态集。则称t为DFA M所接受（识别） 算法：模拟DFA。 输入 输入串x，由文件结束符eof结尾。一个DFA D，其开始状态是s0，其接受状态集合是F。 输出 如果D接受x，则回答“yes”，否则回答“no”。 方法 对输入串x，函数move(s, c)给出一个状态，它是面临输入符号c，状态s的转换。函数nextchar( )返回输入串x中的下一个字符。 例3.4，设计能接受偶数个0和偶数个1组成的串的有限自动机，画出其状态图及状态转换矩阵并判别110101、11101能否被该自动机接受。 3.3.2 非确定的有限自动机 ∑*上的字符串t在M上运行 一个输入符号串t，（表示成Tt1的形式，其中T∈∑，t1∈ ∑*）在NFA M上运行的定义为： ?（Q， Tt1）= ?（ ? （Q，T），t1） Q∈K ∑*上的字符串t被NFA M接受 若t?∑*，? (S0,t)={P1,P2,P3,……}，其中S0∈S， Pi?Z， 则称t为NFA M所接受（识别）。 3.3.3 NFA与DFA的等价性 3.3.4 具有ε动作的FA 3.3.5 具有ε动作的NFA的确定化 3.3.6 DFA状态数的最小化 最小状态DFA的含义: 没有多余状态(死状态)； 没有等价状态（不可区别）。 一个DFA可以通过消除多余状态和合并等价状态转换成最小的与之等价的DFA。 有穷自动机的多余状态指： 从自动机的开始状态出发，任何输入