3
\$\begingroup\$

How does the following look for a json lexer? Are there any things that can be improved upon? Does the pattern look general-purpose enough to be able to generalize it to make it into a useful program, beyond just my personal tokenization of json?

import re

TOKENS = [
    # (name, regex)
    ('OPEN_BRACE', r'{'),
    ('CLOSE_BRACE', r'}'),
    ('OPEN_BRACKET', r'\['),
    ('CLOSE_BRACKET', r'\]'),
    ('COMMA', r','),
    ('SPACE', r'\s'),
    ('COLON', r':'),
    ('NULL', r'null'),
    ('TRUE', r'true'),
    ('FALSE', r'false'),
    ('NUMBER', r'-?(?:0|[1-9]\d*)(?:\.\d+)?(?:e[-+]\d+)?'),
    ('STRING', r'"[^"\\]*(\\"[^"\\]*)*"'),
    ('EOF', r'^$')
]

class Token:
    def __init__(self, type, value):
        self.type=type
        self.value=value
    def __eq__(self, other):
        return other == self.value
    def __str__(self):
        return '<%s -- %s>' % (self.type, self.value)

class Lexer:
    def __init__(self, input):
        self.input = input
        self.idx = 0
        self.tokens = []
    def pprint(self):
        print [str(token) for token in self.tokens]
    def getNextToken(self):
        substring = self.input[self.idx:] if self.idx < len(self.input) else ''
        for token in TOKENS:
            s = re.match(token[1], substring)
            if s:
                self.idx += s.end()
                token = Token(token[0], s.group())
                self.tokens.append(token)
                return token
        raise RuntimeError("Unrecognized token at position %d -- '%s'" % (self.idx, substring[:5]))
    def parse(self):
        tok = True
        while tok:
            tok = self.getNextToken()
            if tok == '':break
        return self.tokens

l = Lexer('{"name": "david"}')
l.parse()
l.pprint()
\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

Some basic advice. Use Python 3. Put some blank lines between your methods and functions to make the code easier to read and edit.

Your Token class is a perfect candidate for a dataclass. It has a tiny number of attributes and is also well-suited to be immutable.

It is handy for a Token to know where it came from. This is not required for lexing, but I would typically include a pos attribute in a Token class. That allows to to trace a token back to its origin during a debugging scenario.

A Token should not have a sneaky definition of equality for no good reason. Your Token.__eq__() method says a string equals a token if their text values are the same. That's non-intuitive and the benefit it provides your program is tiny (it allows you to terminate the lexing loop with if tok == ''). Much better is to play by the book and stop lexing when you hit EOF. The code is just as easy to write and a lot more straightforward for the reader.

Unless you have a reason for it, don't tokenize whitespace one space at a time. It spawns lots of unhelpful tokens that can be condensed to one. I converted your SPACE token definition to the following:

('WHITESPACE', r'\s+'),

Pay careful attention to naming. A couple examples. (1) Your TOKENS are not actually tokens (ie, instances of the Token class). They are token definitions, or something along those lines. (2) A lexer does not parse; it tokenizes. Give its primary method a proper name like lex() or tokenize().

Speaking of lexing and parsing. A now-deleted comment implied that your lexer is ill-conceived because it fails to enforce the syntax rules of JSON. That is both incorrect and a common error when first trying build a lexer: we let our brains get ahead of ourselves and start smuggling higher-level concepts (like the syntax for JSON) into a low-level task (writing a lexer that converts text to narrowly-valid tokens). Your lexer should accept a sequences of valid tokens even if they are JSON gibberish.

Token-defintion order matters. When lexing you have to take special care to attempt to match the token definitions in an order that will avoid confusion, which can occur if one definition embraces a simpler definition (for example, a quoted string can contain lots of other stuff). One strategy to avoid such problems it to attempt the "bigger" entities first. Even though I found no specific problems along these lines in your lexer, on general principle I rearranged the ordering of the token definitions.

Your lexer generates a lot of substrings. Each time the next token is requested, you first have to create a string representing the rest-of-the-text (everything after self.idx). That's not necessary if you take advantage of the fact that compiled regular expression objects take an optional pos parameter telling them where to start matching. In the illustration below, I pre-compiled all of the regexes when defining TOKEN_DEFINITIONS.

When to return information and where to accumulate it. Since the lexer is accumulating the tokens, it's not clear to me that Lexer.lex() should return anything (I opted for no). Another question is which method should accumulate the tokens? At least to my eye, that seems more appropriate for lex() than get_next_token().

Your quoted-string regex doesn't work correctly. What you want to match is easy to describe in words:

"    Initial double-quote.
.*?  Stuff, non-greedy (otherwise we'll go to the last double-quote).
"    Closing double-quote (details to follow).

The tricky part is that closing double-quote. It cannot be preceded by a backslash. That calls for a negative-lookbehind. So the components of the necessary regex look like this:

"
.*?
(?<!\\)"

It can be confusing to test stuff like this because you have to correctly navigate the string processing happening at the level of your Python syntax. One strategy is to create a variety of quoted strings in Python, put them into a dict, use the json library to created valid JSON text, and then make sure that your lexer can handle it.

Speaking of testing, set your programs up to facilitate testing. In a real project of my own, I would use proper unit tests, but even in a code review context I typically start by rearranging the author's code into a form that I can subject to experimentation and testing. As shown below, I created a top-level main() function and an easy way to add examples as I checked and edited your code.

import re
import json
import sys
from dataclasses import dataclass

def json_simple():
    # A simple chunk of JSON with various data types.
    d = dict(
        msg = "hello world",
        n = 99.34,
        status = True,
        other = None,
    )
    return json.dumps(d, indent = 4)

def good_tokens_bad_json():
    # The lexer should accept this. Let the parser reject it.
    return ''' true null "hi" } 123 {  '''

def json_quoting_example():
    # Some strings with internal double-quotes and backslashes.
    examples = (
        # Just quotes.
        r'__"foo"__',
        r'__"foo__',
        r'__foo"__',
        # Quotes with leading backslashes.
        r'__\"foo\"__',
        r'__\"foo__',
        r'__foo\"__',
        # Quotes with 2 leading backslashes.
        r'__\\"foo\\"__',
        r'__\\"foo__',
        r'__foo\\"__',
    )

    # Convert those examples into a dict and then JSON text.
    d = {
        f'ex{i}' : ex
        for i, ex in enumerate(examples)
    }
    return json.dumps(d, indent = 4)

def invalid_text():
    return '''{"a": 123, blort: 99}'''

EXAMPLES = dict(
    quoting = json_quoting_example(),
    goodbad = good_tokens_bad_json(),
    simple = json_simple(),
    invalid = invalid_text(),
)

def main():
    args = sys.argv[1:] + ['simple']
    k = args[0]
    text = EXAMPLES[k]
    lex = Lexer(text)
    lex.lex()
    for tok in lex.tokens:
        print(tok)

EOF = 'EOF'

TOKEN_DEFINITIONS = [
    # Try to match these bigger concepts first.
    ('QUOTED_STRING', r'".*?(?<!\\)"'),
    ('NUMBER', r'-?(?:0|[1-9]\d*)(?:\.\d+)?(?:e[-+]\d+)?'),
    # Everything else is atomic and simple, so no confusion to worry about.
    ('OPEN_BRACE', r'{'),
    ('CLOSE_BRACE', r'}'),
    ('OPEN_BRACKET', r'\['),
    ('CLOSE_BRACKET', r'\]'),
    ('COMMA', r','),
    ('WHITESPACE', r'\s+'),
    ('COLON', r':'),
    ('NULL', r'null'),
    ('TRUE', r'true'),
    ('FALSE', r'false'),
    (EOF, r'$')
]

TOKEN_DEFINITIONS = [
    (type, re.compile(pattern))
    for type, pattern in TOKEN_DEFINITIONS
]

@dataclass(frozen = True)
class Token:
    pos: int
    type: str
    value: str

class Lexer:

    def __init__(self, text):
        self.text = text
        self.pos = 0
        self.tokens = []

    def lex(self):
        while True:
            tok = self.get_next_token()
            self.tokens.append(tok)
            if tok.type == EOF:
                break

    def get_next_token(self):
        for tok_type, rgx in TOKEN_DEFINITIONS:
            m = rgx.match(self.text, pos = self.pos)
            if m:
                value = m.group()
                self.pos += len(value)
                return Token(self.pos, tok_type, value)

        chunk = self.text[self.pos : self.pos + 20]
        msg = f'Unrecognized token: position={self.pos} content={chunk!r}'
        raise ValueError(msg)

if __name__ == '__main__':
    main()

Postscript: my regular expression for quoted strings is also bad. It fails when the string actually ends with a backslash. I believe that this answer shows how to do it correctly (but I did not test it extensively, which one really must do this these sorts of things). Here are the components of the regular expression broken down and applied to your situation (double-quoted strings only):

"                      # Opening quote.
(
    (\\{2})*           # Just an even N of backslashes.
    |                  # OR ...
    (
        .*?            # Stuff, non-greedy.
        [^\\]          # Non backslash.
        (\\{2})*       # Even N of backslashes.
    )
)
"                      # Closing quote.
\$\endgroup\$
5
  • \$\begingroup\$ appreciate all the help and insight. btw, I mixed up the string regex, it would be \\. instead of just \\". So the new regex pattern would be r'"[^"\\]*(\\.[^"\\]*)*"' -- regex101.com/r/F56NG2/1 from here: softec.lu/site/RegularExpressions/UnrollingTheLoop \$\endgroup\$
    – David542
    Dec 25, 2022 at 0:35
  • 2
    \$\begingroup\$ You are absolutely right about the lexing stuff. That's why I deleted my faulty comment. I like to clean up after myself in the rare cases I make a mess. ;) \$\endgroup\$ Dec 25, 2022 at 10:06
  • \$\begingroup\$ Excellent review! Tip: to match a string, simply do r'"(\\.|[^"])*"'. There's no need for complicated regexps. \$\endgroup\$
    – Niccolo M.
    Dec 28, 2022 at 11:26
  • \$\begingroup\$ @NiccoloM. Perhaps I'm overlooking something, but that regex matches too much. For example, an odd number of backslashes, which is an invalid quoted-string: "\\\". \$\endgroup\$
    – FMc
    Dec 29, 2022 at 17:03
  • \$\begingroup\$ @FMc Oh my, you're right. It seems that a fix is r'"(\\.|[^"\\])*"'. Touch wood touch wood ;-) \$\endgroup\$
    – Niccolo M.
    Dec 29, 2022 at 17:54
2
\$\begingroup\$

Not lexing correctly

Your lexer does not handle strings properly:

from json import dumps, loads

utf8_string = '"A quoted random UTF-8 string €.'
json = dumps(utf8_string)
print(loads(json))
l = Lexer(json)
l.parse()
l.pprint()

Results in:

python .\jsonlex.py
"A quoted random UTF-8 string €.
Traceback (most recent call last):
  File "C:\Users\Richard Neumann\Desktop\jsonlex.py", line 59, in <module>
    l.parse()
  File "C:\Users\Richard Neumann\Desktop\jsonlex.py", line 49, in parse
    tok = self.getNextToken()
          ^^^^^^^^^^^^^^^^^^^
  File "C:\Users\Richard Neumann\Desktop\jsonlex.py", line 45, in getNextToken
    raise RuntimeError("Unrecognized token at position %d -- '%s'" % (self.idx, substring[:5]))
RuntimeError: Unrecognized token at position 0 -- '"\"A '

Which, as you can see from the comparison to the json library should be a totally fine JSON string.

You should consider writing unit test for your lexer and testing it against valid JSON input such as above.

Outdated Python version

Judging from the use of the print statement you seem to be using Python 2.x which is unmaintained for two years now. Switch to Python 3 for all future projects.

Use custom exceptions

Consider using a custom exception, such as

class JSONLexingError(Exception):
    """Indicate an error when lexing a JSON string."""

to indicate errors during lexing instead of using a bare RuntimeError.

PEP-8

It is unlawful for a Python code review to be missing the PEP-8 hammer. ;) Use PascalCase for class names (which you already do) and snake_case for function names.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.