Shaving the yak, a grammar parser-generator for modified EBNF, Part 1

class Tokenizer:
    """Tokenizes a given grammar."""

    def __init__(self, _grammar: str):
        self.grammar = _grammar
        self.line = 0
        self.column = 0
        self.tokens = []

Nothing really to say here, except that an instance of Tokenizer implicitly has a grammar already associated with it. It occurred to me that I could probably build a generator that takes some kind of streaming input and outputs tokens. This would be stateless, and unless we were clever, we would lose the ability to have absolute line and column numbers.

Here's the final bit of lexeme information that ties everything together.

This completes our defition for "lexeme". Here we pair the enum with a match string. All of these strings will be used to match on things within our text.

    lexemes = {

        r"[A-Z][A-Z0-9_]*": TokenType.Terminal,
        r"[a-zA-Z_][a-zA-Z0-9_]*": TokenType.Name,
        r"(\"[^\n\r]*\"|\'[^\n\r]*\')(?<!\\\")": TokenType.String,
        r"->": TokenType.Arrow,
        r";": TokenType.Semicolon,
        r"\(": TokenType.LParen,
        r"\)": TokenType.RParen,
        r"\|": TokenType.Pipe,
        r"\+": TokenType.Plus,
        r"\*": TokenType.Star,
        r"\?": TokenType.Question,
        " ": TokenType.Whitespace,
        "\n": TokenType.Newline,
    }

The order of the lexemes matters. If a lexeme is a substring of another lexeme, it must come after the containing lexeme because regex matches greedily. Here, the lexemes that are affected are the Terminal and Name lexemes. Terminal happens to be all caps, and Name can be all caps, so we need to check for Terminal first.

Now, finally, the meat.

    def tokenize(self):
        # Strip whitespace from front and back of grammar.
        self.grammar = self.grammar.strip()
        # Strip out extra spaces.
        self.grammar = re.sub('[ \r\t]+', ' ', self.grammar)

The first thing we do is strip off any extra space before and after all the text, as well as compress any spaces in the text. Note that we don't strip out newlines. We'll be turning those into tokens.

Next, we tokenize. :)

       # Tokenize the grammar.
        _grammar = self.grammar

        while _grammar:

            token = None
            for lexeme, token_type in self.lexemes.items():
                match = re.match(lexeme, _grammar)
                if match:
                    token = Token(token_type, match.group(0), self.line, self.column)
                    _grammar = _grammar[match.end():]

                    # Check if we've entered a new line.
                    if token.token_type == TokenType.Newline:
                        self.line += 1

                        # Reset the column number when we're done with a line.
                        self.column = 0

                    # We strip off the front of the list after every match, so we use the previous match end as our
                    # index.
                    self.column += match.end()
                    break
            else:
                raise LexException("Could not match lexeme:\n" +
                                self.grammar.split('\n')[self.line] + "\n" +
                                " " * self.column + "^" + "\n")

             self.tokens.append(token)

        self.tokens.append(Token(TokenType.EOF, None, self.line, self.column))

        return self.tokens

The core of the functionality is the while loop. While we have anything left in _grammar, keep trying to do stuff.

Then we loop through each lexeme we could expect, for lexeme, token_type inb self.lexemes.items() unpacks our lexeme definition. I think there is a more elegent way to do this, but this brute force method works. Unfortunately that makes our time complexity for generating tokens m x n where m is the number of lexemes and n is the number of tokens we could possibly find. The other part of improving on this would necessitate bringing parsing into our lexer in order to intelligently search for tokens, which is no bueno.

We run the lexeme through a regex match, and check if we found a match. If we did, a few important things happen; first, we generate a token with the appropriate bits of information; second, we strip off the token we found with _grammar = _grammar[match.end()]. This is how we move forward in this implementation. When we make it to a point where _grammar is empty, ie "", then we're done.

If we found a newline we need to increment our self.line and self.column state. We also increment our column number.

Finally, we add our found token to our list of self.tokens.

Once _grammar is empty, we add an EOF token and return all the tokens to the caller.