LL(1) tokenizer for LISP

I am trying to write a LISP interpreter in C#, so I started with a tokenizer. I haven't finished it yet (have to handle floating point numbers & symbols), but I already rewrote it two times because I can't wasn't satisfied with design.

    public class TokenizerException : System.ApplicationException
{
public TokenizerException() {}
public TokenizerException(string message) {}
public TokenizerException(string message, System.Exception inner) {}

// Constructor needed for serialization
// when exception propagates from a remoting server to the client.
protected TokenizerException(System.Runtime.Serialization.SerializationInfo info,
System.Runtime.Serialization.StreamingContext context) {}
}
public abstract class Token
{
public string val;
public Token(string val)
{
if(val != null) this.val = val;
else this.val = "";
}
}
class OpenParenToken: Token
{
public OpenParenToken(string value) : base(value) {}
}
class CloseParenToken: Token
{
public CloseParenToken(string value) : base(value) {}
}
class NumberToken: Token
{
public NumberToken(string value) : base(value) {}
}
class StringToken: Token
{
public StringToken(string value) : base(value) {}
}
class IdToken: Token
{
public IdToken(string value) : base(value) {}
}
class SymbolToken: Token
{
public SymbolToken(string value) : base(value) {}
}

public class Tokenizer
{

private const string parens = "([])";
private string code;
private char ch;
private object token;
private List<Token> tokens;

private int p = 0;

public Tokenizer(string code)
{
this.code = code;
tokens = new List<Token>();
}

private char getCh()
{
ch = code[p];
return ch;
}

public void DumpTokens()
{
foreach(object t in tokens)
{
Console.Write("<"+t.GetType()+", "+(t as Token).val+"> ");
}
Console.WriteLine();
}

private char NextCh()
{
if(p >= code.Length) throw new TokenizerException("End of input reached, cant get more chars");
ch = getCh();
if(char.IsWhiteSpace(ch)) { p++; return NextCh(); }
else return ch;
}

private Token NextParenToken(char ch)
{
Token t;
if(parens.IndexOf(ch) <= parens.Length/2)
{
t = new OpenParenToken(ch.ToString());
}
else t = new CloseParenToken(ch.ToString());
return t;
}

private Token NextNumberToken()
{
int startPos = p;
while(p < code.Length)
{
char c = getCh();
if(!char.IsDigit(c)) break;
p++;
}
p--;
NumberToken n = new NumberToken(code.Substring(startPos, p - startPos + 1));
return n;
}

private Token NextStringToken()
{
if(p + 1 > code.Length) throw new TokenizerException("Unmatched \" at the end of the code");
int startPos = ++p;
while(p < code.Length)
{
char c = getCh();
if(c == '\"') break;
p++;
}

StringToken t = new StringToken(code.Substring(startPos, p - startPos + 1));
return t;
}

private Token NextIDToken()
{
int startPos = p;
while(p < code.Length)
{
getCh();
if(parens.IndexOf(ch) > parens.Length/2 || char.IsWhiteSpace(ch)) break;
if(parens.IndexOf(ch) >= 0 && parens.IndexOf(ch) <= parens.Length/2) throw new TokenizerException("Bad identifier at " + p);
p++;
}
p--;
string id = code.Substring(startPos, p - startPos + 1);
IdToken t = new IdToken(id);
IdTable.insert(id, t);

return t;
}

public Token NextToken()
{
char ch = NextCh();
if(parens.Contains(ch))
{
return NextParenToken(ch);
}

if(char.IsDigit(ch))
{
return NextNumberToken();
}

if(ch == '\"')
{
return NextStringToken();
}

// identifiers
return NextIDToken();
}

public void Lex()
{
tokens.Clear();
for(p=0; p < code.Length; p++)
{
NextToken();
}
}

}

• Are you sure you want to write a tokenizer in C#? Why not go with a language that is specifically designed to tokenize a stream. Such as LEX. – Martin York Feb 7 '11 at 23:45
• Yeah. I choose it as my C# course assignment. Of course, the best language to write LISP intepreter is Lisp itself ;) – Daniil Feb 8 '11 at 12:26
• You can still use C# and make use of lexer/parser generators (unless the assignment explicitly forbids it of course). Tools like LEX+YACC or ANTLR use domain specific languages in which you only specify the lexing logic and then compile them into code in your main language for you. So all you have to write yourself is the logic for actually running the lisp code after it has been lexed and parsed. – sepp2k Feb 8 '11 at 14:16
• Honestly, using lex is overkill for something as simple as Lisp's tokens. – munificent Feb 11 '11 at 5:37
• Sure, but there's also the overhead of requiring the people working with your code to now know two languages, the effort to integrate it into your build process, inability to step through it in your debugger... And you've saved, what, a hundred lines of code? – munificent Aug 13 '11 at 1:33

1) I don't use an inheritance hierarchy for the token, instead I find it more convenient to use an enum property on the token to identify the type.

2) You might want to think about "reading" the whitespace as a token that simply isn't returned (this is an extension of Snowbear's point about not using recursion to read the next char).

3) LL(1) is a term that refers to parsers, not scanners (tokenisers).

4) I also like implement my scanners as an IEnumerator that takes the string to be scanned in the constructor ... but that's just a matter of personal taste. :)

• "parser not scanners". Right. Altought its possible to make tools to mix scanning & parsing, its complicated, and sort of "bad practice" or "antipattern". Specially for someone new to compiler design stuff – umlcat Mar 28 '11 at 15:45

1) I would remove string val from your base Token class, it smells like stringly typed code. Your inheritors may have more specific information, for example number token may provide a double instead of string
2) public string val; - Pascal case for public properties is a rule for .Net
3) if(val != null) this.val = val; else this.val = ""; is a long form for:
this.val = val ?? "";
4) private char NextCh() recursion makes no sense here, regular loop is more than enough.
5) haven't found any sense having this field: private char ch;, you have it as local variable everywhere. This field should be removed.
6) code field can be made readonly
7) getCh() one-line method should be removed
8) 'token' field should be removed since it doesn't seem to be used and doesn't make any sense in 'Tokenizer' context
9) Is IdTable a singleton? Singletons are evil.
10) String.IndexOf(c) does the same as this

    while(p < code.Length)
{
char c = getCh();
if(c == '\"') break;
p++;
}


11) Your tricks with parentheses and indexOf <= Length/2 do not improve readability at all
12) IMO your class is too stateful, while parsing tokens in each method you have to keep in mind all those fields you have in your class. I would recommend remove ALL fields and use method parameters instead.

The main comment I have is that I think that C# is the wrong language to pick for tokenizing a language. Its perfectly good for the main bulk of the lisp interpretor but one of the major skills of software engineer is picking the correct language for the job. Not just of ease of writing but ease of maintainability and future work.

Now I personally like LEX but there are other lexical generators out there. But I just want to show you how simple the LEX file is. Even if you don't know the exact syntax of LEX it is simple enough that most people will immediately be able to read (assuming a CS background) and even the most complex modification can be done within an hour given an appropriate book.

OK I am not 100% sure of the exact rules for tokenizing Lisp.

DIGIT           [0-9]
NUMBER          [+-]?{DIGIT}+
EXP             [EeDd]{NUMBER}
IDTOKEN         [^)(; \t\v\r]
IDENTIFIER      {IDTOKEN}+
SPACE           [ \t\v\r]

%x              STRING COMMENT
%%

;                               { BEGIN(COMMENT); }
<COMMENT>[^\n]+                 { /* IGNORE */ }
<COMMENT>\n                     { BEGIN(INITIAL); }

{NUMBER}                        { return CONSTANT_NUMBER_INT; }

{NUMBER}{EXP}                   { return CONSTANT_NUMBER_FLOAT; }
{NUMBER}?"."{DIGIT}+{EXP}?      { return CONSTANT_NUMBER_FLOAT; }
{NUMBER}"."{DIGIT}*{EXP}?       { return CONSTANT_NUMBER_FLOAT; }

{NUMBER}\/{NUMBER}              { return CONSTANT_NUMBER_RATIO; }

\"                              { BEGIN(STRING); yymore(); }
<STRING>[^\"\\\n]+              { yymore(); }
<STRING>\\.                     { yymore(); }
<STRING>\"                      { BEGIN(INITIAL); return CONSTANT_STRING; }
<STRING>\n                      { error("NewLine inside string");}

{IDENTIFIER}                    { return NAME; }

$${ return '('; }$$                              { return ')'; }

\n                              { lineCount++; }
{SPACE}+                        { /* Ignore Space */ }

%%
/* Add this rule if there are things that can't match
* But Lisp seems to be very flexible on Identifier
* names so it seems like it is not required.
.                               { error("Unknown character"); }
*/
`

50 lines is a lot easier to read than 200.

Suggestion, many tools like your code have a "next" operation. It will be a good idea to separate that functions, into a "read" and a "move".

The first function will read the next token, but allow to stay in the same pointer, and the second function will confirm that the token has been accepted.