Shulou(Shulou.com)06/02 Report--

This article will explain in detail what is the content of DFA in the grammar rules of Python. The content of the article is of high quality, so the editor will share it with you for reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Grammar.h

DFA (Deterministic Finite Automaton), which includes Python grammar rules, is defined in Graminit.c. For DFA, please refer to the book Compilers: Principles, Techniques, and Tools by Alfred V. Aho et al. To define DFA,graminit.c, some types located in grammar.h are referenced: arc, state, dfa, grammar.

Label defines the symbol corresponding to the edge of the transition from state to another state, which can be a non-Non-Terminal or a Terminal. The Label must be attached to one or more edges. Lb_type represents the type of symbol, such as the Terminator NAME, represents an identifier, or the non-Terminator stmt, represents a statement, and so on.

Lb_str represents the content of a specific symbol. For example, label (NAME, "if") means that when a parser is in one state, if the marker 'if'' is encountered, it moves another state. If label is a non-Terminator, the situation is more complicated, and you need to jump to another DFA corresponding to that non-Terminator, see the compiler related books.

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

In Graminit.c, arc represents the arc / edge from one state in DFA to another in DFA, which includes Python syntax rules. A_lbl represents the Label corresponding to arc, while a_arrow records the target state of arc. Because arc belongs to a certain state, there is no need to record the initial state of arc.

/ * An arc from one state to another * / typedef struct {short astatlblr; / * Label of this arc * / short axiarrow; / * State where this arc goes to * /} arc

State represents the state node in DFA. Each state records a collection of edges from that state, which is stored in the s_arc. Other members s_lower, s_upper, s_accel, and s_accept record the Accelerator corresponding to state, which will be described later. Note that the Accelerator information is not defined in the graminit.c, but is calculated at run time.

/ * A state in a DFA * / typedef struct {int slots; arc * sarcs; / * Array of arcs * / * Optional accelerators * / int swatches; / * Lowest label index * / int swatches; / * Highest label index * / int * slots accel; / * Accelerator * / int slots; / * Nonzero for accepting state * /} state

The starting state d_initial and the set d_state of all states are recorded in the DFA structure. D_first records the firstset of the non-Terminator corresponding to the DFA, that is, when you encounter a Terminator in the firstset, you need to jump to this DFA. D_first will be used later when calculating Accelerators.

/ * A DFA * / typedef struct {int dudes type; / * Non-terminal this represents * / char * dumbname; / * For printing * / http://new.51cto.com/wuyou/int dudes initials; / * Initial state * / int dudes states; state * dstats; / * Array of states * / bitset dudes first;} dfa

Grammar represents the entire syntax of Python, recording all DFA and all label. G_start is the starting symbol of Python syntax, which is usually single_input. However, the actual starting symbol can be specified when the Parser is created, which can be one of single_input, file_input, or eval_input.

On the Python grammar rules of what the DFA content is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.