Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2584 > unrolled thread

Re: Parsing using a Graphics Processing Unit (GPU)?

Back to article view | Back to comp.compilers

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Parsing using a Graphics Processing Unit (GPU)? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2020-09-03 17:52 +0300
    Re: Parsing using a Graphics Processing Unit (GPU)? Stefan Monnier <monnier@iro.umontreal.ca> - 2020-09-22 18:18 -0400

#2584 — Re: Parsing using a Graphics Processing Unit (GPU)?

I hate getting overly involved in this, but not only is GPU lexing
possible, it probably isn't that complicated.

To make this practical, let's assume we are lexing a language like C
and we have split our file into arbitrary chunks (say 1000 bytes) and
are trying to process them in parallel.

First, note that while the preprocessor can do some pretty complicated
things to the output token stream, it doesn't have that impact at the
lexical level, the level of turning things into "raw" tokens.  You
cannot write a macro that introduces a quote character or a comment
delimiter. And those are your main issues in terms of lexing.  Yes,
you have to do symbol table lookup (and macro expansion) as a
post-step, but you aren't doing that on a character-by-character
basis.

In fact, you basically have only a few different "states" to worry about.

1) you are lexing normally, not in one of the special cases that follows.
2) you are in a string, i.e. you have seen a quote character and until
you see the matching one, you are not tokenizing at all.  There are
two quote characters so call them states 2a and 2b.
3) you have seen a C comment start /* and are looking for */.  Again,
you are not tokenizing.
4) you have seen a C++ comment start // and are looking for a newline.
Not tokenizing.
5) you have seen a # (preceded only with whitespace) and are looking
for a newline.  You are tokenizing, but the line is a preprocessor
directive.
6) you are in code that is in a #if and will be skipped for that reason.
7) you are at the start of your buffer and the previous character might be a \

So, given those states, assume that your chunk starts in state 1 and
lex like that, but saving the contents as a string in case of state 2.
On a quote, keep going but reverse the text contexts.  Similar idea
for comment marks and newlines and hash characters.  You only have to
deal with state 7 for the first character and if you consider the
first character part of the previous chunk, just that you get to
inspect, you can probably finesse that issue.

For each chunk, you have roughly two interesting sequences of possible
tokens, whether you were in a string or not.  And you can easily patch
those together because your left context always tells you which state
you enter a chunk in.

Now, while I did this hand-waving analysis for C.  Most languages are
not significantly more complex at the lexical level.  Basically, you
are tokenizing or you are collecting a string or the text will be
entirely thrown away, and you mostly care about the first two cases
(tokenizing or building a string and even building a string is easy
(although can use memory) so you really only care about the tokenizing
case.

So build a SIMD lexer using techniques based upon Wu Manber (and
Glushkov NFAs) and break your text into chunks and let the GPU have a
field day.

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

[toc] | [next] | [standalone]

#2616

> I hate getting overly involved in this, but not only is GPU lexing
> possible, it probably isn't that complicated.

Indeed.  Extra bonus points if you do it generically by having the `lex`
tool do that parallelization for you.  I think in the general case it
could be a potentially costly parallelization, but in practice it should
be pretty efficient for most programming languages.


        Stefan

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web