![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lex.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / vol2 / lex|
Return to lex.ms CVS log | Up to [Research Unix] / researchv10dc / vol2 / lex |
1.1 root 1: .so ../ADM/mac
2: .XX lex 375 "Lex \(em A Lexical Analyzer Generator"
3: .hc ~
4: ...ND July 21, 1975
5: ...TR 39
6: ...RP
7: ...TM 75-1274-15 39199 39199-11
8: .ds L \f2Lex\fP
9: .ds l \f2lex\fP
10: .nr dP 2
11: .nr dV 3p
12: .TL
13: Lex \(em A Lexical Analyzer Generator
14: .AU ``MH 2C-569'' 6377
15: M. E. Lesk
16: E. Schmidt
17: .AI
18: .MH
19: .AB
20: .PP
21: \*L helps write programs whose control flow
22: is directed by instances of regular
23: expressions in the input stream.
24: It is well suited for editor-script type transformations and
25: for segmenting input in preparation for
26: a parsing routine.
27: .PP
28: \*L source is a table of regular expressions and corresponding program fragments.
29: The table is translated to a program
30: which reads an input stream, copying it to an output stream
31: and partitioning the input
32: into strings which match the given expressions.
33: As each such string is recognized the corresponding
34: program fragment is executed.
35: The recognition of the expressions
36: is performed by a deterministic finite automaton
37: generated by \*l.
38: The program fragments written by the user are executed in the order in which the
39: corresponding regular expressions occur in the input stream.
40: .PP
41: The lexical analysis
42: programs written with \*l accept ambiguous specifications
43: and choose the longest
44: match possible at each input point.
45: If necessary, substantial look~ahead
46: is performed on the input, but the
47: input stream will be backed up to the
48: end of the current partition, so that the user
49: has general freedom to manipulate it.
50: .PP
51: \*L can generate analyzers in either C or Ratfor, a language
52: which can be translated automatically to portable Fortran.
53: This manual, however, will only discuss generating analyzers
54: in C.
55: \*L is designed to simplify
56: interfacing with \fIyacc\fP, for those
57: with access to this compiler-compiler system.
58: .AE
59: .2C
60: .NH
61: Introduction.
62: .PP
63: \*L is a program generator designed for
64: lexical processing of character input streams.
65: It accepts a high-level, problem oriented specification
66: for character string matching,
67: and
68: produces a program in a general purpose language which recognizes
69: regular expressions.
70: The regular expressions are specified by the user in the
71: source specifications given to \*l.
72: The \*l written code recognizes these expressions
73: in an input stream and partitions the input stream into
74: strings matching the expressions. At the bound~aries
75: between strings
76: program sections
77: provided by the user are executed.
78: The \*l source file associates the regular expressions and the
79: program fragments.
80: As each expression appears in the input to the program written by \*l,
81: the corresponding fragment is executed.
82: .PP
83: The user supplies the additional code
84: beyond expression matching
85: needed to complete his tasks, possibly
86: including code written by other generators.
87: The program that recognizes the expressions is generated in the
88: general purpose programming language employed for the
89: user's program fragments.
90: Thus, a high level expression
91: language is provided to write the string expressions to be
92: matched while the user's freedom to write actions
93: is unimpaired.
94: This avoids forcing the user who wishes to use a string manipulation
95: language for input analysis to write processing programs in the same
96: and often inappropriate string handling language.
97: .PP
98: \*L is not a complete language, but rather a generator representing
99: a new language feature which can be added to
100: different programming languages, called ``host languages.''
101: Just as general purpose languages
102: can produce code to run on different computer hardware,
103: \*l can write code in different host languages.
104: The host language is used for the output code generated by \*l
105: and also for the program fragments added by the user.
106: Compatible run-time libraries for the different host languages
107: are also provided.
108: This makes \*l adaptable to different environments and
109: different users.
110: Each application
111: may be directed to the combination of hardware and host language appropriate
112: to the task, the user's background, and the properties of local
113: implementations.
114: At present, the only supported host language is C|reference(cbook),
115: although Fortran (in the form of Ratfor|reference(ratfor spe) has been available
116: in the past.
117: .PP
118: \*L turns the user's expressions and actions
119: (called
120: .I source
121: in this memo) into the host general-purpose language;
122: the generated program is named
123: .I yylex .
124: The
125: .I yylex
126: program
127: will recognize expressions
128: in a stream
129: (called
130: .I input
131: in this memo)
132: and perform the specified actions for each expression as it is detected.
133: See Figure 1.
134: .KF
135: .TS
136: center;
137: l _ r
138: l|c|r
139: l _ r
140: l _ r
141: l|c|r
142: l _ r
143: c s s
144: c s s.
145:
146: Source \(-> \*l \(-> yylex
147:
148: .sp
149:
150: Input \(-> yylex \(-> Output
151:
152: .sp
153: \fBFigure 1.\fP An overview of \*l
154: .TE
155: .KE
156: .PP
157: For a trivial example, consider a program to delete
158: from the input
159: all blanks or tabs at the ends of lines.
160: .P1 0
161: %%
162: [ \et]+$ ;
163: .P2
164: is all that is required.
165: The program
166: contains a
167: .CW %%
168: delimiter to mark the beginning of the rules, and
169: one rule.
170: This rule contains a regular expression
171: which matches one or more
172: instances of the characters blank or tab
173: (written
174: .CW \et
175: for visibility, in accordance with the C language convention)
176: just prior to the end of a line.
177: The brackets indicate the character
178: class made of blank and tab; the
179: .CW +
180: indicates ``one or more ...'';
181: and the
182: .CW $
183: indicates ``end of line,'' as in QED.
184: No action is specified,
185: so the program generated by \*l (yylex) will ignore these characters.
186: Everything else will be copied.
187: To change any remaining
188: string of blanks or tabs to a single blank,
189: add another rule:
190: .P1 0
191: %%
192: [ \et]+$ ;
193: [ \et]+ printf(" ");
194: .P2
195: The finite automaton generated for this
196: source will scan for both rules at once,
197: observing at
198: the termination of the string of blanks or tabs
199: whether or not there is a newline character, and executing
200: the desired rule action.
201: The first rule matches all strings of blanks or tabs
202: at the end of lines, and the second
203: rule all remaining strings of blanks or tabs.
204: .PP
205: \*L can be used alone for simple transformations, or
206: for analysis and statistics gathering on a lexical level.
207: \*L can also be used with a parser generator
208: to perform the lexical analysis phase; it is particularly
209: easy to interface \*l and \fIyacc\fP|reference(latest yacc).
210: \*L programs recognize only regular expressions;
211: \fIyacc\fP writes parsers that accept a large class of context free grammars,
212: but require a lower level analyzer to recognize input tokens.
213: Thus, a combination of \*l and \fIyacc\fP is often appropriate.
214: When used as a preprocessor for a later parser generator,
215: \*l is used to partition the input stream,
216: and the parser generator assigns structure to
217: the resulting pieces.
218: The flow of control
219: in such a case (which might be the first half of a compiler,
220: for example) is shown in Figure 2.
221: Additional programs,
222: written by other generators
223: or by hand, can
224: be added easily to programs written by \*l.
225: .KF
226: .TS
227: center;
228: l c c c l
229: l c c c l
230: l c c c l
231: l _ c _ l
232: l|c|c|c|l
233: l _ c _ l
234: l c c c l
235: l _ c _ l
236: l|c|c|c|l
237: l _ c _ l
238: l c s s l.
239: lexical grammar
240: rules rules
241: \(da \(da
242:
243: \*l \fIyacc\fP
244:
245: \(da \(da
246:
247: Input \(-> yylex \(-> yyparse \(-> Parsed input
248:
249: .sp
250: \fBFigure 2.\fP \*L with \fIyacc\fP
251: .TE
252: .KE
253: \fIYacc\fP users
254: will realize that the name
255: .I yylex
256: is what \fIyacc\fP expects its lexical analyzer to be named,
257: so that the use of this name by \*l simplifies
258: interfacing.
259: .PP
260: \*L generates a deterministic finite automaton from the regular expressions
261: in the source|reference(aho corasick).
262: The automaton is interpreted, rather than compiled, in order
263: to save space.
264: The result is still a fast analyzer.
265: In particular, the time taken by a \*l program
266: to recognize and partition an input stream is
267: proportional to the length of the input.
268: The number of \*l rules or
269: the complexity of the rules is
270: not important in determining speed,
271: unless rules which include
272: forward context require a significant amount of re~scanning.
273: What does increase with the number and complexity of rules
274: is the size of the finite
275: automaton, and therefore the size of the program
276: generated by \*l.
277: .PP
278: In the program written by \*l, the user's fragments
279: (representing the
280: .I actions
281: to be performed as each regular expression
282: is found)
283: are gathered
284: as cases of a switch.
285: The automaton interpreter directs the control flow.
286: Opportunity is provided for the user to insert either
287: declarations or additional statements in the routine containing
288: the actions, or to
289: add subroutines outside this action routine.
290: .PP
291: \*L is not limited to source which can
292: be interpreted on the basis of one character
293: look~ahead.
294: For example,
295: if there are two rules, one looking for
296: .CW ab
297: and another for
298: .CW abcdefg ,
299: and the input stream is
300: .CW abcdefh ,
301: \*L will recognize
302: .CW ab
303: and leave
304: the input pointer just before
305: .CW cdefh .
306: Such backup is more costly
307: than the processing of simpler languages.
308: .NH
309: \*L Source.
310: .PP
311: The general format of \*l source is:
312: .P1 0
313: {definitions}
314: %%
315: {rules}
316: %%
317: {user subroutines}
318: .P2
319: where the definitions and the user subroutines
320: are often omitted.
321: The second
322: .CW %%
323: is optional, but the first is required
324: to mark the beginning of the rules.
325: The absolute minimum \*l program is thus
326: .P1 0
327: %%
328: .P2
329: (no definitions, no rules) which translates into a program
330: which copies the input to the output unchanged.
331: .PP
332: In the outline of \*l programs shown above, the
333: .I rules
334: represent the user's control
335: decisions; they are a table, in which the left column
336: contains
337: .I
338: regular expressions
339: .R
340: (see section 3)
341: and the right column contains
342: .I actions ,
343: program fragments to be executed when the expressions
344: are recognized.
345: Thus an individual rule might appear
346: .P1 0
347: integer printf("found keyword INT");
348: .P2
349: to look for the string
350: .CW integer
351: in the input stream and
352: print the message ``found keyword INT'' whenever it appears.
353: In this example the host procedural language is C and
354: the C library function
355: .I printf
356: is used to print the string.
357: The end
358: of the expression is indicated by the first blank or tab character.
359: If the action is merely a single C expression,
360: it can just be given on the right side of the line; if it is
361: compound, or takes more than a line, it should be enclosed in
362: braces.
363: As a slightly more useful example, suppose it is desired to
364: change a number of words from British to American spelling.
365: \*L rules such as
366: .P1 0
367: colour printf("color");
368: mechanise printf("mechanize");
369: petrol printf("gas");
370: .P2
371: would be a start. These rules are not quite enough,
372: since
373: the word
374: .CW petroleum
375: would become
376: .CW gaseum ;
377: a way of dealing
378: with this will be described later.
379: .NH
380: \*L Regular Expressions.
381: .PP
382: The definitions of regular expressions are very similar to those
383: in QED|reference(qed cstr).
384: A regular
385: expression specifies a set of strings to be matched.
386: It contains text characters (which match the corresponding
387: characters in the strings being compared)
388: and operator characters (which specify
389: repetitions, choices, and other features).
390: The letters of the alphabet and the digits are
391: always text characters; thus the regular expression
392: .P1 0
393: integer
394: .P2
395: matches the string
396: .CW integer
397: wherever it appears
398: and the expression
399: .P1 0
400: a57D
401: .P2
402: looks for the string
403: .CW a57D .
404: .PP
405: .I Operators .
406: The operator characters are
407: .P1 0
408: " \e [ ] ^ - ? . \(** + | ( ) $ / { } % < >
409: .P2
410: and if they are to be used as text characters, an escape
411: should be used.
412: The quotation mark operator (")
413: indicates that whatever is contained between a pair of quotes
414: is to be taken as text characters.
415: Thus
416: .P1 0
417: xyz"++"
418: .P2
419: matches the string
420: .CW xyz++
421: when it appears. Note that a part of a string may be quoted.
422: It is harmless but unnecessary to quote an ordinary
423: text character; the expression
424: .P1 0
425: "xyz++"
426: .P2
427: is the same as the one above.
428: Thus by quoting every non-alphanumeric character
429: being used as a text character, the user can avoid remembering
430: the list above of current
431: operator characters, and is safe should further extensions to \*l
432: lengthen the list.
433: .PP
434: An operator character may also be turned into a text character
435: by preceding it with \e as in
436: .P1 0
437: xyz\e+\e+
438: .P2
439: which
440: is another, less readable, equivalent of the above expressions.
441: Another use of the quoting mechanism is to get a blank into
442: an expression; normally, as explained above, blanks or tabs end
443: a rule.
444: Any blank character not contained within
445: .CW []
446: (see below) must
447: be quoted.
448: Several normal C escapes with
449: .CW \e
450: are recognized:
451: .CW \en
452: is newline,
453: .CW \et
454: is tab, and
455: .CW \eb
456: is backspace.
457: To enter
458: .CW \e
459: itself, use
460: .CW \e\e .
461: Since newline is illegal in an expression,
462: .CW \en
463: must be used;
464: it is not
465: required to escape tab and backspace.
466: Every character but blank, tab, newline and the list above is always
467: a text character.
468: .PP
469: .I "Character classes" .
470: Classes of characters can be specified using the operator pair
471: .CW [] .
472: The construction
473: .CW [abc]
474: matches a
475: single character, which may be
476: .CW a ,
477: .CW b ,
478: or
479: .CW c .
480: Within square brackets,
481: most operator meanings are ignored.
482: Only three characters are special:
483: these are
484: .CW \e ,
485: .CW -
486: and
487: .CW ^ .
488: The
489: .CW -
490: character
491: indicates ranges. For example,
492: .P1 0
493: [a-z0-9<>_]
494: .P2
495: indicates the character class containing all the lower case letters,
496: the digits,
497: the angle brackets, and underline.
498: Ranges may be given in either order.
499: Using
500: .CW -
501: between any pair of characters which are
502: not both upper case letters, both lower case letters, or both digits
503: is implementation dependent and will get a warning message.
504: (E.g.,
505: .CW [0\e-z]
506: in ASCII is many more characters
507: than it is in EBCDIC).
508: If it is desired to include the
509: character - in a character class, it should be first or
510: last; thus
511: .P1 0
512: [-+0-9]
513: .P2
514: matches all the digits and the two signs.
515: .PP
516: In character classes,
517: the
518: .CW ^
519: operator must appear as the first character
520: after the left bracket; it indicates that the resulting string
521: is to be complemented with respect to the computer character set.
522: Thus
523: .P1 0
524: [^abc]
525: .P2
526: matches all characters except
527: .CW a ,
528: .CW b , or
529: .CW c ,
530: including
531: all special or control characters; or
532: .P1 0
533: [^a-zA-Z]
534: .P2
535: is any character which is not a letter.
536: The
537: .CW \e
538: character provides the usual escapes within
539: character class brackets.
540: .PP
541: .I "Arbitrary character" .
542: To match almost any character, the operator character
543: .CW .
544: is the class of all characters except newline.
545: Escaping into octal is possible although non-portable:
546: .P1 0
547: [\e40-\e176]
548: .P2
549: matches all printable characters in the ASCII character set, from octal
550: 40 (blank) to octal 176 (tilde).
551: .PP
552: .I "Optional expressions" .
553: The operator
554: .CW ?
555: indicates
556: an optional element of an expression.
557: Thus
558: .P1 0
559: ab?c
560: .P2
561: matches either
562: .CW ac
563: or
564: .CW abc .
565: .PP
566: .I "Repeated expressions" .
567: Repetitions of classes are indicated by the operators
568: .CW *
569: and
570: .CW + .
571: .P1 0
572: a*
573: .P2
574: is any number of consecutive
575: .CW a
576: characters, including zero; while
577: .P1 0
578: a+
579: .P2
580: is one or more instances of
581: .CW a .
582: For example,
583: .P1 0
584: [a-z]+
585: .P2
586: is all strings of lower case letters.
587: And
588: .P1 0
589: [A-Za-z][A-Za-z0-9]*
590: .P2
591: indicates all alphanumeric strings with a leading
592: alphabetic character.
593: This is a typical expression for recognizing identifiers in
594: computer languages.
595: .PP
596: .I "Alternation and Grouping" .
597: The operator
598: .CW |
599: indicates alternation:
600: .P1 0
601: (ab|cd)
602: .P2
603: matches either
604: .CW ab
605: or
606: .CW cd .
607: Note that parentheses are used for grouping, although
608: they are
609: not necessary on the outside level;
610: .P1 0
611: ab|cd
612: .P2
613: would have sufficed.
614: Parentheses
615: can be used for more complex expressions:
616: .P1 0
617: (ab|cd+)?(ef)*
618: .P2
619: matches such strings as
620: .CW abefef ,
621: .CW efefef ,
622: .CW cdef ,
623: or
624: .CW cddd ;
625: but not
626: .CW abc ,
627: .CW abcd ,
628: or
629: .CW abcdef .
630: .PP
631: .I "Context sensitivity" .
632: \*L will recognize a small amount of surrounding
633: context. The two simplest operators for this are
634: .CW ^
635: and
636: .CW $ .
637: If the first character of an expression is
638: .CW ^ ,
639: the expression will only be matched at the beginning
640: of a line (after a newline character, or at the beginning of
641: the input stream).
642: This can never conflict with the other meaning of
643: .CW ^ ,
644: complementation
645: of character classes, since that only applies within
646: the
647: .CW []
648: operators.
649: If the very last character is
650: .CW $ ,
651: the expression will only be matched at the end of a line (when
652: immediately followed by newline).
653: The latter operator is a special case of the
654: .CW /
655: operator character,
656: which indicates trailing context.
657: The expression
658: .P1 0
659: ab/cd
660: .P2
661: matches the string
662: .CW ab ,
663: but only if followed by
664: .CW cd .
665: Thus
666: .P1 0
667: ab$
668: .P2
669: is the same as
670: .P1 0
671: ab/\en
672: .P2
673: Left context is handled in \*l by
674: .I "start conditions"
675: as explained in section 10. If a rule is only to be executed
676: when the \*l automaton interpreter is in start condition
677: .I x ,
678: the rule should be prefixed by
679: .P1 0
680: <x>
681: .P2
682: using the angle bracket operator characters.
683: If we considered ``being at the beginning of a line'' to be
684: start condition
685: .I ONE ,
686: then the
687: .CW ^
688: operator
689: would be equivalent to
690: .P1 0
691: <ONE>
692: .P2
693: Start conditions are explained more fully later.
694: .PP
695: .I "Repetitions and Definitions" .
696: The operators
697: .CW {}
698: specify
699: either repetitions (if they enclose numbers)
700: or
701: definition expansion (if they enclose a name). For example
702: .P1 0
703: {digit}
704: .P2
705: looks for a predefined string named
706: .I digit
707: and inserts it
708: at that point in the expression.
709: The definitions are given in the first part of the \*l
710: input, before the rules.
711: In contrast,
712: .P1 0
713: a{1,5}
714: .P2
715: looks for 1 to 5 occurrences of
716: .CW a .
717: .PP
718: Finally, initial
719: .CW %
720: is special, being the separator
721: for \*l source segments.
722: .NH
723: \*L Actions.
724: .PP
725: When an expression written as above is matched, \*l
726: executes the corresponding action. This section describes
727: some features of \*l which aid in writing actions. Note
728: that there is a default action, which
729: consists of copying the input to the output. This
730: is performed on all strings not otherwise matched. Thus
731: the \*l user who wishes to absorb the entire input, without
732: producing any output, must provide rules to match everything.
733: When \*l is being used with \fIyacc\fP, this is the normal
734: situation.
735: One may consider that actions are what is done instead of
736: copying the input to the output; thus, in general,
737: a rule which merely copies can be omitted.
738: Also, a character combination
739: which is omitted from the rules
740: and which appears as input
741: is likely to be printed on the output, thus calling
742: attention to the gap in the rules.
743: .PP
744: One of the simplest things that can be done is to ignore
745: the input. Specifying a C null statement,
746: .CW ;
747: as an action
748: causes this result. A frequent rule is
749: .P1 0
750: [ \et\en] ;
751: .P2
752: which causes the three spacing characters (blank, tab, and newline)
753: to be ignored.
754: .PP
755: Another easy way to avoid writing actions is the action character
756: .CW | ,
757: which indicates that the action for this rule is the action
758: for the next rule.
759: The previous example could also have been written
760: .P1 0
761: " " |
762: "\et" |
763: "\en" ;
764: .P2
765: with the same result, although in different style.
766: The quotes around
767: .CW \en
768: and
769: .CW \et
770: are not required.
771: .PP
772: In more complex actions, the user
773: will
774: often want to know the actual text that matched some expression
775: like
776: .CW [a-z]+ .
777: \*L leaves this text in an external character
778: array named
779: .I yytext .
780: Thus, to print the name found,
781: a rule like
782: .P1 0
783: [a-z]+ printf("%s", yytext);
784: .P2
785: will print
786: the string in
787: .I yytext .
788: The C function
789: .I printf
790: accepts a format argument and data to be printed;
791: in this case, the format is ``print string'' (\f(CW%\fP indicating
792: data conversion, and
793: .CW s
794: indicating string type),
795: and the data are the characters
796: in
797: .I yytext .
798: So this just places
799: the matched string
800: on the output.
801: This action
802: is so common that
803: it may be written as
804: .CW ECHO :
805: .P1 0
806: [a-z]+ ECHO;
807: .P2
808: is the same as the above.
809: Since the default action is just to
810: print the characters found, one might ask why
811: give a rule, like this one, which merely specifies
812: the default action?
813: Such rules are often required
814: to avoid matching some other rule
815: which is not desired. For example, if there is a rule
816: which matches
817: .I read
818: it will normally match the instances of
819: .I read
820: contained in
821: .I bread
822: or
823: .I readjust ;
824: to avoid
825: this,
826: a rule
827: of the form
828: .CW [a-z]+
829: is needed.
830: This is explained further below.
831: .PP
832: Sometimes it is more convenient to know the end of what
833: has been found; hence \*l also provides a count
834: .I yyleng
835: of the number of characters matched.
836: To count both the number
837: of words and the number of characters in words in the input, the user might write
838: .P1 0
839: [a-zA-Z]+ {words++; chars += yyleng;}
840: .P2
841: which accumulates in
842: .I chars
843: the number
844: of characters in the words recognized.
845: The last character in the string matched can
846: be accessed by
847: .P1 0
848: yytext[yyleng-1]
849: .P2
850: .PP
851: Occasionally, a \*l
852: action may decide that a rule has not recognized the correct
853: span of characters.
854: Two routines are provided to aid with this situation.
855: First,
856: .I yymore()
857: can be called to indicate that the next input expression recognized is to be
858: tacked on to the end of this input. Normally,
859: the next input string would overwrite the current
860: entry in
861: .I yytext .
862: Second,
863: .I yyless(n)
864: may be called to indicate that not all the characters matched
865: by the currently successful expression are wanted right now.
866: The argument
867: .I n
868: indicates the number of characters in
869: .I yytext
870: to be retained.
871: Further characters previously matched
872: are
873: returned to the input. This provides the same sort of
874: look~ahead offered by the
875: .CW /
876: operator,
877: but in a different form.
878: .PP
879: .I "Example" :
880: Consider a language which defines
881: a string as a set of characters between quotation
882: .CW \"
883: marks, and provides that
884: to include a
885: .CW \"
886: in a string it must be preceded by a
887: .CW \e .
888: The regular expression which matches that is somewhat confusing,
889: so that it might be preferable to write
890: .P1 0
891: \e"[^"]* {
892: if (yytext[yyleng-1] == '\e\e'
893: yymore();
894: else
895: ... normal user processing
896: }
897: .P2
898: which will, when faced with a string such as
899: .CW \"abc\e"def" ,
900: first match
901: the five characters
902: .CW \"abc\e ;
903: then
904: the call to
905: .I yymore()
906: will
907: cause the next part of the string,
908: .CW \"def ,
909: to be tacked on the end.
910: Note that the final quote terminating the string should be picked
911: up in the code labeled ``normal processing''.
912: .PP
913: The function
914: .I yyless
915: might be used to reprocess
916: text in various circumstances. Consider the C problem of distinguishing
917: the ambiguity of
918: .CW =-a .
919: Suppose it is desired to treat this as
920: .CW "=- a"
921: but print a message. A rule might be
922: .P1 0
923: =-[a-zA-Z] {
924: printf("Operator (=-) ambiguous\en");
925: yyless(yyleng-1);
926: ... action for =- ...
927: }
928: .P2
929: which prints a message, returns the letter after the
930: operator to the input stream, and treats the operator as
931: .CW =- .
932: Alternatively it might be desired to treat this as
933: .CW "= -a" .
934: To do this, just return the minus
935: sign as well as the letter to the input:
936: .P1 0
937: =-[a-zA-Z] {
938: printf("Operator (=-) ambiguous\en");
939: yyless(yyleng-2);
940: ... action for = ...
941: }
942: .P2
943: will perform the other interpretation.
944: Note that the expressions for the two cases might more easily
945: be written
946: .P1 0
947: =-/[A-Za-z]
948: .P2
949: in the first case and
950: .P1 0
951: =/-[A-Za-z]
952: .P2
953: in the second;
954: no backup would be required in the rule action.
955: It is not necessary to recognize the whole identifier
956: to observe the ambiguity.
957: The
958: possibility of
959: .CW =-3 ,
960: however, makes
961: .P1 0
962: =-/[^ \et\en]
963: .P2
964: a still better rule.
965: .PP
966: In addition to these routines, \*l also permits
967: access to the I/O routines
968: it uses.
969: They are:
970: .IP 1)
971: .I
972: input()
973: .R
974: which returns the next input character;
975: .IP 2)
976: .I
977: output(c)
978: .R
979: which writes the character
980: .I c
981: on the output; and
982: .IP 3)
983: .I
984: unput(c)
985: .R
986: pushes the character
987: .I c
988: back onto the input stream to be read later by
989: .I input() .
990: .LP
991: By default these routines are provided as macro definitions,
992: but the user can override them and supply private versions.
993: These routines
994: define the relationship between external files and
995: internal characters, and must all be retained
996: or modified consistently.
997: They may be redefined, to
998: cause input or output to be transmitted to or from strange
999: places, including other programs or internal memory;
1000: but the character set used must be consistent in all routines;
1001: a value of zero returned by
1002: .I input
1003: must mean end of file; and
1004: the relationship between
1005: .I unput
1006: and
1007: .I input
1008: must be retained
1009: or the \*l look~ahead will not work.
1010: \*L does not look ahead at all if it does not have to,
1011: but every rule ending in
1012: .CW +
1013: .CW *
1014: .CW ?
1015: .CW $
1016: or containing
1017: .CW /
1018: implies look~ahead.
1019: Look~ahead is also necessary to match an expression that is a prefix
1020: of another expression.
1021: See below for a discussion of the character set used by \*l.
1022: The standard \*l library imposes
1023: a 100 character limit on backup.
1024: .PP
1025: Another \*l library routine that the user will sometimes want
1026: to redefine is
1027: .I yywrap()
1028: which is called whenever \*l reaches an end-of-file.
1029: If
1030: .I yywrap
1031: returns a 1, \*l continues with the normal wrapup on end of input.
1032: Sometimes, however, it is convenient to arrange for more
1033: input to arrive
1034: from a new source.
1035: In this case, the user should provide
1036: a
1037: .I yywrap
1038: which
1039: arranges for new input and
1040: returns 0. This instructs \*l to continue processing.
1041: The default
1042: .I yywrap
1043: always returns 1.
1044: .PP
1045: This routine is also a convenient place
1046: to print tables, summaries, etc. at the end
1047: of a program. Note that it is not
1048: possible to write a normal rule which recognizes
1049: end-of-file; the only access to this condition is
1050: through
1051: .I yywrap .
1052: In fact, unless a private version of
1053: .I input()
1054: is supplied
1055: a file containing nulls
1056: cannot be handled,
1057: since a value of 0 returned by
1058: .I input
1059: is taken to be end-of-file.
1060: ........
1061: .NH
1062: Ambiguous Source Rules.
1063: .PP
1064: \*L can handle ambiguous specifications.
1065: When more than one expression can match the
1066: current input, \*l chooses as follows:
1067: .IP 1)
1068: The longest match is preferred.
1069: .IP 2)
1070: Among rules which matched the same number of characters,
1071: the rule given first is preferred.
1072: .LP
1073: Thus, suppose the rules
1074: .P1 0
1075: integer keyword action ...;
1076: [a-z]+ identifier action ...;
1077: .P2
1078: to be given in that order. If the input is
1079: .I integers ,
1080: it is taken as an identifier, because
1081: .CW [a-z]+
1082: matches 8 characters while
1083: .CW integer
1084: matches only 7.
1085: If the input is
1086: .I integer ,
1087: both rules match 7 characters, and
1088: the keyword rule is selected because it was given first.
1089: Anything shorter (e.g. \fIint\fR\|) will
1090: not match the expression
1091: .I integer
1092: and so the identifier interpretation is used.
1093: .PP
1094: The principle of preferring the longest
1095: match makes rules containing
1096: expressions like
1097: .CW .*
1098: dangerous.
1099: For example,
1100: .P1 0
1101: \&'.*'
1102: .P2
1103: might seem a good way of recognizing
1104: a string in single quotes.
1105: But it is an invitation for the program to read far
1106: ahead, looking for a distant
1107: single quote.
1108: Presented with the input
1109: .P1 0
1110: \&'first' quoted string here, 'second' here
1111: .P2
1112: the above expression will match
1113: .P1 0
1114: \&'first' quoted string here, 'second'
1115: .P2
1116: which is probably not what was wanted.
1117: A better rule is of the form
1118: .P1 0
1119: \&'[^'\en]*'
1120: .P2
1121: which, on the above input, will stop
1122: after
1123: .I 'first' .
1124: The consequences
1125: of errors like this are mitigated by the fact
1126: that the
1127: .CW .
1128: operator will not match newline.
1129: Thus expressions like
1130: .CW .*
1131: stop on the
1132: current line.
1133: Don't try to defeat this with expressions like
1134: .CW [.\en]+
1135: or
1136: equivalents;
1137: the \*l generated program will try to read
1138: the entire input file, causing
1139: internal buffer overflows.
1140: .PP
1141: Note that \*l is normally partitioning
1142: the input stream, not searching for all possible matches
1143: of each expression.
1144: This means that each character is accounted for
1145: once and only once.
1146: For example, suppose it is desired to
1147: count occurrences of both
1148: .CW she
1149: and
1150: .CW he
1151: in an input text.
1152: Some \*l rules to do this might be
1153: .P1 0
1154: she s++;
1155: he h++;
1156: \en |
1157: \&. ;
1158: .P2
1159: where the last two rules ignore everything besides
1160: .CW he
1161: and
1162: .CW she .
1163: Remember that
1164: .CW .
1165: does not include newline.
1166: Since
1167: .CW she
1168: includes
1169: .CW he ,
1170: \*l will normally
1171: .I not
1172: recognize
1173: the instances of
1174: .CW he
1175: included in
1176: .CW she ,
1177: since once it has passed a
1178: .CW she
1179: those characters are gone.
1180: .PP
1181: Sometimes the user would like to override this choice. The action
1182: .I REJECT
1183: means ``go do the next alternative.''
1184: It causes whatever rule was second choice after the current
1185: rule to be executed.
1186: The position of the input pointer is adjusted accordingly.
1187: Suppose the user really wants to count the included instances of
1188: .CW he :
1189: .P1 0
1190: she {s++; REJECT;}
1191: he {h++; REJECT;}
1192: \en |
1193: \&. ;
1194: .P2
1195: these rules are one way of changing the previous example
1196: to do just that.
1197: After counting each expression, it is rejected; whenever appropriate,
1198: the other expression will then be counted. In this example, of course,
1199: the user could note that
1200: .CW she
1201: includes
1202: .CW he
1203: but not
1204: vice versa, and omit the
1205: .I REJECT
1206: action on
1207: .CW he ;
1208: in other cases, however, it
1209: would not be possible a priori to tell
1210: which input characters
1211: were in both classes.
1212: .PP
1213: Consider the two rules
1214: .P1 0
1215: a[bc]+ { ... ; REJECT;}
1216: a[cd]+ { ... ; REJECT;}
1217: .P2
1218: If the input is
1219: .CW ab ,
1220: only the first rule matches,
1221: and on
1222: .CW ad
1223: only the second matches.
1224: The input string
1225: .CW accb
1226: matches the first rule for four characters
1227: and then the second rule for three characters.
1228: In contrast, the input
1229: .CW accd
1230: agrees with
1231: the second rule for four characters and then the first
1232: rule for three.
1233: .PP
1234: In general, REJECT is useful whenever
1235: the purpose of \*l is not to partition the input
1236: stream but to detect all examples of some items
1237: in the input, and the instances of these items
1238: may overlap or include each other.
1239: Suppose a digram table of the input is desired;
1240: normally the digrams overlap, that is the word
1241: .CW the
1242: is considered to contain
1243: both
1244: .CW th
1245: and
1246: .CW he .
1247: Assuming a two-dimensional array named
1248: .I digram
1249: to be incremented, the appropriate
1250: source is
1251: .P1 0
1252: %%
1253: [a-z][a-z] {digram[yytext[0]][yytext[1]]++;
1254: REJECT;};
1255: \en ;
1256: .P2
1257: where the REJECT is necessary to pick up
1258: a letter pair beginning at every character, rather than at every
1259: other character.
1260: .NH
1261: \*L Source Definitions.
1262: .PP
1263: Remember the format of the \*l
1264: source:
1265: .P1 0
1266: {definitions}
1267: %%
1268: {rules}
1269: %%
1270: {user routines}
1271: .P2
1272: So far only the rules have been described. The user needs
1273: additional options,
1274: though, to define variables for use in his program and for use
1275: by \*l.
1276: These can go either in the definitions section
1277: or in the rules section.
1278: .PP
1279: Remember that \*l is turning the rules into a program.
1280: Any source not intercepted by \*l is copied
1281: into the generated program. There are three classes
1282: of such things.
1283: .IP 1)
1284: Any line which is not part of a \*l rule or action
1285: which begins with a blank or tab is copied into
1286: the \*l generated program.
1287: Such source input prior to the first
1288: .CW %%
1289: delimiter will be external
1290: to any function in the code; if it appears immediately after the first
1291: .CW %% ,
1292: it appears in an appropriate place for declarations
1293: in the function written by \*l which contains the actions.
1294: This material must look like program fragments,
1295: and should precede the first \*l rule.
1296: .IP
1297: As a side effect of the above, lines which begin with a blank
1298: or tab, and which contain a comment,
1299: are passed through to the generated program.
1300: This can be used to include comments in either the \*l source or
1301: the generated code. The comments should follow the host
1302: language convention.
1303: .IP 2)
1304: Anything included between lines containing
1305: only
1306: .CW %{
1307: and
1308: .CW %}
1309: is
1310: copied out as above. The delimiters are discarded.
1311: This format permits entering text like preprocessor statements that
1312: must begin in column 1,
1313: or copying lines that do not look like programs.
1314: .IP 3)
1315: Anything after the third
1316: .CW %%
1317: delimiter, regardless of formats, etc.,
1318: is copied out after the \*l output.
1319: .PP
1320: Definitions intended for \*l are given
1321: before the first
1322: .CW %%
1323: delimiter. Any line in this section
1324: not contained between
1325: .CW %{
1326: and
1327: .CW %} ,
1328: and beginning
1329: in column 1, is assumed to define \*l substitution strings.
1330: The format of such lines is
1331: .P1 0
1332: name translation
1333: .P2
1334: and it
1335: causes the string given as a translation to
1336: be associated with the name.
1337: The name and translation
1338: must be separated by at least one blank or tab, and the name must begin with a letter.
1339: The translation can then be called out
1340: by the {name} syntax in a rule.
1341: Using {D} for the digits and {E} for an exponent field,
1342: for example, might abbreviate rules to recognize numbers:
1343: .P1 0
1344: D [0-9]
1345: E [DEde][-+]?{D}+
1346: %%
1347: {D}+ printf("integer");
1348: {D}+"."{D}\(**({E})? |
1349: {D}\(**"."{D}+({E})? |
1350: {D}+{E} printf("real");
1351: .P2
1352: Note the first two rules for real numbers;
1353: both require a decimal point and contain
1354: an optional exponent field,
1355: but the first requires at least one digit before the
1356: decimal point and the second requires at least one
1357: digit after the decimal point.
1358: To correctly handle the problem
1359: posed by a Fortran expression such as
1360: .CW 35.EQ.I ,
1361: which does not contain a real number, a context-sensitive
1362: rule such as
1363: .P1 0
1364: [0-9]+/"."EQ printf("integer");
1365: .P2
1366: could be used in addition to the normal rule for integers.
1367: .PP
1368: The definitions
1369: section may also contain other commands, including the
1370: selection of a host language, a character set table,
1371: a list of start conditions, or adjustments to the default
1372: size of arrays within \*l itself for larger source programs.
1373: These possibilities
1374: are discussed below under ``Summary of Source Format,''
1375: section 12.
1376: .NH
1377: Usage.
1378: .PP
1379: There are two steps in
1380: compiling a \*l source program.
1381: First, the \*l source must be turned into a generated program
1382: in the host general purpose language.
1383: Then this program must be compiled and loaded, usually with
1384: a library of \*l subroutines.
1385: The generated program
1386: is on a file named
1387: .CW lex.yy.c .
1388: The I/O library is defined in terms of the C standard
1389: library|reference(stdio).
1390: .PP
1391: The library is accessed by the loader flag
1392: .CW -ll .
1393: So an appropriate
1394: set of commands is
1395: .P1 0
1396: lex source
1397: cc lex.yy.c -ll
1398: .P2
1399: The resulting program is placed on the usual file
1400: .CW a.out
1401: for later execution.
1402: To use \*l with \fIyacc\fP see below.
1403: Although the default \*l I/O routines use the C standard library,
1404: the \*l automata themselves do not do so;
1405: if private versions of
1406: .I input ,
1407: .I output
1408: and
1409: .I unput
1410: are given, the library can be avoided.
1411: .NH
1412: \*L and \fIyacc\fP.
1413: .PP
1414: If you want to use \*l with \fIyacc\fP, note that what \*l writes is a function
1415: named
1416: .I yylex ,
1417: the name required by \fIyacc\fP for its analyzer.
1418: Normally, the default main program on the \*l library
1419: calls this routine, but if \fIyacc\fP is loaded, and its main
1420: program is used, \fIyacc\fP will call
1421: .I yylex .
1422: In this case each \*l rule should end with
1423: .P1 0
1424: return(token);
1425: .P2
1426: where the appropriate token value is returned.
1427: An easy way to get access
1428: to \fIyacc\fP's names for tokens is to
1429: compile the \*l output file as part of
1430: the \fIyacc\fP output file by placing the line
1431: .P1 0
1432: #include "lex.yy.c"
1433: .P2
1434: in the last section of \fIyacc\fP input.
1435: Supposing the grammar to be
1436: named ``good'' and the lexical rules to be named ``better''
1437: the
1438: .UX
1439: command sequence can just be:
1440: .P1 0
1441: yacc good
1442: lex better
1443: cc y.tab.c -ly -ll
1444: .P2
1445: The \fIyacc\fP library
1446: .CW -ly ) (
1447: should be loaded before the \*l library,
1448: to obtain a main program which invokes the \fIyacc\fP parser.
1449: The generations of \*l and \fIyacc\fP programs can be done in
1450: either order.
1451: .NH
1452: Examples.
1453: .PP
1454: As a trivial problem, consider copying an input file while
1455: adding 3 to every positive number divisible by 7.
1456: Here is a suitable \*l source program
1457: .P1 0
1458: %%
1459: int k;
1460: [0-9]+ {
1461: k = atoi(yytext);
1462: if (k%7 == 0)
1463: printf("%d", k+3);
1464: else
1465: printf("%d",k);
1466: }
1467: .P2
1468: to do just that.
1469: The rule
1470: .CW [0-9]+
1471: recognizes strings of digits;
1472: .I atoi
1473: converts the digits to binary
1474: and stores the result in
1475: .I k .
1476: The operator
1477: .CW %
1478: (remainder) is used to check whether
1479: .I k
1480: is divisible by 7; if it is,
1481: it is incremented by 3 as it is written out.
1482: It may be objected that this program will alter such
1483: input items as
1484: .I 49.63
1485: or
1486: .I X7 .
1487: Furthermore, it increments the absolute value
1488: of all negative numbers divisible by 7.
1489: To avoid this, just add a few more rules after the active one,
1490: as here:
1491: .P1 0
1492: %%
1493: int k;
1494: -?[0-9]+ {
1495: k = atoi(yytext);
1496: printf("%d", k%7 == 0 ? k+3 : k);
1497: }
1498: -?[0-9.]+ ECHO;
1499: [A-Za-z][A-Za-z0-9]+ ECHO;
1500: .P2
1501: Numerical strings containing a
1502: .CW .
1503: or preceded by a letter will be picked up by
1504: one of the last two rules, and not changed.
1505: The
1506: .I if-else
1507: has been replaced by
1508: a C conditional expression to save space;
1509: the form
1510: .CW a?b:c
1511: means ``if
1512: .CW a
1513: then
1514: .CW b
1515: else
1516: .CW c .
1517: .PP
1518: For an example of statistics gathering, here
1519: is a program which histograms the lengths
1520: of words, where a word is defined as a string of letters.
1521: .P1 0
1522: int lengs[100];
1523: %%
1524: [a-z]+ lengs[yyleng]++;
1525: \&. |
1526: \en ;
1527: %%
1528: .P3
1529: yywrap()
1530: {
1531: int i;
1532: printf("Length No. words\en");
1533: for(i=0; i<100; i++)
1534: if (lengs[i] > 0)
1535: printf("%5d%10d\en",i,lengs[i]);
1536: return(1);
1537: }
1538: .P2
1539: This program
1540: accumulates the histogram, while producing no output. At the end
1541: of the input it prints the table.
1542: The final statement
1543: .CW return(1)
1544: indicates that \*l is to perform wrapup. If
1545: .I yywrap
1546: returns zero (false)
1547: it implies that further input is available
1548: and the program is
1549: to continue reading and processing.
1550: To provide a
1551: .I yywrap
1552: that never
1553: returns true causes an infinite loop.
1554: .PP
1555: As a larger example,
1556: here are some parts of a program written by N. L. Schryer
1557: to convert double precision Fortran to single precision Fortran.
1558: Because Fortran does not distinguish upper and lower case letters,
1559: this routine begins by defining a set of classes including
1560: both cases of each letter:
1561: .P1 0
1562: a [aA]
1563: b [bB]
1564: c [cC]
1565: \&...
1566: z [zZ]
1567: .P2
1568: An additional class recognizes white space:
1569: .P1 0
1570: W [ \et]*
1571: .P2
1572: The first rule changes
1573: ``double precision'' to ``real'', or ``DOUBLE PRECISION'' to ``REAL''.
1574: .P1 0
1575: {d}{o}{u}{b}{l}{e}{W}\e
1576: {p}{r}{e}{c}{i}{s}{i}{o}{n} {
1577: printf(yytext[0]=='d'? "real" : "REAL");
1578: }
1579: .P2
1580: Care is taken throughout this program to preserve the case
1581: (upper or lower)
1582: of the original program.
1583: The conditional operator is used to
1584: select the proper form of the keyword.
1585: The next rule copies continuation card indications to
1586: avoid confusing them with constants:
1587: .P1 0
1588: ^" "[^ 0] ECHO;
1589: .P2
1590: In the regular expression, the quotes surround the
1591: blanks.
1592: It is interpreted as
1593: ``beginning of line, then five blanks, then
1594: anything but blank or zero.''
1595: Note the two different meanings of
1596: .CW ^ .
1597: There follow some rules to change double precision
1598: constants to ordinary floating constants.
1599: .P1 0
1600: [0-9]+{W}{d}{W}[+-]?{W}[0-9]+ |
1601: [0-9]+{W}"."{W}{d}{W}[+-]?{W}[0-9]+ |
1602: "."{W}[0-9]+{W}{d}{W}[+-]?{W}[0-9]+ {
1603: /* convert constants */
1604: for(p=yytext; *p != 0; p++)
1605: {
1606: if (*p == 'd' || *p == 'D')
1607: *p =+ 'e'- 'd';
1608: ECHO;
1609: }
1610: .P2
1611: After the floating point constant is recognized, it is
1612: scanned by the
1613: .I for
1614: loop
1615: to find the letter
1616: .CW d
1617: or
1618: .CW D .
1619: The program then adds
1620: .CW 'e'-'d' ,
1621: which converts
1622: it to the next letter of the alphabet.
1623: The modified constant, now single-precision,
1624: is written out again.
1625: There follow a series of names which must be respelled to remove
1626: their initial \fId\fR.
1627: By using the
1628: array
1629: .I yytext
1630: the same action suffices for all the names (only a sample of
1631: a rather long list is given here).
1632: .P1 0
1633: {d}{s}{i}{n} |
1634: {d}{c}{o}{s} |
1635: {d}{s}{q}{r}{t} |
1636: {d}{a}{t}{a}{n} |
1637: \&...
1638: {d}{f}{l}{o}{a}{t} printf("%s",yytext+1);
1639: .P2
1640: Another list of names must have initial \fId\fR changed to initial \fIa\fR:
1641: .P1 0
1642: {d}{l}{o}{g} |
1643: {d}{l}{o}{g}10 |
1644: {d}{m}{i}{n}1 |
1645: {d}{m}{a}{x}1 {
1646: yytext[0] =+ 'a' - 'd';
1647: ECHO;
1648: }
1649: .P2
1650: And one routine
1651: must have initial \fId\fR changed to initial \fIr\fR:
1652: .P1 0
1653: {d}1{m}{a}{c}{h} {
1654: yytext[0] =+ 'r' - 'd';
1655: ECHO;
1656: }
1657: .P2
1658: To avoid such names as \fIdsinx\fR being detected as instances
1659: of \fIdsin\fR, some final rules pick up longer words as identifiers
1660: and copy some surviving characters:
1661: .P1 0
1662: [A-Za-z][A-Za-z0-9]* |
1663: [0-9]+ |
1664: \en |
1665: \&. ECHO;
1666: .P2
1667: Note that this program is not complete; it
1668: does not deal with the spacing problems in Fortran or
1669: with the use of keywords as identifiers.
1670: .NH
1671: Left Context Sensitivity.
1672: .PP
1673: Sometimes
1674: it is desirable to have several sets of lexical rules
1675: to be applied at different times in the input.
1676: For example, a compiler preprocessor might distinguish
1677: preprocessor statements and analyze them differently
1678: from ordinary statements.
1679: This requires
1680: sensitivity
1681: to prior context, and there are several ways of handling
1682: such problems.
1683: The
1684: .CW ^
1685: operator, for example, is a prior context operator,
1686: recognizing immediately preceding left context just as
1687: .CW $
1688: recognizes
1689: immediately following right context.
1690: Adjacent left context could be extended, to produce a facility similar to
1691: that for adjacent right context, but it is unlikely
1692: to be as useful, since often the relevant left context
1693: appeared some time earlier, such as at the beginning of a line.
1694: .PP
1695: This section describes three means of dealing
1696: with different environments: a simple use of flags,
1697: when only a few rules change from one environment to another,
1698: the use of
1699: .I
1700: start conditions
1701: .R
1702: on rules,
1703: and the possibility of making multiple lexical analyzers all run
1704: together.
1705: In each case, there are rules which recognize the need to change the
1706: environment in which the
1707: following input text is analyzed, and set some parameter
1708: to reflect the change. This may be a flag explicitly tested by
1709: the user's action code; such a flag is the simplest way of dealing
1710: with the problem, since \*l is not involved at all.
1711: It may be more convenient,
1712: however,
1713: to have \*l remember the flags as initial conditions on the rules.
1714: Any rule may be associated with a start condition. It will only
1715: be recognized when \*l is in
1716: that start condition.
1717: The current start condition may be changed at any time.
1718: Finally, if the sets of rules for the different environments
1719: are very dissimilar,
1720: clarity may be best achieved by writing several distinct lexical
1721: analyzers, and switching from one to another as desired.
1722: .PP
1723: Consider the following problem: copy the input to the output,
1724: changing the word \fImagic\fR to \fIfirst\fR on every line which began
1725: with the letter \fIa\fR, changing \fImagic\fR to \fIsecond\fR on every line
1726: which began with the letter \fIb\fR, and changing
1727: \fImagic\fR to \fIthird\fR on every line which began
1728: with the letter \fIc\fR. All other words and all other lines
1729: are left unchanged.
1730: .PP
1731: These rules are so simple that the easiest way
1732: to do this job is with a flag:
1733: .P1 0
1734: int flag;
1735: %%
1736: ^a {flag = 'a'; ECHO;}
1737: ^b {flag = 'b'; ECHO;}
1738: ^c {flag = 'c'; ECHO;}
1739: \en {flag = 0 ; ECHO;}
1740: magic {
1741: switch (flag)
1742: {
1743: case 'a': printf("first"); break;
1744: case 'b': printf("second"); break;
1745: case 'c': printf("third"); break;
1746: default: ECHO; break;
1747: }
1748: }
1749: .P2
1750: should be adequate.
1751: .PP
1752: To handle the same problem with start conditions, each
1753: start condition must be introduced to \*l in the definitions section
1754: with a line reading
1755: .P1 0
1756: %Start name1 name2 ...
1757: .P2
1758: where the conditions may be named in any order.
1759: The word \fIStart\fR may be abbreviated to \fIs\fR or \fIS\fR.
1760: The conditions may be referenced at the
1761: head of a rule with the
1762: .CW <>
1763: brackets:
1764: .P1 0
1765: <name1>expression
1766: .P2
1767: is a rule which is only recognized when \*l is in the
1768: start condition \fIname1\fR.
1769: To enter a start condition,
1770: execute the action statement
1771: .P1 0
1772: BEGIN name1;
1773: .P2
1774: which changes the start condition to \fIname1\fR.
1775: To resume the normal state,
1776: .P1 0
1777: BEGIN 0;
1778: .P2
1779: resets the initial condition
1780: of the \*l automaton interpreter.
1781: A rule may be active in several
1782: start conditions:
1783: .P1 0
1784: <name1,name2,name3>
1785: .P2
1786: is a legal prefix. Any rule not beginning with the
1787: .CW <>
1788: prefix operator is always active.
1789: .PP
1790: The same example as before can be written:
1791: .P1 0
1792: %START AA BB CC
1793: %%
1794: ^a {ECHO; BEGIN AA;}
1795: ^b {ECHO; BEGIN BB;}
1796: ^c {ECHO; BEGIN CC;}
1797: \en {ECHO; BEGIN 0;}
1798: <AA>magic printf("first");
1799: <BB>magic printf("second");
1800: <CC>magic printf("third");
1801: .P2
1802: where the logic is exactly the same as in the previous
1803: method of handling the problem, but \*l does the work
1804: rather than the user's code.
1805: .NH
1806: Character Set.
1807: .PP
1808: The programs generated by \*l handle
1809: character I/O only through the routines
1810: .I input ,
1811: .I output ,
1812: and
1813: .I unput .
1814: Thus the character representation
1815: provided in these routines
1816: is accepted by \*l and employed to return
1817: values in
1818: .I yytext .
1819: For internal use
1820: a character is represented as a small integer
1821: which, if the standard library is used,
1822: has a value equal to the integer value of the bit
1823: pattern representing the character on the host computer.
1824: Normally, the letter
1825: .CW a
1826: is represented as the same form as the character constant
1827: .CW 'a' .
1828: If this interpretation is changed, by providing I/O
1829: routines which translate the characters,
1830: \*l must be told about
1831: it, by giving a translation table.
1832: This table must be in the definitions section,
1833: and must be bracketed by lines containing only
1834: .CW %T .
1835: The table contains lines of the form
1836: .P1 0
1837: {integer} {character string}
1838: .P2
1839: which indicate the value associated with each character.
1840: .KF
1841: .P1 0
1842: %T
1843: 1 Aa
1844: 2 Bb
1845: \&...
1846: 26 Zz
1847: 27 \en
1848: 28 +
1849: 29 -
1850: 30 0
1851: 31 1
1852: \&...
1853: 39 9
1854: %T
1855: .P2
1856: .sp
1857: .ce 1
1858: Sample character table.
1859: .KE
1860: Thus the next example
1861: maps the lower and upper case letters together into the integers 1 through 26,
1862: newline into 27, + and - into 28 and 29, and the
1863: digits into 30 through 39.
1864: Note the escape for newline.
1865: If a table is supplied, every character that is to appear either
1866: in the rules or in any valid input must be included
1867: in the table.
1868: No character
1869: may be assigned the number 0, and no character may be
1870: assigned a bigger number than the size of the hardware character set.
1871: .NH
1872: Summary of Source Format.
1873: .PP
1874: The general form of a \*l source file is:
1875: .P1
1876: {definitions}
1877: %%
1878: {rules}
1879: %%
1880: {user subroutines}
1881: .P2
1882: The definitions section contains
1883: a combination of
1884: .IP 1)
1885: Definitions, in the form ``name space translation''.
1886: .IP 2)
1887: Included code, in the form ``space code''.
1888: .IP 3)
1889: Included code, in the form
1890: .P1
1891: %{
1892: code
1893: %}
1894: .P2
1895: .ns
1896: .IP 4)
1897: Start conditions, given in the form
1898: .P1
1899: %S name1 name2 ...
1900: .P2
1901: .ns
1902: .IP 5)
1903: Character set tables, in the form
1904: .P1
1905: %T
1906: number space character-string
1907: \&...
1908: %T
1909: .P2
1910: .ns
1911: .IP 6)
1912: Changes to internal array sizes, in the form
1913: .SP .5
1914: %\fIx\fP \fInnn
1915: .SP .5
1916: where \fInnn\fR is a decimal integer representing an array size
1917: and \fIx\fR selects the parameter as follows:
1918: .TS
1919: center;
1920: c c
1921: cFCW l.
1922: Letter Parameter
1923: p positions
1924: n states
1925: e tree nodes
1926: a transitions
1927: k packed character classes
1928: o output array size
1929: .TE
1930: .LP
1931: Lines in the rules section have the form ``expression action''
1932: where the action may be continued on succeeding
1933: lines by using braces to delimit it.
1934: .PP
1935: Regular expressions in \*l use the following
1936: operators:
1937: .TS
1938: center;
1939: lFCW l.
1940: x the character "x"
1941: "x" an "x", even if x is an operator.
1942: \ex an "x", even if x is an operator.
1943: [xy] the character x or y.
1944: [x-z] the characters x, y or z.
1945: [^x] any character but x.
1946: \&. any character but newline.
1947: ^x an x at the beginning of a line.
1948: <y>x an x when \*l is in start condition y.
1949: x$ an x at the end of a line.
1950: x? an optional x.
1951: x* 0,1,2, ... instances of x.
1952: x+ 1,2,3, ... instances of x.
1953: x|y an x or a y.
1954: (x) an x.
1955: x/y an x but only if followed by y.
1956: {xx} the translation of xx from the
1957: definitions section.
1958: x{m,n} \fIm\fR through \fIn\fR occurrences of x
1959: .TE
1960: .NH
1961: Caveats and Bugs.
1962: .PP
1963: There are pathological expressions which
1964: produce exponential growth of the tables when
1965: converted to deterministic machines;
1966: fortunately, they are rare.
1967: .PP
1968: REJECT does not rescan the input; instead it remembers the results of the previous
1969: scan. This means that if a rule with trailing context is found, and
1970: REJECT executed, the user
1971: must not have used
1972: .I unput
1973: to change the characters forthcoming
1974: from the input stream.
1975: This is the only restriction on the user's ability to manipulate
1976: the not-yet-processed input.
1977: .NH
1978: Acknowledgments.
1979: .PP
1980: As should
1981: be obvious from the above, the outside of \*l
1982: is patterned
1983: on \fIyacc\fP and the inside on Aho's string matching routines.
1984: Therefore, both S. C. Johnson and A. V. Aho
1985: are really originators
1986: of much of \*l,
1987: as well as debuggers of it.
1988: Many thanks are due to both.
1989: .PP
1990: The code of the current version of \*l was designed, written,
1991: and debugged by Eric Schmidt.
1992: .NH
1993: References.
1994: .LP
1995: |reference_placement
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.