在语法分析程序中加入语义计算(自顶向下翻译)

沿用上一篇中的例子,在语法分析中加入一些额外的操作,实现我们的特定目标。
在上下文无关文法的基础上,为每个文法符号配备若干相关的值(“属性”),代表与文法符号相关的信息。
在语法分析树中自上而下传递的是继承属性,自下而上的传递的是综合属性(有时候综合属性也依赖于兄弟结点的属性值)。
一遍扫描的处理方法能在语法分析的同时计算属性值,这种方法处理 L-属性文法和 S-属性文法是很有效的。

所谓 L-属性文法,是指每个产生式的语义规则中,每个符号的属性要么是综合属性,要么是只依赖于它左边符号的属性的继承属性。
这类属性文法允许我们通过一次遍历就计算出所有属性值。如 LL(1) 这种自上而下分析方法的分析过程,可以看成是深度优先建立语法树的过程,因此,我们可以在自上而下语法分析的同时实现L属性文法的计算。

在本文的例子中,我们想要输出括号表达式中每个字母的嵌套深度,以及整个句子的最大深度和括号对数。
下面是括号表达式的上下文无关文法,它是满足LL(1)文法的条件的。

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

加入属性: level表示当前所在层级,是继承属性。depth是综合属性,用来计算整个句子的最大深度。pair表示括号对数,是综合属性。
为便于表示,我直接给出了翻译模式,它比用属性文法写出语义规则更为直观。翻译模式给出了使用语义规则进行计算的次序,这样可以把某些实现细节表示出来。

本例的翻译模式如下:

S' -> {S.level=0, S.pair=0, S.depth=0}
    S#
    {print(S.depth, S.pair)}
S -> (
    {T.level=S.level+1}
    T)
    {S.pair=T.pair+1, S.depth=T.depth+1}  
S -> {print(S.level)}
    a
    {S.pair=0, S.depth=0}
T -> {S.level=T.level, T1.level=T.level}
    S,T1 
    {T.depth=max(S.depth,T1.depth), T1.pari=S.pair}  
T -> {S.level=T.level}
    S 
    {T.depth=S.depth}

大括号中描述了在分析过程中不同阶段所做的运算。符号的继承属性计算应放在符号前面,综合属性的计算放在产生式末尾,这和分析过程是对应的。在递归分析程序中,每个非终结符对应了一个子程序。在调用子程序之前,需要向子程序传递继承属性;而当子程序结束的时候,应当返回该过程对应非终结符的综合属性。通过参数和返回值的形式就能够让属性在递归遍历语法树的过程中得以传递。

具体的程序示例如下:


class LexicalAnalysor():
    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):
        depth, pair = self.S(0)
        if self.sym == '#':
            print("success")
            print('depth=%d, pair=%d'%(depth, pair))
            exit(0)
        else:
            self.ERROR() 

    def S(self, count):
        if self.sym == '(':
            self.ADVANCE()
            depth, pair = self.T(count+1) 
            if self.sym == ')':
                self.ADVANCE()
                return (depth+1, pair+1)
            else:
                self.ERROR()
        elif self.sym == 'a':
            print("a's level is %d at position %d" % (count, self.index))
            self.ADVANCE()
            return (0,0)
        else:
            self.ERROR()

    def T(self, count):
        depth, pair = self.S(count)
        while self.sym == ',':
            self.ADVANCE()
            depth1, pair1 = self.S(count)
            depth = max(depth, depth1)
            pair += pair1
        return (depth, pair)


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

运行结果:

C:\Users\ouyang\Desktop>python match.py
Input a sentence: (a,a,(a,a,(a,(a)),a,(a,a)),a)
tokens: '(a,a,(a,a,(a,(a)),a,(a,a)),a)#'
a's level is 1 at position 1
a's level is 1 at position 3
a's level is 2 at position 6
a's level is 2 at position 8
a's level is 3 at position 11
a's level is 4 at position 14
a's level is 2 at position 18
a's level is 3 at position 21
a's level is 3 at position 23
a's level is 1 at position 27
success
depth=4, pair=5