As we have our Community Oriented Development Extravaganza, Requiring Extreme Vigor Inciting Extraordinary Winners 2017 Challenge. Finally I had some time to write a tokenizer for my own language. It is the most complex tokenizer I have written so far. The language consists of 32 keywords and supports most of the operators. Beyond that we have numeric literals, string literals, address literals (virtual memory pointer address) and character literals. I read a lot before writing this tokenizer, as many similiar questions were asked here on Code Review. And because it is my first attempt in implementing a programming language in C#, I did C before, I would like to know what I can improve or change, if there are any exceptions I did not notice.
The tokenizer generates tokens which I will use to generate an AST during parsing. I did not use Regex or any lexer generators as that was not the point for me.
In the tokens sfunc
and svar
, the s
stands for static
.
I didn't include the preprocessor here, as it is already fairly big chunk of code.
CharStream.cs
using System;
using System.Collections.Generic;
using System.Text;
namespace Compiler.Lexer
{
public class CharStream
{
private readonly IList<string> Lines;
public bool EOF { get; private set; }
public int CurrentLineNumber { get; set; }
public int CurrentPosition { get; set; }
public CharStream(string source)
{
if (!string.IsNullOrEmpty(source))
{
Lines = Preprocessor.Utilities.GenerateList(source);
}
else
{
EOF = true;
return;
}
int line = 0;
while (string.IsNullOrEmpty(Lines[line]))
{
line++;
}
EOF = false;
CurrentLineNumber = line;
CurrentPosition = 0;
}
public char? Peek()
{
if (EOF)
{
return null;
}
char? c = Get();
Unget();
return c;
}
public string Peek(int count)
{
string peek = Get(count);
Unget(count);
return peek;
}
public char? Get()
{
if (EOF)
{
return null;
}
while (String.IsNullOrEmpty(Lines[CurrentLineNumber])
&& CurrentLineNumber < Lines.Count)
{
CurrentLineNumber++;
}
char c = Lines[CurrentLineNumber][CurrentPosition];
if (CurrentPosition + 1 < Lines[CurrentLineNumber].Length)
{
CurrentPosition++;
}
else
{
if (CurrentLineNumber + 1 < Lines.Count)
{
CurrentLineNumber++;
CurrentPosition = 0;
}
else
{
EOF = true;
}
}
return c;
}
public string Get(int count)
{
var stringBuilder = new StringBuilder();
for (int i = 0; i < count; i++)
{
char? c = Get();
if (c == null)
{
return null;
}
else
{
stringBuilder.Append(c);
}
}
return stringBuilder.ToString();
}
private void Unget()
{
if (EOF)
{
EOF = false;
}
else
{
if (CurrentPosition > 0)
{
CurrentPosition--;
}
else if (CurrentLineNumber > 0)
{
while (string.IsNullOrEmpty(Lines[--CurrentLineNumber])) ;
CurrentPosition = Lines[CurrentLineNumber].Length - 1;
}
}
}
private void Unget(int count)
{
for (int i = 0; i < count; i++)
{
Unget();
}
}
}
}
TokenKind.cs
using System;
namespace Compiler.Lexer
{
// do not change token numbers
public enum TokenKind : ushort
{
UnknownToken = 0,
AndKeyword = 1,
BreakKeyword = 2,
CaseKeyword = 3,
CatchKeyword = 4,
ClassKeyword = 5,
ConstKeyword = 6,
ContinueKeyword = 7,
DefaultKeyword = 8,
DoKeyword = 9,
ElseKeyword = 10,
EnumKeyword = 11,
FalseKeyword = 12,
ForKeyword = 13,
FuncKeyword = 14,
IfKeyword = 15,
InKeyword = 16,
IsKeyword = 17,
NewKeyword = 18,
NorKeyword = 19,
NullKeyword = 20,
ObjectKeyword = 21,
OrKeyword = 22,
PackageKeyword = 23,
ReturnKeyword = 24,
SfuncKeyword = 25,
SvarKeyword = 26,
SwitchKeyword = 27,
ThisKeyword = 28,
TrueKeyword = 29,
TryKeyword = 30,
VarKeyword = 31,
WhileKeyword = 32,
Identifier = 100,
CharacterLiteral = 101,
StringLiteral = 102,
IntegerLiteral = 103,
RealLiteral = 104,
AddressLiteral = 105,
Assignment = 200,
Addition = 201,
Subtraction = 202,
UnaryPlus = 203,
UnaryMinus = 204,
Multiplication = 205,
Division = 206,
Modulo = 207,
EqualTo = 208,
NotEqualTo = 209,
GeaterThan = 210,
LessThan = 211,
GreaterThanOrEqualTo = 212,
LessThanOrEqualTo = 213,
LogicalNOT = 214,
LogicalAND = 215,
LogicalOR = 216,
PostfixPlus = 217,
PostfixMinus = 218,
PrefixPlus = 219,
PrefixMinus = 220,
BitwiseNOT = 300,
BitwiseAND = 301,
BitwiseOR = 302,
BitwiseXOR = 303,
BitwiseLeftShift = 304,
BitwiseRightShift = 305,
AdditionAssignment = 400,
SubtractionAssignment = 401,
MultiplicationAssignment = 402,
DivisionAssignment = 403,
ModuloAssignment = 404,
BitwiseANDAssignment = 405,
BitwiseORAssignment = 406,
BitwiseXORAssignment = 407,
BitwiseLeftShiftAssignment = 408,
BitwiseRightShiftAssignment = 409,
OpenParenthesis = 500,
CloseParenthesis = 501,
OpenBrace = 502,
CloseBrace = 503,
OpenBracket = 504,
CloseBracket = 505,
Colon = 506,
Semicolon = 507,
Comma = 508,
Dot = 509,
Question = 510,
}
}
Token.cs
using System;
namespace Compiler.Lexer
{
public sealed class Token
{
public TokenKind Kind { get; }
public string Lexeme { get; }
public int LineNumber { get; }
public int Position { get; }
public Token(TokenKind kind, string lexeme, int lineNumber, int position)
{
Kind = kind;
Lexeme = lexeme;
LineNumber = lineNumber;
Position = position;
}
}
}
Tokenizer.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Compiler.Lexer
{
public partial class Tokenizer
{
private CharStream Stream;
private Token LastToken;
public Tokenizer(string source)
{
Stream = new CharStream(source);
LastToken = new Token
(TokenKind.UnknownToken, string.Empty, 0, 0);
}
public Token Get()
{
Token get;
int lineNumber = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
do
{
if (Stream.EOF)
{
return null;
}
} while (IsWhiteSpace());
get = IsSymbol();
if (get != null)
{
return get;
}
get = IsOperator();
if (get != null)
{
return get;
}
get = IsIdentifier();
if (get != null)
{
return get;
}
get = IsCharacterLiteral();
if (get != null)
{
return get;
}
get = IsStringLiteral();
if (get != null)
{
return get;
}
get = IsNumericLiteral();
if (get != null)
{
return get;
}
get = IsAddressLiteral();
if (get != null)
{
return get;
}
get = new Token(TokenKind.UnknownToken, Stream.Get().ToString(),
lineNumber, position);
return get;
}
public Token Peek()
{
int line = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
Token previousToken = LastToken;
Token peek = Get();
Stream.CurrentLineNumber = line;
Stream.CurrentPosition = position;
LastToken = previousToken;
return peek;
}
private bool IsWhiteSpace()
{
bool isWhiteSpace = false;
while (Stream.Peek() != null && char.IsWhiteSpace((char)Stream.Peek()))
{
isWhiteSpace = true;
Stream.Get();
}
return isWhiteSpace;
}
private Token IsSymbol()
{
int lineNumber = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
string lexeme = Stream.Peek().ToString();
TokenKind tokenKind;
if (SymbolToTokenKind.TryGetValue(lexeme, out tokenKind))
{
Stream.Get();
Token token = new Token(tokenKind, lexeme, lineNumber, position);
LastToken = token;
return token;
}
return null;
}
private Token IsOperator()
{
int lineNumber = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
var lexeme = new StringBuilder();
char? firstChar = null;
if (Stream.Peek() == '+' || Stream.Peek() == '-')
{
firstChar = Stream.Peek();
}
while (Stream.Peek() != null
&& lineNumber == Stream.CurrentLineNumber
&& OperatorToTokenKind.ContainsKey(Stream.Peek().ToString())
|| (Stream.Peek() == '+' && firstChar == '+')
|| (Stream.Peek() == '-' && firstChar == '-'))
{
lexeme.Append(Stream.Get());
}
if ((lexeme.ToString() == "+" || lexeme.ToString() == "-")
& (ushort)LastToken.Kind > 99 && (ushort)LastToken.Kind < 200)
{
//A+B or A-B
lexeme.Insert(0, 'A');
lexeme.Insert(2, 'B');
}
else if (lexeme.ToString() == "+" || lexeme.ToString() == "-")
{
//+A or -A
lexeme.Insert(1, 'A');
}
if ((lexeme.ToString() == "++" || lexeme.ToString() == "--")
& (ushort)LastToken.Kind > 99 && (ushort)LastToken.Kind < 200)
{
//A++ or A--
lexeme.Insert(0, 'A');
}
else if (lexeme.ToString() == "++" || lexeme.ToString() == "--")
{
//++A or --A
lexeme.Insert(2, 'A');
}
TokenKind tokenKind;
if (OperatorToTokenKind.TryGetValue(lexeme.ToString(), out tokenKind))
{
Token token = new Token
(tokenKind, lexeme.ToString(), lineNumber, position);
LastToken = token;
return token;
}
return null;
}
private Token IsIdentifier()
{
int lineNumber = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
var lexeme = new StringBuilder();
TokenKind tokenKind;
Token token;
if (Stream.Peek() == null
|| !(char.IsLetter((char)Stream.Peek()) || Stream.Peek() == '_'))
{
return null;
}
lexeme.Append(Stream.Get());
int count = 0;
while (Stream.Peek() != null
&& lineNumber == Stream.CurrentLineNumber
&& (char.IsLetter((char)Stream.Peek())
|| char.IsDigit((char)Stream.Peek())
|| Stream.Peek() == '_'))
{
count++;
lexeme.Append(Stream.Get());
}
if (KeywordToTokenKind.TryGetValue(lexeme.ToString(), out tokenKind))
{
token = new Token
(tokenKind, lexeme.ToString(), lineNumber, position);
LastToken = token;
return token;
}
token = new Token
(TokenKind.Identifier, lexeme.ToString(), lineNumber, position);
LastToken = token;
return token;
}
private Token IsCharacterLiteral()
{
int lineNumber = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
var lexeme = new StringBuilder();
Token token;
if (Stream.Peek() != '\'')
{
return null;
}
int singleQuoteCount = 2;
while (Stream.Peek() != null
&& singleQuoteCount > 0
&& lineNumber == Stream.CurrentLineNumber)
{
char c = (char)Stream.Get();
if (c == '\\' && Stream.Peek() == '\'')
{
singleQuoteCount++;
}
if (c == '\'')
{
singleQuoteCount--;
}
lexeme.Append(c);
}
if (singleQuoteCount != 0)
{
return null;
}
token = new Token
(TokenKind.CharacterLiteral, lexeme.ToString(), lineNumber, position);
LastToken = token;
return token;
}
private Token IsStringLiteral()
{
int lineNumber = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
var lexeme = new StringBuilder();
Token token;
if (Stream.Peek() != '\"')
{
return null;
}
int doubleQuoteCount = 2;
while (Stream.Peek() != null && doubleQuoteCount > 0)
{
char c = (char)Stream.Get();
if (c == '\\' && Stream.Peek() == '\"')
{
doubleQuoteCount++;
}
if (c == '\"')
{
doubleQuoteCount--;
}
lexeme.Append(c);
}
if (doubleQuoteCount != 0)
{
return null;
}
token = new Token
(TokenKind.StringLiteral, lexeme.ToString(), lineNumber, position);
LastToken = token;
return token;
}
private Token IsNumericLiteral()
{
int lineNumber = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
var lexeme = new StringBuilder();
Token token;
bool isReal = false;
if (Stream.Peek() == null || !char.IsDigit((char)Stream.Peek()))
{
return null;
}
while (Stream.Peek() != null
&& lineNumber == Stream.CurrentLineNumber
&& (char.IsDigit((char)Stream.Peek())
|| Stream.Peek() == '.'
|| Stream.Peek() == 'M'))
{
if (Stream.Peek() == '.' && (!char.IsDigit(Stream.Peek(2)[1]) || isReal))
{
break;
}
if (Stream.Peek() == '.')
{
isReal = true;
}
lexeme.Append(Stream.Get());
}
if (isReal)
{
token = new Token
(TokenKind.RealLiteral, lexeme.ToString(), lineNumber, position);
}
else
{
token = new Token
(TokenKind.IntegerLiteral, lexeme.ToString(), lineNumber, position);
}
LastToken = token;
return token;
}
private Token IsAddressLiteral()
{
int lineNumber = Stream.CurrentLineNumber;
int position = Stream.CurrentPosition;
var lexeme = new StringBuilder();
Token token;
bool isAddress = false;
if (Stream.Peek() == null || Stream.Peek() != '@')
{
return null;
}
while (Stream.Peek() != null
&& lineNumber == Stream.CurrentLineNumber
&& (char.IsDigit((char)Stream.Peek())
|| Stream.Peek() == '@'))
{
if (Stream.Peek() == '@' && (!char.IsDigit(Stream.Peek(2)[1]) || isAddress))
{
break;
}
if (Stream.Peek() == '@')
{
isAddress = true;
}
lexeme.Append(Stream.Get());
}
token = new Token
(TokenKind.AddressLiteral, lexeme.ToString(), lineNumber, position);
LastToken = token;
return token;
}
}
}
Keywords.cs
using System;
using System.Collections.Generic;
namespace Compiler.Lexer
{
public partial class Tokenizer
{
private static readonly Dictionary<string, TokenKind> KeywordToTokenKind =
new Dictionary<string, TokenKind>(StringComparer.OrdinalIgnoreCase)
{
["and"] = TokenKind.AndKeyword,
["break"] = TokenKind.BreakKeyword,
["case"] = TokenKind.CaseKeyword,
["catch"] = TokenKind.CatchKeyword,
["class"] = TokenKind.ClassKeyword,
["const"] = TokenKind.ConstKeyword,
["continue"] = TokenKind.ContinueKeyword,
["default"] = TokenKind.DefaultKeyword,
["do"] = TokenKind.DoKeyword,
["else"] = TokenKind.ElseKeyword,
["enum"] = TokenKind.EnumKeyword,
["false"] = TokenKind.FalseKeyword,
["for"] = TokenKind.ForKeyword,
["func"] = TokenKind.FuncKeyword,
["if"] = TokenKind.IfKeyword,
["in"] = TokenKind.InKeyword,
["is"] = TokenKind.IsKeyword,
["new"] = TokenKind.NewKeyword,
["nor"] = TokenKind.NorKeyword,
["null"] = TokenKind.NullKeyword,
["object"] = TokenKind.ObjectKeyword,
["or"] = TokenKind.OrKeyword,
["package"] = TokenKind.PackageKeyword,
["return"] = TokenKind.ReturnKeyword,
["sfunc"] = TokenKind.SfuncKeyword,
["svar"] = TokenKind.SvarKeyword,
["switch"] = TokenKind.SwitchKeyword,
["this"] = TokenKind.ThisKeyword,
["true"] = TokenKind.TrueKeyword,
["try"] = TokenKind.TryKeyword,
["var"] = TokenKind.VarKeyword,
["while"] = TokenKind.WhileKeyword,
};
}
}
Operators.cs
using System;
using System.Collections.Generic;
namespace Compiler.Lexer
{
public partial class Tokenizer
{
private static readonly Dictionary<string, TokenKind> OperatorToTokenKind =
new Dictionary<string, TokenKind>(StringComparer.OrdinalIgnoreCase)
{
["="] = TokenKind.Assignment,
["A+B"] = TokenKind.Addition,
["A-B"] = TokenKind.Subtraction,
["+A"] = TokenKind.UnaryPlus,
["-A"] = TokenKind.UnaryMinus,
["*"] = TokenKind.Multiplication,
["/"] = TokenKind.Division,
["%"] = TokenKind.Modulo,
["=="] = TokenKind.EqualTo,
["!="] = TokenKind.NotEqualTo,
[">"] = TokenKind.GeaterThan,
["<"] = TokenKind.LessThan,
[">="] = TokenKind.GreaterThanOrEqualTo,
["<="] = TokenKind.LessThanOrEqualTo,
["!"] = TokenKind.LogicalNOT,
["&&"] = TokenKind.LogicalAND,
["||"] = TokenKind.LogicalOR,
["A++"] = TokenKind.PostfixPlus,
["A--"] = TokenKind.PostfixMinus,
["++A"] = TokenKind.PrefixPlus,
["--A"] = TokenKind.PrefixMinus,
["~"] = TokenKind.BitwiseNOT,
["&"] = TokenKind.BitwiseAND,
["|"] = TokenKind.BitwiseOR,
["^"] = TokenKind.BitwiseXOR,
["<<"] = TokenKind.BitwiseLeftShift,
[">>"] = TokenKind.BitwiseRightShift,
["+="] = TokenKind.AdditionAssignment,
["-="] = TokenKind.SubtractionAssignment,
["*="] = TokenKind.MultiplicationAssignment,
["/="] = TokenKind.DivisionAssignment,
["%="] = TokenKind.ModuloAssignment,
["&="] = TokenKind.BitwiseANDAssignment,
["|="] = TokenKind.BitwiseORAssignment,
["^="] = TokenKind.BitwiseXORAssignment,
["<<="] = TokenKind.BitwiseLeftShiftAssignment,
[">>="] = TokenKind.BitwiseRightShiftAssignment,
};
}
}
Symbols.cs
using System;
using System.Collections.Generic;
namespace Compiler.Lexer
{
public partial class Tokenizer
{
private static readonly Dictionary<string, TokenKind> SymbolToTokenKind =
new Dictionary<string, TokenKind>(StringComparer.OrdinalIgnoreCase)
{
["("] = TokenKind.OpenParenthesis,
[")"] = TokenKind.CloseParenthesis,
["{"] = TokenKind.OpenBrace,
["}"] = TokenKind.CloseBrace,
["["] = TokenKind.OpenBracket,
["]"] = TokenKind.CloseBracket,
[":"] = TokenKind.Colon,
[";"] = TokenKind.Semicolon,
[","] = TokenKind.Comma,
["."] = TokenKind.Dot,
["?"] = TokenKind.Question,
};
}
}
Utilities.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
namespace Compiler.Preprocessor
{
public static class Utilities
{
public static List<string> GenerateList(string source)
{
return source.Split(new string[] { "\r\n", "\n" },
StringSplitOptions.None).ToList();
}
}
}
Test script
Tokenizer tokenizer = new Tokenizer(source);
Token token;
while ((token = tokenizer.Peek()) != null)
{
Console.WriteLine(token.Kind + " LEX: " + token.Lexeme + " POS: " + token.Position + " LN: " + token.LineNumber);
tokenizer.Get();
}
Samples
Hello World
func Main():
print("Hello World")
Generated tokens:
- FuncKeyword LEX: func POS: 0 LN: 0
- Identifier LEX: Main POS: 5 LN: 0
- OpenParenthesis LEX: ( POS: 9 LN: 0
- CloseParenthesis LEX: ) POS: 10 LN: 0
- Colon LEX: : POS: 11 LN: 0
- Identifier LEX: print POS: 4 LN: 1
- OpenParenthesis LEX: ( POS: 9 LN: 1
- StringLiteral LEX: "Hello World" POS: 10 LN: 1
- CloseParenthesis LEX: ) POS: 23 LN: 1
Fibonacci
func Fib(n):
if n == 1 or n == 2:
return 1
return fib(n - 1) + fib(n-1)
func Main():
print(fib(5))
Generated tokens:
- FuncKeyword LEX: func POS: 0 LN: 0
- Identifier LEX: Fib POS: 5 LN: 0
- OpenParenthesis LEX: ( POS: 8 LN: 0
- Identifier LEX: n POS: 9 LN: 0
- CloseParenthesis LEX: ) POS: 10 LN: 0
- Colon LEX: : POS: 11 LN: 0
- IfKeyword LEX: if POS: 4 LN: 1
- Identifier LEX: n POS: 7 LN: 1
- EqualTo LEX: == POS: 9 LN: 1
- IntegerLiteral LEX: 1 POS: 12 LN: 1
- OrKeyword LEX: or POS: 14 LN: 1
- Identifier LEX: n POS: 17 LN: 1
- EqualTo LEX: == POS: 19 LN: 1
- IntegerLiteral LEX: 2 POS: 22 LN: 1
- Colon LEX: : POS: 23 LN: 1
- ReturnKeyword LEX: return POS: 8 LN: 2
- IntegerLiteral LEX: 1 POS: 15 LN: 2
- ReturnKeyword LEX: return POS: 4 LN: 3
- Identifier LEX: fib POS: 11 LN: 3
- OpenParenthesis LEX: ( POS: 14 LN: 3
- Identifier LEX: n POS: 15 LN: 3
- Subtraction LEX: A-B POS: 17 LN: 3
- IntegerLiteral LEX: 1 POS: 19 LN: 3
- CloseParenthesis LEX: ) POS: 20 LN: 3
- Addition LEX: A+B POS: 22 LN: 3
- Identifier LEX: fib POS: 24 LN: 3
- OpenParenthesis LEX: ( POS: 27 LN: 3
- Identifier LEX: n POS: 28 LN: 3
- Subtraction LEX: A-B POS: 29 LN: 3
- IntegerLiteral LEX: 1 POS: 30 LN: 3
- CloseParenthesis LEX: ) POS: 31 LN: 3
- FuncKeyword LEX: func POS: 0 LN: 5
- Identifier LEX: Main POS: 5 LN: 5
- OpenParenthesis LEX: ( POS: 9 LN: 5
- CloseParenthesis LEX: ) POS: 10 LN: 5
- Colon LEX: : POS: 11 LN: 5
- Identifier LEX: print POS: 4 LN: 6
- OpenParenthesis LEX: ( POS: 9 LN: 6
- Identifier LEX: fib POS: 10 LN: 6
- OpenParenthesis LEX: ( POS: 13 LN: 6
- IntegerLiteral LEX: 5 POS: 14 LN: 6
- CloseParenthesis LEX: ) POS: 15 LN: 6
- CloseParenthesis LEX: ) POS: 16 LN: 6