Plex and Pyacc: what changed

Revision 1 to 2. 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	146		`Now I will explain you why you can NOT do things that way !`
147	147
148		-	~~<u>We start with Lex:</u>\~~
	148	+	We start with Lex:\
149	149		\# 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	150
151	151		1. 1. return : This is the normal return of a token = integer
152	152		2. returnc: With this it is possible to return one character, it is needed for the literals in Yacc rules
153	153
154	154		Now we correct the return of a token from example above:
155	155
156	156		``` pascal
157	157		[0-9]+[dD]? begin yylval.yyInteger := StrToInt(yytext); yyruleno := NUMBER; end; <- nothing, because yyruleno ends up in nirvana
158	158		[0-9]+[dD]? begin yylval.yyInteger := StrToInt(yytext); return(NUMBER); end; <- good
159	159		```
160	160
161	161		And the litteral return :
162	162
163	163		``` pascal
164	164		[+*/()] begin yyruleno := Integer(yytext[0]); end; <- ouch !
165	165		[+*/()] returnc(yytext[1]); <- returns single characters we want
166	166		```
167	167
168	168		Can you see the difference ?\
169	169		Why the hell one should use index NULL ? And no need for begins and ends.\
170	170		Last but not least the strange function:
171	171
172	172		``` pascal
173	173		function meuyywrap (): Integer; <- ??? what is this for ??? this no overload for yywrap !
174	174		begin
175	175		Result := 1;
176	176		end;
177	177		```
178	178
179	179		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		-	\
	180	+
181	181		The working Lex file:
182	182
183	183		``` pascal
184	184		{ Analisador léxico da calculadora para a disciplina de PCS
185	185
186	186		Aluno: Felipe Monteiro de Carvalho }
187	187
188	188		%{
189	189		%}
190	190		%%
191	191
192	192		[0-9]+[dD]? begin yylval.yyInteger := StrToInt(yytext); return(NUMBER); end;
193	193
194	194		[0-9a-fA-F]+[hH] begin yylval.yyInteger := StrToInt(yytext); return(NUMBER); end;
195	195
196	196		[ \t] ; { ignorar espaços em branco }
197	197
198	198		[-] return(MENOS);
199	199
200	200		[+*/()] returnc(yytext[1]);
201	201
202	202		[=][hH] return(IGUALH);
203	203
204	204		[=][dD]? return(IGUALD);
205	205
206	206		\n returnc(yytext[1]);
207	207
208	208		. yyerror('Caracter inexperado');
209	209
210	210		%%
211	211		```
212	212
213		-	\
214		-	~~<u>Now we go on with Yacc:</u>\~~
	213	+	Now we go on with Yacc:\
215	214		The main block:\
216	215		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.\
217	216		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.\
218	217		With this we can forget all but the yyparse() call.\
219		-	\
	218	+
220	219		Additional functionality:\
221	220		As a feature we want to write user defined error messages. For this we simply overload the yyerror procedure.\
222		-	\
	221	+
223	222		The working Yacc file:
224	223
225	224		``` pascal
226	225		/* Parser
227	226
228	227		Aluno: Felipe Monteiro de Carvalho */
229	228		%{
230	229		program calculadora;
231	230
232	231		{$mode delphi}
233	232
234	233		uses SysUtils, yacclib, lexlib;
235	234
236	235		procedure yyerror(s: string); // Called by yyparse on error <- overload !
237	236		begin
238	237		WriteLn(Format('Erro: %s', [s]));
239	238		end;
240	239
241	240		%}
242	241
243	242		%start entrada
244	243		%token <Integer> NUMBER IGUALD IGUALH MENOS
245	244		%type <Integer> expressao termo fator
246	245
247	246		%%
248	247
249	248		entrada
250	249		: /* linha vazia */ { }
251	250		\| entrada linha { }
252	251		\| entrada linha '\n' { writeln('DONE.'); yyaccept; } /* <- nice end with RETURN */
253	252		;
254	253		linha
255	254		: expressao IGUALD '\n' { WriteLn(Format('Resultado: %d', [$1])); }
256	255		\| expressao IGUALH '\n' { WriteLn(Format('Resultado: %Xh', [$1])); } /* <- hex = X , add 'h' to identify this result as a hex number */
257	256		;
258	257		expressao
259	258		: expressao '+' termo { $$ := $1 + $3; }
260	259		\| expressao MENOS termo { $$ := $1 - $3; }
261	260		\| termo { $$ := $1; }
262	261		;
263	262		termo
264	263		: termo '' fator { $$ := $1 $3; }
265	264		\| termo '/' fator { if ($3 = 0) then
266	265		yyerror('Divisao por zero!')
267	266		else
268	267		$$ := $1 div $3; }
269	268		\| fator { $$ := $1; }
270	269		;
271	270		fator
272	271		: NUMBER { $$ := $1; }
273	272		\| MENOS NUMBER { $$ := -1 * $2; }
274	273		\| '(' expressao ')' { $$ := $2; }
275	274		;
276	275
277	276		%%
278	277
279	278
280	279		{$include lexer.pas}
281	280
282	281		begin
283	282		yyparse ();
284	283		end.
285	284		```
286	285
287	286		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.\
288	287		WOW. The calculator works as expected !\
289	288		GVS 00:09, 9 March 2014 (CET)\
290	289		=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.\
291	290		We start with Lex and its regular expressions. I don't explain how to build them, read the documentation to find this out.\
292	291		I will try explain some implementation details.\
293		-	\
	292	+
294	293		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.\
295	294		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.\
296	295		Example: Integer and Real numbers without sign
297	296
298	297		``` pascal
299	298		[0-9]+ ReturnVerb(INUM,1)
300	299		'.'[0-9]+ ReturnVerb(RNUM,2)
301	300		[0-9]+"."[0-9]+ ReturnVerb(RNUM,3)
302	301		```
303	302
304	303		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.\
305	304		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.\
306	305		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.\
307		-	\
	306	+
308	307		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.\
309	308		Example: Rules consisting of predefined parts
310	309
311	310		``` pascal
312	311		L [A-Za-z]
313	312		D [0-9]
314	313
315	314		%%
316	315
317	316		{D}+(\.{D}+)?([Ee][+-]?{D}+)? return(RNUM);
318	317
319	318		{L} return(CH);
320	319
321	320		" " ;
322	321
323	322		. \|
324	323		\n returnc(yytext[1]);
325	324		```
326	325
327	326		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.\
328	327		Example: Line Comment
329	328
330	329		`%{`\
331	330		`procedure CommentEOL;`\
332	331		` var c:char;`\
333	332		`begin`\
334	333		` c:= get_char;`\
335	334		` while (c <> #0)and(c <> #10) do c:= get_char;`\
336	335		`end; `\
337	336		`%}`\
338	337		`"//" CommentEOL;`
339	338
340	339		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.\
341	340		Example: A language with '/' as an ID, '//' as a unused sequence until EOL or \#26
342	341
343	342		``` pascal
344	343		"/" begin
345	344		c := get_char;
346	345		if c <> '/' then
347	346		begin
348	347		unget_char(c);
349	348		ReturnC(yytext[1]);
350	349		end
351	350		else
352	351		begin (* line comment *)
353	352		while ((c<>#10)and(c<>#13)and(c<>#26)) do c := get_char;
354	353		if c=#26 then unget_char(c);
355	354		end;
356	355		end;
357	356		```
358	357
359		-	\
360	358		Lets talk about returnc.\
361	359		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.\
362	360		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.\
363		-	\
	361	+
364	362		The short way to debug lex is to overload the return procedures.\
365	363		Example: Overload lex return
366	364
367	365		``` pascal
368	366		procedure return ( n : Integer );
369	367		begin
370	368		writeln('return >',yytext,'< = ',n);
371	369		(* now do the 'inherited' code return would do *)
372	370		yyretval := n;
373	371		yydone := true;
374	372		end(return);
375	373
376	374		procedure returnc ( c : Char );
377	375		begin
378	376		writeln('returnc >',yytext,'< c = ',c,' , n = ',ord(c));
379	377		(* now do the 'inherited' code returnc would do *)
380	378		yyretval := ord(c);
381	379		yydone := true;
382	380		end(returnc);
383	381		```
384	382
385	383		The result of this is shown next for calculating 4*5 as a hex value with the calculator above:
386	384
387	385		``` pascal
388	386		4*5=h
389	387		return >4< = 257
390	388		returnc >< c = , n = 42
391	389		return >5< = 257
392	390		return >=h< = 259
393	391		returnc >
394	392		< c =
395	393		, n = 10
396	394		Resultado: 14h
397	395		```
398	396
399	397		Remark: You see the NEWLINE from input causing the same on output (n = 10).\
400		-	\
	398	+
401	399		Now its time for Yacc.\
402		-	\
	400	+
403	401		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.\
404	402		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).\
405	403		Example: FPC Parser snippet to parse CLASS\
406	404
407	405		``` pascal
408	406		Class_Typed_Type : _CLASSFORWARD /* 'Class ;' */
409	407		\| LClass_PRE _OF { LDisable(co_Class); } id
410	408		/* Class Type */
411	409		\| LClass_PRE Class_Component_List { LDisable(co_Class); }
412	410		\| LClass_PRE '(' Class_Implemented_Interface ')'
413	411		Class_Component_List { LDisable(co_Class); }
414	412		;
415	413		LClass_PRE : _CLASS { LEnable(co_Class); } ;
416	414		Class_Implemented_Interface :
417	415		id
418	416		\| id ',' Class_Interface_Identifiers
419	417		;
420	418		Class_Interface_Identifiers : Y_Id_Comma_List ;
421	419		Class_Component_List : OPT_Class_Components _END ;
422	420		OPT_Class_Components :
423	421		/* EMPTY */
424	422		\| Class_Component_LOOP
425	423		;
426	424		Class_Component_LOOP : /* LOOP */
427	425		Class_Component
428	426		\| Class_Component_LOOP Class_Component
429	427		;
430	428		Class_Component :
431	429		Class_Visibility_Specifier
432	430		\| Class_Field_Definition
433	431		\| Class_Method_Definition { LClassModifiers(false); }
434	432		\| Class_Property_Definition
435	433		;
436	434		Class_Visibility_Specifier : /* 'private' \| 'public' \| 'published' \| 'protected' \| 'strict' 'private' ; */
437	435		CVI_PRIVATE
438	436		\| CVI_PROTECTED
439	437		\| NKW_PUBLIC
440	438		\| CVI_PUBLISHED
441	439		\| CVI_STRICT CVI_PRIVATE
442	440		;
443	441
444	442		Class_Field_Definition : /* all decl starting with id as a field */
445	443		/* Const
446	444		type */
447	445		Class_Variable_Declaration
448	446		\| Class_ClassVariable_Declaration
449	447		;
450	448		Class_Variable_Declaration :
451	449		Y_Id_Comma_List ':' { LEnable(co_ClassVarStatic); LHints(true); } RClass_Variable_Declaration ;
452	450		RClass_Variable_Declaration :
453	451		Result_Type OPT_Hint ';' OPT_Static { LDisable(co_ClassVarStatic); LHints(false); }
454	452		;
455	453		OPT_Static :
456	454		/* EMTY */
457	455		\| NKW_STATIC ';'
458	456		;
459	457		Class_ClassVariable_Declaration : _CLASS Class_Variable_Declaration ;
460	458		Class_Method_Definition :
461	459		Class_PuF_Definition
462	460		\| Class_CuD_Definition
463	461		\| _CLASS Class_PuF_Definition
464	462		;
465	463
466	464		Class_PuF_Definition : PuF_Definition ;
467	465		Class_CuD_Definition :
468	466		_CONSTRUCTOR PLike_Definition
469	467		\| _DESTRUCTOR PLike_Definition
470	468		;
471	469		```
472	470
473	471		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).\
474	472		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.\
475		-	\
	473	+
476	474		The rule in between pitfall:\
477	475		Example: Hello in between
478	476
479	477		``` pascal
480	478		rule1 : ID rule2 { writeln($2); }
481	479
482	480		rule2 : ID1 { $$:='Hello'; } ID3 { $$:= $2; }
483	481		```
484	482
485	483		'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.\
486		-	\
	484	+
487	485		Additional explanation to this last two examples:\
488	486		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.\
489		-	\
490	487
491	488		# Useful Links
492	489
493	490		[[Make your own compiler, interpreter, parser, or expression analyzer]]
494	491
495	492		GVS 04:48, 9 March 2014 (CET)
496	493
497	494		---
498	495		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).
499	496		Category: Code
500	497		Category: Compiler design
501	498		Category: Utilities

Back to history