0
\$\begingroup\$

From what I understand, a lexer that parses a language (e.g., C) is essentially a state machine that builds a list of tokens (essentially pointers) it finds in the source code. Has anyone ever considered whether or not this problem maps well to FPGA architectures?

\$\endgroup\$
  • 1
    \$\begingroup\$ They do not. The FSM is too complex. A processor can go through a large FSM faster than an FPGA with less logic utilization. \$\endgroup\$ – user110971 Dec 27 '16 at 14:48
2
\$\begingroup\$

Yes, it would work well. FPGAs contain wide, fast memories that make it easy to implement a state machine that could process one input symbol per clock.

But the question remains, does it make sense to do this in the context of the other things that need to happen when processing languages? CPUs with high speed clocks also execute table-driven state machines very efficiently, and they provide a better environment for implementing the higher-level parsing tasks.

\$\endgroup\$
  • \$\begingroup\$ Can you point to any relevant case studies or popular implementations? \$\endgroup\$ – Dmitri Nesteruk Jan 1 '17 at 18:10
  • \$\begingroup\$ Perhaps the most well-known example is the GNU compiler collection (aka "GCC"). However, this is not the easiest way to start if this topic is completely new to you. \$\endgroup\$ – Dave Tweed Jan 1 '17 at 19:52
  • \$\begingroup\$ You mean to tell me someone has implemented some part of GCC on an FPGA? \$\endgroup\$ – Dmitri Nesteruk Jan 1 '17 at 23:26
  • 1
    \$\begingroup\$ No, of course not. I don't think that anyone has ever done what you're suggesting. I thought you wanted examples of language parsing. \$\endgroup\$ – Dave Tweed Jan 2 '17 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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