随心玩玩（十四）词法解析器

写在前面：和大佬交流的时候我完全啊吧啊吧，只能恶补一下这部分知识了

---

参考资料：https://academic.jyunko.cn/2023/03/03/Now-You-Have-Three-Problems.html#magic
本文章翻译自参考资料，有需要的自行查看参考资料即可
只是写的部分有少许加工

现在有两个问题，如果问题的解决方案涉及使用正则表达式解析文本。

1.也许实际上并不需要正则表达式。
2.也许这个问题可以通过简单的字符串分割或其他方法来解决。

然而，其他人可能会想得更仔细一些，并想知道如果我做了一些更大胆的事情，导致了第三个问题怎么办？

如果认真思考如何解析文本，会意识到其中很大一部分涉及输入。让我们编写一个函数：

def shift(inp):
    return bool(inp) and (inp[0], inp[1:])
1
2

给定一个输入序列inp，这将返回第一个inp[0]和所有剩余的inp[1:]
或者，如果根本没有输入，它就会返回False。
看起来很奇怪，但以下是逐步遍历字符串字符的工作原理：

>>> shift('bar')
('b', 'ar')
>>> shift('ar')    # Applied to the remaining characters 'ar'
('a', 'r')
>>> shift('r')
('r', '')
>>> shift('')
False
>>>
1
2
3
4
5
6
7
8
9

对于每个函数，拥有某种相反的函数总是一个好范式。
比如输入的相反的函数是什么？当然就是不输入。我们这样写：

def nothing(inp):
    return (None, inp)
1
2

它从任何输入返回None，还返回与接收到的相同的输入。

>>> nothing('bar')
(None, 'bar')
>>>
1
2
3

nothing()只是意味着选择不对输入执行任何操作。

这两个函数都是所谓的“解析器”的实例。解析器是由其函数名和返回值定义的函数。
具体来说，解析器是接受输入（inp）并在成功时返回一个元组的函数，(value, remaining)
其中value是一些感兴趣的值，并remaining表示仍待解析的所有剩余输入。
失败时，解析器返回False。

尽管这两个函数已经很短，但可以使用以下命令使它们更短lambda：

shift   = lambda inp: bool(inp) and (inp[0], inp[1:])
nothing = lambda inp: (None, inp)
1
2

lambda这样做的好处是可以让代码变得紧凑并且让人很有感觉。

现在假设这里有一个解析系统。与任何系统一样都有规则。在这个系统中，只能使用提供的两个解析器（shift和nothing），还可以使用 lambda，来用现有解析器创建新解析器。

解析器修饰符

让我们编写一个将谓词应用于解析器结果的规则：

filt = lambda predicate: (
         lambda parser:
           lambda inp: (m:=parser(inp)) and predicate(m[0]) and m)
1
2
3

三个 lambda？！？什么地狱绘卷？在python甚至它可以写成四个lambda

filt = lambda predicate: (
         lambda parser:
           lambda inp:
             (lambda m: m and predicate(m[0]) and m)(parser(inp)))
1
2
3
4

所以可读性很重要。然而这就是衣托答辩。

让我们好好理解一下这个filt，我们先要知道和理解predicate是谓词的意思。

我们从简单的例子入手理解lambda，
add_1这函数就表示接收输入一个参数x，输出x+1

add_1 = lambda x: x + 1
res = add_1(1)
print(res)
1
2
3

那么lambda函数进行抽象就可以表示为：
func = lambda x: f(x)
func这个函数表示接受x，输出f(x)，有了这个理解我们来看filt，

进行抽象的迁移，filt表示输入一个predicate，输出(lambda parser: lambda inp: (lambda m: m and predicate(m[0]) and m)(parser(inp)))，(lambda parser:…这么长一段就看成f(predicate)就好，就可以理解为输入了predicate进行了一个复杂操作。表示为：filt = f(predicate)

进一步看内部，lambda parser: lambda inp: (lambda m: m and predicate(m[0]) and m)(parser(inp))
这表示接受一个parser参数，输出lambda inp: (lambda m: m and predicate(m[0]) and m)(parser(inp))。

再进一步看内部，lambda inp: (lambda m: m and predicate(m[0]) and m)(parser(inp))，表示输入参数inp，输出 (lambda m: m and predicate(m[0]) and m)(parser(inp))，这下就有了初步的眉目，输入的参数inp经过了parser处理，再输入进 (lambda m: m and predicate(m[0]) and m)这个函数。

再再进一步看内部(lambda m: m and predicate(m[0]) and m)，表示输入了参数m，输出m and predicate(m[0]) and m，这个输出是比较特殊的return用法，重构后的写法应该是下面的示例def _(m)，m[0]满足谓词且m不是False则返回m

def _(m):
    if predicate(m[0]) and m: return m
    return False
1
2
3

我们可以做一个测试，打印'123' and True and '456'，这输出了"456"，而and过程出现了一个False则返回False

print('123' and True and '456')
456
print('123' and False and '456')
False
1
2
3
4

总结，filt函数作用是先输入inp进行解析器操作，之后对解析器输出[0]位置进行谓词判断。如果谓词判断为True则输出解析器结果，否则输出False。

该filt函数将谓词和解析器作为输入，可以形成新的解析器。
filt是由lambda组合在一起新的解析器。
以下是示例：
其中str.isdigit和str.isalpha是谓词，shift是解析器
下面是两个新生成的digit和letter解析器。
digit就会检查第一个字符是不是数字，如果是的话输出shift位移后的结果。
letter就会检查第一个字符是不是字母，如果是的话输出shift位移后的结果。
返回值False意味着解析不起作用。

>>> digit = filt(str.isdigit)(shift)
>>> letter = filt(str.isalpha)(shift)
>>> digit('456')
('4', '56')
>>> letter('456')
False
>>>
1
2
3
4
5
6
7

除此之外我还想写得更多一点：

filt(predicate) ：
返回一个确定谓词的filt函数，可以称为谓词确定的过滤器
# ---------------------------------------
filt(predicate)(paser)： 
返回一个确定谓词和解析器的filt函数，这个filt函数可以视为一个新的解析器，带有谓词判断功能的解析器
# ---------------------------------------
filt(predicate)(paser)(inp) ：
返回一个新的解析器输入inp的结果
# ---------------------------------------
1
2
3
4
5
6
7
8
9

filt可以通过匿名谓词轻松制作其他有用的过滤器。

这是一个用于精确匹配文字的过滤器：
其中lambda v: v == value是一个匿名谓词，这个匿名谓词用于全等于判断预定义的值
literal以value作为参数，返回一个filt(lambda v: v == value)，可以看作是参数待定的谓词确定的filt函数，很拗口…直接理解成一个新的过滤器也好

literal = lambda value: filt(lambda v: v == value)
1

这是另一个新过滤器memberof，其中匿名谓词要求值必须来自预定义的一组值：

memberof = lambda values: filt(lambda v: v in values)
1

以下是这些过滤器应用的一些示例：
其中dot和even都是两个新定义的带谓词功能的解析器。
dot要求第一个字符全等于’.’ 后再输出shift解析器的值
even要求第一个字符全在’02468’中 后再输出digit解析器的值

>>> dot = literal('.')(shift)  
>>> even = memberof('02468')(digit)
>>> dot('.456')
('.', '456')
>>> dot('45.6')
False
>>> even('456')
('4', '56')
>>> even('345')
False
>>>
1
2
3
4
5
6
7
8
9
10
11

当然，你可以继续简化事情。要匹配单个字符，可以编写如下：
其中lambda v: literal(v)是一个参数待确定的确定谓词的过滤器，再和解析器组合，形成了一个参数待确定的带有谓词判断的解析器char

char = lambda v: literal(v)(shift)
1

下面dot经过参数'.'传递入char，就可以视为带有谓词判断的解析器了（完全体）

>>> dot = char('.')
>>> dot('.456')
('.', '456')
>>>
1
2
3
4

那么filt()目的是忽略某事，忽略某事反过来就是做某事。
因此，我们需要一个相反的函数来保持代码平衡。我们称该操作为fmap()：

fmap = lambda func: \
    (lambda parser: lambda inp: (lambda m: m and (func(m[0]), m[1]))(parser(inp)))
1
2

fmap()将函数func和解析器parser作为输入并创建一个新的解析器，其中提供的func将应用于成功的解析。
例如用来fmap()改变值：

>>> ndigit = fmap(int)(digit)
>>> ndigit('456')
(4, '56')
>>> tenx = fmap(lambda x: 10*x)
>>> tenx(ndigit)('456')
(40, '56')
>>> tenx(digit)('456')
('4444444444', '56')
>>>
1
2
3
4
5
6
7
8
9

重复

到目前为止，解析器仅适用于单个输入。为了做更有趣的事情，需要匹配多个输入。例如，多个数字或多个字母。如果能够定义这样的函数那就太好了：

digits = one_or_more(digit)
1

one_or_more()接受解析器作为输入并创建一个新的解析器作为输出。
它重复调用提供的解析器，直到无法进行谓词判断。返回生成一个列表。

def one_or_more(parser):
    def parse(inp):
        result = []
        while True:
            m = parser(inp)
            if m is False:
                break
            value, inp = m
            result.append(value)
        return bool(result) and (result, inp)
    return parse
1
2
3
4
5
6
7
8
9
10
11

这是例子：
其中digits('456')会一直判断到结束，
但是digits('1abc')判断到a就结束了，
因为他们的谓词是str.isdigit

>>> digit = filt(str.isdigit)(shift)
>>> digits = one_or_more(digit)
>>> digits('456')
(['4','5','6'], '')
>>> digits('1abc')
(['1'], 'abc')
>>> digits('abc')
False
>>>
1
2
3
4
5
6
7
8
9

如果不喜欢将数字分成一个列表，请使用fmap将它们重新组合在一起：
其中fmap(''.join)是一个谓词明确的执行器，作用是对解析器结果m[0]进行拼接，
digits就变成了一个带有执行器的解析器。

>>> digits = fmap(''.join)(one_or_more(digit))
>>> digits('456')
('456', '')
>>>
1
2
3
4

如果您想要一个数值，请再添加一个fmap：

>>> value = fmap(int)(digits)
>>> value('456')
(456, '')
>>>
1
2
3
4

题外话：向同事展示该one_or_more() 功能后，他们可能会因为你不遵循风格指南而生气。他们会说，你应该使用 lambda。解决这个问题并不容易，但你也许可以用 functools.wraps()这样的方法来愚弄他们：

from functools import wraps

@wraps(lambda parser:_)
def one_or_more(parser):
    @wraps(lambda inp:_)
    def parse(inp):
        ...
    return parse
1
2
3
4
5
6
7
8

顺序

有时你想要解析一件又一件的事情。可以像这样编写排序运算符：

def seq(*parsers):
    def parse(inp):
        result = []
        for p in parsers:
            m = p(inp)
            if m is False:
                return False
            value, inp = m
            result.append(value)
        return (result, inp)
    return parse
1
2
3
4
5
6
7
8
9
10
11

seq()接受任意数量的解析器作为输入。然后它创建一个新的解析器，将它们一个接一个地排序。所有解析器都必须成功才能成功解析。下面是例子：
其中，
letter是带谓词判断的判断是否为字母的shift解析器，
digit是带谓词判断的判断是否为数字的shift解析器
fmap(''.join)(one_or_more(digit))就是刚刚上面刚写的带执行器的带重复功能的digit解析器

>>> seq(letter, digit, letter)('a4x')
(['a', '4', 'x'], '')
>>> seq(letter, digit, letter)('abc')
False
>>> seq(letter, fmap(''.join)(one_or_more(digit)))('x12345')
(['x', '12345'], '')
>>> 
1
2
3
4
5
6
7

一旦完成排序，您就可以编写一些有用的变体。例如：
left是输入p1,p2参数后返回一个功能为经过seq解析器的返回左位置结果的解析器
right是输入p1,p2参数后返回一个功能为经过seq解析器的返回右位置结果的解析器

left = lambda p1, p2: fmap(lambda p: p[0])(seq(p1, p2))
right = lambda p1, p2: fmap(lambda p: p[1])(seq(p1, p2))

>>> left(letter, digit)('a4')
('a', '')
>>> right(letter, digit)('a4')
('4', '')
>>>
1
2
3
4
5
6
7
8

选择

匹配的相反操作？也许它是一个只需要匹配给定解析器之一解析器。称这个操作为either()：
either是输入p1,p2解析器作为参数，输出任一匹配解析器的结果的解析器

either = lambda p1, p2: (lambda inp: p1(inp) or p2(inp))
>>> alnum = either(letter, digit)
>>> alnum('4a')
('4', 'a')
>>> alnum('a4')
('a', '4')
>>> alnum('$4')
False
>>>
1
2
3
4
5
6
7
8
9

either()允许构建选项并最终有机会使用nothing. 例如：
maybe是一个parser作为参数，输出一个解析器待定而另一个解析器为nothing的either的解析器

maybe = lambda parser: either(parser, nothing)
1

>>> maybe(digit)('456')
('4', '56')
>>> maybe(digit)('abc')
(None, 'abc')
>>>
1
2
3
4
5

您还可以使用它来实现zero_or_more()：

zero_or_more = lambda parser: either(one_or_more(parser), seq())
1

>>> zero_or_more(digit)('456')
(['4','5','6'], '')
>>> zero_or_more(digit)('abc')
([], 'abc')
>>>
1
2
3
4
5

还可以用来either()构建一个功能更强大的 choice()函数，该函数允许在任意数量的提供的解析器之间进行选择。
实现使用递归choice

choice = lambda parser, *parsers: (
           either(parser, choice(*parsers)) if parsers else parser)
1
2

思考：重写choice()以不使用递归。你真的需要吗nothing？

例1：解析数字

我们来看看解析数字的问题。假设数字有两种不同的形式。整数如1234，小数如12.34。然而，小数有点复杂，因为它们可以用尾随小数（如 12.）或前导小数（如 .34）来书写。假设您要将整数转换为 Python 整数，将小数转换为 Python 浮点数。你会如何解析任何数字？可以这样做：
dot是全等判断小数点.的shift解析器
digit是数字判断的shift解析器
digits是重复digit解析器
decdigits可以理解成小数解析器，匹配三种格式其中的一个即可，选择其中一个seq作为解析器
integer和decimal是两个带执行器的解析器，作用是转为num类型
number是要么是decimal要么是integer解析器

dot = char('.')
digit = filt(str.isdigit)(shift)
digits = fmap(''.join)(one_or_more(digit))
decdigits = fmap(''.join)(choice(
               seq(digits, dot, digits),
               seq(digits, dot),
               seq(dot, digits)))

integer = fmap(int)(digits)
decimal = fmap(float)(decdigits)
number = choice(decimal, integer)
1
2
3
4
5
6
7
8
9
10
11

让我们尝试一下我们的number()功能。

>>> number('1234')
(1234, '')
>>> number('12.3')
(12.3, '')
>>> number('.123')
(0.123, '')
>>> number('123.')
(123.0, '')
>>> number('.xyz')
False
>>>
1
2
3
4
5
6
7
8
9
10
11

例2：键值对

假设您要解析形式的键值对，name=value;其中 name由字母组成，并且value是任何数值。进一步假设任何部分周围可能存在任意空白（应忽略）。您可以这样做：

空白的处理可能需要一些研究。关键是使用特殊token()函数来丢弃前导空格。
letter匹配字母
letter匹配多字母
ws匹配0个或者多个空格
token先ws，后p，取p部分
eq：结合token匹配等号，等于过滤空格匹配等号
semi：过滤空格匹配；
name：过滤空格匹配letters
value：过滤空格匹配number

letter = filt(str.isalpha)(shift)
letters = fmap(''.join)(one_or_more(letter))
ws = zero_or_more(filt(str.isspace)(shift))
token = lambda p: right(ws, p)
eq = token(char('='))
semi = token(char(';'))
name = token(letters)
value = token(number)
keyvalue = seq(left(name, eq), left(value, semi))
1
2
3
4
5
6
7
8
9

让我们尝试一下：

>>> keyvalue('xyz=123;')
(['xyz', 123], '')
>>> keyvalue('   pi = 3.14  ;')
(['pi', 3.14], '')
>>>
1
2
3
4
5

例3：构建字典

假设想要扩展解析器，以便将任意数量的键对对写入key1=value1; key2=value2; key3=value3;具有相同键和值的 Python 字典中。操作方法如下：

keyvalues = fmap(dict)(zero_or_more(keyvalue))
1

例子：

>>> keyvalues('x=2; y=3.4; z=.789;')
({'x': 2, 'y': 3.4, 'z': 0.789}, '')
>>> keyvalues('')
({}, '')
>>>
1
2
3
4
5

例4：验证字典键

假设想编写一个仅接受带有键x和y的字典的解析器。您可以使用filt()这样的方式进行检查：

xydict = filt(lambda d: d.keys() == {'x', 'y'})(keyvalues)
1

例子：

>>> xydict('x=4;y=5;')
({'x': 4, 'y': 5}, '')
>>> xydict('y=5;x=4;')
({'y': 5, 'x': 4}, '')
>>> xydict('x=4;y=5;z=6;')
False
>>>
1
2
3
4
5
6
7

此示例说明了功能如何以有趣的方式组合在一起。早些时候，该filt()函数用于过滤单个字符，但现在它被应用于字典。

可组合性

让一切顺利进行的基本特征是对可组合性的关注。从本质上讲，这是解析器的接口：

def parser(inp):
    ...
    if success:
        return (value, remaining)
    else:
        return False
1
2
3
4
5
6

其他一切都围绕这个构建。所有不同的函数（例如filt()、fmap()、zero_or_more()、seq()和 ）choice() 都会创建具有相同接口的新解析器。因此，一切都可以同时与任何地方的一切协同工作。也许主要关注的领域是fmap()。由于这会将用户定义的函数应用于解析的值，因此提供的函数显然必须与之兼容。

概念分解

考虑一下 的表述filt()。当你使用时 filt()，你可能会觉得它看起来有点滑稽。像这样：

digit = filt(str.isdigit)(shift)
1

为什么shift外面是这样的？此外，这不是更多的内部实现细节吗？我们不能像这样隐藏它吗：

filt = lambda predicate: (
         lambda inp: (m:=shift(inp)) and predicate(m[0]) and m)

digit = filt(str.isdigit)
1
2
3
4

filt()是的这是可以做到的，但是将其移入内部会限制单个字符的实用性 。
但更喜欢一个filt()非常灵活的。
原始公式允许将谓词应用于任何解析器，甚至是返回数据结构的更复杂的解析器。
如果解析器的选择被拉入内部，你就不能这样做了。

关于（和相关函数）的另一个问题filt()与其奇怪的调用约定有关。
为什么输入谓词和解析器参数是通过单独的函数调用处理的，而不是一起传递给单个函数？例如，为什么不？

filt = lambda predicate, parser: (
         lambda inp: (m:=parser(inp)) and predicate(m[0]) and m)

digit = filt(str.isdigit, shift)
1
2
3
4

以这种方式制定函数会使定义有用的变体，例如literal，literal仅通过与谓词部分相关来定义。像这样：

literal = lambda value: filt(lambda v: v == value)
1

这是专注而优雅的。但是，如果filt()需要附加参数，该参数会溢出到外部函数中，迫使您编写如下代码：

literal = lambda value, parser: filt(lambda v: v == value, parser)
1

那太丑了。最初的方法不需要我们了解有关 的任何进一步细节filt()。

魔法

让我们shift()暂时讨论一下这个函数。按照最初的表述，它将输入字符串拆分为第一个字符和所有剩余文本。这是原始代码：

def shift(inp):
    return bool(inp) and (inp[0], inp[1:])
1
2

它是这样工作的：

>>> shift('hello world')
('h', 'ello world')
>>>
1
2
3

这不是在 Python 中处理文本的有效方法。事实上，这可能是您可以设计的最糟糕的文本处理方式。在我的机器上运行测试时，将具有 100000 个键值对的字符串解析到字典中需要大约 2.5 分钟！

核心问题是计算时发生的内存复制 inp[1:]。事实上，每次调用都会shift()生成输入文本的近乎完整的副本。有可能避免这种情况吗？

精明的观察者会注意到，在所提供的所有代码中，inp除了将输入值传递到其他地方之外，从未对输入值进行任何操作。唯一查看它的代码就是函数shift() ！此外，也没有任何代码会查看剩余文本的值。因此，我们可以选择将这些部分的数据表示完全更改为其他内容。也许我们可以使用一个元组，而不是将输入表示为字符串， (text, n)其中n是表示当前位置的整数。让我们尝试shift()这样重写：

def shift(inp):
    text, n = inp
    return n < len(text) and (text[n], (text, n+1))
1
2
3

以下是这个新版本的工作：

>>> shift(('abc', 0))     # Note the use a tuple now
('a', ('abc', 1))
>>> shift(('abc', 1))
('b', ('abc', 2))
>>> shift(('abc', 2))
('c', ('abc' 3))
>>> shift(('abc', 3))
False
>>>
1
2
3
4
5
6
7
8
9

请注意，输入字符串在一步一步中不会发生变化。没有复制，也没有切片。Python 将有效地将字符串作为引用传递。唯一改变的值是整数索引。

无需更改任何其他代码。只要您以预期的格式提供输入，您就可以验证一切是否仍然正常运行。

为了隐藏一些输入细节，我可能更愿意引入一个特殊的 Input()函数来将用户提供的输入转换为我的内部格式。例如：

Input = lambda inp: (inp, 0)

# Example
result = keyvalues(Input('x=2; y=3.4; z=.789'))
1
2
3
4

我用大写字母Input来保持我的选择余地。也许这是我以后会改变到课堂上的东西。也许我这样做只是为了表达“噗噗！！！” 至 PEP-8。谁说得准呢？

尽管如此，当对与之前相同的 100000 个键值对输入进行测试时，解析时间从 2.5 分钟以上下降到约 2.3 秒。这真是太神奇了。我们通过更改输入表示并仅调整一行代码来解决性能问题。

为什么这有效？我认为它是有效的，因为我们编写的所有功能都不是基于输入数据的直接操作，而是基于函数组合。更改数据表示形式对零件的组成没有影响。

更多魔法

尽管我们在性能上取得了很大的进步，但我们仍然执行大量低级的单字符操作。也许使用更合适的分词器会更有意义。例如，也许我们可以使用我的 SLY工具来编写一个像这样的词法分析器：

from sly import Lexer

class KVLexer(Lexer):
    tokens = { EQ, SEMI, NAME, INTEGER, FLOAT }
    ignore = ' \t\n'
    FLOAT = r'(\d+\.\d+)|(\d+\.)|(\.\d+)'
    INTEGER = r'\d+'
    NAME = r'[a-zA-Z]+'    
    EQ = r'='
    SEMI = r';'
1
2
3
4
5
6
7
8
9
10

词法分析器生成标记，而不是字符。例如：

>>> lexer = KVLexer()
>>> list(lexer.tokenize("x=2;"))
[Token(type='NAME', value='x', lineno=1, index=0, end=1),
 Token(type='EQ', value='=', lineno=1, index=1, end=2),
 Token(type='INTEGER', value='2', lineno=1, index=2, end=3),
 Token(type='SEMI', value=';', lineno=1, index=3, end=4)]
>>>
1
2
3
4
5
6
7

我们可以将我们的解析框架与这样的分词器一起使用吗？当然！为此，您将替换低级字符处理以使用标记，但其他部分保持解析器的其余部分完好无损。这是一个新的解析器：

expect = lambda ty:\
           fmap(lambda tok: tok.value)(filt(lambda tok: tok.type == ty)(shift))
name = expect('NAME')
integer = fmap(int)(expect('INTEGER'))
decimal = fmap(float)(expect('FLOAT'))
value = choice(decimal, integer)
keyvalue = seq(left(name, expect('EQ')), left(value, expect('SEMI')))
keyvalues = fmap(dict)(zero_or_more(keyvalue))

Input = lambda inp: (list(KVLexer().tokenize(inp)), 0)
1
2
3
4
5
6
7
8
9
10

让我们验证一下它是否有效：

>>> r = keyvalues(Input('x=2; y=3.4; z=.789;'))
>>> r[0]
{'x': 2, 'y': 3.4, 'z': 0.789}
>>>
1
2
3
4

当在我的大型测试输入上运行时，这个版本的运行时间约为 0.9 秒，比以前快了约 2.5 倍。

轰隆隆！

我开始思考我在 PLY和 SLY等其他一些工具中花费了无数时间对 LALR(1) 解析器进行微优化。说真的，我花了很多时间盯着那些代码，试图消除我能识别的每一点性能开销。因此，这些工具长期以来一直是最快的纯 Python 解析器实现之一。这种新方法与那种方法相比如何？

为了测试它，我在 SLY 中指定了一个类似的 KV 对解析器：

from sly import Parser

class KVParser(Parser):
    tokens = KVLexer.tokens

    @_('{ keyvalue }')
    def keyvalues(self, p):
        return dict(p.keyvalue)

    @_('NAME EQ value SEMI')
    def keyvalue(self, p):
        return (p.NAME, p.value)

    @_('INTEGER')
    def value(self, p):
        return int(p.INTEGER)

    @_('FLOAT')
    def value(self, p):
        return float(p.FLOAT)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

以下是如何使用它来解析我们的小示例：

>>> lexer = KVLexer()
>>> parser = KVParser()
>>> tokens = lexer.tokenize('x=2; y=3.4; z=.789;')
>>> parser.parse(tokens)
{'x': 2, 'y': 3.4, 'z': 0.789}
>>>
1
2
3
4
5
6

我现在将尝试输入 100000 个键值对。需要2.3秒。它比上次测试慢三倍——上次测试使用完全相同的令牌流！它甚至比最初仅处理单个角色的“魔法”版本还要慢一些。怎么会这样？

这不是我所期望的结果。LALR(1) 解析器完全由表查找和状态机驱动。没有回溯，也不涉及深层次的组合函数。

作为最后的手段，我决定使用 PLY 重新实现整个解析器，它具有更优化的实现。运行时间约为 1.2 秒。它也输了。

退一步来说，在这里进行详细的性能分析并不是我的目标——在许多病态的极端情况下，这种新方法可能会遇到麻烦。主要的收获是它比我想象的要快得多。

迭代

在Python中，迭代的概念有明确的定义。有理由问为什么不使用迭代器或生成器函数来实现这一点？可以 shift()像这样重写吗？

shift = lambda inp: (x:=next(inp, False)) and (x, inp)
1

一项实验似乎表明它可能有效：

>>> inp = iter('abc')
>>> shift(inp)
('a', <str_iterator object at 0x10983e140>)
>>> shift(inp)
('b', <str_iterator object at 0x10983e140>)
>>> shift(inp)
('c', <str_iterator object at 0x10983e140>)
>>> shift(inp)
False
>>>
1
2
3
4
5
6
7
8
9
10

不幸的是，它实际上不起作用，因为我们的解析方法涉及回溯——尤其是在 、 和 函数中做出 either()决策maybe()时choice()。处理时 either()，解析可能会成功进行一段时间，然后突然失败。当这种情况发生时，一切都会倒回并尝试不同的解析分支。

没有机制可以倒回通用 Python 迭代器。尽管有时可以复制迭代器或使用一些魔法 itertools，但这样做似乎很棘手。更糟糕的是，要使其发挥作用，需要在整个实施过程中进行繁琐的更改，而不是隔离到单个位置。现在，我将把它作为练习。

完整代码

# -- Parsing framework

def shift(inp):
    text, n = inp
    return n < len(text) and (text[n], (text, n+1))

nothing = lambda inp: (None, inp)

filt = lambda predicate: (
         lambda parser:
           lambda inp: (m:=parser(inp)) and predicate(m[0]) and m)

literal = lambda value: filt(lambda v: v==value)
char = lambda value: literal(value)(shift)

fmap = lambda func: (
         lambda parser:
           lambda inp: (m:=parser(inp)) and (func(m[0]), m[1]))

either = lambda p1, p2: (lambda inp: p1(inp) or p2(inp))
maybe  = lambda parser: either(parser, nothing)
choice = lambda parser, *parsers: either(parser, choice(*parsers)) if parsers else parser

def seq(*parsers):
    def parse(inp):
        result = [ ]
        for p in parsers:
            if not (m:=p(inp)):
                return False
            value, inp = m
            result.append(value)
        return (result, inp)
    return parse

left = lambda p1, p2: fmap(lambda p: p[0])(seq(p1, p2))
right = lambda p1, p2: fmap(lambda p: p[1])(seq(p1, p2))

def one_or_more(parser):
    def parse(inp):
        result = [ ]
        while (m:=parser(inp)):
            value, inp = m
            result.append(value)
        return bool(result) and (result, inp)
    return parse

zero_or_more = lambda parser: either(one_or_more(parser), seq())

Input = lambda inp: (inp, 0)

# -- Example: Convert "key1=value1; key2=value2; ..." into a dict

# numbers and values
dot = char('.')
digit = filt(str.isdigit)(shift)
digits = fmap(''.join)(one_or_more(digit))
decdigits = fmap(''.join)(choice(
               seq(digits, dot, digits),
               seq(digits, dot),
               seq(dot, digits)))

integer = fmap(int)(digits)
decimal = fmap(float)(decdigits)
number = choice(decimal, integer)

# names
letter = filt(str.isalpha)(shift)
letters = fmap(''.join)(one_or_more(letter))

# Whitespace
ws = zero_or_more(filt(str.isspace)(shift))
token = lambda p: right(ws, p)

# Tokens (removed whitespace)
eq = token(char('='))
semi = token(char(';'))
name = token(letters)
value = token(number)

# Single key=value; pair
keyvalue = seq(left(name, eq), left(value, semi))

# Multiple key-values
keyvalues = fmap(dict)(zero_or_more(keyvalue))

# Example
result, remaining = keyvalues(Input("x=2; y=3.4; z=.789;"))
print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88