6
$\begingroup$

Recently I read the source code of Clang, and found that it just do the lex thing by reading characters one by one and manually do the matching. But both my teacher when I'm in college and the book "Compilers Principles, Techniques, and Tools" take lots time to illustrate how to build a regular expression state machine, and I remember the tool Flex also build a state machine (correct me if I'm wrong). I think it's easy to lost in the manually matching code and if there's something changed in a language, it is a little difficult to update the matching code.

So why nowadays people prefer to manually do the matching rather than use regular expression? Is this because the table generated by the regex tool too big if the token table is complicated? Or is this an efficiency trade-off?

p.s. Evidence for "more and more":

  • Clang

  • Gcc (as long as they abandoned flex/bison)

  • OpenJDK
  • Python
  • Protobuf

What interesting is, the author of protobuf wants to use regular expression, but give up due to open source project get better keep independent, I think this counts a reason.

Improve this question
$\endgroup$
6
  • $\begingroup$ Your teacher probably doesn't write compilers for a living. $\endgroup$
    – Yuval Filmus
    Mar 1, 2019 at 12:49
  • $\begingroup$ Why people write programs in a particular way doesn't really seem like a question about computer science, to me. It also seems to be very much a matter of opinion. $\endgroup$
    – David Richerby
    Mar 1, 2019 at 13:58
  • $\begingroup$ Can you edit your question to add some evidence for "more and more handcraft lex do not use regular expression any more"? I am not accepting nor denying the trend claimed in the title. However, I do not see any clear evidence provided in the question. Only one practical instance is mentioned, Clang. However, Clang could have been using handcraft lex all along; I haven't checked. $\endgroup$
    – John L.
    Mar 1, 2019 at 13:59
  • $\begingroup$ On the other hand, even without "more and more", I would like to know more about/explain by myself how/why the approach taught in textbook is not followed strictly, if it is true, too. $\endgroup$
    – John L.
    Mar 1, 2019 at 14:06
  • 1
    $\begingroup$ @Apass.Jack I add some evidence for you information. Indeed compilers as long as I can get the source code, none of them use regular expression. $\endgroup$
    – ravenisadesk
    Mar 1, 2019 at 15:41

1 Answer 1

Reset to default
4
$\begingroup$

While I cannot give you a definitive answer, but I think there are a couple of reasons for handcrafting lexers and parsers:

  • Good error reporting and recovery: most of tools such as Lex that provide a declarative way of defining regular expressions are hard to customize for error reporting or recovery. When you hand-craft your lexer or parser, you have more control when you encounter an error.

  • Performance: while Lex is using Finite State Automata in their lexers, and they are efficient (assuming the automata can be loaded in memory) it may pay off to handcraft your lexer to have a tight control on both runtime and memory usage. Most regular expression engines in programming languages use backtracking and may have exponential worst case runtime.

  • Infrequent changes: the token definitions (and even syntax) of programming languages doesn't change that often. So I think in the prototyping phase it makes sense to use a tool to automate the process, but when the syntax became stable, it will pay off to handcraft the lexer and parser, both in terms of error reporting and performance.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice answer. It would be nice if a few quotes in the source code or from the real developers are included. (What is even better, claim you are one.) $\endgroup$
    – John L.
    Mar 1, 2019 at 16:02
  • 1
    $\begingroup$ I'm not involved in developing parsers for real programming languages, but I've been doing research in parsing technology and parser generators, and from what I understand the main two factors for handwritten parsers (and lexers I would generalize) is more control in terms performance and error recovery. These two links about Clag may be helpful which describe why they use a handwritten recursive-descent parser: clang.llvm.org/features.html#unifiedparser gcc.gnu.org/wiki/New_C_Parser It would be indeed nice if some of the developers would confirm this. $\endgroup$
    – Wickoo
    Mar 1, 2019 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.