Python語(yǔ)法規(guī)則中的DFA的內(nèi)容是什么

這篇文章將為大家詳細(xì)講解有關(guān)Python語(yǔ)法規(guī)則中的DFA的內(nèi)容是什么，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

Grammar.h
Graminit.c中定義了包括Python語(yǔ)法規(guī)則的DFA(Deterministic Finite Automaton)，關(guān)于DFA請(qǐng)參考Alfred V. Aho等人所著的Compilers: Principles, Techniques, and Tools一書(shū)。為了定義DFA，graminit.c引用了位于grammar.h中的一些類(lèi)型：arc, state, dfa, grammar。

Label定義了從狀態(tài)轉(zhuǎn)移到另外一個(gè)狀態(tài)所經(jīng)過(guò)的邊所對(duì)應(yīng)的符號(hào)，可以是非終結(jié)符(Non-Terminal)，也可以是終結(jié)符(Terminal)。Label一定依附于一條或者多條邊。Lb_type代表符號(hào)的類(lèi)型，如終結(jié)符NAME，代表一個(gè)標(biāo)示符，或者非終結(jié)符stmt，代表一個(gè)語(yǔ)句，等等。

Lb_str代表具體符號(hào)的內(nèi)容。比如，label (NAME, “if”)表示當(dāng)parser處于某個(gè)狀態(tài)，如果遇到了’if’這個(gè)標(biāo)示符，則移動(dòng)另外一個(gè)狀態(tài)。如果label是一個(gè)非終結(jié)符的話，情況則要復(fù)雜一些，需要跳轉(zhuǎn)到該非終結(jié)符對(duì)應(yīng)的另外一個(gè)DFA，請(qǐng)參看編譯器相關(guān)書(shū)籍。

/* A label of an arc */  typedef struct {  int lb_type;  char *lb_str;  } label;

在Graminit.c中定義了包括Python語(yǔ)法規(guī)則的DFA中arc代表DFA中一個(gè)狀態(tài)到另一個(gè)狀態(tài)的弧/邊。A_lbl代表arc所對(duì)應(yīng)的Label，而a_arrow記錄了arc的目標(biāo)狀態(tài)。因?yàn)閍rc是屬于某個(gè)狀態(tài)的，因此不用紀(jì)錄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é)點(diǎn)。每個(gè)state記錄了從該state出發(fā)的邊的集合，存放在s_arc中。其他的一些成員s_lower, s_upper, s_accel, s_accept記錄了state所對(duì)應(yīng)的Accelerator，其作用會(huì)在后面講述。注意Accelerator信息并沒(méi)有定義在graminit.c中，而是在運(yùn)行時(shí)計(jì)算出來(lái)的。

/* 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所對(duì)應(yīng)的非終結(jié)符的firstset，也就是說(shuō)，當(dāng)遇到firstset中的終結(jié)符的時(shí)候，便需要跳轉(zhuǎn)到此DFA中。d_first在后面計(jì)算Accelerators的時(shí)候會(huì)被用到。

/* 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的整個(gè)語(yǔ)法，記錄了所有的DFA和所有的label。G_start則是Python語(yǔ)法的起始symbol，一般是single_input。不過(guò)實(shí)際的起始symbol可以在創(chuàng)建Parser的時(shí)候指定，可以是single_input, file_input, eval_input中的一個(gè)。

關(guān)于Python語(yǔ)法規(guī)則中的DFA的內(nèi)容是什么就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。