语法分析 | 递归下降分析算法

对于给定的文法G如下：

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

可以简单的使用parse_S  paser_N parse_V 这样的进行判断。例如：

class Parser:
    def __init__(self, text):
        self.text = text
        self.index = 0
        self.current_token = self.text[self.index]

    def match(self, token):
        if self.text[self.index]==token:
            self.index += 1
            return True

    def parse(self):
        return self.S()

    def S(self):
        if self.N():
            if self.V():
                if self.N():
                    return True
        return False

    def N(self):
        if self.match('s') or self.match('t') or self.match('g') or self.match('w'):
            return True
        return False

    def V(self):
        if self.match('e') or self.match('d'):
            return True
        return False

# 给定文法G
input_sentence = 'gds'

# 初始化解析器
p = Parser(input_sentence)

# 执行解析
if p.parse():
    print("句子 '{}' 可以被文法G正确解析。".format(input_sentence))
else:
    print("句子 '{}' 不能被文法G解析。".format(input_sentence))

稍微复杂一点就是对算术的一个计算了

例如：

E -> E + T
   | T
T -> T * F
   | F
F -> num

实现的方式如下:

class Parser:
    def __init__(self, text):
        self.text = text
        self.index = 0
        self.current_token = text[self.index] if text else None

    def match(self, token):
        if self.current_token == token:
            self.current_token = self.text[self.index + 1] if self.index + 1 < len(self.text) else None
            self.index += 1
            return True
        return False

    def parse(self):
        return self.E()

    def E(self):
        if self.T():
            while self.match('+') and self.T():
                pass
            return True
        return False

    def T(self):
        if self.F():
            while self.match('*') and self.F():
                pass
            return True
        return False

    def F(self):
        if self.current_token and self.current_token.isdigit():
            self.current_token = self.text[self.index + 1] if self.index + 1 < len(self.text) else None
            self.index += 1
            return True
        return False

# 给定文法
input_sentence = "3+4*1+1"

# 初始化解析器
p = Parser(input_sentence)

# 执行解析
if p.parse() and p.index == len(input_sentence):
    print("句子 '{}' 可以被文法正确解析。".format(input_sentence))
else:
    print("句子 '{}' 不能被文法解析。".format(input_sentence))