Writing Compilers Quickly
links.org
links.org
We've settled on Ragel for lexers; Craig wrote "ralex", which I don't use or understand but which he insists we're about to open source. So I recommend Ragel. Or Flex. Or anything but just hand-hacking your own tokenizer.
* Skip whitespace and comments, keeping track of newlines as needed
* Check for end of file
* Determine token type from first character (typically a switch statement or equivalent)
* Scan in remainder of token's characters (depending on token type - and possibly more discrimination for common prefixes, such as 10 vs 10.25, ints vs floats)
* Do any conversions, such as string -> numbers as necessary
* Look up identifiers for keywords
A simple hand-written scanner for a language like C (excluding the preprocessor etc.) written in C itself shouldn't exceed a couple of hundred lines or so. If you're willing to sacrifice some readability and performance, I guess you could squish it down close to 60.
With languages that need more complicated state transition mechanics than C or similar, using a generator may make sense. But fully general regexes are ill-suited for creating lexical analysers. With lexical analysis, you're looking to classify a pattern of characters from the head of a list; language and library regex support will generally only tell you if a particular string matches / starts with a regex, or lets you search a string for the regex. A lexer effectively wants to annotate multiple acceptance states in the FSA, and return different values depending on which acceptance state was chosen. Regexes from languages and libraries generally only pop out with a boolean, having merged the acceptance states together in the DFA (never mind non-regular regular expressions, such as those with backrefs etc.). So using regexes for writing a lexer will be inefficient and won't give you hints when the language defined by one regex is actually a subset of the language defined by another.
* whitespace around operators is optional, except that sometimes a symbol adjacent to a variable means something completely different
* "foo" is a keyword in type signatures, but a normal identifier otherwise
* indentation is meaningful, and must generate INDENT or DEDENT tokens depending on the indentation of some arbitrary number of prior lines
* indentation is meaningful based on whether the first non-whitespace token on a line is aligned in the same column as a specific token in the prior line, based on parsed syntax, oh god what were these people smoking
...and so on. It's easy to get into situations where merely lexing requires keeping some sort of context, requires interleaving with parsing such that parse errors may cause the lexer to backtrack and reinterpret things, or possibly even worse.
In fact, I wouldn't be surprised if it were possible to construct an especially pathological bit of perl that couldn't be lexically analyzed without running the program.
Isn't this decision something that should be punted out of the tokenizer and into the parser?
All of the stuff I mentioned gives you the choice of either more work during parsing (which is usually hard enough already), or building a crazy Rube Goldberg-esque tokenizer--neither of which is appealing.
Yes and no. It's trivial to construct a pathological Perl 5 program which has indeterminate parsing without running... but in those cases where it's possible, you have only one of two or three possible interpretations for a specific sequence of tokens.
As well, no one would write code that indeterminate by accident. It's always malicious.
It's 382 lines of ANSI C according to sloccount. Reading the array at the top of the file, there are about 30 tokens in Lua. So, you are probably going to write at least 30 test cases.
Writing that in less than an hour is being generous. But, it should be doable in a day.
http://www.daimi.au.dk/~sandmann/scanner.c
It's 387 lines of C, and if you wanted to prove a point, you could get the line-count down by compacting the table and removing braces etc.
Note that it doesn't make any C specific assumptions. Each type of token is matched by its own function, and then in the end the longest match is chosen. This is exactly what lex does - with two differences: (a) my scanner is slower, and (b) you have the full recognition power of C instead of just regular expressions. These days (b) outweighs (a) so much that it's just not funny.
I'd agree that flex/lex are just not worth it anymore.
http://github.com/nostrademons/eve-language/blob/master/boot...
That's 52 lines of rules. 68 lines of boilerplate code that was copied verbatim out of the Alex manual and changed a bit to work in a different monad. About 70 lines of code to add the indent/dedent/newline tokens for whitespace sensitivity. Note that that's with whitespace rules that are more permissive than just about any language out there (you can break lines without a continuation character between any pair of matched delimiters, as well as before or after any infix operator).
Yes, hand-writing a lexer is easy. Writing one with a lexer generator is even easier (and would be easier still if Alex had an easier API to work with).
Personally, I like lexers, but would rather move the language definition to one where recursive descent parsing works.
I've only just got into parsing and I know for sure that there are more challenging problems, but for a dynamic language like Javascript there is a pretty major example of where this worked. JS Lint: http://www.jslint.com/fulljslint.js
1) Split source into lines
2) Run each line through a regex: /^\s([(){}\[.,:;'"~\?\]#@]|==?=?|\/(\(jslint|members?|global)?|=|\/)?|\[\/=]?|\+[+=]?|-[\-=]?|%=?|&[&=]?|\|[|=]?|>>?>?=?|<([\/=!]|\!(\[|--)?|<=?)?|\^=?|\!=?=?|[a-zA-Z_$][a-zA-Z0-9_$]|[0-9]+([xX][0-9a-fA-F]+|\.[0-9]*)?([eE][+\-]?[0-9]+)?)/
3) Look at the resulting token character by character and define what kind of token it is.
Once it has these parsed tokens JS Lint then uses a Pratt Parser to check syntax and style, but you could easily use the same tokenizer and build a parse tree as part of a translator or compiler instead.