-
Notifications
You must be signed in to change notification settings - Fork 1
/
tply.txt
1544 lines (1145 loc) · 56.5 KB
/
tply.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
TP Lex and Yacc - The Compiler Writer's Tools for Turbo Pascal
== === === ==== = === ======== ======== ===== === ===== ======
Version 4.1 User Manual
======= === ==== ======
Albert Graef
Department of Musicinformatics
Johannes Gutenberg-University Mainz
April 1998
Introduction
============
This document describes the TP Lex and Yacc compiler generator toolset. These
tools are designed especially to help you prepare compilers and similar
programs like text processing utilities and command language interpreters with
the Turbo Pascal (TM) programming language.
TP Lex and Yacc are Turbo Pascal adaptions of the well-known UNIX (TM)
utilities Lex and Yacc, which were written by M.E. Lesk and S.C. Johnson at
Bell Laboratories, and are used with the C programming language. TP Lex and
Yacc are intended to be approximately "compatible" with these programs.
However, they are an independent development of the author, based on the
techniques described in the famous "dragon book" of Aho, Sethi and Ullman
(Aho, Sethi, Ullman: "Compilers : principles, techniques and tools," Reading
(Mass.), Addison-Wesley, 1986).
Version 4.1 of TP Lex and Yacc works with all recent flavours of Turbo/Borland
Pascal, including Delphi, and with the Free Pascal Compiler, a free Turbo
Pascal-compatible compiler which currently runs on DOS and Linux (other ports
are under development). Recent information about TP Lex/Yacc, and the sources
are available from the TPLY homepage:
http://www.musikwissenschaft.uni-mainz.de/~ag/tply
For information about the Free Pascal Compiler, please refer to:
http://tfdec1.fys.kuleuven.ac.be/~michael/fpc/fpc.html
TP Lex and Yacc, like any other tools of this kind, are not intended for
novices or casual programmers; they require extensive programming experience
as well as a thorough understanding of the principles of parser design and
implementation to be put to work successfully. But if you are a seasoned Turbo
Pascal programmer with some background in compiler design and formal language
theory, you will almost certainly find TP Lex and Yacc to be a powerful
extension of your Turbo Pascal toolset.
This manual tells you how to get started with the TP Lex and Yacc programs and
provides a short description of these programs. Some knowledge about the C
versions of Lex and Yacc will be useful, although not strictly necessary. For
further reading, you may also refer to:
- Aho, Sethi and Ullman: "Compilers : principles, techniques and tools."
Reading (Mass.), Addison-Wesley, 1986.
- Johnson, S.C.: "Yacc - yet another compiler-compiler." CSTR-32, Bell
Telephone Laboratories, 1974.
- Lesk, M.E.: "Lex - a lexical analyser generator." CSTR-39, Bell Telephone
Laboratories, 1975.
- Schreiner, Friedman: "Introduction to compiler construction with UNIX."
Prentice-Hall, 1985.
- The Unix Programmer's Manual, Sections `Lex' and `Yacc'.
Credits
-------
I would like to thank Berend de Boer ([email protected]), who adapted TP Lex
and Yacc to take advantage of the large memory models in Borland Pascal 7.0
and Delphi, and Michael Van Canneyt ([email protected]),
the maintainer of the Linux version of the Free Pascal compiler, who is
responsible for the Free Pascal port. And of course thanks are due to the many
TP Lex/Yacc users all over the world for their support and comments which
helped to improve these programs.
Getting Started
---------------
Instructions on how to compile and install TP Lex and Yacc on all supported
platforms can be found in the README file contained in the distribution.
Once you have installed TP Lex and Yacc on your system, you can compile your
first TP Lex and Yacc program expr. Expr is a simple desktop calculator
program contained in the distribution, which consists of a lexical analyzer in
the TP Lex source file exprlex.l and the parser and main program in the TP
Yacc source file expr.y. To compile these programs, issue the commands
lex exprlex
yacc expr
That's it! You now have the Turbo Pascal sources (exprlex.pas and expr.pas)
for the expr program. Use the Turbo Pascal compiler to compile these programs
as usual:
tpc expr
(Of course, the precise compilation command depends on the type of compiler
you are using. Thus you may have to replace tpc with bpc, dcc or dcc32,
depending on the version of the Turbo/Borland/Delphi compiler you have, and
with ppc386 for the Free Pascal compiler. If you are using TP Lex and Yacc
with Free Pascal under Linux, the corresponding commands are:
plex exprlex
pyacc expr
ppc386 expr
Note that in the Linux version, the programs are named plex and pyacc to
avoid name clashes with the corresponding UNIX utilities.)
Having compiled expr.pas, you can execute the expr program and type some
expressions to see it work (terminate the program with an empty line). There
is a number of other sample TP Lex and Yacc programs (.l and .y files) in the
distribution, including a TP Yacc cross reference utility and a complete
parser for Standard Pascal.
The TP Lex and Yacc programs recognize some options which may be specified
anywhere on the command line. E.g.,
lex -o exprlex
runs TP Lex with "DFA optimization" and
yacc -v expr
runs TP Yacc in "verbose" mode (TP Yacc generates a readable description of
the generated parser).
The TP Lex and Yacc programs use the following default filename extensions:
- .l: TP Lex input files
- .y: TP Yacc input files
- .pas: TP Lex and Yacc output files
As usual, you may overwrite default filename extensions by explicitly
specifying suffixes.
If you ever forget how to run TP Lex and Yacc, you can issue the command lex
or yacc (resp. plex or pyacc) without arguments to get a short summary of the
command line syntax.
TP Lex
======
This section describes the TP Lex lexical analyzer generator.
Usage
-----
lex [options] lex-file[.l] [output-file[.pas]]
Options
-------
-v "Verbose:" Lex generates a readable description of the generated
lexical analyzer, written to lex-file with new extension `.lst'.
-o "Optimize:" Lex optimizes DFA tables to produce a minimal DFA.
Description
-----------
TP Lex is a program generator that is used to generate the Turbo Pascal source
code for a lexical analyzer subroutine from the specification of an input
language by a regular expression grammar.
TP Lex parses the source grammar contained in lex-file (with default suffix
.l) and writes the constructed lexical analyzer subroutine to the specified
output-file (with default suffix .pas); if no output file is specified, output
goes to lex-file with new suffix .pas. If any errors are found during
compilation, error messages are written to the list file (lex-file with new
suffix .lst).
The generated output file contains a lexical analyzer routine, yylex,
implemented as:
function yylex : Integer;
This routine has to be called by your main program to execute the lexical
analyzer. The return value of the yylex routine usually denotes the number
of a token recognized by the lexical analyzer (see the return routine in the
LexLib unit). At end-of-file the yylex routine normally returns 0.
The code template for the yylex routine may be found in the yylex.cod
file. This file is needed by TP Lex when it constructs the output file. It
must be present either in the current directory or in the directory from which
TP Lex was executed (TP Lex searches these directories in the indicated
order). (NB: For the Linux/Free Pascal version, the code template is searched
in some directory defined at compile-time instead of the execution path,
usually /usr/lib/fpc/lexyacc.)
The TP Lex library (LexLib) unit is required by programs using Lex-generated
lexical analyzers; you will therefore have to put an appropriate uses clause
into your program or unit that contains the lexical analyzer routine. The
LexLib unit also provides various useful utility routines; see the file
lexlib.pas for further information.
Lex Source
----------
A TP Lex program consists of three sections separated with the %% delimiter:
definitions
%%
rules
%%
auxiliary procedures
All sections may be empty. The TP Lex language is line-oriented; definitions
and rules are separated by line breaks. There is no special notation for
comments, but (Turbo Pascal style) comments may be included as Turbo Pascal
fragments (see below).
The definitions section may contain the following elements:
- regular definitions in the format:
name substitution
which serve to abbreviate common subexpressions. The {name} notation
causes the corresponding substitution from the definitions section to
be inserted into a regular expression. The name must be a legal
identifier (letter followed by a sequence of letters and digits;
the underscore counts as a letter; upper- and lowercase are distinct).
Regular definitions must be non-recursive.
- start state definitions in the format:
%start name ...
which are used in specifying start conditions on rules (described
below). The %start keyword may also be abbreviated as %s or %S.
- Turbo Pascal declarations enclosed between %{ and %}. These will be
inserted into the output file (at global scope). Also, any line that
does not look like a Lex definition (e.g., starts with blank or tab)
will be treated as Turbo Pascal code. (In particular, this also allows
you to include Turbo Pascal comments in your Lex program.)
The rules section of a TP Lex program contains the actual specification of
the lexical analyzer routine. It may be thought of as a big CASE statement
discriminating over the different patterns to be matched and listing the
corresponding statements (actions) to be executed. Each rule consists of a
regular expression describing the strings to be matched in the input, and a
corresponding action, a Turbo Pascal statement to be executed when the
expression matches. Expression and statement are delimited with whitespace
(blanks and/or tabs). Thus the format of a Lex grammar rule is:
expression statement;
Note that the action must be a single Turbo Pascal statement terminated
with a semicolon (use begin ... end for compound statements). The statement
may span multiple lines if the successor lines are indented with at least
one blank or tab. The action may also be replaced by the | character,
indicating that the action for this rule is the same as that for the next
one.
The TP Lex library unit provides various variables and routines which are
useful in the programming of actions. In particular, the yytext string
variable holds the text of the matched string, and the yyleng Byte variable
its length.
Regular expressions are used to describe the strings to be matched in a
grammar rule. They are built from the usual constructs describing character
classes and sequences, and operators specifying repetitions and alternatives.
The precise format of regular expressions is described in the next section.
The rules section may also start with some Turbo Pascal declarations
(enclosed in %{ %}) which are treated as local declarations of the
actions routine.
Finally, the auxiliary procedures section may contain arbitrary Turbo
Pascal code (such as supporting routines or a main program) which is
simply tacked on to the end of the output file. The auxiliary procedures
section is optional.
Regular Expressions
-------------------
The following table summarizes the format of the regular expressions
recognized by TP Lex (also compare Aho, Sethi, Ullman 1986, fig. 3.48).
c stands for a single character, s for a string, r for a regular expression,
and n,m for nonnegative integers.
expression matches example
---------- ---------------------------- -------
c any non-operator character c a
\c character c literally \*
"s" string s literally "**"
. any character but newline a.*b
^ beginning of line ^abc
$ end of line abc$
[s] any character in s [abc]
[^s] any character not in s [^abc]
r* zero or more r's a*
r+ one or more r's a+
r? zero or one r a?
r{m,n} m to n occurrences of r a{1,5}
r{m} m occurrences of r a{5}
r1r2 r1 then r2 ab
r1|r2 r1 or r2 a|b
(r) r (a|b)
r1/r2 r1 when followed by r2 a/b
<x>r r when in start condition x <x>abc
---------------------------------------------------
The operators *, +, ? and {} have highest precedence, followed by
concatenation. The | operator has lowest precedence. Parentheses ()
may be used to group expressions and overwrite default precedences.
The <> and / operators may only occur once in an expression.
The usual C-like escapes are recognized:
\n denotes newline
\r denotes carriage return
\t denotes tab
\b denotes backspace
\f denotes form feed
\NNN denotes character no. NNN in octal base
You can also use the \ character to quote characters which would otherwise
be interpreted as operator symbols. In character classes, you may use
the - character to denote ranges of characters. For instance, [a-z]
denotes the class of all lowercase letters.
The expressions in a TP Lex program may be ambigious, i.e. there may be inputs
which match more than one rule. In such a case, the lexical analyzer prefers
the longest match and, if it still has the choice between different rules,
it picks the first of these. If no rule matches, the lexical analyzer
executes a default action which consists of copying the input character
to the output unchanged. Thus, if the purpose of a lexical analyzer is
to translate some parts of the input, and leave the rest unchanged, you
only have to specify the patterns which have to be treated specially. If,
however, the lexical analyzer has to absorb its whole input, you will have
to provide rules that match everything. E.g., you might use the rules
. |
\n ;
which match "any other character" (and ignore it).
Sometimes certain patterns have to be analyzed differently depending on some
amount of context in which the pattern appears. In such a case the / operator
is useful. For instance, the expression a/b matches a, but only if followed
by b. Note that the b does not belong to the match; rather, the lexical
analyzer, when matching an a, will look ahead in the input to see whether
it is followed by a b, before it declares that it has matched an a. Such
lookahead may be arbitrarily complex (up to the size of the LexLib input
buffer). E.g., the pattern a/.*b matches an a which is followed by a b
somewhere on the same input line. TP Lex also has a means to specify left
context which is described in the next section.
Start Conditions
----------------
TP Lex provides some features which make it possible to handle left context.
The ^ character at the beginning of a regular expression may be used to
denote the beginning of the line. More distant left context can be described
conveniently by using start conditions on rules.
Any rule which is prefixed with the <> construct is only valid if the lexical
analyzer is in the denoted start state. For instance, the expression <x>a
can only be matched if the lexical analyzer is in start state x. You can have
multiple start states in a rule; e.g., <x,y>a can be matched in start states
x or y.
Start states have to be declared in the definitions section by means of
one or more start state definitions (see above). The lexical analyzer enters
a start state through a call to the LexLib routine start. E.g., you may
write:
%start x y
%%
<x>a start(y);
<y>b start(x);
%%
begin
start(x); if yylex=0 then ;
end.
Upon initialization, the lexical analyzer is put into state x. It then
proceeds in state x until it matches an a which puts it into state y.
In state y it may match a b which puts it into state x again, etc.
Start conditions are useful when certain constructs have to be analyzed
differently depending on some left context (such as a special character
at the beginning of the line), and if multiple lexical analyzers have to
work in concert. If a rule is not prefixed with a start condition, it is
valid in all user-defined start states, as well as in the lexical analyzer's
default start state.
Lex Library
-----------
The TP Lex library (LexLib) unit provides various variables and routines
which are used by Lex-generated lexical analyzers and application programs.
It provides the input and output streams and other internal data structures
used by the lexical analyzer routine, and supplies some variables and utility
routines which may be used by actions and application programs. Refer to
the file lexlib.pas for a closer description.
You can also modify the Lex library unit (and/or the code template in the
yylex.cod file) to customize TP Lex to your target applications. E.g.,
you might wish to optimize the code of the lexical analyzer for some
special application, make the analyzer read from/write to memory instead
of files, etc.
Implementation Restrictions
---------------------------
Internal table sizes and the main memory available limit the complexity of
source grammars that TP Lex can handle. There is currently no possibility to
change internal table sizes (apart from modifying the sources of TP Lex
itself), but the maximum table sizes provided by TP Lex seem to be large
enough to handle most realistic applications. The actual table sizes depend on
the particular implementation (they are much larger than the defaults if TP
Lex has been compiled with one of the 32 bit compilers such as Delphi 2 or
Free Pascal), and are shown in the statistics printed by TP Lex when a
compilation is finished. The units given there are "p" (positions, i.e. items
in the position table used to construct the DFA), "s" (DFA states) and "t"
(transitions of the generated DFA).
As implemented, the generated DFA table is stored as a typed array constant
which is inserted into the yylex.cod code template. The transitions in each
state are stored in order. Of course it would have been more efficient to
generate a big CASE statement instead, but I found that this may cause
problems with the encoding of large DFA tables because Turbo Pascal has
a quite rigid limit on the code size of individual procedures. I decided to
use a scheme in which transitions on different symbols to the same state are
merged into one single transition (specifying a character set and the
corresponding next state). This keeps the number of transitions in each state
quite small and still allows a fairly efficient access to the transition
table.
The TP Lex program has an option (-o) to optimize DFA tables. This causes a
minimal DFA to be generated, using the algorithm described in Aho, Sethi,
Ullman (1986). Although the absolute limit on the number of DFA states that TP
Lex can handle is at least 300, TP Lex poses an additional restriction (100)
on the number of states in the initial partition of the DFA optimization
algorithm. Thus, you may get a fatal `integer set overflow' message when using
the -o option even when TP Lex is able to generate an unoptimized DFA. In such
cases you will just have to be content with the unoptimized DFA. (Hopefully,
this will be fixed in a future version. Anyhow, using the merged transitions
scheme described above, TP Lex usually constructs unoptimized DFA's which are
not far from being optimal, and thus in most cases DFA optimization won't have
a great impact on DFA table sizes.)
Differences from UNIX Lex
-------------------------
Major differences between TP Lex and UNIX Lex are listed below.
- TP Lex produces output code for Turbo Pascal, rather than for C.
- Character tables (%T) are not supported; neither are any directives
to determine internal table sizes (%p, %n, etc.).
- Library routines are named differently from the UNIX version (e.g.,
the `start' routine takes the place of the `BEGIN' macro of UNIX
Lex), and, of course, all macros of UNIX Lex (ECHO, REJECT, etc.) had
to be implemented as procedures.
- The TP Lex library unit starts counting line numbers at 0, incrementing
the count BEFORE a line is read (in contrast, UNIX Lex initializes
yylineno to 1 and increments it AFTER the line end has been read). This
is motivated by the way in which TP Lex maintains the current line,
and will not affect your programs unless you explicitly reset the
yylineno value (e.g., when opening a new input file). In such a case
you should set yylineno to 0 rather than 1.
TP Yacc
=======
This section describes the TP Yacc compiler compiler.
Usage
-----
yacc [options] yacc-file[.y] [output-file[.pas]]
Options
-------
-v "Verbose:" TP Yacc generates a readable description of the generated
parser, written to yacc-file with new extension .lst.
-d "Debug:" TP Yacc generates parser with debugging output.
Description
-----------
TP Yacc is a program that lets you prepare parsers from the description
of input languages by BNF-like grammars. You simply specify the grammar
for your target language, augmented with the Turbo Pascal code necessary
to process the syntactic constructs, and TP Yacc translates your grammar
into the Turbo Pascal code for a corresponding parser subroutine named
yyparse.
TP Yacc parses the source grammar contained in yacc-file (with default
suffix .y) and writes the constructed parser subroutine to the specified
output-file (with default suffix .pas); if no output file is specified,
output goes to yacc-file with new suffix .pas. If any errors are found
during compilation, error messages are written to the list file (yacc-file
with new suffix .lst).
The generated parser routine, yyparse, is declared as:
function yyparse : Integer;
This routine may be called by your main program to execute the parser.
The return value of the yyparse routine denotes success or failure of
the parser (possible return values: 0 = success, 1 = unrecoverable syntax
error or parse stack overflow).
Similar to TP Lex, the code template for the yyparse routine may be found in
the yyparse.cod file. The rules for locating this file are analogous to those
of TP Lex (see Section `TP Lex').
The TP Yacc library (YaccLib) unit is required by programs using Yacc-
generated parsers; you will therefore have to put an appropriate uses clause
into your program or unit that contains the parser routine. The YaccLib unit
also provides some routines which may be used to control the actions of the
parser. See the file yacclib.pas for further information.
Yacc Source
-----------
A TP Yacc program consists of three sections separated with the %% delimiter:
definitions
%%
rules
%%
auxiliary procedures
The TP Yacc language is free-format: whitespace (blanks, tabs and newlines)
is ignored, except if it serves as a delimiter. Comments have the C-like
format /* ... */. They are treated as whitespace. Grammar symbols are denoted
by identifiers which have the usual form (letter, including underscore,
followed by a sequence of letters and digits; upper- and lowercase is
distinct). The TP Yacc language also has some keywords which always start
with the % character. Literals are denoted by characters enclosed in single
quotes. The usual C-like escapes are recognized:
\n denotes newline
\r denotes carriage return
\t denotes tab
\b denotes backspace
\f denotes form feed
\NNN denotes character no. NNN in octal base
Definitions
-----------
The first section of a TP Yacc grammar serves to define the symbols used in
the grammar. It may contain the following types of definitions:
- start symbol definition: A definition of the form
%start symbol
declares the start nonterminal of the grammar (if this definition is
omitted, TP Yacc assumes the left-hand side nonterminal of the first
grammar rule as the start symbol of the grammar).
- terminal definitions: Definitions of the form
%token symbol ...
are used to declare the terminal symbols ("tokens") of the target
language. Any identifier not introduced in a %token definition will
be treated as a nonterminal symbol.
As far as TP Yacc is concerned, tokens are atomic symbols which do not
have an innert structure. A lexical analyzer must be provided which
takes on the task of tokenizing the input stream and return the
individual tokens and literals to the parser (see Section `Lexical
Analysis').
- precedence definitions: Operator symbols (terminals) may be associated
with a precedence by means of a precedence definition which may have
one of the following forms
%left symbol ...
%right symbol ...
%nonassoc symbol ...
which are used to declare left-, right- and nonassociative operators,
respectively. Each precedence definition introduces a new precedence
level, lowest precedence first. E.g., you may write:
%nonassoc '<' '>' '=' GEQ LEQ NEQ /* relational operators */
%left '+' '-' OR /* addition operators */
%left '*' '/' AND /* multiplication operators */
%right NOT UMINUS /* unary operators */
A terminal identifier introduced in a precedence definition may, but
need not, appear in a %token definition as well.
- type definitions: Any (terminal or nonterminal) grammar symbol may be
associated with a type identifier which is used in the processing of
semantic values. Type tags of the form <name> may be used in token and
precedence definitions to declare the type of a terminal symbol, e.g.:
%token <Real> NUM
%left <AddOp> '+' '-'
To declare the type of a nonterminal symbol, use a type definition of
the form:
%type <name> symbol ...
e.g.:
%type <Real> expr
In a %type definition, you may also omit the nonterminals, i.e. you
may write:
%type <name>
This is useful when a given type is only used with type casts (see
Section `Grammar Rules and Actions'), and is not associated with a
specific nonterminal.
- Turbo Pascal declarations: You may also include arbitrary Turbo Pascal
code in the definitions section, enclosed in %{ %}. This code will be
inserted as global declarations into the output file, unchanged.
Grammar Rules and Actions
-------------------------
The second part of a TP Yacc grammar contains the grammar rules for the
target language. Grammar rules have the format
name : symbol ... ;
The left-hand side of a rule must be an identifier (which denotes a
nonterminal symbol). The right-hand side may be an arbitrary (possibly
empty) sequence of nonterminal and terminal symbols (including literals
enclosed in single quotes). The terminating semicolon may also be omitted.
Different rules for the same left-hand side symbols may be written using
the | character to separate the different alternatives:
name : symbol ...
| symbol ...
...
;
For instance, to specify a simple grammar for arithmetic expressions, you
may write:
%left '+' '-'
%left '*' '/'
%token NUM
%%
expr : expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '(' expr ')'
| NUM
;
(The %left definitions at the beginning of the grammar are needed to specify
the precedence and associativity of the operator symbols. This will be
discussed in more detail in Section `Ambigious Grammars'.)
Grammar rules may contain actions - Turbo Pascal statements enclosed in
{ } - to be executed as the corresponding rules are recognized. Furthermore,
rules may return values, and access values returned by other rules. These
"semantic" values are written as $$ (value of the left-hand side nonterminal)
and $i (value of the ith right-hand side symbol). They are kept on a special
value stack which is maintained automatically by the parser.
Values associated with terminal symbols must be set by the lexical analyzer
(more about this in Section `Lexical Analysis'). Actions of the form $$ := $1
can frequently be omitted, since it is the default action assumed by TP Yacc
for any rule that does not have an explicit action.
By default, the semantic value type provided by Yacc is Integer. You can
also put a declaration like
%{
type YYSType = Real;
%}
into the definitions section of your Yacc grammar to change the default value
type. However, if you have different value types, the preferred method is to
use type definitions as discussed in Section `Definitions'. When such type
definitions are given, TP Yacc handles all the necessary details of the
YYSType definition and also provides a fair amount of type checking which
makes it easier to find type errors in the grammar.
For instance, we may declare the symbols NUM and expr in the example above
to be of type Real, and then use these values to evaluate an expression as
it is parsed.
%left '+' '-'
%left '*' '/'
%token <Real> NUM
%type <Real> expr
%%
expr : expr '+' expr { $$ := $1+$3; }
| expr '-' expr { $$ := $1-$3; }
| expr '*' expr { $$ := $1*$3; }
| expr '/' expr { $$ := $1/$3; }
| '(' expr ')' { $$ := $2; }
| NUM
;
(Note that we omitted the action of the last rule. The "copy action"
$$ := $1 required by this rule is automatically added by TP Yacc.)
Actions may not only appear at the end, but also in the middle of a rule
which is useful to perform some processing before a rule is fully parsed.
Such actions inside a rule are treated as special nonterminals which are
associated with an empty right-hand side. Thus, a rule like
x : y { action; } z
will be treated as:
x : y $act z
$act : { action; }
Actions inside a rule may also access values to the left of the action,
and may return values by assigning to the $$ value. The value returned
by such an action can then be accessed by other actions using the usual $i
notation. E.g., we may write:
x : y { $$ := 2*$1; } z { $$ := $2+$3; }
which has the effect of setting the value of x to
2*(the value of y)+(the value of z).
Sometimes it is desirable to access values in enclosing rules. This can be
done using the notation $i with i<=0. $0 refers to the first value "to the
left" of the current rule, $-1 to the second, and so on. Note that in this
case the referenced value depends on the actual contents of the parse stack,
so you have to make sure that the requested values are always where you
expect them.
There are some situations in which TP Yacc cannot easily determine the
type of values (when a typed parser is used). This is true, in particular,
for values in enclosing rules and for the $$ value in an action inside a
rule. In such cases you may use a type cast to explicitly specify the type
of a value. The format for such type casts is $<name>$ (for left-hand side
values) and $<name>i (for right-hand side values) where name is a type
identifier (which must occur in a %token, precedence or %type definition).
Auxiliary Procedures
--------------------
The third section of a TP Yacc program is optional. If it is present, it
may contain any Turbo Pascal code (such as supporting routines or a main
program) which is tacked on to the end of the output file.
Lexical Analysis
----------------
For any TP Yacc-generated parser, the programmer must supply a lexical
analyzer routine named yylex which performs the lexical analysis for
the parser. This routine must be declared as
function yylex : Integer;
The yylex routine may either be prepared by hand, or by using the lexical
analyzer generator TP Lex (see Section `TP Lex').
The lexical analyzer must be included in your main program behind the
parser subroutine (the yyparse code template includes a forward
definition of the yylex routine such that the parser can access the
lexical analyzer). For instance, you may put the lexical analyzer
routine into the auxiliary procedures section of your TP Yacc grammar,
either directly, or by using the the Turbo Pascal include directive
($I).
The parser repeatedly calls the yylex routine to tokenize the input
stream and obtain the individual lexical items in the input. For any
literal character, the yylex routine has to return the corresponding
character code. For the other, symbolic, terminals of the input language,
the lexical analyzer must return corresponding Integer codes. These are
assigned automatically by TP Yacc in the order in which token definitions
appear in the definitions section of the source grammar. The lexical
analyzer can access these values through corresponding Integer constants
which are declared by TP Yacc in the output file.
For instance, if
%token NUM
is the first definition in the Yacc grammar, then TP Yacc will create
a corresponding constant declaration
const NUM = 257;
in the output file (TP Yacc automatically assigns symbolic token numbers
starting at 257; 1 thru 255 are reserved for character literals, 0 denotes
end-of-file, and 256 is reserved for the special error token which will be
discussed in Section `Error Handling'). This definition may then be used,
e.g., in a corresponding TP Lex program as follows:
[0-9]+ return(NUM);
You can also explicitly assign token numbers in the grammar. For this
purpose, the first occurrence of a token identifier in the definitions
section may be followed by an unsigned integer. E.g. you may write:
%token NUM 299
Besides the return value of yylex, the lexical analyzer routine may also
return an additional semantic value for the recognized token. This value
is assigned to a variable named "yylval" and may then be accessed in actions
through the $i notation (see above, Section `Grammar Rules and Actions').
The yylval variable is of type YYSType (the semantic value type, Integer
by default); its declaration may be found in the yyparse.cod file.
For instance, to assign an Integer value to a NUM token in the above
example, we may write:
[0-9]+ begin
val(yytext, yylval, code);
return(NUM);
end;
This assigns yylval the value of the NUM token (using the Turbo Pascal
standard procedure val).
If a parser uses tokens of different types (via a %token <name> definition),
then the yylval variable will not be of type Integer, but instead of a
corresponding variant record type which is capable of holding all the
different value types declared in the TP Yacc grammar. In this case, the
lexical analyzer must assign a semantic value to the corresponding record
component which is named yy<name> (where <name> stands for the corresponding
type identifier).
E.g., if token NUM is declared Real:
%token <Real> NUM
then the value for token NUM must be assigned to yylval.yyReal.
How The Parser Works
--------------------
TP Yacc uses the LALR(1) technique developed by Donald E. Knuth and F.
DeRemer to construct a simple, efficient, non-backtracking bottom-up
parser for the source grammar. The LALR parsing technique is described
in detail in Aho/Sethi/Ullman (1986). It is quite instructive to take a
look at the parser description TP Yacc generates from a small sample
grammar, to get an idea of how the LALR parsing algorithm works. We
consider the following simplified version of the arithmetic expression
grammar:
%token NUM
%left '+'
%left '*'
%%
expr : expr '+' expr
| expr '*' expr
| '(' expr ')'
| NUM
;
When run with the -v option on the above grammar, TP Yacc generates the
parser description listed below.
state 0:
$accept : _ expr $end
'(' shift 2
NUM shift 3
. error
expr goto 1
state 1:
$accept : expr _ $end
expr : expr _ '+' expr
expr : expr _ '*' expr
$end accept
'*' shift 4
'+' shift 5
. error
state 2:
expr : '(' _ expr ')'
'(' shift 2
NUM shift 3
. error
expr goto 6
state 3:
expr : NUM _ (4)
. reduce 4
state 4:
expr : expr '*' _ expr
'(' shift 2
NUM shift 3
. error
expr goto 7
state 5:
expr : expr '+' _ expr
'(' shift 2
NUM shift 3
. error
expr goto 8
state 6:
expr : '(' expr _ ')'
expr : expr _ '+' expr
expr : expr _ '*' expr
')' shift 9
'*' shift 4
'+' shift 5
. error
state 7:
expr : expr '*' expr _ (2)
expr : expr _ '+' expr
expr : expr _ '*' expr
. reduce 2
state 8:
expr : expr '+' expr _ (1)
expr : expr _ '+' expr
expr : expr _ '*' expr
'*' shift 4
$end reduce 1
')' reduce 1
'+' reduce 1
. error
state 9:
expr : '(' expr ')' _ (3)
. reduce 3
Each state of the parser corresponds to a certain prefix of the input
which has already been seen. The parser description lists the grammar
rules wich are parsed in each state, and indicates the portion of each