Plex and Pyacc: what changed

Revision 2 to 3. Removed lines have a minus sign; added lines have a plus sign.

Old	New		Line
1	1		Free Pascal comes with substitutes for the GNU projects Lex and YACC. They are called Plex and Pyacc and they can be used to generate compilers and regular expression analyzers in Pascal instead of C.
2	2
3	3		## Library contents
4	4
5	5		TP Lex and Yacc can be found here: <http://svn.freepascal.org/cgi-bin/viewvc.cgi/trunk/utils/tply/>
6	6
7	7		## Documentation
8	8
9	9		Download the manual here: <http://svn.freepascal.org/cgi-bin/viewvc.cgi/trunk/utils/tply/tply.doc?revision=1>
10	10
11	11		## Simple example application
12	12
13	13		This is a very simple calculator, which shows how to use plex and pyacc. The files in this simple project are:
14	14
15	15		- build.sh
16	16		- lexer.l
17	17		- parser.y
18	18
19	19		WARNING: The code below compiles but currently doesn't work \<-- Because it is simply wrong. See below and learn why !
20	20
21	21		### build.sh
22	22
23	23		``` pascal
24	24		plex lexer.l
25	25		pyacc -d parser.y
26	26		mv parser.pas calculadora.pas
27	27		fpc calculadora.pas
28	28		```
29	29
30	30		### lexer.l
31	31
32	32		``` pascal
33	33		{ Analisador léxico da calculadora para a disciplina de PCS
34	34
35	35		Aluno: Felipe Monteiro de Carvalho }
36	36
37	37		%{
38	38		%}
39	39		%%
40	40
41	41		[0-9]+[dD]? begin yylval.yyInteger := StrToInt(yytext); yyruleno := NUMBER; end;
42	42
43	43		[0-9a-fA-F]+[hH] begin yylval.yyInteger := StrToInt(yytext); yyruleno := NUMBER; end;
44	44
45	45		[ \t] begin end; { ignorar espaços em branco }
46	46
47	47		[-] begin yyruleno := MENOS; end;
48	48
49	49		[+*/()] begin yyruleno := Integer(yytext[0]); end;
50	50
51	51		[=][hH] begin yyruleno := IGUALH; end;
52	52
53	53		[=][dD]? begin yyruleno := IGUALD; end;
54	54
55	55		\n begin yyruleno := Integer(yytext[0]); end;
56	56
57	57		. begin yyerror('Caracter inexperado'); end;
58	58
59	59		%%
60	60		function meuyywrap (): Integer;
61	61		begin
62	62		Result := 1;
63	63		end;
64	64		```
65	65
66	66		### parser.y
67	67
68	68		``` pascal
69	69		/* Parser
70	70
71	71		Aluno: Felipe Monteiro de Carvalho */
72	72		%{
73	73		program calculadora;
74	74
75	75		{$mode delphi}
76	76
77	77		uses SysUtils, yacclib, lexlib;
78	78
79	79		%}
80	80
81	81		%start entrada
82	82		%token <Integer> NUMBER IGUALD IGUALH MENOS
83	83		%type <Integer> expressao termo fator
84	84
85	85		%%
86	86
87	87		entrada
88	88		: /* linha vazia */ { }
89	89		\| entrada linha { }
90	90		;
91	91		linha
92	92		: expressao IGUALD '\n' { WriteLn(Format('Resultado: %d', [$1])); }
93	93		\| expressao IGUALH '\n' { WriteLn(Format('Resultado: %H', [$1])); }
94	94		;
95	95		expressao
96	96		: expressao '+' termo { $$ := $1 + $3; }
97	97		\| expressao MENOS termo { $$ := $1 - $3; }
98	98		\| termo { $$ := $1; }
99	99		;
100	100		termo
101	101		: termo '' fator { $$ := $1 $3; }
102	102		\| termo '/' fator { if ($3 = 0) then
103	103		yyerror('Divisao por zero!')
104	104		else
105	105		$$ := $1 div $3; }
106	106		\| fator { $$ := $1; }
107	107		;
108	108		fator
109	109		: NUMBER { $$ := $1; }
110	110		\| MENOS NUMBER { $$ := -1 * $2; }
111	111		\| '(' expressao ')' { $$ := $2; }
112	112		;
113	113
114	114		%%
115	115
116	116		procedure meuyyerror(s: PChar); // Called by yyparse on error
117	117		begin
118	118		WriteLn(Format('Erro: %s', [s]));
119	119		end;
120	120
121	121		{$include lexer.pas}
122	122
123	123		begin
124	124		yywrap := @meuyywrap;
125	125		// yyerror := @meuyyerror;
126	126		yyparse ();
127	127		end.
128	128		```
129	129
130	130		### How to use it
131	131
132	132		Type for example: 5+3=
133	133
134	134		And it will answer with: 8
135	135
136	136		You can also try 3*8=H to request an answer in Hexadecimal instead of decimal
137	137
138	138		# How to do it the right way
139	139
140	140		Sorry that I have to do this, but this example is wrong !
141	141
142	142		First of all I recommend you to read the manual and try to understand it.\
143	143		Secondly take a look at the examples provided with original tply package by Albert Graef distributed at: <http://www.musikwissenschaft.uni-mainz.de/~ag/tply>\
144	144		There you will find a more sophisticated calculator example named 'expr'. If you take a look at it you will find out that this is a basic example for Lex/Yacc generated parsers and it works.\
145	145
146		-	~~`Now I will explain you why you can NOT do things that way !`~~
	146	+	```text
	147	+	Now I will explain you why you can NOT do things that way !
	148	+	```
147	149
148	150		We start with Lex:\
149	151		\# Lex returns a token to the parser which is always an integer value. The token is defined as an constant value with the %token command. Tokens can only be returned to Yacc through two commands, return and returnc.
150	152
151	153		1. 1. return : This is the normal return of a token = integer
152	154		2. returnc: With this it is possible to return one character, it is needed for the literals in Yacc rules
153	155
154	156		Now we correct the return of a token from example above:
155	157
156	158		``` pascal
157	159		[0-9]+[dD]? begin yylval.yyInteger := StrToInt(yytext); yyruleno := NUMBER; end; <- nothing, because yyruleno ends up in nirvana
158	160		[0-9]+[dD]? begin yylval.yyInteger := StrToInt(yytext); return(NUMBER); end; <- good
159	161		```
160	162
161	163		And the litteral return :
162	164
163	165		``` pascal
164	166		[+*/()] begin yyruleno := Integer(yytext[0]); end; <- ouch !
165	167		[+*/()] returnc(yytext[1]); <- returns single characters we want
166	168		```
167	169
168	170		Can you see the difference ?\
169	171		Why the hell one should use index NULL ? And no need for begins and ends.\
170	172		Last but not least the strange function:
171	173
172	174		``` pascal
173	175		function meuyywrap (): Integer; <- ??? what is this for ??? this no overload for yywrap !
174	176		begin
175	177		Result := 1;
176	178		end;
177	179		```
178	180
179	181		The yywrap function is for loading multiple files, do we need this if we read from stdin and write to stdout ? No, we don't !\
180	182
181	183		The working Lex file:
182	184
183	185		``` pascal
184	186		{ Analisador léxico da calculadora para a disciplina de PCS
185	187
186	188		Aluno: Felipe Monteiro de Carvalho }
187	189
188	190		%{
189	191		%}
190	192		%%
191	193
192	194		[0-9]+[dD]? begin yylval.yyInteger := StrToInt(yytext); return(NUMBER); end;
193	195
194	196		[0-9a-fA-F]+[hH] begin yylval.yyInteger := StrToInt(yytext); return(NUMBER); end;
195	197
196	198		[ \t] ; { ignorar espaços em branco }
197	199
198	200		[-] return(MENOS);
199	201
200	202		[+*/()] returnc(yytext[1]);
201	203
202	204		[=][hH] return(IGUALH);
203	205
204	206		[=][dD]? return(IGUALD);
205	207
206	208		\n returnc(yytext[1]);
207	209
208	210		. yyerror('Caracter inexperado');
209	211
210	212		%%
211	213		```
212	214
213	215		Now we go on with Yacc:\
214	216		The main block:\
215	217		If we want to read a file we have to assign and open it before we can parse it. If we want to read more files we have to use yywrap.\
216	218		With a parser like this we need only stdio. So we need to do nothing because Lex assigns and opens the 'files' known as stdin and stdout.\
217	219		With this we can forget all but the yyparse() call.\
218	220
219	221		Additional functionality:\
220	222		As a feature we want to write user defined error messages. For this we simply overload the yyerror procedure.\
221	223
222	224		The working Yacc file:
223	225
224	226		``` pascal
225	227		/* Parser
226	228
227	229		Aluno: Felipe Monteiro de Carvalho */
228	230		%{
229	231		program calculadora;
230	232
231	233		{$mode delphi}
232	234
233	235		uses SysUtils, yacclib, lexlib;
234	236
235	237		procedure yyerror(s: string); // Called by yyparse on error <- overload !
236	238		begin
237	239		WriteLn(Format('Erro: %s', [s]));
238	240		end;
239	241
240	242		%}
241	243
242	244		%start entrada
243	245		%token <Integer> NUMBER IGUALD IGUALH MENOS
244	246		%type <Integer> expressao termo fator
245	247
246	248		%%
247	249
248	250		entrada
249	251		: /* linha vazia */ { }
250	252		\| entrada linha { }
251	253		\| entrada linha '\n' { writeln('DONE.'); yyaccept; } /* <- nice end with RETURN */
252	254		;
253	255		linha
254	256		: expressao IGUALD '\n' { WriteLn(Format('Resultado: %d', [$1])); }
255	257		\| expressao IGUALH '\n' { WriteLn(Format('Resultado: %Xh', [$1])); } /* <- hex = X , add 'h' to identify this result as a hex number */
256	258		;
257	259		expressao
258	260		: expressao '+' termo { $$ := $1 + $3; }
259	261		\| expressao MENOS termo { $$ := $1 - $3; }
260	262		\| termo { $$ := $1; }
261	263		;
262	264		termo
263	265		: termo '' fator { $$ := $1 $3; }
264	266		\| termo '/' fator { if ($3 = 0) then
265	267		yyerror('Divisao por zero!')
266	268		else
267	269		$$ := $1 div $3; }
268	270		\| fator { $$ := $1; }
269	271		;
270	272		fator
271	273		: NUMBER { $$ := $1; }
272	274		\| MENOS NUMBER { $$ := -1 * $2; }
273	275		\| '(' expressao ')' { $$ := $2; }
274	276		;
275	277
276	278		%%
277	279
278	280
279	281		{$include lexer.pas}
280	282
281	283		begin
282	284		yyparse ();
283	285		end.
284	286		```
285	287
286	288		Hint: One does not need to type tokens as done in this example as the default yylval is always integer. If you do type tokens pyacc will generate a corresponding YYStype for you.\
287	289		WOW. The calculator works as expected !\
288	290		GVS 00:09, 9 March 2014 (CET)\
289	291		=Additional Information= If you are a beginner you may have more questions than answers after reading the above. Thus I will try to show you things to make live easier.\
290	292		We start with Lex and its regular expressions. I don't explain how to build them, read the documentation to find this out.\
291	293		I will try explain some implementation details.\
292	294
293	295		A lexer can use multiple rules that start with the same character or set of characters. This is not recommended because it can cause a problem. The main problem is that the lexer uses the rule with the longest match and returns that token. Now if you return different tokens with these rules you may not be able to match the yacc rule you expected. This is the common error if you write wrong lex rules and wonder why yacc returns syntax errors. If you use such rules in a way they can be identified correctly this can be a benefit. But with such rules you should take care if you need the 'loop' as in (a\\|b)* which can consist of a unknown number of 'a' or 'b' or even be empty. This is not a good start or end for your rule if the 'constant' characters do not cause a significant match.\
294	296		One common use is the detection of numbers where you have two rules, one for integers and one for reals. The rule for integer is then the beginning of the rule for real and there is no problem. There is also no problem if these rules return the same token. Then the only question is if you can find a better rule that includes both single rules in one rule.\
295	297		Example: Integer and Real numbers without sign
296	298
297	299		``` pascal
298	300		[0-9]+ ReturnVerb(INUM,1)
299	301		'.'[0-9]+ ReturnVerb(RNUM,2)
300	302		[0-9]+"."[0-9]+ ReturnVerb(RNUM,3)
301	303		```
302	304
303	305		Now you ask: Why should I parse numbers without sign ? This is a yacc problem, because the sign can be in an expression as a operator e.g. 'a+b' or as a prefix sign e.g. '-1'. Then you may have a token defined for MINUS and you don't need to know if the sign is a prefix sign or an operator, the yacc rules will handle it.\
304	306		Taking a look to the code you will see that I returned the token via the 'ReturnVerb' procedure. This is for debugging the lexer to see the token at the time it is matched. The procedure writes the token number and rule index and then calls the normal return procedure. This is useful because I see the token and the text representation of the matching rule. The text can be read from yytext which is always the current match.\
305	307		One issue you should keep in mind: The lexer is a function that is called from the parser and the token is returned at the point of time the function exits. The parser uses yylval only if he needs this value and one can not find out at which time this will be. The only valid way to return a value to your parser is to use yylval AND to set this value right before the call of return or returnc, otherwise the value is lost or you run into trouble. For details see below at the returnc explanation.\
306	308
307	309		You can combine rules with predefined rule parts standing before the rule part in your file. This makes it easier to write longer rules and you can use them in multiple rules.\
308	310		Example: Rules consisting of predefined parts
309	311
310	312		``` pascal
311	313		L [A-Za-z]
312	314		D [0-9]
313	315
314	316		%%
315	317
316	318		{D}+(\.{D}+)?([Ee][+-]?{D}+)? return(RNUM);
317	319
318	320		{L} return(CH);
319	321
320	322		" " ;
321	323
322	324		. \|
323	325		\n returnc(yytext[1]);
324	326		```
325	327
326	328		One important thing you can see in this example is that one always has to catch all characters of input. Even if you don't need them like the SPACE. Typically in programming languages the so called WHITE SPACE is ignored at all. This is the most difficult thing to match all the unused characters to empty rules without breaking the rules for tokens (difficult because they do not appear in your output where wrong parsed and returned tokens can be found, things you don't see are hard to find). Empty rules do not call return or returnc. If you can not find a rule you can use built in functions to to read the characters yourself or write additional characters to input. This is commonly used with comments. After a initial match of a short rule to match the start of a comment the input is read until the end of the comment or EOF is found.\
327	329		Example: Line Comment
328	330
329		-	~~`%{`\~~
330		-	~~`procedure CommentEOL;`\~~
331		-	~~` var c:char;`\~~
332		-	~~`begin`\~~
333		-	~~` c:= get_char;`\~~
334		-	~~` while (c <> #0)and(c <> #10) do c:= get_char;`\~~
335		-	~~`end; `\~~
336		-	~~`%}`\~~
337		-	~~`"//" CommentEOL;`~~
	331	+	``` pascal
	332	+	%{
	333	+	procedure CommentEOL;
	334	+	var c:char;
	335	+	begin
	336	+	c:= get_char;
	337	+	while (c <> #0)and(c <> #10) do c:= get_char;
	338	+	end;
	339	+	%}
	340	+	"//" CommentEOL;
	341	+	```
338	342
339	343		With this all the characters the get_char function reads from input are lost. If one is reading a multi line comment the ending maker may have to be written back. This is done with unget_char. This characters can than be read in next call of yylex to be evaluated.\
340	344		Example: A language with '/' as an ID, '//' as a unused sequence until EOL or \#26
341	345
342	346		``` pascal
343	347		"/" begin
344	348		c := get_char;
345	349		if c <> '/' then
346	350		begin
347	351		unget_char(c);
348	352		ReturnC(yytext[1]);
349	353		end
350	354		else
351	355		begin (* line comment *)
352	356		while ((c<>#10)and(c<>#13)and(c<>#26)) do c := get_char;
353	357		if c=#26 then unget_char(c);
354	358		end;
355	359		end;
356	360		```
357	361
358	362		Lets talk about returnc.\
359	363		As I said above (at the correction part) that tokens are always integer but returnc gets an character as an argument you might say that is not true. But it is, returnc uses ORD to convert the character to integer. Now you will understand why your token constants (have you look at yacc generated pasacl code) are always higher than 256; its the full ASCII range for litteral tokens so other tokens are higher.\
360	364		If you use returnc you can deal with literals in yacc rules but you have to make sure to return ALL the characters you use in yacc. Yacc does not care about not returned characters and your rules will never match.\
361	365
362	366		The short way to debug lex is to overload the return procedures.\
363	367		Example: Overload lex return
364	368
365	369		``` pascal
366	370		procedure return ( n : Integer );
367	371		begin
368	372		writeln('return >',yytext,'< = ',n);
369	373		(* now do the 'inherited' code return would do *)
370	374		yyretval := n;
371	375		yydone := true;
372	376		end(return);
373	377
374	378		procedure returnc ( c : Char );
375	379		begin
376	380		writeln('returnc >',yytext,'< c = ',c,' , n = ',ord(c));
377	381		(* now do the 'inherited' code returnc would do *)
378	382		yyretval := ord(c);
379	383		yydone := true;
380	384		end(returnc);
381	385		```
382	386
383	387		The result of this is shown next for calculating 4*5 as a hex value with the calculator above:
384	388
385	389		``` pascal
386	390		4*5=h
387	391		return >4< = 257
388	392		returnc >< c = , n = 42
389	393		return >5< = 257
390	394		return >=h< = 259
391	395		returnc >
392	396		< c =
393	397		, n = 10
394	398		Resultado: 14h
395	399		```
396	400
397	401		Remark: You see the NEWLINE from input causing the same on output (n = 10).\
398	402
399	403		Now its time for Yacc.\
400	404
401	405		Benefits of literals in rules are that you can use them with less trouble. Another thing is that the rules are more readable. The trouble with non literal tokens is that you easily generate conflicts in yacc rules. This is a problem with tokens that appear very often in your rules and thus the parser has to do different things with them. It is always a good idea to write rules in such a way that their beginning is significant. If you can not write such rules you might have to change your lexer.\
402	406		Using EMPTY with rules cause trouble too if you use them in combination with loops. In loops you can have only one rule that produces empty. The other rules have to have a significant beginning/ending or part (this needs to be unique in this loop of rules). It is also a problem if you have different rules that end with the same token and the loop separator is this token. Then the parser can not decide what to do if this token is found. Typically the use of SEMICOLON can cause this in a pascal parser (semicolons are not always allowed or close different rules that are not significant itself).\
403	407		Example: FPC Parser snippet to parse CLASS\
404	408
405	409		``` pascal
406	410		Class_Typed_Type : _CLASSFORWARD /* 'Class ;' */
407	411		\| LClass_PRE _OF { LDisable(co_Class); } id
408	412		/* Class Type */
409	413		\| LClass_PRE Class_Component_List { LDisable(co_Class); }
410	414		\| LClass_PRE '(' Class_Implemented_Interface ')'
411	415		Class_Component_List { LDisable(co_Class); }
412	416		;
413	417		LClass_PRE : _CLASS { LEnable(co_Class); } ;
414	418		Class_Implemented_Interface :
415	419		id
416	420		\| id ',' Class_Interface_Identifiers
417	421		;
418	422		Class_Interface_Identifiers : Y_Id_Comma_List ;
419	423		Class_Component_List : OPT_Class_Components _END ;
420	424		OPT_Class_Components :
421	425		/* EMPTY */
422	426		\| Class_Component_LOOP
423	427		;
424	428		Class_Component_LOOP : /* LOOP */
425	429		Class_Component
426	430		\| Class_Component_LOOP Class_Component
427	431		;
428	432		Class_Component :
429	433		Class_Visibility_Specifier
430	434		\| Class_Field_Definition
431	435		\| Class_Method_Definition { LClassModifiers(false); }
432	436		\| Class_Property_Definition
433	437		;
434	438		Class_Visibility_Specifier : /* 'private' \| 'public' \| 'published' \| 'protected' \| 'strict' 'private' ; */
435	439		CVI_PRIVATE
436	440		\| CVI_PROTECTED
437	441		\| NKW_PUBLIC
438	442		\| CVI_PUBLISHED
439	443		\| CVI_STRICT CVI_PRIVATE
440	444		;
441	445
442	446		Class_Field_Definition : /* all decl starting with id as a field */
443	447		/* Const
444	448		type */
445	449		Class_Variable_Declaration
446	450		\| Class_ClassVariable_Declaration
447	451		;
448	452		Class_Variable_Declaration :
449	453		Y_Id_Comma_List ':' { LEnable(co_ClassVarStatic); LHints(true); } RClass_Variable_Declaration ;
450	454		RClass_Variable_Declaration :
451	455		Result_Type OPT_Hint ';' OPT_Static { LDisable(co_ClassVarStatic); LHints(false); }
452	456		;
453	457		OPT_Static :
454	458		/* EMTY */
455	459		\| NKW_STATIC ';'
456	460		;
457	461		Class_ClassVariable_Declaration : _CLASS Class_Variable_Declaration ;
458	462		Class_Method_Definition :
459	463		Class_PuF_Definition
460	464		\| Class_CuD_Definition
461	465		\| _CLASS Class_PuF_Definition
462	466		;
463	467
464	468		Class_PuF_Definition : PuF_Definition ;
465	469		Class_CuD_Definition :
466	470		_CONSTRUCTOR PLike_Definition
467	471		\| _DESTRUCTOR PLike_Definition
468	472		;
469	473		```
470	474
471	475		This are context sensitive rules to switch between the different cases CLASS can be used in a class type declaration. The LEnable and LDisable switches the lexer to a different mode. To do this the line 'LClass_PRE : _CLASS { LEnable(co_Class); } ;' is a own rule that has to be completed first to give the lexer time to switch the modes (the next lookahead character of the parser triggers the rule end; the parser has to reduce the rule to get to the next state before the next token is evaluated which we want to switch to a different token).\
472	476		Remark: This example parser switches between different sets of KEYWORDS because not all tokens that are used are real RESERVED words of the language. This means that e.g. 'public' is not a keyword and is only enabled on context as 'NKW_PUBLIC'. The '_CLASSFORWARD' is a typical conflict where the string 'Class ;' terminates with SEMICOLON. Thus the lexer does a lookahead if a semicolon is found behind 'Class' and then returns the token '_CLASSFORWARD' instead of '_CLASS' and the problem is solved.\
473	477
474	478		The rule in between pitfall:\
475	479		Example: Hello in between
476	480
477	481		``` pascal
478	482		rule1 : ID rule2 { writeln($2); }
479	483
480	484		rule2 : ID1 { $$:='Hello'; } ID3 { $$:= $2; }
481	485		```
482	486
483	487		'Hello' can only be assigned with the last statement '{ \$\$:= \$2; }' as yacc generates a new state for the rule in between. The assignment must be at the end of this rule.\
484	488
485	489		Additional explanation to this last two examples:\
486	490		This are different cases ! The first example is for switching the lexer and the second example is for parsers internal value handling to return the right value to the next rule.\
487	491
488	492		# Useful Links
489	493
490	494		[[Make your own compiler, interpreter, parser, or expression analyzer]]
491	495
492	496		GVS 04:48, 9 March 2014 (CET)
493	497
494	498		---
495	499		From the Free Pascal wiki, page "Plex and Pyacc", as it stood on 2020-02-23 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).
496	500		Category: Code
497	501		Category: Compiler design
498	502		Category: Utilities

Back to history