Schemey - lexer

Question

¹Note: This is the first post in - hopefully - a series of posts I plan to make.

Project background

Schemey is a project I've been working on for the past 3-4 weeks. It is an implementation of a subset of the Scheme programming language. The project is still very new and most likely has bugs in certain parts(which is why I'm posting this here ).

Actual, I just finished posting the repository of my project on github, and documentation of the project can be found here. Please note, while I've tried my best to make sure my project is "release ready", this is the first version of my project's repository and its documentation, so typos can be expected. Also note, all code in the repository is in the public domain, so feel free to use it as you please.

Structure of the lexer

The way I designed my lexer was to base it off of the maximal-munch rule, instead of using regex like I was originally planning to.

The lexer itself is fairly small(around 150-200 lines), and I've add documentation throughout the code, so I'm confident I don't have to explain it in very much detail. Without further ado, here is the code:

lexer.py

"""
lexer.py
----------------------------------------
A simple lexer based upon the "maximal munch" rule.
Because of this, the lexer is not generic and must
be created anew for each specific language.
----------------------------------------
Algerbrex
All code in this module is
public domain.
Last modified: February 5 2017
"""

from collections import namedtuple
from _builtins import builtin_map

# Sometimes we need to return the current position
# the lexer is on, to raise an appropriate error. 
# Whenever there is an error, an instance is returned 
# to the parser.
Error = namedtuple('Error', 'pos')


def is_identifier(char):
    """ Test if `char` is a valid Scheme identifier.
    """
    return char.isalnum() or char in builtin_map.keys() or char in ('?', '!', '.')


class Token:
    """ A simple Token structure.
        Contains the token type, value,
        and the position of the token.
    """

    def __init__(self, token_type, val, pos):
        # copy the attributes of the Character object
        # to this class instance.
        self.token_type = token_type
        self.val = val
        self.pos = pos

    def __str__(self):
        return "{}({}) at {}".format(self.token_type, self.val, self.pos)


class TokenTypes:
    """ A Structure for each possible type
        of token.
    """
    BOOLEAN = 'BOOLEAN'
    NUMBER = 'NUMBER'
    IDENTIFIER = 'IDENTIFIER'
    LPAREN = 'LPAREN'
    RPAREN = 'RPAREN'
    QUOTE = 'QUOTE'


class Lexer:
    """ A simple lexer based upon the "maximal munch" rule.
    """

    def __init__(self, buffer):
        """Initialize the lexer with buffer as input."""
        self.buffer = buffer
        self.pos = 0

    def next_token(self):
        """ Return the next token(Which is a token object.)
            found in the input buffer. None is returned if we've
            reached the end of the buffer.
            If a lexing error occurs(The current character
            is not known), a LexerError is raised.
        """
        # Continue to skip past garbage characters.
        while self._get_char(self.pos) in (';', ' ', '\n', '\t', '\r'):
            self._skip_comments()
            self._skip_whitespace()

        if self._get_char(self.pos) is None:
            return None
        char = self.buffer[self.pos]
        if char == '#' and self.buffer[self.pos + 1] in ('t', 'f'):
            return self._process_boolean()
        elif char.isdigit():
            return self._process_number()
        elif is_identifier(char):
            return self._process_identifier()
        elif char == '(':
            return self._process_lparen()
        elif char == ')':
            return self._process_rparen()
        elif char == "'":
            return self._process_quote()
        else:
            return Error(self.pos)

    def _skip_whitespace(self):
        """
        Skip past all characters which are whitespace.
        """
        while self._get_char(self.pos):
            if self.buffer[self.pos] in (' ', '\n', '\t', '\r'):
                self.pos += 1
            else:
                break

    def _skip_comments(self):
        """
        Skip past all characters in the comment.
        """
        if self._get_char(self.pos) != ';':
            return
        while self._get_char(self.pos) and self._get_char(self.pos) != '\n':
            self.pos += 1

    def _process_boolean(self):
        """ Construct a boolean Token.
        """
        retval = Token(TokenTypes.BOOLEAN, self.buffer[self.pos:self.pos + 2], self.pos)
        self.pos += 2
        return retval

    def _process_number(self):
        """ Construct a numeric Token.
        """
        endpos = self.pos + 1
        while self._get_char(endpos) and self._get_char(endpos).isdigit():
            endpos += 1
        retval = Token(TokenTypes.NUMBER, self.buffer[self.pos:endpos], self.pos)
        self.pos = endpos
        return retval

    def _process_identifier(self):
        """ Construct an identifier Token.
        """
        endpos = self.pos + 1
        while self._get_char(endpos) and is_identifier(self._get_char(endpos)):
            endpos += 1
        retval = Token(TokenTypes.IDENTIFIER, self.buffer[self.pos:endpos], self.pos)
        self.pos = endpos
        return retval

    def _process_lparen(self):
        """ Construct a left parenthesis Token.
        """
        retval = Token(TokenTypes.LPAREN, self.buffer[self.pos], self.pos)
        self.pos += 1
        return retval

    def _process_rparen(self):
        """ Construct a right parenthesis Token.
        """
        retval = Token(TokenTypes.RPAREN, self.buffer[self.pos], self.pos)
        self.pos += 1
        return retval

    def _process_quote(self):
        """ Construct a quote Token.
        """
        retval = Token(TokenTypes.QUOTE, self.buffer[self.pos], self.pos)
        self.pos += 1
        return retval

    def _get_char(self, pos):
        """
        Try and get the next character from the buffer.
        If an IndexError is raised, return None.
        """
        try:
            return self.buffer[pos]
        except IndexError:
            return None

Note that there are some style inconsistencies(such as docstring formatting) , that I am planning to fix in the next release of project. Mainly what I'm looking for in the review is:

• Docstring helpfulness: Are my docstrings helpful and do they mostly match what the function/method/class/module does?
• Lexer implementation: How well would you say I implemented a basic lexer?
• OOP design: Am I using Python classes in the correct way? eg. Should some methods be functions and visa versa?

---

1_{UPDATE: After the Schemey project has began to grow, I deiced that it would really be a bit to big of a hassle to ask for a review of the entire project. I will, of course, leave this post up, but I don't think I'll be adding anymore posts related to this one in the future. I've removed the now erroneous information in my post above, and crossed out my note for future reference.}

Answer 1

Overall, the code is quite clean and understandable. Though, I have never done anything like you are doing, but here are some notes about the code:

• the Token and TokenTypes classes may use "__slots__" for faster attribute access and memory savings
• the char in builtin_map.keys() can and should be replaced with just char in builtin_map to avoid creating the list of keys and looking up in the list instead of in the hashtable - O(n) vs O(1)
• the char in ('?', '!', '.') should be replaced with something like char in ADDITIONAL_BUILTIN_CHARS where ADDITIONAL_BUILTIN_CHARS = {'?', '!', '.'} (note - Python 2.7+ syntax) - it is a set that you should define on the module level - or, may be even move to _builtins module to keep all the related constants together
• all the other places where you use in to check if character is one of multiple characters can benefit from a similar improvement - defining as a set, giving a meaningful name and moving to the module level
• the Lexer should probably support the "iterator" protocol (advancing to the next token continuously), like for example this or this one does

• the PEP8 import guidelines suggest to put a new line between the different types of imports, replace:

  from collections import namedtuple
  from _builtins import builtin_map
  

  with:

  from collections import namedtuple
  
  from _builtins import builtin_map
  

• one-line doc strings can stay on a single line (PEP257)

As a side note, I think you should not be putting the "modified date" into the module itself - let the github and git handle it.