🪴 Quartz 4.0

状态机

6 min read

状态机模型

  • 状态（States）：定义程序在处理文本时可能处于的不同阶段。
  • 输入（Inputs）：程序从输入源读取的字符。
  • 转换（Transitions）：根据当前状态和输入字符，程序如何从一个状态转换到另一个状态。
  • 动作（Actions）：在特定状态下，根据输入执行的操作，例如打印字符。

基于状态机读取文本

题目要求：

Consider the task of reading a text from standard input line-by-line and writing the first word of each line to standard output. First we skip all leading whitespace characters, if any. Then we print all the characters of the first word. Finally we skip all the trailing characters until a newline character is encountered. Whenever a sequence of newline characters is encountered not at the beginning of the stream, we print only the first one and skip the remaining ones; else, we skip all. Next we restart the process at the following line. Upon encountering the end-of-file condition (regardless of the stage), we stop.
  1. 读取文本：从标准输入（通常是键盘输入或文件）逐行读取文本。
  2. 跳过前导空白：每读取一行，首先跳过该行开头的所有空白字符（如空格、制表符等）。
  3. 打印第一个单词：打印出跳过空白后遇到的连续非空白字符序列，也就是第一个单词。
  4. 跳过剩余字符：在打印完第一个单词之后，跳过该行剩余的所有字符，直到遇到换行符。
  5. 处理换行符：
    • 如果遇到连续的换行符，不是在文件的开头，只打印第一个换行符，并且跳过其余的换行符。
    • 如果是在文件的开头遇到换行符，跳过所有换行符。
  6. 重复处理：在处理完一行后，继续读取下一行，并重复上述步骤。
  7. 结束条件：当遇到文件结束（EOF）条件时，停止处理。

三种状态

  • BEFORE：表示当前处于第一个单词之前的状态，正在寻找第一个非空白字符。
  • INSIDE：表示当前处于第一个单词内部的状态，正在打印单词字符。
  • AFTER：表示当前处于第一个单词之后的状态，正在跳过该行的剩余字符直到换行符。

无状态机编程

#include <ctype.h>
#include <stdio.h>
 
int main(void) {
  int c;
 
  do {
    do {
      c = getchar();
    } while (isspace(c));
 
    while (!isspace(c) && c != EOF) {
      putchar(c);
      c = getchar();
    }
    
    while (c != '\n' && c != EOF) {
      c = getchar();
    }
    
    if (c == '\n') {
      putchar(c);
    }
  } while (c != EOF);
 
  return 0;
}

基于状态机的程序

#include <ctype.h>
#include <stdio.h>
 
enum State {BEFORE, INSIDE, AFTER};
 
int main(void) {
  int c;
  enum State s = BEFORE;
 
  while ((c = getchar()) != EOF) {
    switch (s) {
      case BEFORE:
        if (!isspace(c)) {
          putchar(c);
          s = INSIDE;
        }
        
        break;
      case INSIDE:
        if (c == '\n') {
          putchar(c);
          s = BEFORE;
        } else if (isspace(c)) {
          s = AFTER;
        } else {
          putchar(c);
        }
          
        break;
      case AFTER:
        if (c == '\n') {
          putchar(c);
          s = BEFORE;
        }
        
        break;
    }
  }
 
  return 0;
}

分解状态与循环

#include <ctype.h>
#include <stdio.h>
 
enum State {BEFORE, INSIDE, AFTER};
 
void step(enum State* const s, int const c) {
  switch (*s) {
    case BEFORE:
      if (!isspace(c)) {
        putchar(c);
        *s = INSIDE;
      }
      
      break;
    case INSIDE:
      if (c == '\n') {
        putchar(c);
        *s = BEFORE;
      } else if (isspace(c)) {
        *s = AFTER;
      } else {
        putchar(c);
      }
        
      break;
    case AFTER:
      if (c == '\n') {
        putchar(c);
        *s = BEFORE;
      }
      
      break;
  }
}
 
int main(void) {
  int c;
  enum State s = BEFORE;
 
  while ((c = getchar()) != EOF) {
    step(&s, c);
  }
 
  return 0;
}

事件驱动的有限状态机

在计算中，如果从一个状态到另一个状态的转换是由事件或消息触发的，则有限状态机(FSM) 是事件驱动的。这与术语有限状态机的解析理论起源相反，在解析理论中，机器被描述为消耗字符或标记。

示例

此代码描述了一个非常基本的汽车收音机系统的状态机。它基本上是一个读取传入事件的无限循环。状态机只有 2 个状态：收音机模式或 CD 模式。事件可以是收音机和 CD 之间的模式切换，也可以是进入下一个模式（收音机的下一个预设或 CD 的下一首曲目）。

/********************************************************************/
#include <stdio.h>
 
/********************************************************************/
typedef enum
{
  ST_RADIO,
  ST_CD
} STATES;
 
typedef enum
{
  EVT_MODE,
  EVT_NEXT
} EVENTS;
 
EVENTS readEventFromMessageQueue(void);
 
/********************************************************************/
int main(void)
{
  /* Default state is radio */
  STATES state = ST_RADIO;
  int stationNumber = 0;
  int trackNumber = 0;
 
  /* Infinite loop */
  while (1)
  {
    /* Read the next incoming event. Usually this is a blocking function. */
    EVENTS event = readEventFromMessageQueue();
 
    /* Switch the state and the event to execute the right transition. */
    switch (state)
    {
    case ST_RADIO:
      switch (event)
      {
      case EVT_MODE:
        /* Change the state */
        state = ST_CD;
        break;
      case EVT_NEXT:
        /* Increase the station number */
        stationNumber++;
        break;
      }
      break;
 
    case ST_CD:
      switch (event)
      {
      case EVT_MODE:
        /* Change the state */
        state = ST_RADIO;
        break;
      case EVT_NEXT:
        /* Go to the next track */
        trackNumber++;
        break;
      }
      break;
    }
  }
}
```

Graph View