Comment by chubot | Hacker News Reader

Comment by chubot | Hacker News Reader

Parent Full thread

FYI PostGres appears to have over 400 keywords, shown here:

https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f...

The way I've seen most languages do it is something like this:

    switch (c[0]) {
      case 'c':
        if (strcmp(c, "case") == 0) return CASE;
        if (strcmp(c, "continue") == 0) return CONTINUE;
        ...

      case 'f':
        if (strcmp(c, "for") == 0) return FOR;
        if (strcmp(c, "friend") == 0) return FRIEND;
        ...
 
    }

I suspect that's good enough if you have a typical keyword list of say 20-100.

I just looked at Clang and it appears to build the list at runtime, using a regular hash table. I think this is because it has to handle C, C++, and Objective C, and they have different sets of keywords.

It seems like they could change it to use something like perfect hashing, and if that's even a 1% win, it would be worth it for the extra build complexity, since C and C++ compilation take up so many CPU cycles in the world.

See lib/Basic/IdentifierTable.cpp.

Although another problem is that the list of keywords depends on whether you're compiling C89, C99, C++98, C++11, etc. But that is a finite list so it seems like it still can be done with code generation ahead of time like PostGres does.

In Oil [1] I use re2c [1] recognize keywords, along with the rest of the complex lexing process, and it works well. It builds a DFA expressed in C code. The slower parts are elsewhere :)

EDIT: In theory, the DFA seems better than perfect hashing because you can bail on the second character if you get "xzoo" and no keyword starts with "xz". I think with perfect hashing yo still have to look at every byte.

The switch statement above also avoids looking at every byte in certain cases.

[1] http://www.oilshell.org/

[2] http://re2c.org/

You don't necessarily have to look at every byte to compute the hash - gperf will generate hash functions that uses only a few characters at seemingly random offsets. You do however have to do a full strcmp() to rule out a hash collision (with words outside of your set) so DFA wins there.

Imho though, the most significant difference between DFA and a PHF would be the DFA would likely generate code that introduces a lot of branches and control flow, which your CPU branch predictor might have a harder time with than a series of arithmetic ops and a single table lookup.

By the way, thanks for oilshell. I don't use it, but your blog is a superb resource on parsing techniques.

Thanks, glad you like the blog!

Nobody is really using Oil yet because I made it more of a programming language than an interactive shell, but that's changing right now :) There should be something interesting for people to use within a few months.

I would like to see a comparison between DFA and perfect hashing sometime. I wanted to do it myself, but I couldn't justify it because there are other slow parts of the parser. I am surprised that postgres got such a large speedup, to be honest. I guess it has to do with the large number of keywords.

BTW, this is related:

https://github.com/oilshell/blog-code/tree/master/fgrep-prob...

I match thousands of fixed strings "in parallel", and compare different regex engines, and compilation vs. interpretation.

The biggest surprise is that interpreted regexes like grep and ripgrep are faster than compiled DFAs with re2c for 13 strings. When you search for thousands of strings in parallel, re2c takes over.

This could be compared to perfect hashing, I think.

This will be mentioned on my blog, but I'm not sure if I'll have time to do a detailed breakdown.

The motivation for this was somewhat different. I was trying to understand if the Aho-Corasick algorithm to generate a DFA from fixed strings is "important", given that you can already generate a DFA from a regex. In other words, Aho-Corasick seems like more or less a special case of the typical regex -> DFA compilation.

When parsing C, typedef names essentially introduce new keywords so the table is constantly changing.

Yes this is a good point! That's probably why it's dynamic in Clang and not done ahead of time.

FWIW I mention the C Lexer Hack here:

The Oil Lexer: Introduction and Recap

http://www.oilshell.org/blog/2017/12/15.html#toc_5

Oops, now I agree with the people below: keywords and type names / identifiers are different :-/

typedef introduces new type names not keywords.

Depending on whether an identifier is a type name or not affects the grammar.

    x * y;

Is this a multiplication expression or a variable pointer to a value of type x?

    (x) * y

Is this a typecast of *y to the x type, or is it x multiplied by y?

This is what people mean when they say that typedefs introduce keywords in C. An easy way to solve it is to look up type names from the lexer and return a different token type (i.e. not identifier). This puts type names into a different category of lexeme to identifiers.

https://en.wikipedia.org/wiki/The_lexer_hack

I think you are confused about the concept of keywords. Yes x*y can mean two things, but neither of the interpretation has anything to do with keywords. According to the C99 standard the set of keywords is exactly and exhaustively defined in Section 6.4.1. Doing something like `typedef unsigned mynum;` doesn't make `mynum` a keyword.

I doubt barrkel is confused, as (s)he writes: ”This is what people mean when they say that typedefs introduce keywords in C.“ (it also is why caf included essentially in their comment)

Just as you cannot have a variable or function named int, you cannot have one with the same name as a typedef, for example. Also, typedef names legally can appear in the same places as the built-in types int, long, etc.

That’s why, when you write a parser for C, many times, you often need to include typedef names in the set of things to check for.

Given that there typically are way more typedef names than keywords, and you often have to check “is this a built-in type or typedef name”, keeping the two checks separate and optimizing the latter doesn’t make much sense.

Nope, not confused about keyword concept.

Normally keywords are reserved words that can't be used as identifiers because they'd make the grammar ambiguous. C typedef names aren't like this; by definition, you use them as an identifier, it's how they come into being.

Fortran is an oddball example, though: whitespace is optional (Fortan77), and keywords can be used as identifiers, making parsing difficult. There are reasons more modern languages make different choices in design.

Why is this relevant to keyword lookup? Anyway you're not supposed to use reserved keywords as either a variable or type name except primitive types (which is obviously a type).

Because it happens in the lexer, and depending on how you design your symbol table lookups, you may want to use the same hash function for all table lookups, instead of calculating different hashes for each table. Symbol table lookups can compare hash value first (store the full hash code per entry) to skip the expensive string comparison too.

Perfect hashing isn't always what you want in any case. For many languages, especially symbolically flavoured ones like C, most strings found by the lexer aren't keywords. A hash table which is mostly empty and is statically verified not to contain keyword collisions is ideal. Keep the hash code calculation separate, and do it only once. Little point in repeatedly calculating it.

There's a lot of overlap with those keywords, so perhaps the best bet is to create a single superset and use an attribute returned by the lookup to see if it's needed by the target language.

Reply on news.ycombinator.com