641719104956b358aa59eec291609198
Python 的抽象语法树(一)

Python的抽象语法树(一)

之前三章的内容,我们分别谈及了语法分析中涉及到的文法定义、文法分析以及消除左递归等内容。

今天我们来谈谈语法分析的另一大部分内容:抽象语法树。

抽象语法树

简单来说,抽象语法树是在语法分析过程中,对词法符号进行文法分析后,选择某一条产生式进行展开后的结果。

假设我们有如下代码:

a - (b + c)

这里我们忽略a, b, c三者的值

首先得到词法分析的结果,Token流:

NAME MINUS LPAR NAME PLUS NAME RPAR

结合我们在Python的语法分析(一)提到的文法定义,分析出来的大致的抽象语法树如下图所示:

感兴趣推导过程的读者可以自行尝试推导一次,涉及到的文法定义如下:

// 重点区块1
test: or_test ['if' or_test 'else' test] | lambdef
test_nocond: or_test | lambdef_nocond
lambdef: 'lambda' [varargslist] ':' test
lambdef_nocond: 'lambda' [varargslist] ':' test_nocond
or_test: and_test ('or' and_test)*
and_test: not_test ('and' not_test)*
not_test: 'not' not_test | comparison
comparison: expr (comp_op expr)*

// 重点区块2
expr: xor_expr ('|' xor_expr)*
xor_expr: and_expr ('^' and_expr)*
and_expr: shift_expr ('&' shift_expr)*
shift_expr: arith_expr (('<<'|'>>') arith_expr)*

// 重点区块3
arith_expr: term (('+'|'-') term)*
term: factor (('*'|'@'|'/'|'%'|'//') factor)*
factor: ('+'|'-'|'~') factor | power
top Created with Sketch.