4 ms·

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

• kccqzy 8y ago
  typedef introduces new type names not keywords.
  • barrkel 8y ago
    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 https://en.wikipedia.org/wiki/The_lexer_hack
    • summerlight 8y ago
      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).
      • barrkel 8y ago
        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.
    • kccqzy 8y ago
      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.
      • Someone 8y ago
        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.
      • barrkel 8y ago
        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.
• chubot 8y ago
  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 http://www.oilshell.org/blog/2017/12/15.html#toc_5
  • chubot 8y ago
    Oops, now I agree with the people below: keywords and type names / identifiers are different :-/