有限状态转换器中后续符号$合成时填充上下文的作用及必要性问询

符号$的上下文填充实现 #

• $是边界标记符，核心作用是把隐式的上下文依赖转化为显式的输入序列匹配规则，适配无匹配延迟的要求：
  • 对于需要上下文的转换逻辑，比如“在上下文序列C之后输入符号x时输出y”，会将输入序列重构为C$x；
  • 转换器会预先定义匹配C$的状态转移规则，当输入流走到$时，转换器已完成上下文的识别并切换到对应状态；
  • 后续输入x时，直接触发预定义的输出y操作，实现输入一个符号就输出一个结果的无延迟要求，不需要缓存之前的上下文符号。

为什么要做上下文填充/移除 #

• 本质是为了满足无匹配延迟+确定性转换器的双重约束：
  • 无匹配延迟要求每输入一个符号必须立即输出对应结果，不能缓存上下文等待后续输入再决策——如果保留隐式上下文，转换器需要暂存之前的输入符号，这会导致输出延迟（比如要等下一个符号输入才能确定当前输出）；
  • 上下文的“额外信息”会破坏确定性：相同的输入符号在不同上下文下可能对应不同输出，而确定性转换器要求相同输入必须对应唯一输出。用$标记上下文后，把上下文作为输入序列的一部分，让每个输入符号的转换规则唯一确定；
  • 填充并处理上下文并没有丢失信息，只是把隐式的上下文依赖转化为显式的符号匹配规则，让转换器在单步内完成上下文识别+当前符号转换，同时符合单音移（输入输出长度一致）的要求。

内容的提问来源于stack exchange，提问作者Anantha Krishnan