7 ms·

Writing Compilers Quickly

31 points by r11t 17y ago

hga 17y ago
Read the linked http://en.wikipedia.org/wiki/Monkey_patch http://en.wikipedia.org/wiki/Monkey_patch if you want to find out what monkey patching and duck punching are ^_^.
kingkongreveng_ 17y ago
A perl programmer talking about compilers in 2010 doesn't mention Parrot? Parrot has to be the easiest and fastest way to get a compiler up and running these days.
- tptacek 17y ago
  He's not targeting a VM or a runtime, is he? His compiler looks more like a code generator, a la yacc.
  - kingkongreveng_ 17y ago
    Well the CaPerl project he mentions just translates perl5 with his special keywords to standard perl5 code, I think. Who knows what he's doing here.
    - tptacek 17y ago
      He's writing yacc for crypto protocols. You write an algorithm in his Stupid language, you and others verify it Stupidly, and then compile it to your real language.
      - statictype 17y ago
        So the language's compiler does analysis of the algorithm for common crypto flaws? (like buffer-overruns and timeable iterations ...)?
        tptacek 17y ago
        Nope. It does nothing at all except to standardize the notation.
tptacek 17y ago
Could not disagree more about lexer generators. Every device we support comes with 1-2 parsers, and we started out thinking that Ruby's built-in regex support made flex unnecessary. Bzzzt. Lexers are fiddley whether you write them in Flex or Ruby, but the Ruby version is harder to write. 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.
- barrkel 17y ago
  I don't agree, for a simple reason - most programming language lexical analysis is extremely simple and a lexer can be hand-written in less than an hour. Here's the outline of a NextToken routine (or whatever you want to call it) that does the lexical analysis: * 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.
pmjordan 17y ago
I'm wondering if he's tried to do real work with ANTLR and ANTLRWorks in particular. I found them extremely temperamental and fiddly to work with, but this was more than a year ago.
- gchpaco 17y ago
  They haven't gotten any less temperamental or brittle. The default tokens have a rude tendency to store the entire input stream as it is being parsed, which was a really rude surprise for us (had to rip it out and do LL(1) by hand, with minimal memory demands). I like a lot of features of ANTLR, but it is not the sort of tool I like to use and abuse.
marshallp 17y ago
use lisp macros or prolog dcg's

31 points by r11t 17y ago

hga 17y ago

Read the linked http://en.wikipedia.org/wiki/Monkey_patch http://en.wikipedia.org/wiki/Monkey_patch if you want to find out what monkey patching and duck punching are ^_^.

kingkongreveng_ 17y ago

A perl programmer talking about compilers in 2010 doesn't mention Parrot? Parrot has to be the easiest and fastest way to get a compiler up and running these days.

tptacek 17y ago
He's not targeting a VM or a runtime, is he? His compiler looks more like a code generator, a la yacc.
- kingkongreveng_ 17y ago
  Well the CaPerl project he mentions just translates perl5 with his special keywords to standard perl5 code, I think. Who knows what he's doing here.
  - tptacek 17y ago
    He's writing yacc for crypto protocols. You write an algorithm in his Stupid language, you and others verify it Stupidly, and then compile it to your real language.
    - statictype 17y ago
      So the language's compiler does analysis of the algorithm for common crypto flaws? (like buffer-overruns and timeable iterations ...)?
      - tptacek 17y ago
        Nope. It does nothing at all except to standardize the notation.

tptacek 17y ago

Could not disagree more about lexer generators. Every device we support comes with 1-2 parsers, and we started out thinking that Ruby's built-in regex support made flex unnecessary. Bzzzt. Lexers are fiddley whether you write them in Flex or Ruby, but the Ruby version is harder to write. 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.

barrkel 17y ago
I don't agree, for a simple reason - most programming language lexical analysis is extremely simple and a lexer can be hand-written in less than an hour. Here's the outline of a NextToken routine (or whatever you want to call it) that does the lexical analysis: * 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.

pmjordan 17y ago

I'm wondering if he's tried to do real work with ANTLR and ANTLRWorks in particular. I found them extremely temperamental and fiddly to work with, but this was more than a year ago.

gchpaco 17y ago
They haven't gotten any less temperamental or brittle. The default tokens have a rude tendency to store the entire input stream as it is being parsed, which was a really rude surprise for us (had to rip it out and do LL(1) by hand, with minimal memory demands). I like a lot of features of ANTLR, but it is not the sort of tool I like to use and abuse.

marshallp 17y ago

use lisp macros or prolog dcg's