Skip to main content

首页

Python源码分析（1）：语法分析

词法分析

一段程序文本有一个一个字符组成，但是对程序来说，程序的最小意义单位是Token，比如一个变量名，一个字符串常量，一个运算符。

将程序文本从一个字符序列转换为一个Token序列称为词法分析，一般采用确定有穷自动机（DFA）模型。

词法分析比较简单，略过，具体实现可以查看Parser/tokenizer.c#tok_get，基本上就是一个巨大的DFA。

语法分析

词法分析得到的Token序列将作为语法分析的输入，语法分析的输出是一棵语法树。

语法描述：

  • 语法（又称文法）由一系列产生式（又称规则）组成；
  • 产生式的左边是一个非终结符，右边是一个Token（终结符）和非终结符组成的序列。

LL（1）语法分析

  • 第一个L表示自顶向下分析是从做向右扫描Token序列；
  • 第一个L表示分析过程中采用最左推导；
  • （1）表示只需向右看一个Token便可以决定选择哪个产生式（规则）进行推导。

Python中的语法结构体定义：

typedef struct {
    int          g_ndfas;
    const dfa   *g_dfa;         /* Array of DFAs */
    const labellist g_ll;
    int          g_start;       /* Start symbol of the grammar */
    int          g_accel;       /* Set if accelerators present */
} grammar;

主要是一个dfa数组和终端符列表。Python 采用 LL（1）语法分析，每个产生式都对应一个dfa。

以上是grammar的定义，全局变量的声明在 Python/graminit.c中。

在编译过程中，如果Grammar文件修改了，会重新生成 Include/graminit.h 和 Python/graminit.c 具体的命令在Makefile里：

regen-grammar: regen-token
 # Regenerate Include/graminit.h and Python/graminit.c
 # from Grammar/Grammar using pgen
 @$(MKDIR_P) Include
 PYTHONPATH=$(srcdir) $(PYTHON_FOR_REGEN) -m Parser.pgen \
    $(srcdir)/Grammar/Grammar \
 	$(srcdir)/Grammar/Tokens \
 	$(srcdir)/Include/graminit.h.new \
 	$(srcdir)/Python/graminit.c.new
 $(UPDATE_FILE) $(srcdir)/Include/graminit.h $(srcdir)/Include/graminit.h.new
 $(UPDATE_FILE) $(srcdir)/Python/graminit.c $(srcdir)/Python/graminit.c.new

graminit.c中一共定义了92个dfa，对应的是Grammar文件中的92条产生式。

向右扫描一个Token进行推导的具体实现: Parser/parser.c 中的 PyParser_AddToken函数。

目录

2020/06/08