语法分析-上下文无关文法简单理解

一个上下文无关文法包括：

一个字符集、一个变元集合以及一个产生式集合，并且变元集合中有一个变元被称为初始变元。

所谓产生式就是 S→aSb 这样的，由一个变元变成变元和字符组成的串的式子。

举个例子:

自然语言中的句子的典型结构
主语 谓语 宾语
名词 动词 名词
例子：
名词：{羊， 老虎， 草， 水}
动词：{吃， 喝}
句子：
羊 吃 草
羊 喝 水
老虎 吃 老虎
草 吃 老虎

那么也可以套用如上的。

对这个例子，我们进行形式化分析：

（S 表示句子， -> 表示推出， N 表示名词， V 表示动词）

S -> N V N 
N -> s(sheep)
   | t(tiger)
   | g(grass)
   | w(water)
V -> e(eat)
   | d(drink)

我们将其中的大写符号叫做非终结符：{S, N, V}

将小写的符号（名词+谓词）叫做终结符：{s, t, g, w, e, d}

开始符号是：S

上下文无关文法

上下文无关文法 G 是一个四元组：

G = (T, N, P, S)

其中 T 是终结符集合
N 是非终结符集合
P 是一组产生式规则
每条规则的形式： X -> β1 β2 ... βn, n >= 0
其中 X ∈ N, βi ∈（T ∪ N）
S 是唯一的开始符号（非终结符）
S ∈ N

G = {N, T, P, S}
非终结符号：N = {S, N, V}
终结符号： T = {s, t, g, w, e, d}
开始符号：S
产生式规则集合：
{ S -> N V N,
N -> s,
N -> t,
N -> g,
N -> w,
V -> e,
V -> d}

那么可以使用代码来演示一下

grammar = {
    'S': ['N', 'V', 'N'],
    'N': ['s', 't', 'g', 'w'],
    'V': ['e', 'd']
}

# 文法推导函数
def derive(symbol, input_string):
    if symbol not in grammar:
        return False
    #推导函数
    count=0
    for production in grammar[symbol]:
        #从左到右推导  第一位是N
        if production not in grammar:
            continue
        #判断是否在文法中
        if input_string[count] in grammar[production]:
            count+=1
    return count == len(input_string)

#随机生成文法
def run_derive(symbol):
    ret=""
    if symbol not in grammar:
        return ''
    #读取文法规则
    for production in grammar[symbol]:
        if production in grammar:
            name=grammar[production]
            #随机长度
            


# 使用推导函数
input_string = "set"
print(derive('S', input_string))

教程地址：https://www.bilibili.com/video/BV1m7411d7iS