BNF与有限状态自动机

[TheMatrix]

以下的代码我隔一段时间就要revisit。代码本身太美了。

而且总感觉里面还能挖出点什么。总是想要变换一下视角，看看能变出什么。

变换表象，挣扎图存。这是我的一个联想。

#f: state --> state
#where state is an integer
#finite states
#there is a special state 0 stands for error state

sequential and parallel

代码： 全选

from functools import reduce

#sequential - or composition
def seq(*fs):
    def s2(f, g):
        def fn(s):
            return g(f(s))
        return fn
    return reduce(s2, fs)

#parallel
def par(*fs):
    def p2(f, g):
        def fn(s):
            return f(s) or g(s)
        return fn
    return reduce(p2, fs)

regular expression operators:
? - optional
* - zero or more
+ - one or more

代码： 全选

#identity - or blank
def id(s):
    return s

#optional
def opt(f):
    return par(f, id)

#one or more
def mor(f):
    return seq(f, zmo(f))

#zero or more
def zmo(f):
    #basically, return opt(mor(f))
    #but, make sure it's zero-safe
    return opt(lambda s: mor(f)(s) if s else s)

[TheMatrix]

这段代码首先是highly highly functional的。全都是二阶函数。只有一个是一阶函数：id。

它们全都是take one or more function，return a function。

[TheMatrix]

这段代码首先是highly highly functional的。全都是二阶函数。只有一个是一阶函数：id。

它们全都是take one or more function，return a function。

这就预示着它是highly highly abstract的，也是highly highly dense的。

这就跟智能沾边了。

因为智能，我感觉就是抽象，抽象，再抽象。也就是一个东西，我不直接改它，我改能生成它的rule。然后，我又不直接改它的rule了，我改能生成它的rule的rule。。。

知幻即离 - 这又是我的一个联想。

[TheMatrix]

这就预示着它是highly highly abstract的，也是highly highly dense的。

这就跟智能沾边了。

因为智能，我感觉就是抽象，抽象，再抽象。也就是一个东西，我不直接改它，我改能生成它的rule。然后，我又不直接改它的rule了，我改能生成它的rule的rule。。。

知幻即离 - 这又是我的一个联想。

但是抽象，抽象，再抽象，到某一个层次，它要落地。突然之间，down to earth。哦，原来是这么回事啊！就是这个感觉。

[TheMatrix]

#f: state --> state
#where state is an integer
#finite states
#there is a special state 0 stands for error state

sequential and parallel

代码： 全选

from functools import reduce

#sequential - or composition
def seq(*fs):
    def s2(f, g):
        def fn(s):
            return g(f(s))
        return fn
    return reduce(s2, fs)

#parallel
def par(*fs):
    def p2(f, g):
        def fn(s):
            return f(s) or g(s)
        return fn
    return reduce(p2, fs)

首先这个f是什么 - 所有的二阶函数都作用在它上面，得到另一个f。

f是一个作用在state space上的函数。f: state --> state。

state用正整数表示，0 代表一个特殊的state (error)。

f同时也是一个BNF表示中的一项。BNF是Backus–Naur form。就是这个东西：



f是state space上的一个函数，我也是过了很久才想清楚 - 因为我首先是把它当成 BNF中的一项。

但是它并不仅仅是state状态转换图中的一个箭头。

[TheMatrix]

sequential and parallel

代码： 全选

from functools import reduce

#sequential - or composition
def seq(*fs):
    def s2(f, g):
        def fn(s):
            return g(f(s))
        return fn
    return reduce(s2, fs)

#parallel
def par(*fs):
    def p2(f, g):
        def fn(s):
            return f(s) or g(s)
        return fn
    return reduce(p2, fs)

用reduce写比较elegant。

不用reduce写，实际上更清楚。seq就是函数一个一个走，必须都成功。par也是函数一个一个走，第一个成功就返回。而且mor递归那个地方简单了，不用检查s是否为0了。这个地方我没明白是怎么回事。

代码： 全选

def seq(*fs):
    def fn(s):
        for f in fs:
            s = f(s)
            if not s:
                return s
        return s
    return fn
    
def par(*fs):
    def fn(s):
        for f in fs:
            t = f(s)
            if t:
                return t
        return t
    return fn

def id(s):
    return s

def opt(f):
    return par(f, id)

def mor(f):
    #return seq(f, zmo(f))
    return seq(f, lambda s: zmo(f)(s))

def zmo(f):
    return opt(mor(f))

[TheMatrix]

用reduce写比较elegant。

不用reduce写，实际上更清楚。seq就是函数一个一个走，必须都成功。par也是函数一个一个走，第一个成功就返回。而且mor递归那个地方简单了，不用检查s是否为0了。这个地方我没明白是怎么回事。

代码： 全选

def seq(*fs):
    def fn(s):
        for f in fs:
            s = f(s)
            if not s:
                return s
        return s
    return fn
    
def par(*fs):
    def fn(s):
        for f in fs:
            t = f(s)
            if t:
                return t
        return t
    return fn

def id(s):
    return s

def opt(f):
    return par(f, id)

def mor(f):
    #return seq(f, zmo(f))
    return seq(f, lambda s: zmo(f)(s))

def zmo(f):
    return opt(mor(f))

这就是BNF的基础函数。有了这些就可以写parser了。

比如SQL的语法：

"""
select ...
from ...
where ...
group by ...
having ...
order by ...
"""

select关键字之后可以有一个或多个column，表达为mor(column)。

order by clause可有可无，表达为opt(order_by)。

最后加一个end。表示输入的结尾。

所以这个SQL的BNF就可以这样表达：

seq(select, mor(column), from_clause, where, group_by, having, opt(order_by), end)

这已经是程序了。

代码： 全选

def sql(s):
    return seq(select, mor(column), from_clause, where, group_by, having, opt(order_by), end)(s)

把用到的关键字定义一下。这些可以从lexer出来。但是为了简单，直接写成单字母token：

代码： 全选

def keyword(k):
    def fn(s):
        if s and input[s-1] == k:
            return s+1
        return 0
    return fn

end = keyword("e")
select = keyword("S")
column = keyword("C")
from_clause = keyword("F")
join = keyword("J")
where = keyword("W")
group_by = keyword("G")
having = keyword("H")
order_by = keyword("O")

它能接受这样的语句：
input = "SCCCFWGHe"
result = sql(1)
print(result)

[TheMatrix]

这就是BNF的基础函数。有了这些就可以写parser了。

比如SQL的语法：

"""
select ...
from ...
where ...
group by ...
having ...
order by ...
"""

select关键字之后可以有一个或多个column，表达为mor(column)。

order by clause可有可无，表达为opt(order_by)。

最后加一个end。表示输入的结尾。

所以这个SQL的BNF就可以这样表达：

seq(select, mor(column), from_clause, where, group_by, having, opt(order_by), end)

这已经是程序了。

代码： 全选

def sql(s):
    return seq(select, mor(column), from_clause, where, group_by, having, opt(order_by), end)(s)

把用到的关键字定义一下。这些可以从lexer出来。但是为了简单，直接写成单字母token：

代码： 全选

def keyword(k):
    def fn(s):
        if s and input[s-1] == k:
            return s+1
        return 0
    return fn

end = keyword("e")
select = keyword("S")
column = keyword("C")
from_clause = keyword("F")
join = keyword("J")
where = keyword("W")
group_by = keyword("G")
having = keyword("H")
order_by = keyword("O")

它能接受这样的语句：
input = "SCCCFWGHe"
result = sql(1)
print(result)

稍微加点复杂度：

group_by和having的关系是：它们都是optional的，但是having如果有，必须跟着group by。

那就需要这样表达：
seq(select, mor(column), from_clause, where, opt(seq(group_by, opt(having))), opt(order_by), end)

[TheMatrix]

BNF的一个item怎么理解，这件事我想了很久。希望能挖出一些新的视角。

BNF的一个item，也就是那几个基础高阶函数（seq, par, etc）作用在的那个东西。

f: state --> state

我这个函数signature也是最近才写出来的，以前我不是这么写的。

这代表f是state空间上的一个自变换。也就是说BNF的一个item，是state空间上的一个自变换。或者说BNF的item的空间，是state空间上的自变换空间。

那么seq和par就是这个空间上的乘法和加法。seq是乘法，par是加法。乘法和加法都满足结合律。乘法对加法有分配律。但是乘法和加法都不是可交换的。加法也不是可交换的 - 因为par函数遇到第一个满足的f就返回。

这形成了state自变换空间的一个algebra。这个有点意思。可以再开发一下。但是我觉得这个是经典的理解。应该已经被开发透了。

[TheMatrix]

BNF的一个item怎么理解，这件事我想了很久。希望能挖出一些新的视角。

另一个看法是路径。状态图是有向图，状态转换是一个箭头，这是两个状态直接连接的情况。两个状态不直接连接的话，也可能会有路径连接。这样的一个路径就是BNF的一个item。这是形象化的理解。再加上一些可变量，最后和state空间自变换应该是等价的。但是形象化的理解是其内核。

一个完整的BNF，本身就可以画成一个图，在parser的问题中就是语法图。这个图是以BNF item为节点的。但是在我们前面的理解中，一个BNF item，f: state --> state，本身是一个路径（状态图上的路径），至少是一个箭头，它并不是一个节点。也就是说状态图和语法图不是同一个图。

语法图可以展开成一个状态图。但是很多语法图都可以展开成同一个状态图。也就是说语法图是状态图的一种抽象，但是这个抽象具有一些人为的任意性 - 你觉得这样抽象好，我觉得那样抽象好，得到的是不同的语法图，但是展开成同样的状态图。

而一个输入文本能够被一个BNF接受，或者说被一个语法图接受，就是它能够在展开的状态图上trace out出一条路径（在BNF所选定的起点和终点之间）（BNF本身是自带起点和终点的）。

[wdong]

yacc是一个古早的语法编译器。把BNF语法写好后，用这个yacc过一遍就能得到一个parser。

https://github.com/aaalgo/undergraduate ... /sql/sql.y

当时时兴搞流处理，也就是把数据和查询倒转。先写好SQL，然后数据流来了过SQL筛一遍把结果筛出来。我本科毕业论文就是做了这么一个系统。上面这个文件就是用yacc写的SQL语法。没有子查询。select from where group having都实现了。

[wdong]

楼主你需要的是怎么把上面这两个抽象的函数变成容易看懂的东西，而不是去研究怎么写这种咒语一样的东西。很多东西刚发明的时候因为对问题的本质和解法的本质了解不深入，视角不对，所以有这种非常难懂的东西。技术的进步是怎么把难懂的变成易懂的。

[TheMatrix]

楼主你需要的是怎么把上面这两个抽象的函数变成容易看懂的东西，而不是去研究怎么写这种咒语一样的东西。很多东西刚发明的时候因为对问题的本质和解法的本质了解不深入，视角不对，所以有这种非常难懂的东西。技术的进步是怎么把难懂的变成易懂的。

seq和par不容易看懂吗？sequential和parallel，多形象啊？

你的实现中有这两个函数吗？写出来我看看？

[wdong]

seq和par不容易看懂吗？sequential和parallel，多形象啊？

你的实现中有这两个函数吗？写出来我看看？

这是编译器干的事情，我的实现里没有。

[TheMatrix]

这是编译器干的事情，我的实现里没有。

你的代码我看了。你这个代码是给yacc处理的。而我这个实现的就是yacc。

yacc比直接动手写parser的抽象层次要高一层。所以它更优美。

而我认为抽象层次高，是更加走向智能的标志。我不直接改代码，我改可以生成代码的规则。下一步就是我不直接改生成代码的规则，我改生成代码规则的规则。。。这是我的看法。

从神经网络的messy程度，现在大家可能认为越messy越智能。这可能是错的。

当然，抽象也有好的抽象和坏的抽象。我说的是好的抽象。

[TheMatrix]

你的代码我看了。你这个代码是给yacc处理的。而我这个实现的就是yacc。

yacc比直接动手写parser的抽象层次要高一层。所以它更优美。

而我认为抽象层次高，是更加走向智能的标志。我不直接改代码，我改可以生成代码的规则。下一步就是我不直接改生成代码的规则，我改生成代码规则的规则。。。这是我的看法。

从神经网络的messy程度，现在大家可能认为越messy越智能。这可能是错的。

当然，抽象也有好的抽象和坏的抽象。我说的是好的抽象。

yacc/BNF正是一个好的抽象的例子：因为yacc的语法特别简单，只有两条：并行和串行，也就是seq和par这两个函数。这正体现了更高层次的抽象反而更简单。

[TheMatrix]

另一个看法是路径。状态图是有向图，状态转换是一个箭头，这是两个状态直接连接的情况。两个状态不直接连接的话，也可能会有路径连接。这样的一个路径就是BNF的一个item。这是形象化的理解。再加上一些可变量，最后和state空间自变换应该是等价的。但是形象化的理解是其内核。

一个完整的BNF，本身就可以画成一个图，在parser的问题中就是语法图。这个图是以BNF item为节点的。但是在我们前面的理解中，一个BNF item，f: state --> state，本身是一个路径（状态图上的路径），至少是一个箭头，它并不是一个节点。也就是说状态图和语法图不是同一个图。

语法图可以展开成一个状态图。但是很多语法图都可以展开成同一个状态图。也就是说语法图是状态图的一种抽象，但是这个抽象具有一些人为的任意性 - 你觉得这样抽象好，我觉得那样抽象好，得到的是不同的语法图，但是展开成同样的状态图。

而一个输入文本能够被一个BNF接受，或者说被一个语法图接受，就是它能够在展开的状态图上trace out出一条路径（在BNF所选定的起点和终点之间）（BNF本身是自带起点和终点的）。

BNF item作为路径这个思路，我一直觉得还可以深挖。

因为BNF的功能就是识别一个文本属于某种语法，比如这个是SQL，那个是Python，等等。

这和识别一个图片其实是类似的：这个图片是一只猫，那个图片是一只狗。

也就是在一个语法图（概念图）所描述的地图（状态图）上找一条路径。

当然现在看不可能是手写的语法图，也就是不可能是传统意义上rule based。

还要再往上走一层抽象。

[wdong]

你知道LLM可以接BNF吗？语法制导生成，可以生成完全符合语法的内容。

[TheMatrix]

你知道LLM可以接BNF吗？语法制导生成，可以生成完全符合语法的内容。

不知道。但是我不奇怪。肯定在现在的LLM的能力之内。

[TheMatrix]

以下的代码我隔一段时间就要revisit。代码本身太美了。

#f: state --> state
#where state is an integer
#finite states
#there is a special state 0 stands for error state

bnf (f: state --> state) 作为状态空间上的自变换，美则美矣，因为它简单，但是丧失了一些信息。

自变量是一个state，这是没问题的。但是函数值不仅仅是一个新的state，还包括很多信息。比如path，从起始的state怎么一步一步到达新的state。如果加上这些，就变成：f: state --> path, where path is a list of state。这就不再是state空间上的自变换了。

自变换的好处是可以有composition。但是也没必要执着于它。它是什么就是什么。f: state --> state 这个抽象对于识别一个语法true/false是够了。但是没有更多的信息。

从 f: state --> (state, X) 出发，seq要做的，是把这样的一些函数串在一起，函数结果也要串在一起。结果要串在一起的话，说明X必须是一个list。list of what? 为了保持最大的通用性，就不明确的说list of what了，可以是list of anything，可以是list of list。

所以这两天我想来想去，又回到我之前给出的函数signature了：
f: state --> (state, [])