状态转换图-《编译原理与实践》

状态转换图是设计词法分析程序的一种很好的方法，它既可以描述单词的结构，也可以识别单词。只要用程序实现了识别单词的状态转换图就可以完成词法分析器。

状态转换图是一个有限图，结点用圆圈表示，称为状态。状态之间用带箭头的弧线连接，称为边。由状态0到状态1的边上标记的字符表示使状态0转换到状态1的输入字符或字符类。例如，图3-3（a）表示在状态0下，若输入的字符是a，则读进a，并转换到状态1；若输入的字符是b，则读进b，并转换到状态2。一张状态转换图只包含有限个状态（即有限个结点），其中，有一个初态（用“⇒”表示），至少有一个终态（用双圈表示）。用状态转换图识别单词时从初态开始，读进输入符号串的一个符号a，沿着状态转换标记为a的边进入下一状态，重复执行直到进入终结状态。即，如果存在一个从起始状态到终结状态的路径，路径上的标记用连接运算符连接在一起形成一个符号串，如果它和输入符号串相同，则称该输入符号串可以接受；如果不能进入任何一个终结状态，则称该状态转换图不能识别或接受这个输入符号串。例如，图3-3（b）是识别L语言定义的标识符的状态转换图，其中，状态0为初态，状态2为终态。用此状态转换图识别标识符的过程是：从初态0开始，读取一个字符，如果该字符是字母，则读入它，并转向状态1，否则，识别标识符失败；在状态1，读取下一个字符，若该字符为字母或数字，则读进，状态仍然处于状态1（可利用while循环实现）；若在状态1读入的字符不是字母或数字时，就转向状态2（该字符已读进）；状态2是接受状态，意味着已识别出一个标识符，识别过程结束。然而此时已读入了一个不是字母或数字的字符，它不属于刚刚识别的标识符的一部分，而属于下一个单词，因此，输入指针必须回退一个字符，将其退回给扫描缓冲区，并在终态结点上标上星号*。图3-3（c）中给出了识别整数的状态转换图，图3-3（d）是识别实数的状态转换图，不带正负号，既可以识别整数，也可以识别带指数和（或）小数的实数。

(https://www.xing528.com)

图3-3　状态转换图

高级语言主要包括五种单词，每种单词都有其构成规则，包含多个状态转换图，每个图说明一组单词的构成，设计时首先画出每种单词的状态转换图，然后根据状态转换图编写识别该类单词的函数。