词法分析 | 自顶向下分析算法

首先我们给定文法G如下：

S -> N V N
N -> s
   | t
   | g
   | w
V -> e
   | d

需要推导出句子s如下：
g d w

使用图演示一下具体的过程

使用一个脚本来演示类似的算法

class Parser:
    def __init__(self, grammar):
        self.grammar = grammar  # 文法规则，以字典形式存储

    def parse(self, sentence):
        stack = []  # 初始化栈
        productions = self.grammar['S']
        for production in productions:
            stack.append(production)
        index = 0
        tmp_n=0
        tmp_v=0
        index2=0
        access_list=[]
        while stack:
            if index2>=len(stack):
                index2=int(len(stack)-1)
                if index2<0:index2=0
            top = stack[index2]
            del stack[index2]
            if top in self.grammar:  # 非终结符
                if top=='N':
                    stack.insert(index,self.grammar[top][tmp_n])
                    tmp_n+=1
                if top=='V':
                    stack.insert(index,self.grammar[top][tmp_v])
                    tmp_v+=1
            else:
                if top!=sentence[index]:
                    stack.insert(index,self.grammar['S'][index])
                else:
                    access_list.append(top)
                    tmp_n=0
                    tmp_v=0
                    index+=1
                    index2+=1
            #break
        return "".join(access_list) == "".join(sentence)  # 所有符号匹配成功

# 定义文法
grammar = {
    'S': ['N','V', 'N'],
    'N': ['s', 't', 'g', 'w'],
    'V': ['e', 'd']
}

parser = Parser(grammar)
sentence = ['g','d','w']

print(sentence[0])
if parser.parse(sentence):
    print("句子", sentence, "符合文法")
else:
    print("句子", sentence, "不符合文法")

上述自上而下的方式太过于消耗性能，可以改为如下的方式

例子如下：

class Parser:
    def __init__(self, grammar):
        self.grammar = grammar  # 文法规则，以字典形式存储

    def parse(self, sentence):
        stack = []  # 初始化栈
        productions = self.grammar['S']
        for production in productions:
            stack.append(production)
        index = 0
        access_list=[]
        while stack:
            top = stack.pop()
            if top in self.grammar:  # 非终结符
                flag=False
                for i2 in self.grammar[top]:
                    if i2 == sentence[index]:
                        index+=1
                        access_list.append(i2)
                        flag=True
                if not flag:
                    return False
                
        print(access_list)   
        return "".join(access_list) == "".join(sentence)  # 所有符号匹配成功

# 定义文法
grammar = {
    'S': ['N','V', 'N'],
    'N': ['s', 't', 'g', 'w'],
    'V': ['e', 'd']
}

parser = Parser(grammar)
sentence = ['g','d','w']

if parser.parse(sentence):
    print("句子", sentence, "符合文法")
else:
    print("句子", sentence, "不符合文法")