Return to lex.ms CVS log

Up to [Research Unix] / researchv10dc / vol2 / lex

Annotation of researchv10dc/vol2/lex/lex.ms, revision 1.1

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.