一个递归下降分析程序例子

当一个文法满足LL(1)条件时,就可以为它构建一个不带回溯的自上而下分析程序。这个程序由一组递归过程组成,每个过程对应文法的一个非终结符。
本例展示了一个分析括号表达式((a,(a,a)))的程序实现。
文法 G(S) 定义如下:


G(S):
    S' -> S#
    S -> (T) | a
    T -> S,T | S    /* or T -> S{,S} */

下面是用 Python 实现的分析程序:


#!/bin/python3
class LexicalAnalysor():
    """
    G(S):
    S' -> S#
    S -> (T) | a
    T -> S,T | S    /* or T -> S{,S} */
    """
    def __init__(self, tokens):
        if tokens[-1] != '#':
            tokens += '#'
        self.tokens = tokens
        self.sym = tokens[0]
        self.index = 0

    def ADVANCE(self):
        self.index += 1
        try:
            self.sym = self.tokens[self.index]
        except Exception as e:
            print(e)
            self.ERROR()

    def ERROR(self):
        print("error at position %d!" % self.index)
        exit()

    def Start(self):
        self.S()
        if self.sym == '#':
            print("success")
            exit(0)
        else:
            self.ERROR() 

    def S(self):
        if self.sym == '(':
            self.ADVANCE()
            self.T() 
            if self.sym == ')':
                self.ADVANCE()
            else:
                self.ERROR()
        elif self.sym == 'a':
            self.ADVANCE()
        else:
            self.ERROR()

    def T(self):
        self.S()
        while self.sym == ',':
            self.ADVANCE()
            self.S()


if __name__ == '__main__':
    analyser = LexicalAnalysor("(a,(a,a),a,(a,a))")
    print("tokens: '%s'" % analyser.tokens)
    analyser.Start()

运行结果:
match