You are looking at historical revision 20339 of this page. It may differ significantly from its current revision.



lexgen is a lexer generator comprised in its core of only five small procedures that can be combined to form pattern matchers.

A pattern matcher procedure takes a list of streams, and returns a new list of streams advanced by every combination allowed by the pattern.

A stream is defined as a list that contains a list of characters

consumed by the pattern matcher, and a list of characters not yet consumed. E.g., the list

 ((#\a) (#\b #\c #\d #\e))

represents a stream that contains the consumed character a, and the unconsumed characters b c d e.

Note that the number of streams returned by a pattern matcher may not match the number of streams passed in. If the pattern doesn't match at all, the empty list is returned.

Library Procedures

Every combinator procedure in this library returns a procedure that takes in a continuation procedure and a list of streams as arguments.

Basic procedures

[procedure] (seq MATCHER1 MATCHER2) => MATCHER

seq builds a matcher that matches a sequence of patterns.

[procedure] (bar MATCHER1 MATCHER2) => MATCHER

bar matches either of two patterns. It's analogous to patterns separated by | in traditional regular expressions.

[procedure] (star MATCHER) => MATCHER

star is an implementation of the Kleene closure. It is analogous to * in traditional regular expressions.

[procedure] (star* MATCHER) => MATCHER

Greedy Kleene closure matching.

[procedure] (redo P Q R) => MATCHER

If matcher P fails (returns an empty list), then invoke matcher Q on the original input stream, otherwise invoke R on the result of P.

Token procedure

[procedure] (tok <Input>) => (LAMBDA TOKEN PROC) => MATCHER

Procedure tok builds pattern matchers based on character comparison operations. It is intended for matching input sequences of arbitrary kinds, e.g. character lists, strings, or other kinds of sequences. To achieve abstraction over the input sequence kind, tok is parameterised on a type class named <Input>. Please see libraries typeclass and input-classes for information on the type class interface.

As an example, the code below creates an input class for character lists and defines a version of tok specialized for character lists.

(require-extension typeclass input-classes)

(define char-list-<Input>
  (make-<Input> null? car cdr))

(define char-list-tok (tok <char-list-<Input>))

Once applied to an input class, tok builds a pattern matcher that, for each stream given, applies a procedure to the given token TOKEN and an input character. If the procedure returns a true value, that value is prepended to the list of consumed elements, and the input character is removed from the list of input elements.

This library provides several procedures for character matching based on the tok procedure. These procedures are enumerated as the fields of another typeclas, <CharLex>, which inherits from the <Token> typeclass:

 (define-class <CharLex> (<Token> T)  char set range lit)

The <Token> typeclass inherits from the <Input> typeclass and contains only the tok field:

 (define-class <Token> (<Input> input)  tok)

This library provides convenience functions to create instances of CharLex based on different input typeclasses:

[procedure] (Input->Token INPUT-CLASS => TOKEN-CLASS)

This procedure takes an instance of the <Input> typeclass, created by the make-<Instance> constructor shown above, and returns an instance of the <Token> typeclass, which in turn contains an instance of tok specialized for the given input class.

[procedure] (Token->CharLex TOKEN-CLASS => CHARLEX-CLASS)

This procedure takes an instance of the <Token> typeclass, and returns an instance of the CharLex typeclass, which contains the following procedures:

[procedure] (char CHAR) => MATCHER

Matches a single character.

[procedure] (set CHAR-SET) => MATCHER

Matches any of a SRFI-14 set of characters.

[procedure] (range CHAR CHAR) => MATCHER

Matches a range of characters. Analogous to character class [].

[procedure] (lit STRING) => MATCHER

Matches a literal string s.

Convenience procedures

These procedures are built from the basic procedures and are provided for convenience.

[procedure] (try PROC) => PROC

Converts a binary predicate procedure to a binary procedure that returns its right argument when the predicate is true, and false otherwise.

[procedure] (lst MATCHER-LIST) => MATCHER

Constructs a matcher for the sequence of matchers in MATCHER-LIST.

[procedure] (pass) => MATCHER

This matcher returns without consuming any input.

[procedure] (pos MATCHER) => MATCHER

Positive closure. Analogous to +.

[procedure] (opt MATCHER) => MATCHER

Optional pattern. Analogous to ?.

[procedure] (bind F P) => MATCHER

Given a rule P and function F, returns a matcher that first applies P to the input stream, then applies F to the returned list of consumed tokens, and returns the result and the remainder of the input stream.

[procedure] (rebind F G P) => MATCHER

Given a rule P and procedures F and G, returns a matcher that first applies F to the input stream, then applies P to the resulting stream, then applies G to the resulting list of consumed elements and returns the result along with the remainder of the input stream.

[procedure] (drop P) => MATCHER

Given a rule P, returns a matcher that always returns an empty list of consumed tokens when P succeeds.

Lexer procedures

[procedure] (longest STREAM-LIST) => STREAM

Takes the resulting streams produced by the application of a pattern on a stream (or streams) and selects the longest match if one exists. If STREAM-LIST is empty, it returns #F.


lex takes a pattern and a string, turns the string into a list of streams (containing one stream), applies the pattern, and returns the longest match. Argument ERROR is a single-argument procedure called when the pattern does not match anything.


Creating a lexer specialized for lists of characters

;; The following definitions create matchers {{char}} {{range}}
;; {{set}} {{lit}} specialized for lists of characters.

(define char-list-<Input>
  (make-<Input> null? car cdr))

(define char-list-<Token>
  (Input->Token char-list-<Input>))

(define char-list-<CharLex>
  (Token->CharLex char-list-<Token>))

(import-instance (<Token> char-list-<Token> char-list/)
		 (<CharLex> char-list-<CharLex> char-list/))

A parser to match floating point numbers

(require-extension typeclass input-classes lexgen srfi-1 srfi-14 test)

;;  A pattern to match floating point numbers. 
;;  "-"?(([0-9]+(\\.[0-9]+)?)|(\\.[0-9]+))([eE][+-]?[0-9]+)? 

(define numpat
  (let* ((digit        (char-list/range #\0 #\9))
	 (digits       (pos digit))
	 (fraction     (seq (char-list/char #\.) digits))
	 (significand  (bar (seq digits (opt fraction)) fraction))
	 (exp          (seq (char-list/set "eE") (seq (opt (char-list/set "+-")) digits)))
	 (sign         (opt (char-list/char #\-))))
    (seq sign (seq significand (opt exp)))))
 (define (err s)
  (print "lexical error on stream: " s)

 (lex numpat err "-123.45e-6")

Tokens with position information

(define-record-type postok
  (make-postok pos token)
  (pos        postok-pos )
  (token      postok-token )

(define pos? pair?)
(define pos-row car)
(define pos-col cdr)
(define make-pos cons)

(define-record-printer (postok x out)
  (fprintf out "#<token ~A: ~A>" 
	   (postok-pos x)
	   (postok-token x)))
(define (getpos p)
  (let ((f (lambda (in) (and (pair? in) (postok-pos (car in)))))
	(g (lambda (i s) (list (make-postok i (car s))))))
    (rebind f g p)))

(define pos-<Input>
  (let ((pos-tail
	 (lambda (strm)
	   (cond ((or (null? strm) (null? (cdr strm)))  '())
		  (let* ((curtok  (car strm))
			 (pos0    (postok-pos curtok))
			 (pos1    (let ((row0 (pos-row pos0))
					(col0 (pos-col pos0)))
				    (case (cadr strm)
				      ((#\newline)  (make-pos (+ 1 row0) 1))
				      ((#\return)   (make-pos row0 1))
				      (else         (make-pos row0 (+ 1 col0))))))
			 (res (cons (make-postok pos1 (cadr strm)) (cddr strm))))
	(pos-null? null?)
	(pos-head  (compose postok-token car)))
    (make-<Input> pos-null? pos-head pos-tail)))

(define pos-<Token>
  (Input->Token pos-<Input>))

(define pos-<CharLex>
  (Token->CharLex pos-<Token>))

(import-instance (<Token> pos-<Token> pos/)
		 (<CharLex> pos-<CharLex> pos/))

(define (make-pos-stream strm)
  (let ((begpos (make-pos 1 1)))
    (list `(() ,(cons (make-postok begpos (car strm)) (cdr strm))))))
(define pos-numpat-stream
  (make-pos-stream (string->list "-123.45e-6")))

(define pbnumpat 
  (let* ((digit        (pos/range #\0 #\9))
	 (digits       (star digit))
	 (fraction     (seq (pos/char #\.) digits))
	 (significand  (bar (seq digits (opt fraction)) fraction))
	 (exp          (seq (pos/set "eE") (seq (opt (pos/set "+-")) digits)))
	 (sign         (opt (pos/char #\-)) )
	 (pat          (seq (getpos (bind make-sign sign))
			    (seq (getpos (bind make-significand (longest significand)))
				 (getpos (bind make-exp (longest (opt exp))))))))

(define (pos-num-parser s)  (car (lex pbnumpat err s)))


Version History


Based on the SML lexer generator by Thant Tessman.

 Copyright 2009-2010 Ivan Raikov and the Okinawa Institute of Science and

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 General Public License for more details.

 A full copy of the GPL license can be found at