Python的源程序是由token构成的。例如return单词是一个关键字token， 字面量2是一个数字字面token。当解析python源代码时，第一个任务就是讲源代码分解成token。Python有以下一些token类型：

1. 标识符。是程序员定义的名称，包括函数名，变量名，类名等等。这些名字必须符合Python语言规范的要求。

2. 操作符。例如+, *等的特殊符号，用于操作数据值并且生成结果。

3. 分隔符。它们用于将表达式分组，用于提供标点符号和赋值。例如(, ), {, }, =, *=等。

4. 字面量。这些符号为某些类型提供常量。比如可以有string类型的字面量”Fred”，byte类型的字面量b”Fred”, 数字字面量2，浮点字面量1e100， 复数字面量10j等等。

5. 注释。

6. NEWLINE。这个特别的token用来表示逻辑行的结束。

7. INDENT和DEDENT:这些标记（块缩进和取消缩进）用于表示对复合语句进行分组缩进。

一组token通过NEWLINE token勾画出逻辑行，所以我们可以认为Python程序是由一系列通过NEWLINE token区隔的逻辑行组成的。这些逻辑行对应Python的语句，并且由数个物理行组成。大多数时候，一个逻辑行对应一个物理行，所以逻辑行由行结束符分割。复合语句可以跨越多个物理行。当表达式位于括号、方括号或大括号中时，逻辑行可以隐式连接在一起，或者使用反斜杠字符显式地连接在一起。缩进在对Python语句分组时也起着核心作用。一个典型的Python语法是：suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT，所以python的tokenizer主要任务是生成缩进和取消缩进的token放入解析树。tokenizer使用栈来追踪缩进，并且使用下面的算法来生成INDENT 和 DEDENT token。

1 Init the indent stack with the value 0.

2 For each logical line taking into consideration line-joining:

3 A. If the current line’s indentation is greater than the

4 indentation at the top of the stack

5 1. Add the current line’s indentation to the top of the stack.

6 2. Generate an INDENT token.

7 B. If the current line’s indentation is less than the indentation

8 at the top of the stack

9 1. If there is no indentation level on the stack that matches

10 the current line’s indentation report an error.

11 2. For each value at the top of the stack that is unequal to

12 the current line’s indentation.

13 a. Remove the value from the top of the stack.

14 b. Generate a DEDENT token.

15 C. Tokenize the current line.

16 For every indentation on the stack except 0, produce a DEDENT token.

Parser/parsetok.c模块中的PyTokenizer_FromFile函数从左到右从上到下地扫描python源代码文件来生成token。空白字符不同于结束符，是用来界定token，但不是必需的。当遇到有歧义的2+2时，会从左到右读取合法的token的最长可能字符串，在这个例子里面，token将会被识别为字面量2，操作符+和字面量2。

生成好的token被传递给解析器，用来生成根据Python语法规定的解析树。当解析器遇到违反语法的token，将会抛出SyntaxError异常。解析器的输出是解析树。

python中的parser模块可以用来提供对解析器根据python代码块生成的解析树的部分访问功能，下面的例子展示了如何使用parser模块来查看一个具体的解析树。

1 >>>code_str = “””def hello_world():

2 return ‘hello world’

3 “””

4 >>> import parser

5 >>> from pprint import pprint

6 >>> st = parser.suite(code_str)

7 >>> pprint(parser.st2list(st))

8 [257,

9 [269,

10 [294,

11 [263,

12 [1, ‘def’],

13 [1, ‘hello_world’],

14 [264, [7, ‘(‘], [8, ‘)’]],

15 [11, ‘:’],

16 [303,

17 [4, ”],

18 [5, ”],

19 [269,

20 [270,

21 [271,

22 [277,

23 [280,

24 [1, ‘return’],

25 [330,

26 [304,

27 [308,

28 [309,

29 [310,

30 [311,

31 [314,

32 [315,

33 [316,

34 [317,

35 [318,

36 [319,

37 [320,

38 [321,

39 [322, [323, [3, ‘”hello world”‘]]]]]]]]]]]]]]]]]\

40 ]]],

41 [4, ”]]],

42 [6, ”]]]]],

43 [4, ”],

44 [0, ”]]

45 >>>

上面的parser.suite(source)返回一个解析树(ST)对象，只要源码语法正确的话，它就是源代码解析树的python中间表示。parser.st2list的调用返回的是解析树用python列表表现的形式。列表中的第一个项目，整数，用来标示python语法的生成规则。下图展示了对应的解析树形式。这些生成规则在Include/token.h和Include/graminit.h头文件中被定义。

在cpython虚拟机中，一个树数据结构用来表示解析树。每个生成规则都是树数据结构上的一个节点，下面展示了这种节点的数据结构，它的定义在Include/node.h中。

1 typedef struct _node {

2 short n_type;

3 char *n_str;

4 int n_lineno;

5 int n_col_offset;

6 int n_nchildren;

7 struct _node *n_child;

8 } node;

当遍历解析树时，可以查询这些节点的类型，它们的子节点，创建该节点的行号等等。Include/node.h文件定义了和解析树节点交互的宏。