![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lexgen.doc CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / sml / lib / lexgen|
Return to lexgen.doc CVS log | Up to [Research Unix] / researchv10dc / cmd / sml / lib / lexgen |
1.1 root 1: A lexical analyzer generator for Standard ML.
2:
3:
4: Andrew W. Appel
5: James S. Mattson
6: David R. Tarditi
7:
8: Princeton University
9:
10: Version 1.2, October 1989
11:
12: Copyright (c) 1989 by Andrew W. Appel, James S. Mattson, David R. Tarditi
13:
14: This software comes with ABSOLUTELY NO WARRANTY.
15: This software is subject only to the PRINCETON STANDARD ML SOFTWARE LIBRARY
16: COPYRIGHT NOTICE, LICENSE AND DISCLAIMER, (in the file "COPYRIGHT",
17: distributed with this software). You may copy and distribute this software;
18: see the COPYRIGHT NOTICE for details and restrictions.
19:
20: I. General Description
21:
22: Computer programs often need to divide their input into words and
23: distinguish between different kinds of words. Compilers, for
24: example, need to distinguish between integers, reserved words, and
25: identifiers. Applications programs often need to be able to
26: recognize components of typed commands from users.
27:
28: The problem of segmenting input into words and recognizing classes of
29: words is known as lexical analysis. Small cases of this problem,
30: such as reading text strings separated by spaces, can be solved by
31: using hand-written programs. Larger cases of this problem, such as
32: tokenizing an input stream for a compiler, can also be solved using
33: hand-written programs.
34:
35: A hand-written program for a large lexical analysis problem, however,
36: suffers from two major problems. First, the program requires a fair
37: amount of programmer time to create. Second, the description of
38: classes of words is not explicit in the program. It must be inferred
39: from the program code. This makes it difficult to verify if the
40: program recognizes the correct words for each class. It also makes
41: future maintenance of the program difficult.
42:
43: Lex, a programming tool for the Unix system, is a successful solution
44: to the general problem of lexical analysis. It uses regular
45: expressions to describe classes of words. A program fragment is
46: associated with each class of words. This information is given to
47: Lex as a specification (a Lex program). Lex produces a program for a
48: function that can be used to perform lexical analysis.
49:
50: The function operates as follows. It finds the longest word starting
51: from the current position in the input stream that is in one of the
52: word classes. It executes the program fragment associated with the
53: class, and sets the current position in the input stream to be the
54: character after the word. The program fragment has the actual text
55: of the word available to it, and may be any piece of code. For many
56: applications it returns some kind of value.
57:
58: Lex allows the programmer to make the language description explicit,
59: and to concentrate on what to do with the recognized words, not how
60: to recognize the words. It saves programmer time and increases
61: program maintainability.
62:
63: Unfortunately, Lex is targeted only C. It also places artificial
64: limits on the size of strings that can be recognized.
65:
66: ML-Lex is a variant of Lex for the ML programming language. ML-Lex
67: has a syntax similar to Lex, and produces an ML program instead of a
68: C program. ML-Lex produces a program that runs very efficiently.
69: Typically the program will be as fast or even faster than a
70: hand-coded lexer implemented in Standard ML.
71:
72: The program typically uses only a small amount of space.
73: ML-Lex thus allows ML programmers the same benefits that Lex allows C
74: programmers. It also does not place artificial limits on the size of
75: recognized strings.
76:
77: II. ML-Lex specifications
78:
79: An ML-Lex specification has the general format:
80:
81: {user declarations}
82: %%
83: {ML-Lex definitions}
84: %%
85: {rules}
86:
87: Each section is separated from the others by a '%%' delimiter.
88:
89: The rules are used to define the lexical analysis function. Each
90: rule has two parts - a regular expression and an action. The regular
91: expression defines the word class that a rule matches. The action is
92: a program fragment to be executed when a rule matches the input. The
93: actions are used to compute values, and must all return values of the
94: same type.
95:
96: The user can define values available to all rule actions in the user
97: declarations section. The user must define two values in this
98: section - a type lexresult and a function eof. Lexresult defines the
99: type of values returned by the rule actions. The function "eof" is
100: called by the lexer when the end of the input stream is reached. It
101: will typically return a value signalling eof or raise an exception.
102: It is called with the same argument as lex (see %arg, below),
103: and must return a value of type lexresult.
104:
105: In the definitions section, the user can define named regular
106: expressions, a set of start states, and specify which of the various
107: bells and whistles of ML-Lex are desired.
108:
109: The start states allow the user to control when certain rules are
110: matched. Rules may be defined to match only when the lexer is in
111: specific start states. The user may change the lexer's start state
112: in a rule action. This allows the user to specify special handling
113: of lexical objects.
114:
115: This feature is typically used to handle quoted strings with escapes
116: to denote special characters. The rules to recognize the inside
117: contents of a string are defined for only one start state. This
118: start state is entered when the beginning of a string is recognized,
119: and exited when the end of the string is recognized.
120:
121: III. Regular expressions.
122:
123: Regular expressions are a simple language for denoting classes of
124: strings. A regular expression is defined inductively over an
125: alphabet with a set of basic operations. The alphabet for ML-Lex is
126: the Ascii character set (character codes 0-127; or if %full is used, 0-255).
127:
128: The syntax and semantics of regular expressions will be described in
129: order of decreasing precedence (from the most tightly-binding operators
130: to the most weakly-binding):
131:
132: An individual character stands for itself, except for the
133: reserved characters ? * + | ( ) ^ $ / ; . = < > [ { " \
134:
135: A backslash followed by one of the reserved characters stands
136: for that character.
137:
138: A set of characters enclosed in square brackets [ ] stands
139: for any one of those characters. Inside the brackets, only
140: the symbols \ - ^ are reserved. An initial up-arrow ^ stands
141: for the complement of the characters listed, e.g. [^abc]
142: stands any character except a, b, or c. The hyphen - denotes
143: a range of characters, e.g. [a-z] stands for any lower-case
144: alphabetic character, and [0-9a-fA-F] stands for any hexadecimal
145: digit. To include ^ literally in a bracketed set, put it anywhere
146: but first; to include - literally in a set, put it first or last.
147:
148: The dot . character stands for any character except newline,
149: i.e. the same as [^\n]
150:
151: The following special escape sequences are available, inside
152: or outside of square-brackets:
153: \b - backspace
154: \n - newline
155: \t - tab
156: \ddd - where ddd is a 3 digit decimal escape.
157:
158: A sequence of characters will stand for itself (reserved
159: characters will be taken literally) if it is enclosed in
160: double quotes " ".
161:
162: A named regular expression (defined in the "definitions"
163: section) may be referred to by enclosing its name in
164: braces { }.
165:
166: Any regular expression may be enclosed in parentheses ( )
167: for syntactic (but, as usual, not semantic) effect.
168:
169: The postfix operator * stands for Kleene closure:
170: zero or more repetitions of the preceding expression.
171:
172: The postfix operator + stands for one or more repetitions
173: of the preceding expression.
174:
175: The postfix operator ? stands for zero or one occurrence of
176: the preceding expression.
177:
178: A postfix repetition range {n1,n2} where n1 and n2 are small
179: integers stands for any number of repetitions between n1 and n2
180: of the preceding expression. The notation {n1} stands for
181: exactly n1 repetitions.
182:
183: Concatenation of expressions denotes concatenation of strings.
184: The expression e1 e2 stands for any string that results from
185: the concatenation of one string that matches e1 with another
186: string that matches e2.
187:
188: The infix operator | stands for alternation. The expression
189: e1 | e2 stands for anything that either e1 or e2 stands for.
190:
191: The infix operator / denotes lookahead. The expression e1 / e2
192: matches any string that e1 stands for, but only when that
193: string is followed by a string that matches e2.
194:
195: When the up-arrow ^ occurs at the beginning of an expression,
196: that expression will only match strings that occur at the
197: beginning of a line (right after a newline character).
198: When the dollar sign $ occurs at the end of an expression,
199: that expression will only match strings that occur at the
200: end of a line (right before a newline character).
201:
202: Here are some examples of regular expressions, and descriptions of the
203: set of strings they denote:
204:
205: 0 | 1 | 2 | 3 A single digit between 0 and 3
206: [0123] A single digit between 0 and 3
207: 0123 The string "0123"
208: 0* All strings of 0 or more 0's
209: 00* All strings of 1 or more 0's
210: 0+ All strings of 1 or more 0's
211: [0-9]{3} Any three-digit decimal number.
212: \\[ntb] The strings "\n" "\t" "\b"
213: (00)* Any string with an even number of 0's.
214:
215: IV. ML-Lex syntax summary
216:
217: A. User declarations
218:
219: Anything up to the first %% is in the user declarations section. The
220: user should note that no symbolic identifier containing '%%' can be
221: used in this section.
222:
223: B. ML-Lex definitions
224:
225: Start states can be defined with
226:
227: %s {identifier list} ;
228:
229: or %S {identifier list} ;
230:
231: An identifier list consists of one or more identifiers.
232:
233: An identifier consists of one or more letters, digits, underscores,
234: or primes. It must begin with a letter.
235:
236: Named expressions can be defined with
237:
238: {identifier} = {regular expression} ;
239:
240: Regular expressions are defined below.
241:
242: The following % commands are also available:
243:
244: %reject - create REJECT() function
245: %count - count newlines using yylineno
246: %full - create lexer for the full 8-bit character set,
247: with characters in the range 0-255 permitted
248: as input.
249: %structure {identifier} - name the structure in the output program
250: {identifier} instead of Mlex
251: %header - use code following it to create header for lexer
252: structure
253: %arg - extra (curried) formal parameter argument to be
254: passed to the lex functions, and to be passed
255: to the eof function in place of ()
256: These functions are discussed below, under values available to
257: actions.
258:
259: C. Rules
260:
261: Each rule has the format:
262:
263: <start state list> {regular expression} => ( ... code ... );
264:
265: All parentheses in ... code ... must be balanced, including those
266: used in strings and comments.
267:
268: The start state list is optional. It consists of a list of
269: identifiers separated by commas, and is delimited by triangle
270: brackets < >. Each identifier must be a start state defined in the
271: %s section above.
272:
273: The regular expression is only recognized when the lexer is in one of
274: the start states in the start state list. If no start state list is
275: given, the expression is recognized in all start states.
276:
277: The lexer begins in a pre-defined start state called INITIAL.
278:
279: The lexer resolves conflicts among rules by choosing the rule with
280: the longest match, and in the case two rules match the same string,
281: choosing the rule listed first in the specification.
282:
283: The rules should match all possible input. If some input occurs that
284: does not match any rule, the lexer created by ML-Lex will raise an
285: exception LexError. Note that this differs from C Lex, which prints
286: any unmatched input on the standard output.
287:
288: V. Values available inside the code associated with a rule.
289:
290: Mlex places the value of the string matched by a regular expression
291: in yytext. Yytext has type string. The user may also recursively
292: call the lexing function with lex().
293:
294: This is convenient for ignoring white space or comments silently:
295:
296: [\ \t\n]+ => ( lex());
297:
298: To switch start states, the user may call YYBEGIN with the name of a
299: start state.
300:
301: The following values will be available only if the corresponding %
302: command is in the ML-Lex definitions sections:
303:
304: value %command description
305: ----- -------- -----------
306: REJECT %reject REJECT() causes the current
307: rule to be "rejected."
308: The lexer behaves as if the
309: current rule had not matched;
310: another rule that matches this
311: string, or that matches the longest
312: possible prefix of this string,
313: is used instead.
314:
315: yylineno %count Current line number
316:
317:
318: These values should be used only if necessary. Adding REJECT to a
319: lexer will slow it down by 20%; adding yylineno will slow it down by
320: another 20%, or more. (It is much more efficient to recognize \n and
321: have an action that increments the line-number variable.) The use of
322: the lookahead operator / will also slow down the entire lexer.
323:
324: VI. Running ML-Lex
325:
326: Use "lexgen.sml"; this will create a structure LexGen. The function
327: LexGen.lexGen creates a program for a lexer from an input
328: specification. It takes a string argument -- the name of the file
329: containing the input specification. The output file name is
330: determined by appending ".sml" to the input file name.
331:
332: VII. Using the program produced by ML-Lex.
333:
334: When the output file is loaded, it will create a structure Mlex that
335: contains the function makeLexer. makeLexer takes a function from int
336: -> string and returns a lexing function.
337:
338: For example,
339:
340: val lexer = Mlex.makeLexer (input (open_in "f"))
341:
342: creates a lexer that operates on the file whose name is f.
343:
344: The function from int -> string should read a string of characters
345: from the input stream. It should return a null string to indicate
346: that the end of the stream has been reached. The integer is the
347: number of characters that the lexer wishes to read; the function may
348: return any non-zero number of characters. For example,
349: val lexer = Mlex.makeLexer (fn n => input_line std_in)
350: is appropriate for interactive streams where prompting, etc. occurs;
351: the lexer won't care that input_line might return a string of more
352: than or less than n characters.
353:
354: The lexer tries to read a large number of characters from the input
355: function at once, and it is desirable that the input function return
356: as many as possible. Reading many characters at once makes the lexer
357: more efficient. Fewer input calls and buffering operations are
358: needed, and input is more efficient in large block reads. For
359: interactive streams this is less of a concern, as the limiting factor
360: is the speed at which the user can type.
361:
362: To obtain a value, invoke the lexer by passing it a unit:
363:
364: val nextToken = lexer()
365:
366: If one wanted to restart the lexer, one would just discard "lexer"
367: and create a new lexer on the same stream with another call to
368: makeLexer. This is the best way to discard any characters buffered
369: internally by the lexer.
370:
371: All code in the user declarations section is placed inside a
372: structure UserDeclarations. To access this structure, use the path name
373: Mlex.UserDeclarations.
374:
375: If any input cannot be matched, the program will raise the exception
376: Mlex.LexError. An internal error (i.e. bug) will cause the
377: exception Internal.LexerError to be raised.
378:
379: If %structure is used, remember that the structure name will no
380: longer be Mlex, but the one specified in the command.
381:
382: VIII. Sample
383:
384: Here is a sample lexer for a calculator program:
385:
386: datatype lexresult= DIV | EOF | EOS | ID of string | LPAREN |
387: NUM of int | PLUS | PRINT | RPAREN | SUB | TIMES
388:
389: val linenum = ref 1
390: val error = fn x => output std_out (x ^ "\n")
391: val eof = fn () => EOF
392: %%
393: %structure CalcLex
394: alpha=[A-Za-z];
395: digit=[0-9];
396: ws = [\ \t];
397: %%
398: \n => (inc linenum; lex());
399: {ws}+ => (lex());
400: "/" => (DIV);
401: ";" => (EOS);
402: "(" => (LPAREN);
403: {digit}+ => (NUM (revfold (fn(a,r)=>ord(a)-ord("0")+10*r) (explode yytext) 0));
404: ")" => (RPAREN);
405: "+" => (PLUS);
406: {alpha}+ => (if yytext="print" then PRINT else ID yytext);
407: "-" => (SUB);
408: "*" => (TIMES);
409: . => (error ("calc: ignoring bad character "^yytext); lex());
410:
411:
412: Here is the parser for the calculator:
413:
414: (* Sample interactive calculator to demonstrate use of lexer produced by ML-Lex
415:
416: The original grammar was
417:
418: stmt_list -> stmt_list stmt
419: stmt -> print exp ; | exp ;
420: exp -> exp + t | exp - t | t
421: t -> t * f | t/f | f
422: f -> (exp) | id | num
423:
424: The function parse takes a stream and parses it for the calculator
425: program.
426:
427: If a syntax error occurs, parse prints an error message and calls itself
428: on the stream. On this system that has the effect of ignoring all input
429: to the end of a line.
430: *)
431:
432: structure Calc =
433: struct
434: open CalcLex
435: open UserDeclarations
436: exception Error
437: fun parse strm =
438: let
439: val say = output std_out
440: val lexer = makeLexer (fn n => input strm (min(1,max(can_input strm,n))))
441: val nexttok = ref (lexer())
442: val advance = fn () => (nexttok := lexer(); !nexttok)
443: val error = fn () => (say ("calc: syntax error on line" ^
444: (makestring(!linenum)) ^ "\n"); raise Error)
445: val lookup = fn i =>
446: if i = "ONE" then 1
447: else if i = "TWO" then 2
448: else (say ("calc: unknown identifier '" ^ i ^ "'\n"); raise Error)
449: fun STMT_LIST () =
450: case !nexttok of
451: EOF => ()
452: | _ => (STMT(); STMT_LIST())
453:
454: and STMT() =
455: (case !nexttok
456: of EOS => ()
457: | PRINT => (advance(); say ((makestring (E():int)) ^ "\n"); ())
458: | _ => (E(); ());
459: case !nexttok
460: of EOS => (advance())
461: | _ => error())
462: and E () = E' (T())
463: and E' (i : int ) =
464: case !nexttok of
465: PLUS => (advance (); E'(i+T()))
466: | SUB => (advance (); E'(i-T()))
467: | RPAREN => i
468: | EOF => i
469: | EOS => i
470: | _ => error()
471: and T () = T'(F())
472: and T' i =
473: case !nexttok of
474: PLUS => i
475: | SUB => i
476: | TIMES => (advance(); T'(i*F()))
477: | DIV => (advance (); T'(i div F()))
478: | EOF => i
479: | EOS => i
480: | RPAREN => i
481: | _ => error()
482: and F () =
483: case !nexttok of
484: ID i => (advance(); lookup i)
485: | LPAREN =>
486: let val v = (advance(); E())
487: in if !nexttok = RPAREN then (advance (); v) else error()
488: end
489: | NUM i => (advance(); i)
490: | _ => error()
491: in STMT_LIST () handle Error => parse strm
492: end
493: end
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.