The alexa Reference Manual

Table of Contents

The alexa Reference Manual

This is the alexa Reference Manual, version 1.0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 10:42:42 2018 GMT+0.

1 Introduction

ALEXA: A Lexical Analyzer Generator

Introduction

ALEXA is a tool similar to lex or flex for generating lexical analyzers. Unlike tools like lex, however, ALEXA defines a domain-specific language within your Lisp program, so you don't need to invoke a separate tool.

The alexa package exports a single macro: define-string-lexer. You can view the documentation for this macro using the standard Common Lisp facilities, e.g., describe or

(format t "~A"
        (documentation 'alexa:define-string-lexer
                       'function))

ALEXA may be used with parsing libraries such as cl-yacc.

Special Features

ALEXA has a few unique features to make lexical analysis easier. These include:

• Bound variables $< and $> to determine the start and end of your matches.
• Bound variables to matches on named registers. For example, (?<DIGIT>\d) will match a digit, and bind it in your Lisp code to the lexical variable $DIGIT.
• Regex aliases. You don't need to re-type [A-Za-z][A-Za-z0-9_] for each identifier. You can instead define the alias (:ident "[A-Za-z][A-Za-z0-9_]") and use {{IDENT}} in your lexical rules.

Example

The following simple example shows how to tokenize simple arithmetic expressions. First, we define what a token is and how to make one.

(deftype token ()
  `(cons keyword t))

(defun tok (type &optional val)
  (cons type val))

Advanced applications may opt to store other information in their token data structure, such as token position in the string (which can be extracted with $< and $>).

Next, we define the lexer. We create two aliases :num and :name to make our lexical rules a little bit easier to read.

(alexa:define-string-lexer arith-lexer
  "Make a lexical analyzer for arithmetic expressions."
  ((:num "\\d+")
   (:name "[A-Za-z][A-Za-z0-9_]*"))
  ("{{NAME}}" (return (tok :variable (intern $@))))
  ("{{NUM}}"  (return (tok :number (parse-integer $@))))
  ("[+*/-]"   (return (tok :operator (intern $@ 'keyword))))
  ("\\("      (return (tok :left-paren)))
  ("\\)"      (return (tok :right-paren)))
  ("\\s+"     nil))

To use the lexer, we make one by calling arith-lexer on the string being lexically analyzed. To get the next token, we just funcall our lexer. We can make a small helper function to lex an entire string until the lexer has been exhausted.

(defun lex-line (string)
  (loop :with lexer := (arith-lexer string)
        :for tok := (funcall lexer)
        :while tok
          :collect tok))

Calling lex-line on arithmetic expressions now gives us our expected results.

> (lex-line "2*(x+1)/z")
((:NUMBER . 2)
 (:OPERATOR . :*)
 (:LEFT-PAREN)
 (:VARIABLE . |x|)
 (:OPERATOR . :+)
 (:NUMBER . 1)
 (:RIGHT-PAREN)
 (:OPERATOR . :/)
 (:VARIABLE . |z|))
 
> (lex-line "1/(1/R_1 + 1/R_2)")
((:NUMBER . 1)
 (:OPERATOR . :/)
 (:LEFT-PAREN)
 (:NUMBER . 1)
 (:OPERATOR . :/)
 (:VARIABLE . R_1)
 (:OPERATOR . :+)
 (:NUMBER . 1)
 (:OPERATOR . :/)
 (:VARIABLE . R_2)
 (:RIGHT-PAREN))

Contributing

If you have suggestions or questions, please file an issue in GitHub. If you have any bug fixes or improvements, please make a pull request.

License and Copyright

This software is released under the BSD 3-clause license. See LICENSE.txt for details.

Copyright © 2016 Rigetti Computin

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 alexa

Author

Robert Smith <robert@rigetti.com>

License

BSD 3-clause (See LICENSE.txt)

Description

A lexical analyzer generator.

Version

1.0.1

Dependencies

• alexandria
• cl-ppcre

Source

alexa.asd (file)

Components

• license.txt (file)
• src (module)

3 Modules

Modules are listed depth-first from the system components tree.

3.1 alexa/src

Dependency

license.txt (file)

Parent

alexa (system)

Location

src/

Components

• package.lisp (file)
• alexa.lisp (file)

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.

4.1 Lisp

4.1.1 alexa.asd

Location

alexa.asd

Systems

alexa (system)

4.1.2 alexa/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

alexa

4.1.3 alexa/src/alexa.lisp

Dependency

package.lisp (file)

Parent

src (module)

Location

src/alexa.lisp

Exported Definitions

• define-string-lexer (macro)
• lexer-match-error (condition)

Internal Definitions

• copy-pattern (function)
• extract-registers (function)
• fill-in-aliases (function)
• generate-pattern (function)
• make-pattern (function)
• pattern (structure)
• pattern-code (function)
• (setf pattern-code) (function)
• pattern-num-registers (function)
• (setf pattern-num-registers) (function)
• pattern-p (function)
• pattern-parse-tree (function)
• (setf pattern-parse-tree) (function)
• pattern-regex (function)
• (setf pattern-regex) (function)
• pattern-register-names (function)
• (setf pattern-register-names) (function)
• pattern-register-variables (function)
• walk-tree (function)

4.2 Other

4.2.1 alexa/LICENSE.txt

Parent

alexa (system)

Location

LICENSE.txt

5 Packages

Packages are listed by definition order.

5.1 alexa

A lexical analyzer generator.

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

• define-string-lexer (macro)
• lexer-match-error (condition)

Internal Definitions

• copy-pattern (function)
• extract-registers (function)
• fill-in-aliases (function)
• generate-pattern (function)
• make-pattern (function)
• pattern (structure)
• pattern-code (function)
• (setf pattern-code) (function)
• pattern-num-registers (function)
• (setf pattern-num-registers) (function)
• pattern-p (function)
• pattern-parse-tree (function)
• (setf pattern-parse-tree) (function)
• pattern-regex (function)
• (setf pattern-regex) (function)
• pattern-register-names (function)
• (setf pattern-register-names) (function)
• pattern-register-variables (function)
• walk-tree (function)

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

6.1 Exported definitions

6.1.1 Macros

Macro: define-string-lexer NAME &body BODY

Define a lexical analyzer named NAME.

Defining a lexical analyzer is actually defining a function named NAME whose lambda list is

(STRING &KEY (START 0) (END (LENGTH STRING)))

The STRING is the string to be analyzed, and START/END are the starting and ending positions to be looked at. Calling the function named NAME will produce a closure which, if called repeatedly, will produce results according to the lexical rules defined. When the input string is exhausted, NIL is returned, and the string will be unbound within the closure to allow garbage collection.

Signals LEXER-MATCH-ERROR as a continuable error if no match was found.

The syntax of BODY is:

<doc string>?
(<alias definition>*)
<lexical action>*

An <alias definition> is a list

(<keyword> <regex string>)

The name of the keyword may be used in the <lexical action> regexes. A <lexical action> is a list

(<regex string> &body <code>)

The <regex string> is matched against the input string greedily and in the order they are listed in the BODY. If a match succeeds, then it will execute <code>. Within <code>, the following symbols are bound:

$1, $2, ..., $n: String match on (unnamed) register n
$NAME : String match on named register (?<NAME>...)
$@ : Entire string match.
$<, $> : Start and end position of match.

Generally, <code> should explicitly RETURN some token object for a semantic analyzer to examine. An explcit RETURN is needed.

The <regex string> of the lexical action may use the names of the symbols defined in the <alias definition> forms. For example, given the alias definitions

((:int "\\d+")
(:ident "[a-z]+"))

one can use {{INT}} and {{IDENT}} within the <regex string>s of the <lexical action>.

Package

alexa

Source

alexa.lisp (file)

6.1.2 Conditions

Condition: lexer-match-error ()

Error to be signaled if the lexer didn’t find a match.

Package

alexa

Source

alexa.lisp (file)

Direct superclasses

simple-error (condition)

6.2 Internal definitions

6.2.1 Functions

Function: copy-pattern INSTANCE

Package

alexa

Source

alexa.lisp (file)

Function: extract-registers PARSE-TREE

Package

alexa

Source

alexa.lisp (file)

Function: fill-in-aliases ALIASES REGEX

Package

alexa

Source

alexa.lisp (file)

Function: generate-pattern PAT CONTINUE-TAG STRING-VAR START-VAR END-VAR

Package

alexa

Source

alexa.lisp (file)

Function: make-pattern &key (REGEX REGEX) (PARSE-TREE PARSE-TREE) (NUM-REGISTERS NUM-REGISTERS) (REGISTER-NAMES REGISTER-NAMES) (CODE CODE)

Package

alexa

Source

alexa.lisp (file)

Function: pattern-code INSTANCE

Function: (setf pattern-code) VALUE INSTANCE

Package

alexa

Source

alexa.lisp (file)

Function: pattern-num-registers INSTANCE

Function: (setf pattern-num-registers) VALUE INSTANCE

Package

alexa

Source

alexa.lisp (file)

Function: pattern-p OBJECT

Package

alexa

Source

alexa.lisp (file)

Function: pattern-parse-tree INSTANCE

Function: (setf pattern-parse-tree) VALUE INSTANCE

Package

alexa

Source

alexa.lisp (file)

Function: pattern-regex INSTANCE

Function: (setf pattern-regex) VALUE INSTANCE

Package

alexa

Source

alexa.lisp (file)

Function: pattern-register-names INSTANCE

Function: (setf pattern-register-names) VALUE INSTANCE

Package

alexa

Source

alexa.lisp (file)

Function: pattern-register-variables PAT PACKAGE

Package

alexa

Source

alexa.lisp (file)

Function: walk-tree F TREE

Package

alexa

Source

alexa.lisp (file)

6.2.2 Structures

Structure: pattern ()

Package

alexa

Source

alexa.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots

Slot: regex

Readers

pattern-regex (function)

Writers

(setf pattern-regex) (function)

Slot: parse-tree

Readers

pattern-parse-tree (function)

Writers

(setf pattern-parse-tree) (function)

Slot: num-registers

Readers

pattern-num-registers (function)

Writers

(setf pattern-num-registers) (function)

Slot: register-names

Readers

pattern-register-names (function)

Writers

(setf pattern-register-names) (function)

Slot: code

Readers

pattern-code (function)

Writers

(setf pattern-code) (function)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types