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.
