Skip to main content
deleted 19 characters in body
Source Link
kaya3
  • 20.8k
  • 46
  • 126

I suspect that more keywords may make implementing a compiler more complicated, slower as there are more keywords to compare tokens against or similar

This is probably unfounded. There are two parts to it:

  • The lexer has to tell whether a token like while or count is a keyword or an identifier. This can be done by looking up the string in a hashtable, which takes O(1) time independently of the number of keywords.
  • When the parser sees a keyword token, it has to branch on the kind of keyword; for example, on an if token call parseIfStmt, on a while token call parseWhileStmt, on a throw token call parseThrowStmt and so on. This can be done in a switch statement which can be compiled to something more efficient than just checking the keywords one-by-one. If the lexer has already reduced keywords from strings to enum values, then a dense switch can use a jump table, whereas if they are still strings then a hashtable is a good option. Either way, the time taken to choose the right branch doesn't have to scale with the number of keywords.

So having more keywords probably has very little effect on the performance of the compiler's performance, in and of itself.

That said, having more concepts in the language might mean the compiler has more work to do after parsing, and if the additional concepts in the language correspond with additional keywords then these two things would be correlated.

I suspect that more keywords may make implementing a compiler more complicated, slower as there are more keywords to compare tokens against or similar

This is probably unfounded. There are two parts to it:

  • The lexer has to tell whether a token like while or count is a keyword or an identifier. This can be done by looking up the string in a hashtable, which takes O(1) time independently of the number of keywords.
  • When the parser sees a keyword token, it has to branch on the kind of keyword; for example, on an if token call parseIfStmt, on a while token call parseWhileStmt, on a throw token call parseThrowStmt and so on. This can be done in a switch statement which can be compiled to something more efficient than just checking the keywords one-by-one. If the lexer has already reduced keywords from strings to enum values, then a dense switch can use a jump table, whereas if they are still strings then a hashtable is a good option. Either way, the time taken to choose the right branch doesn't have to scale with the number of keywords.

So having more keywords probably has very little effect on the performance of the compiler's performance, in and of itself.

That said, having more concepts in the language might mean the compiler has more work to do after parsing, and if the additional concepts in the language correspond with additional keywords then these two things would be correlated.

I suspect that more keywords may make implementing a compiler more complicated, slower as there are more keywords to compare tokens against or similar

This is probably unfounded. There are two parts to it:

  • The lexer has to tell whether a token like while or count is a keyword or an identifier. This can be done by looking up the string in a hashtable, which takes O(1) time independently of the number of keywords.
  • When the parser sees a keyword token, it has to branch on the kind of keyword; for example, on an if token call parseIfStmt, on a while token call parseWhileStmt, on a throw token call parseThrowStmt and so on. This can be done in a switch statement which can be compiled to something more efficient than just checking the keywords one-by-one. If the lexer has already reduced keywords from strings to enum values, then a dense switch can use a jump table, whereas if they are still strings then a hashtable is a good option. Either way, the time taken to choose the right branch doesn't have to scale with the number of keywords.

So having more keywords probably has very little effect on the compiler's performance, in and of itself.

That said, having more concepts in the language might mean the compiler has more work to do after parsing, and if the additional concepts in the language correspond with additional keywords then these two things would be correlated.

Source Link
kaya3
  • 20.8k
  • 46
  • 126

I suspect that more keywords may make implementing a compiler more complicated, slower as there are more keywords to compare tokens against or similar

This is probably unfounded. There are two parts to it:

  • The lexer has to tell whether a token like while or count is a keyword or an identifier. This can be done by looking up the string in a hashtable, which takes O(1) time independently of the number of keywords.
  • When the parser sees a keyword token, it has to branch on the kind of keyword; for example, on an if token call parseIfStmt, on a while token call parseWhileStmt, on a throw token call parseThrowStmt and so on. This can be done in a switch statement which can be compiled to something more efficient than just checking the keywords one-by-one. If the lexer has already reduced keywords from strings to enum values, then a dense switch can use a jump table, whereas if they are still strings then a hashtable is a good option. Either way, the time taken to choose the right branch doesn't have to scale with the number of keywords.

So having more keywords probably has very little effect on the performance of the compiler's performance, in and of itself.

That said, having more concepts in the language might mean the compiler has more work to do after parsing, and if the additional concepts in the language correspond with additional keywords then these two things would be correlated.