Programming in Lua : 11.5

Part II. Tables and Objects Chapter 11. Data Structures

11.5 - Sets and Bags

Suppose you want to list all identifiers used in a program source; somehow you need to filter the reserved words out of your listing. Some C programmers could be tempted to represent the set of reserved words as an array of strings, and then to search this array to know whether a given word is in the set. To speed up the search, they could even use a binary tree or a hash table to represent the set.

In Lua, an efficient and simple way to represent such sets is to put the set elements as indices in a table. Then, instead of searching the table for a given element, you just index the table and test whether the result is nil or not. In our example, we could write the next code:

    reserved = {
      ["while"] = true,     ["end"] = true,
      ["function"] = true,  ["local"] = true,
    }
    
    for w in allwords() do
      if reserved[w] then
        -- `w' is a reserved word
        ...

(Because while is a reserved word in Lua, we cannot use it as an identifier. Therefore, we cannot write while = 1; instead, we use the ["while"] = 1 notation.)

You can have a clearer initialization using an auxiliary function to build the set:

    function Set (list)
      local set = {}
      for _, l in ipairs(list) do set[l] = true end
      return set
    end
    
    reserved = Set{"while", "end", "function", "local", }