12 ms·

One of the moments where I really started to feel like I was starting to 'see the matrix' was when I was working on a regex engine to try to make my compiler fa

One of the moments where I really started to feel like I was starting to 'see the matrix' was when I was working on a regex engine to try to make my compiler faster (it didn't, but that's another story). The asymptotically fast way to approach regex processing actually involves writing a parser to process the regex, so in order to write a fast compiler, you need to write another fast compiler to process the regexes that will process the actual programs that you write. But, if your regexes get complex, you should really write a parser to parse the regexes that will parse the actual program. This is where you realize that it's parsers all the way down. When you think more about regexes this way, you realize that a regex is just a tiny description of a virtual machine (or emulator) that can process the simplest of instructions (check for 'a', accept '0-9', etc.). Each step in the regex is just a piece of bytecode that can execute, and if you turn a regex on its side you can visualize it as just a simple assembly program.

chrisseaton 10y ago
I don't get it - what do regexps have to do with compilers and how do they make compilers faster?
- ender7 10y ago
  The first step in compilation is lexing -- converting a character stream to a stream of semantic "tokens", where a token might be "a number literal" or "the 'while' keyword" or a single character token like "{". This process is usually done via regexs.
  - duaneb 10y ago
    A lot of optimizations on arbitrary byte code often look for patterns in byte streams (or in reified assembly) in similar ways to regexes.
    - teraflop 10y ago
      For many years, an important stage of the GHC Haskell compiler consisted of a giant Perl script full of regexes. http://code.haskell.org/ghc-scp/ghc/docs/comm/the-beast/mangler.html http://code.haskell.org/ghc-scp/ghc/docs/comm/the-beast/mang...
  - chrisseaton 10y ago
    I didn't think of lexer rules as regular expressions but I suppose they are of course. But I can't imagine a lexer would ever be the performance bottleneck in a compiler.
    - adrianratnapala 10y ago
      According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process). I am not sure if this is true any more. It probably depends on the language. Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and difficult languages like C++ will shift the bottlenecks to later stages.
      - jbangert 10y ago
        C++ compilers (at least on most current code bases that don't need modules) still need to parse and lex headers though -- so actual executable code is pretty rare. Most compilations are also debug builds which don't optimize(but creating debug information can also be slow; the really slow step is usually linking)
      - jbangert 10y ago
        C++ compilers (at least on most current code bases that don't need modules) still need to parse and lex headers though -- so actual executable code is pretty rare. Most compilations are also debug builds which don't optimize(but creating debug information can also be slow; the really slow step is usually linking)
      - readittwice 10y ago
        I think I read that too, but I am not sure that this is actually true. Please correct me if I am wrong, according to the Rust developers code generation seems to be the bottleneck. That's why they are working on incremental compilation to improve compilation times. They detect changes in the input files by comparing the AST to the old version. So parsing is always necessary but later stages can be cached. That seems to confirm that parsing is not the bottleneck, at least not for Rust. OTOH that probably also depends on your use case, JS for example needs to get parsed at every page load. Some JS-VMs only parse the source code lazily, at first the parser only detects function boundaries. Only if this function is really executed, the function gets parsed completely.
  - paulddraper 10y ago
    I think they're usually done with a specific FSM, rather than general regular expressions.
  - vidarh 10y ago
    It is rare for lexers to use actual regex engines, in my experience, as it's impractical if you want to do proper error reporting unless you write your own regex engine in which case people tend to opt for hand-writing lexer rules. It's not unheard of, and I have the impression it's getting more common, but still only a small proportion of the compilers I've seen over the years explicitly use regexps.
    - rocket69 10y ago
      So, what parses the regex in the lex, flex, Jison, etc...
      - vidarh 10y ago
        Most tools like that reduces any regexes to dfa's or similar, but most production compilers I've seen don't use tools like that because they're a pain to do proper error reporting for.
        rocket69 10y ago
        Yea, we're not talking about compilers, we're talking about lexers. Regex doesn't even make a little bit of sense in a compiler world. What lexer are you working with?
        vidarh 10y ago
        One of the main uses of lexers are in compiler. There are others, certainly, like parsing various configuration formats etc. but they tend to either use tool generated lexers that tend to use dfa's, or handwritten lexers that may or may not use regexes, but there too it's fairly uncommon to see much regex use. I custom write all of my lexers for exactly the reasons I outlined above.
  - titzer 10y ago
    Not all parsers do a lexing step. Such ones are called "scannerless parsers" and can be much, much faster than parsers with a separate lexing step.
wyager 10y ago
I mean, the whole point of regexes (not to be confused with PCREs) is that any given regex is isomorphic to some canonical finite state machine. It is, specifically speaking, a tiny description of an FSM over the alphabet of ASCII characters (or whatever charset you're using). Interestingly, regexes/FSMs are (IIRC) the most powerful class of machines for which equivalence is decidable. So if you give me any two regexes, I can tell you if they match on all the same strings, but this is not true for any more powerful grammar.
- adrianratnapala 10y ago
  Presumably that means "this is not true for any more powerful class of grammars". Any particular pair grammars from that class. I mean if you showed me a yacc grammar for Pascal and another one for Java, I am sure I could prove they were ineqivelent. More tricky, if you gave someone clever a hand written Pascal parser and that same yacc grammar she could probably prove equivilency with some effort. But there is no guarantee that this is always possible.
  - wyager 10y ago
    Yes, that is what I meant. > I mean if you showed me a yacc grammar for Pascal and another one for Java, This is why I said "any", and not "all". In most practical cases, you can tell if two grammars are different, but it's easy to construct cases where you can't.
- hvidgaard 10y ago
  While it is true for Regular Languages (FSM) strict RegExs, it's hardly true for any contemporary implementation of RegExs. They have back references and other constructs that make them more powerful than a Regular Language, and thereby make it impossible to decide equivalence in the general case.
  - wyager 10y ago
    Hence "not to be confused with PCREs", which most pseudo-regex implementations are based off of.
signa11 10y ago
> When you think more about regexes this way, you realize that a regex is just a tiny description of a virtual machine (or emulator) that can process the simplest of instructions (check for 'a', accept '0-9', etc.). Each step in the regex is just a piece of bytecode that can execute, and if you turn a regex on its side you can visualize it as just a simple assembly program. which is _exactly_ what bpf does :)
posterboy 10y ago
A regular expression is by definition a regular grammar, the least mighty language in the chomsky hierarchy and realizable by finite state automaton. You can get something similar to a virtual equivalent of a turing complete language, due to the fact that the tape of the turing machine is, contrary to the hypothetical theory, practically limit by recourses. CPUs are finite state automatons, yet we use them to solve problems of sufficiently low complexity in NP space. I am not an expert, please correct me if I am wrong.
- pmiller2 10y ago
  Real computers are much closer to linear bounded automata than full Turing machines. https://en.m.wikipedia.org/wiki/Linear_bounded_automaton https://en.m.wikipedia.org/wiki/Linear_bounded_automaton
Lanzaa 10y ago
If you spent much time looking at regexs you might enjoy this set of articles about improving regex engine performance: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

chrisseaton 10y ago

I don't get it - what do regexps have to do with compilers and how do they make compilers faster?

ender7 10y ago
The first step in compilation is lexing -- converting a character stream to a stream of semantic "tokens", where a token might be "a number literal" or "the 'while' keyword" or a single character token like "{". This process is usually done via regexs.
- duaneb 10y ago
  A lot of optimizations on arbitrary byte code often look for patterns in byte streams (or in reified assembly) in similar ways to regexes.
  - teraflop 10y ago
    For many years, an important stage of the GHC Haskell compiler consisted of a giant Perl script full of regexes. http://code.haskell.org/ghc-scp/ghc/docs/comm/the-beast/mangler.html http://code.haskell.org/ghc-scp/ghc/docs/comm/the-beast/mang...
- chrisseaton 10y ago
  I didn't think of lexer rules as regular expressions but I suppose they are of course. But I can't imagine a lexer would ever be the performance bottleneck in a compiler.
  - adrianratnapala 10y ago
    According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process). I am not sure if this is true any more. It probably depends on the language. Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and difficult languages like C++ will shift the bottlenecks to later stages.
    - jbangert 10y ago
      C++ compilers (at least on most current code bases that don't need modules) still need to parse and lex headers though -- so actual executable code is pretty rare. Most compilations are also debug builds which don't optimize(but creating debug information can also be slow; the really slow step is usually linking)
    - jbangert 10y ago
      C++ compilers (at least on most current code bases that don't need modules) still need to parse and lex headers though -- so actual executable code is pretty rare. Most compilations are also debug builds which don't optimize(but creating debug information can also be slow; the really slow step is usually linking)
    - readittwice 10y ago
      I think I read that too, but I am not sure that this is actually true. Please correct me if I am wrong, according to the Rust developers code generation seems to be the bottleneck. That's why they are working on incremental compilation to improve compilation times. They detect changes in the input files by comparing the AST to the old version. So parsing is always necessary but later stages can be cached. That seems to confirm that parsing is not the bottleneck, at least not for Rust. OTOH that probably also depends on your use case, JS for example needs to get parsed at every page load. Some JS-VMs only parse the source code lazily, at first the parser only detects function boundaries. Only if this function is really executed, the function gets parsed completely.
- paulddraper 10y ago
  I think they're usually done with a specific FSM, rather than general regular expressions.
- vidarh 10y ago
  It is rare for lexers to use actual regex engines, in my experience, as it's impractical if you want to do proper error reporting unless you write your own regex engine in which case people tend to opt for hand-writing lexer rules. It's not unheard of, and I have the impression it's getting more common, but still only a small proportion of the compilers I've seen over the years explicitly use regexps.
  - rocket69 10y ago
    So, what parses the regex in the lex, flex, Jison, etc...
    - vidarh 10y ago
      Most tools like that reduces any regexes to dfa's or similar, but most production compilers I've seen don't use tools like that because they're a pain to do proper error reporting for.
      - rocket69 10y ago
        Yea, we're not talking about compilers, we're talking about lexers. Regex doesn't even make a little bit of sense in a compiler world. What lexer are you working with?
        vidarh 10y ago
        One of the main uses of lexers are in compiler. There are others, certainly, like parsing various configuration formats etc. but they tend to either use tool generated lexers that tend to use dfa's, or handwritten lexers that may or may not use regexes, but there too it's fairly uncommon to see much regex use. I custom write all of my lexers for exactly the reasons I outlined above.
- titzer 10y ago
  Not all parsers do a lexing step. Such ones are called "scannerless parsers" and can be much, much faster than parsers with a separate lexing step.

wyager 10y ago

I mean, the whole point of regexes (not to be confused with PCREs) is that any given regex is isomorphic to some canonical finite state machine. It is, specifically speaking, a tiny description of an FSM over the alphabet of ASCII characters (or whatever charset you're using). Interestingly, regexes/FSMs are (IIRC) the most powerful class of machines for which equivalence is decidable. So if you give me any two regexes, I can tell you if they match on all the same strings, but this is not true for any more powerful grammar.

adrianratnapala 10y ago
Presumably that means "this is not true for any more powerful class of grammars". Any particular pair grammars from that class. I mean if you showed me a yacc grammar for Pascal and another one for Java, I am sure I could prove they were ineqivelent. More tricky, if you gave someone clever a hand written Pascal parser and that same yacc grammar she could probably prove equivilency with some effort. But there is no guarantee that this is always possible.
- wyager 10y ago
  Yes, that is what I meant. > I mean if you showed me a yacc grammar for Pascal and another one for Java, This is why I said "any", and not "all". In most practical cases, you can tell if two grammars are different, but it's easy to construct cases where you can't.
hvidgaard 10y ago
While it is true for Regular Languages (FSM) strict RegExs, it's hardly true for any contemporary implementation of RegExs. They have back references and other constructs that make them more powerful than a Regular Language, and thereby make it impossible to decide equivalence in the general case.
- wyager 10y ago
  Hence "not to be confused with PCREs", which most pseudo-regex implementations are based off of.

signa11 10y ago

> When you think more about regexes this way, you realize that a regex is just a tiny description of a virtual machine (or emulator) that can process the simplest of instructions (check for 'a', accept '0-9', etc.). Each step in the regex is just a piece of bytecode that can execute, and if you turn a regex on its side you can visualize it as just a simple assembly program. which is _exactly_ what bpf does :)

posterboy 10y ago

A regular expression is by definition a regular grammar, the least mighty language in the chomsky hierarchy and realizable by finite state automaton. You can get something similar to a virtual equivalent of a turing complete language, due to the fact that the tape of the turing machine is, contrary to the hypothetical theory, practically limit by recourses. CPUs are finite state automatons, yet we use them to solve problems of sufficiently low complexity in NP space. I am not an expert, please correct me if I am wrong.

pmiller2 10y ago
Real computers are much closer to linear bounded automata than full Turing machines. https://en.m.wikipedia.org/wiki/Linear_bounded_automaton https://en.m.wikipedia.org/wiki/Linear_bounded_automaton

Lanzaa 10y ago

If you spent much time looking at regexs you might enjoy this set of articles about improving regex engine performance: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html