龙书《编译原理》第二版数字识别状态转换图出边与输入处理疑问
龙书数字识别状态转换图的设计逻辑说明
为何状态14、16、17没有设置"other"出边
首先要明确这三个状态在整套识别流程里的定位:
- 状态14:读完小数点、且小数点后至少接了一位数字的节点,属于可以直接返回普通浮点数token的终态
- 状态16:读完
E、以及E后面可选的正负号,但还没读到指数部分数字的非终态节点 - 状态17:在E(连同可选正负号)之后读到至少一位数字的节点,属于可以直接返回科学计数法格式浮点数token的终态
这套手工构建的词法识别状态图,本来就遵循通用的回溯实现约定,根本不需要给这些节点单独画"other"出边:
- 所有非终态如果遇到不匹配的字符,会直接触发回溯,退回之前最后一个被标记的有效终态位置
- 所有终态本身已经标记了当前累积串的有效边界,遇到不匹配的字符直接在当前位置截断即可
给这三个状态补"other"出边本质是冗余的:不管画不画,遇到非预期字符的处理逻辑都是固定的回溯、截断流程,图上没必要重复标注这套通用规则。
上述状态遇到非预期"其他"符号的处理逻辑
分场景对应固定处理规则:
- 处于状态14(普通浮点数终态):当前累积的"开头数字+小数点+至少一位小数"的串已经是合法的浮点数token。如果遇到的字符不是数字、也不是
E/e,直接把当前累积的串打包成token返回,输入指针停在这个非预期字符的位置,留到下一轮识别流程处理。 - 处于状态17(科学计数法终态):当前累积的完整科学计数法串已经是合法的浮点数token。如果遇到的字符不是数字,直接把当前累积的串打包成token返回,同样把非预期字符留给下一轮识别流程。
- 处于状态16(E后正负号位置的非终态):当前还没有形成新的合法token,之前记录的有效终态位置依然停留在状态14。如果遇到的字符不是数字,直接触发回溯,退回到状态14对应的终止位置,把之前多读的
E、正负号都回退为待识别字符,按普通浮点数返回token。
输入字符串1.2345E+a的实际识别结果
按流程逐字符推演的结果如下:
- 从串首读入
1,进入首个数字识别状态,累积识别串为"1" - 读入
.,进入小数点识别状态,累积串更新为"1." - 依次读入
2、3、4、5,全程在小数部分的状态跳转,最终停在状态14,累积串为"1.2345"。此时触发终态标记,把当前位置(5之后、E之前的位置)记为最后一个有效终止点 - 读入
E,进入指数标记识别状态,累积串更新为"1.2345E" - 读入
+,进入状态16,累积串更新为"1.2345E+"——因为状态16不是终态,之前记录的有效终止点不会更新 - 读入字符
a,此时在状态16查找对应转换边,发现只有匹配“数字”的出边,a没有对应转换路径,触发回溯逻辑 - 回溯到之前记录的最后一个有效终止点,也就是状态14对应的位置,将累积的
"1.2345"作为普通浮点数token返回 - 回退后输入指针停在字符
E的位置,从这个位置启动下一轮的token识别,依次处理后续的E、+、a字符。
也就是说,针对
1.2345E+a的输入,这套识别逻辑不会把整串识别为非法数字,而是会先返回合法的浮点数token1.2345,剩下的E+a留到后续的识别流程做单独处理。
内容的提问来源于stack exchange,提问作者hengxin
相关产品推荐
相关产品推荐

