algorithm - 这种编程模式的名称是什么？

Question

通常需要处理一系列“ block ”，这些“ block ”是从“原子”流中读取的，其中每个 block 由可变数量的原子组成，程序无法知道它有收到一个完整的 block ，直到它读取下一个 block 的第一个原子(或者原子流耗尽)。

执行此任务的简单算法如下所示:

LOOP FOREVER:
    SET x TO NEXT_ATOM
    IF DONE(x) OR START_OF_CHUNK(x):
        IF NOT EMPTY(accum):
            PROCESS(accum)
        END
        if DONE(x):
            BREAK
        END
        RESET(accum)
    END
    ADD x TO accum
END

所以，我的问题是:

Is there a name for this general class of problems and/or for the programming pattern shown above?

这篇文章的其余部分只是上面抽象描述的几个(相当现实的)示例。 (这些示例是用 Python 编写的，尽管它们可以很容易地翻译成任何命令式语言。)

第一个是生成输入字符串游程编码的函数。在这种情况下，“原子”是单个字符，“ block ”是同一字符的最大运行。因此，程序在读取下一次运行中的第一个字符之前并不知道它已经到达运行的结尾。

def rle(s):
    '''Compute the run-length encoding of s.'''

    n = len(s)
    ret = []
    accum = 0
    v = object()  # unique sentinel; ensures first test against x succeeds
    i = 0
    while True:
        x = s[i] if i < n else None
        i += 1
        if x is None or x != v:
            if accum > 0:
                ret.append((accum, v))
            if x is None:
                break
            accum = 0
        v = x
        accum += 1

    return ret

第二个示例是一个函数，它将一个 FASTA 格式文件的读取句柄作为参数，并解析其内容。在这种情况下，原子是文本行。每个 block 由一个特别标记的第一行组成，称为“defline”(并以“>”作为其第一个字符来区分)，然后是包含核苷酸或蛋白质序列片段的可变数量的行。同样，只有在读取下一个 block 的第一个原子(即 defline)之后，代码才能明确地检测到 block 的结尾。

def read_fasta(fh):
    '''Read the contents of a FASTA-formatted file.'''

    ret = []
    accum = []
    while True:
        x = fh.readline()
        if x == '' or x.startswith('>'):
            if accum:
                ret.append((accum[0], ''.join(accum[1:])))
            if x == '':
                break
            accum = []
        accum.append(x.strip())

    return ret

Answer 1

我唯一能想到的是它是一个非常简单的 LL(1) 解析器。您正在(以一种非常简单的方式)从左到右解析数据，您需要向前看一个值才能知道发生了什么。见http://en.wikipedia.org/wiki/LL_parser