N.Wirth's book on compiler introduces the concept of symbol table and states that every declaration statement results in a new entry in symbol table.

Then after showing how an entry in symbol table looks like he talks about types which can be specified anonymously like the following :


Then it is written that named types are represented in the symbol table entry by an entry of type object -----(1)

which in turn refers to an object of type "Type" and provides the following snippet :

$\ Type = POINTER TO TypDesc; TypDesc = RECORD form, len: INTEGER; fields: Object; base: Type END $

The book is written in pascal or oberon and I don't understand its syntax but I want to know how to interpret this type desc .

Does whatever follows typedesc , describes the fields of the record ? Form ,length,fields and base being the columns of the record ?

Wirth ,for the following declaration :


shows the following symbol table entry :

enter image description here

The picture , I am getting from this is every object will point to its "type" ,.

In case of records , the type will point to the first field . I guess each field is being implemented something like a C structure ,having the pointer to the next field and pointer to its base type as its member . And here in the diagram ,the attribute "next" is pointing to "g" and its attribute "type" is pointing to "integer" .

The above was just an attempt to interpret what the author exactly means by it . Is my understanding correct ?

  • 1
    $\begingroup$ You may want to consider using a more modern reference. This is an overly concrete and low-level (description of a) representation of a symbol table. Conceptually, a symbol table is a mapping from the symbols to information about those symbols and so nowadays you'd likely just use a standard hash table or "dictionary" type. There's little point in worrying about how exactly these are represented for the purposes of building a compiler. $\endgroup$ – Derek Elkins left SE Dec 16 '17 at 23:54
  • $\begingroup$ @DerekElkins : Mordern reference as in a mordern textbook ? $\endgroup$ – Eddie Dorphy Dec 19 '17 at 17:01
  • 1
    $\begingroup$ A newer textbook would likely be okay. There are plenty of freely available books, lecture notes, and even open online courses about compiler design too. Many will use more mainstream languages. Others will use languages that are a better fit for compiler writing. If you just want to make a basic compiler for a simple language, then probably any resource (including this one) will suffice, though some are better written than others. If you care about optimizing for modern hardware, or common modern features like garbage collection, concurrency, and reflection, you'll need recent resources. $\endgroup$ – Derek Elkins left SE Dec 20 '17 at 7:00

Pretty much, yes. The list of variable names form a linked list, and the fields within a record are basically a nested symbol table.

  • $\begingroup$ Thanks Will . Could you elaborate the term "nested symbol table" ? Will it be same as the notion that a field can be of a user defined type which will be having its own linked list like implementation ? $\endgroup$ – Eddie Dorphy Dec 16 '17 at 6:38
  • $\begingroup$ Exactly that. If you look, it is the same structure - a linked list of records, each with the fields "name", "class", "next" (though the name isn't shown in the top row, they definitely have a pointer there), and "type". $\endgroup$ – Will Crawford Dec 16 '17 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.