The parse tree: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: The parse tree

New		Line
1	+	back to contents [[FPC internals]]
2	+
3	+	# The parse tree
4	+
5	+	## Architecture
6	+
7	+	(last updated for fpc version 1.0.x)
8	+
9	+	The tree is the basis of the compiler. When the compiler parses statements and blocks of code, they are converted to a tree representation. This tree representation is actually a doubly linked list. From this tree the code generation can easily be implemented.
10	+
11	+	Assuming that you have the following pascal syntax:
12	+
13	+	`x := x * y + (6 shl x);`
14	+
15	+	The tree structure will be built in memory, where each circle represents an element (a node) in the tree: <http://www.pjh2.de/fpc/CompilerInternalsFigure03.png>
16	+
17	+	## Node types
18	+
19	+	(last updated for fpc version 2.1.1, 2005-06-11)
20	+
21	+	The following tree nodes are possible (of type TNodeTyp):
22	+
23	+	\| Tree type definition \| Description \|
24	+	\|----\|----\|
25	+	\| emptynode \| No node (returns nil when loading from ppu) \|
26	+	\| addn \| Represents the + operator \|
27	+	\| muln \| Represents the * operator \|
28	+	\| subn \| Represents the - operator \|
29	+	\| divn \| Represents the div operator \|
30	+	\| symdifn \| Represents the \>\< operator \|
31	+	\| modn \| Represents the mod operator \|
32	+	\| assignn \| Represents the := operator (assignment) \|
33	+	\| loadn \| Represents the use of a variabele \|
34	+	\| rangen \| Represents a range (i.e. 0..9) \|
35	+	\| ltn \| Represents the \< operator \|
36	+	\| lten \| Represents the \<= operator \|
37	+	\| gtn \| Represents the \> operator \|
38	+	\| gten \| Represents the \>= operator \|
39	+	\| equaln \| Represents the = operator \|
40	+	\| unequaln \| Represents the \<\> operator \|
41	+	\| inn \| Represents the in operator \|
42	+	\| orn \| Represents the or operator \|
43	+	\| xorn \| Represents the xor operator \|
44	+	\| shrn \| Represents the shr operator \|
45	+	\| shln \| Represents the shl operator \|
46	+	\| slashn \| Represents the / operator \|
47	+	\| andn \| Represents the and operator \|
48	+	\| subscriptn \| Represents a field in an object or record \|
49	+	\| derefn \| Represents a pointer reference (such as the ^ operator) \|
50	+	\| addrn \| Represents the @ operator \|
51	+	\| ordconstn \| Represents an ordinal constant \|
52	+	\| typeconvn \| Represents a typecast / type conversion \|
53	+	\| calln \| Represents a routine call \|
54	+	\| callparan \| Represents a parameter passed to a routine \|
55	+	\| realconstn \| Represents a floating point constant \|
56	+	\| unaryminusn \| Represents a sign change (e.g : -) \|
57	+	\| asmn \| Represents an assembler statement node \|
58	+	\| vecn \| Represents array indexing \|
59	+	\| pointerconstn \| Represents a pointer constant \|
60	+	\| stringconstn \| Represents a string constant \|
61	+	\| notn \| Represents the not operator \|
62	+	\| inlinen \| Represents one of the internal routines (writeln,ord,etc.) \|
63	+	\| niln \| Represents the nil pointer \|
64	+	\| errorn \| Represents error in parsing this node (used for error detection and correction) \|
65	+	\| typen \| Represents a type name (i.e typeof(obj)) \|
66	+	\| setelementn \| Represents set elements (i.e : \[a..b\], \[a,b,c\]) (nonconstant) \|
67	+	\| setconstn \| Represents set element constants i.e : \[1..9\], \[1,2,3\]) \|
68	+	\| blockn \| Represents a block of statements \|
69	+	\| statementn \| One statement in a block of nodes \|
70	+	\| ifn \| Represents an if statement \|
71	+	\| breakn \| Represents a break statement \|
72	+	\| continuen \| Represents a continue statement \|
73	+	\| whilerepeatn \| Represents a while or repeat statement \|
74	+	\| forn \| Represents a for statement \|
75	+	\| exitn \| Represents an exit statement \|
76	+	\| withn \| Represents a with statement \|
77	+	\| casen \| Represents a case statement \|
78	+	\| labeln \| Represents a label statement \|
79	+	\| goton \| Represents a goto statement \|
80	+	\| tryexceptn \| Represents a try..except statement \|
81	+	\| raisen \| Represents a raise statement \|
82	+	\| tryfinallyn \| Represents a try..finally statement \|
83	+	\| onn \| Represents an on..do statement (in exception code) \|
84	+	\| isn \| Represents the is operator \|
85	+	\| asn \| Represents the as typecast operator \|
86	+	\| caretn \| Represents the ^ operator \|
87	+	\| starstarn \| Represents the ** operator (exponentiation) \|
88	+	\| arrayconstructorn \| Represents a construction node for \[...\] parsing \|
89	+	\| arrayconstructorrangen \| Range element to allow sets in array construction tree \|
90	+	\| tempcreaten \| for temps in the result/firstpass \|
91	+	\| temprefn \| references to temps \|
92	+	\| tempdeleten \| for temps in the result/firstpass \|
93	+	\| addoptn \| added for optimizations where we cannot suppress \|
94	+	\| nothingn \| NOP, Do nothing \|
95	+	\| loadvmtaddrn \| Load the address of the VMT of a class/object \|
96	+	\| guidconstn \| A GUID COM Interface constant \|
97	+	\| rttin \| Rtti information so they can be accessed in result/firstpass \|
98	+	\| loadparentfpn \| Load the framepointer of the parent for nested procedures \|
99	+
100	+	## Node structure fields (node.pas)
101	+
102	+	(last updated for fpc version 2.1.1, 2005-06-11)
103	+
104	+	``` pascal
105	+	type
106	+	TNode = class
107	+	public
108	+	NodeType: TNodeType; // type of this node
109	+	BlockType: TBlock_Type; // type of the current code block, general/const/type
110	+	ExpectLoc: TCGLoc; // expected location of the result of this node (pass1)
111	+	Location: TLocation; // the location of the result of this node (pass2)
112	+	Parent: TNode; // the parent node of this is node
113	+	// this field is set by concattolist
114	+	Flags: TNodeFlags; // there are some properties about the node stored
115	+	PpuIdx: Longint;
116	+	RegistersInt, // the number of registers needed to evalute the node
117	+	RegistersFpu,
118	+	RegistersMm: Longint; // must be longint !!!!
119	+	{$ifdef SUPPORT_MMX}
120	+	RegistersMmx: Longint;
121	+	{$endif SUPPORT_MMX}
122	+	ResultType: TType;
123	+	FileInfo: TFilePosInfo;
124	+	LocalSwitches: TLocalSwitches;
125	+	{$ifdef extdebug}
126	+	MaxFirstPassCount,
127	+	FirstPassCount: Longint;
128	+	{$endif extdebug}
129	+	end;
130	+	```
131	+
132	+	### TNodeFlag
133	+
134	+	(last updated for fpc version 2.1.1, 2005-06-11)
135	+
136	+	\| TNodeType \| \| Description \|
137	+	\|----\|----\|----\|
138	+	\| nf_swapable \| TBinOp \| operands can be swapped \|
139	+	\| nf_swaped \| TBinOp \| operands are swapped \|
140	+	\| nf_error \| \| Set to TRUE if there was an error parsing this node \|
141	+	\| nf_pass1_done \| general \| \|
142	+	\| nf_write \| general \| Node is written to \|
143	+	\| nf_isproperty \| general \| TRUE if this is a property \|
144	+	\| nf_typedaddr \| TAddrNode \| \|
145	+	\| nf_no_checkpointer \| TDerefNode \| \|
146	+	\| nf_memindex \| TVecNode \| \|
147	+	\| nf_memseg \| TVecNode \| \|
148	+	\| nf_callunique \| TVecNode \| \|
149	+	\| nf_absolute \| TLoadNode \| \|
150	+	\| nf_is_self \| TLoadNode \| \|
151	+	\| nf_load_self_pointer \| TLoadNode \| \|
152	+	\| nf_is_currency \| TAddNode \| \|
153	+	\| nf_has_pointerdiv \| TAddNode \| \|
154	+	\| nf_concat_string \| TAssignmentNode \| \|
155	+	\| nf_use_strconcat \| TAssignmentNode \| \|
156	+	\| nf_forcevaria \| TArrayConstructNode \| \|
157	+	\| nf_novariaallowed \| TArrayConstructNode \| \|
158	+	\| nf_explicit \| TTypeConvNode \| \|
159	+	\| nf_internal \| TTypeConvNode \| no warnings/hints generated \|
160	+	\| nf_load_procvar \| TTypeConvNode \| \|
161	+	\| nf_inlineconst \| TInlineNode \| \|
162	+	\| nf_get_asm_position \| TAsmNode \| \|
163	+	\| nf_block_with_exit \| TBlockNode \| \|
164	+
165	+	### TLocalSwitches
166	+
167	+	(last updated for fpc version 2.1.1, 2005-06-11)
168	+
169	+	Gébnération de code
170	+
171	+	\| TLocalSwitches \| Commutateur \| Paramètre \| Description \|
172	+	\|----\|----\|----\|----\|
173	+	\| cs_check_overflow \| {\$Q+} \| -Co \| Le générateur de code devrait émettre du code de contrôle de dépassement \|
174	+	\| cs_check_range \| {\$R+} \| -Cr, -CR \| Code generator should emit range checking code \|
175	+	\| cs_check_object \| \| -CR \| Code generator should emit code to verify object method call validity \|
176	+	\| cs_check_io \| {\$I+} \| -Ci \| Code generator should emit I/O checking code \|
177	+	\| cs_check_stack \| {\$S+} \| -Ct \| Code generator should emit stack checking code \|
178	+	\| cs_checkpointer \| \| -gc \| Code generator should emit pointer checking code \|
179	+	\| cs_omitstackframe \| N/A \| \| Code generator should not emit frame_pointer setup code in entry code (don't used in the compiler) \|
180	+	\| cs_do_assertion \| {\$C+} \| -Sa \| Code generator supports using the assert inline routine \|
181	+	\| cs_generate_rtti \| {\$M+} \| \| Code generator should emit runtime type information \|
182	+	\| cs_full_boolean_eval \| {\$B+} \| \| Boolean evalution mode \|
183	+	\| cs_typed_const_writable \| {\$J+} \| \| *todo* \|
184	+	\| cs_allow_enum_calc \| \| \| *todo* \|
185	+
186	+	MMX
187	+
188	+	\| TLocalSwitches \| Switch \| Param \| Description \|
189	+	\|----\|----\|----\|----\|
190	+	\| cs_mmx \| {\$MMX+} \| \| Code generator can use MMX commands \|
191	+	\| cs_mmx_saturation \| {\$SATURATION+} \| \| Code generator can use saturated operations (MMX) \|
192	+
193	+	Parser
194	+
195	+	\| TLocalSwitches \| Switch \| Param \| Description \|
196	+	\|----\|----\|----\|----\|
197	+	\| cs_typed_addresses \| {\$T+} \| \| Parser emits typed pointer using the @ operator \|
198	+	\| cs_strict_var_strings \| {\$V+} \| \| String types must be identical (same length) to be compatible \|
199	+	\| cs_ansistrings \| {\$H+} \| -Sh \| Parser creates an ansistring when an unspecified String type is declared instead of the default ShortString \|
200	+
201	+	MACPAS specific
202	+
203	+	\| TLocalSwitches \| Switch \| Param \| Description \|
204	+	\|-----------------------\|--------\|-------\|-------------\|
205	+	\| cs_external_var \| {\$J+} \| \| *todo* \|
206	+	\| cs_externally_visible \| {\$Z+} \| \| *todo* \|
207	+
208	+	### Additional fields
209	+
210	+	(last updated for fpc version 1.0.x)
211	+
212	+	Depending on the tree type, some additional fields may be present in the tree node. This section describes these additional fields. Before accessing these additional fields, a check on the treetype should always be done to verify if not reading invalid memory ranges.
213	+
214	+	#### AddN
215	+
216	+	\| Field \| Description \|
217	+	\|----\|----\|
218	+	\| Use_StrConcat: Boolean; \| Currently unused (use for optimizations in future versions) \|
219	+	\| String_Typ: TStringType; \| In the case where the + operator is applied on a string, this field indicates the string type. \|
220	+
221	+	#### CallParaN
222	+
223	+	\| Field \| Description \|
224	+	\|----\|----\|
225	+	\| Is_Colon_Para : Boolean; \| Used for internal routines which can use optional format parameters (using colons). Is set to TRUE if this parameter was preceded by a colon (i.e : :1) \|
226	+	\| Exact_Match_Found : Boolean; \| Set to TRUE if the parameter type is exactly the same as the one expected by the routine. \|
227	+	\| ConvLevel1Found : Boolean; \| Set to TRUE if the parameter type requires a level 1 type conversion to conform to the parameter expected by the routine. \|
228	+	\| ConvLevel2Found : Boolean; \| Set to TRUE if the parameter type requires a level 2 type conversion to conform to the parameter expected by the routine. \|
229	+	\| HighTree : pTree; \| \|
230	+
231	+	#### AssignN
232	+
233	+	\| Field \| Description \|
234	+	\|----\|----\|
235	+	\| AssignTyp: TAssignTyp; \| Currently unused (Used to be used for C-like assigns) \|
236	+	\| Concat_String: Boolean; \| Currently unused (use for optimizations in future versions) \|
237	+
238	+	#### LoadN
239	+
240	+	\| Field \| Description \|
241	+	\|----\|----\|
242	+	\| SymTableEntry: PSym; \| Symbol table entry for this symbol \|
243	+	\| SymTable: PSymTable; \| Symbol table in which this symbol is stored \|
244	+	\| Is_Absolute: Boolean; \| set to TRUE if this variable is absolute \|
245	+	\| Is_First: Boolean; \| set to TRUE if this is the first occurrence of the load for this variable (used with the varstate variable for optimizations) \|
246	+
247	+	#### CallN
248	+
249	+	\| Field \| Description \|
250	+	\|----\|----\|
251	+	\| SymTableProcEntry: PProcSym; \| Symbol table entry for this routine \|
252	+	\| SymTableProc: PSymTable; \| Symbol table associated with a call (object symbol table or routine symbol table) \|
253	+	\| ProcDefinition: pAbstractProcDef; \| Type definition for this routine \|
254	+	\| MethodPointer: pTree; \| ????????? \|
255	+	\| No_Check: Boolean; \| Currently unused \|
256	+	\| Unit_Specific: Boolean; \| set to TRUE if the routine is imported in a unit specific way (for example: system.writeln()) \|
257	+	\| Return_Value_Used : Boolean \| set to TRUE if the routine is a function and that the return value is not used (in extended syntax parsing - \$X+) \|
258	+	\| Static_Call: Boolean; \| unused \|
259	+
260	+	#### addrn
261	+
262	+	\| Field \| Description \|
263	+	\|-----------------------\|---------------------------------------------------\|
264	+	\| ProcVarLoad: Boolean; \| Set to TRUE if this is a procedural variable call \|
265	+
266	+	#### OrdConstN
267	+
268	+	\| Field \| Description \|
269	+	\|-----------------\|-----------------------------------------\|
270	+	\| Value: LongInt; \| The numeric value of this constant node \|
271	+
272	+	#### RealConstN
273	+
274	+	\| Field \| Description \|
275	+	\|------------------------\|------------------------------------------------\|
276	+	\| Value_Real: Best_Real; \| The numeric value of this constant node \|
277	+	\| Lab_Real: PAsmLabel; \| The assembler label reference to this constant \|
278	+
279	+	#### FixConstN
280	+
281	+	\| Field \| Description \|
282	+	\|---------------------\|-----------------------------------------\|
283	+	\| Value_Fix: LongInt; \| The numeric value of this constant node \|
284	+
285	+	#### FuncRetN
286	+
287	+	\| Field \| Description \|
288	+	\|----\|----\|
289	+	\| FuncRetProcInfo: Pointer; (PProcInfo) \| Pointer to procedure information \|
290	+	\| RetType: TType; \| Indicates the return type of the function \|
291	+	\| Is_First_FuncRet: Boolean; \| \|
292	+
293	+	#### SubscriptN
294	+
295	+	\| Field \| Description \|
296	+	\|----\|----\|
297	+	\| vs: pVarSym; \| Symbol table entry for this variable (a field of object/class/record) \|
298	+
299	+	#### RaiseN
300	+
301	+	\| Field \| Description \|
302	+	\|-------------------\|------------------------------------------------\|
303	+	\| FrameTree: PTree; \| Exception frame tree (code in Raise statement) \|
304	+
305	+	#### VecN
306	+
307	+	\| Field \| Description \|
308	+	\|----------------------\|---------------------------------------------------\|
309	+	\| MemIndex: Boolean; \| Set to TRUE if Mem\[Seg:Ofs\] directive is parsed \|
310	+	\| MemSeg: Boolean; \| Set to TRUE if Mem\[Seg:Ofs\] directive is parsed \|
311	+	\| CallUnique: Boolean; \| \|
312	+
313	+	#### StringConstN
314	+
315	+	\| Field \| Description \|
316	+	\|----\|----\|
317	+	\| Value_Str: PChar; \| The constant value of the string \|
318	+	\| Length: LongInt; \| Length of the string in bytes (or in characters???) \|
319	+	\| Lab_Str: PAsmLabel; \| The assembler label reference to this constant \|
320	+	\| StringType: TStringType; \| The string type (short, long, ansi, wide) \|
321	+
322	+	#### TypeConvN
323	+
324	+	\| Field \| Description \|
325	+	\|----\|----\|
326	+	\| ConvType: TConvertType; \| Indicates the conversion type to do \|
327	+	\| Explizit: Boolean; \| set to TRUE if this was an explicit conversion (with explicit typecast, or calling one of the internal conversion routines) \|
328	+
329	+	#### TypeN
330	+
331	+	\| Field \| Description \|
332	+	\|------------------------\|-----------------------------------\|
333	+	\| TypeNodeType: PDef; \| The type definition for this node \|
334	+	\| TypeNodeSym: PTypeSym; \| The type symbol information \|
335	+
336	+	#### InlineN
337	+
338	+	\| Field \| Description \|
339	+	\|----\|----\|
340	+	\| InlineNumber: Byte; \| Indicates the internal routine called (Cf. code generator) \|
341	+	\| InlineConst: Boolean; \| One or more of the parameters to this inline routine call contains constant values \|
342	+
343	+	#### ProcInlineN
344	+
345	+	Inline nodes are created when a routine is declared as being inline. The routine is actually inlined when the following conditions are satisfied:
346	+
347	+	It is called within the same module
348	+
349	+	The appropriate compiler switch to support inline is activated
350	+
351	+	It is a non-method routine (a standard procedure or function)
352	+
353	+	Otherwise a normal call is made, ignoring the inline directive. In the case where a routine is inlined, all parameters, return values and local variables of the inlined routine are actually allocated in the stack space of the routine which called the inline routine.
354	+
355	+	\| Field \| Description \|
356	+	\|----\|----\|
357	+	\| InlineTree: PTree; \| The complete tree for this inline procedure \|
358	+	\| InlineProcsym: PProcSym; \| Symbol table entry for this procedure \|
359	+	\| RetOffset: LongInt; \| Return offset in parent routine stack space \|
360	+	\| Para_Offset: LongInt; \| Parameter start offset in parent routine stack space \|
361	+	\| Para_Size: LongInt; \| Parameter size in the parent routine stack space \|
362	+
363	+	#### SetConstN
364	+
365	+	\| Field \| Description \|
366	+	\|-----------------------\|------------------------------------------------\|
367	+	\| Value_Set: PConstSet; \| The numeric value of this constant node \|
368	+	\| Lab_Set: PAsmLabel; \| The assembler label reference to this constant \|
369	+
370	+	#### LoopN
371	+
372	+	\| Field \| Description \|
373	+	\|-------\|-------------\|
374	+	\| \| \|
375	+
376	+	#### AsmN
377	+
378	+	\| Field \| Description \|
379	+	\|----\|----\|
380	+	\| p_Asm: PAasmOutput; \| The instruction tree created by the assembler parser \|
381	+	\| Object_Preserved: Boolean; \| set to FALSE if the Self_Register was modified in the asm statement. \|
382	+
383	+	#### CaseN
384	+
385	+	\| Field \| Description \|
386	+	\|----\|----\|
387	+	\| Nodes: PCaseRecord; \| Tree for each of the possible case in the case statement \|
388	+	\| ElseBlock: PTree; \| Else statement block tree \|
389	+
390	+	#### LabelN, GotoN
391	+
392	+	\| Field \| Description \|
393	+	\|------------------------\|------------------------------------------------\|
394	+	\| LabelNr: PAsmLabel; \| Assembler label associated with this statement \|
395	+	\| ExceptionBlock: PTree; \| ? \|
396	+	\| LabSym: PLabelSym; \| Symbol table entry for this label \|
397	+
398	+	#### WithN
399	+
400	+	\| Field \| Description \|
401	+	\|-------------------------------\|-------------\|
402	+	\| WithSymTables: PWithSymTable; \| \|
403	+	\| TableCount: LongInt; \| \|
404	+	\| WithReference: PReference; \| \|
405	+	\| IsLocal: Boolean; \| \|
406	+
407	+	#### OnN
408	+
409	+	\| Field \| Description \|
410	+	\|----------------------------\|-------------\|
411	+	\| ExceptSymTable: PSymTable; \| \|
412	+	\| ExceptType: PObjectDef; \| \|
413	+
414	+	#### ArrayConstructorN
415	+
416	+	\| Field \| Description \|
417	+	\|--------------------------\|-------------\|
418	+	\| CArgs: Boolean; \| \|
419	+	\| CArgSwap: Boolean; \| \|
420	+	\| ForceVaria: Boolean; \| \|
421	+	\| NoVariaAllowed: Boolean; \| \|
422	+	\| ConstructorDef: PDef; \| \|
423	+
424	+	Next chapter: [[Symbol tables]]
425	+
426	+	---
427	+	From the Free Pascal wiki, page "The parse tree", as it stood on 2020-12-19 after a change by Trev, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).
428	+	Category: FPC internals

Back to history