Python語法的相關(guān)規(guī)則中的DFA的相關(guān)內(nèi)容的介紹
我們都知道Graminit.c中定義了其中有包括Python語法規(guī)則的相關(guān)實際應用的相關(guān)內(nèi)容，其中也包括了一些典型的類型，你如果想知道是哪四種典型的類型的話，你就可以瀏覽以下的文章對其進行了解。
Grammar.h
Graminit.c中定義了包括Python語法規(guī)則的DFA(Deterministic Finite Automaton)，關(guān)于DFA請參考Alfred V. Aho等人所著的Compilers: Principles, Techniques, and Tools一書。為了定義DFA，graminit.c引用了位于grammar.h中的一些類型：arc, state, dfa, grammar。
Label定義了從狀態(tài)轉(zhuǎn)移到另外一個狀態(tài)所經(jīng)過的邊所對應的符號，可以是非終結(jié)符(Non-Terminal)，也可以是終結(jié)符(Terminal)。Label一定依附于一條或者多條邊。Lb_type代表符號的類型，如終結(jié)符NAME，代表一個標示符，或者非終結(jié)符stmt，代表一個語句，等等。
Lb_str代表具體符號的內(nèi)容。比如，label (NAME, “if”)表示當parser處于某個狀態(tài)，如果遇到了’if’這個標示符，則移動另外一個狀態(tài)。如果label是一個非終結(jié)符的話，情況則要復雜一些，需要跳轉(zhuǎn)到該非終結(jié)符對應的另外一個DFA，請參看編譯器相關(guān)書籍。
- /* A label of an arc */
- typedef struct {
- int lb_type;
- char *lb_str;
- } label;
在Graminit.c中定義了包括Python語法規(guī)則的DFA中arc代表DFA中一個狀態(tài)到另一個狀態(tài)的弧/邊。A_lbl代表arc所對應的Label，而a_arrow記錄了arc的目標狀態(tài)。因為arc是屬于某個狀態(tài)的，因此不用紀錄arc的起始狀態(tài)。
- /* An arc from one state to another */
- typedef struct {
- short a_lbl; /* Label of this arc */
- short a_arrow; /* State where this arc goes to */
- } arc;
State代表著DFA中的狀態(tài)節(jié)點。每個state記錄了從該state出發(fā)的邊的集合，存放在s_arc中。其他的一些成員s_lower, s_upper, s_accel, s_accept記錄了state所對應的Accelerator，其作用會在后面講述。注意Accelerator信息并沒有定義在graminit.c中，而是在運行時計算出來的。
- /* A state in a DFA */
- typedef struct {
- int s_narcs;
- arc *s_arc; /* Array of arcs */
- /* Optional accelerators */
- int s_lower; /* Lowest label index */
- int s_upper; /* Highest label index */
- int *s_accel; /* Accelerator */
- int s_accept; /* Nonzero for accepting state */
- } state;
DFA結(jié)構(gòu)中記錄了起始狀態(tài)d_initial和所有狀態(tài)的集合d_state。d_first記錄了該DFA所對應的非終結(jié)符的firstset，也就是說，當遇到firstset中的終結(jié)符的時候，便需要跳轉(zhuǎn)到此DFA中。d_first在后面計算Accelerators的時候會被用到。
- /* A DFA */
- typedef struct {
- int d_type; /* Non-terminal this represents */
- char *d_name; /* For printing */
- http://new.51cto.com/wuyou/int d_initial; /* Initial state */
- int d_nstates;
- state *d_state; /* Array of states */
- bitset d_first;
- } dfa;
Grammar代表了Python的整個語法，記錄了所有的DFA和所有的label。G_start則是Python語法的起始symbol，一般是single_input。不過實際的起始symbol可以在創(chuàng)建Parser的時候指定，可以是single_input, file_input, eval_input中的一個。
【編輯推薦】
