Re: Pascal compiler and sets

dallison@bfsec.bt.co.uk (Dave Allison) writes:
>A few weeks ago I posted an article about writing a Pascal compiler which
>generates a C parse tree. I have since (nearly) completed the said
>compiler and have hit a problem with the implementation of sets.


>How are sets usually implemented in Pascal? Is there a small limit placed
>on the size of sets? I can think of a number of implementation methods,
>but would like to see how it is normally done so that I dont have to do
>much more work.


Gee, I was hoping (for your sake) that sets would not be included in your
subset:)


Sets are a classic bugaboo in Pascal. For instance, if you see a constant
set like "[1..10]" how much storage does the set occupy ? If you only
allow enough bits to cover the bits in the constant, then every time it
enters into operation with other sets, it will have to be dynamically
adjusted to match the other set. Of course, we are assuming the obvious;
that the type "set of integer" is impossible on a given machine (it is not
forbidden by the standard, by the way). Now integers are the most extreme
example of this problem for sure, but consider this:


type a = 'a'..'z';
          b = set of char;
          c = set of a;


var x: b;
        y: c;


Now, there are several ways to handle this. You can do the obvious, and
treat b and c as separate cases, with separate storage lengths. But
remember that the standard says that two sets with the same base type are
compatible, thus:


        if x = y then ....


Should be permissable. But then you now have to match up to sets with
entirely different storage formats.


The next most obvious solution is to say "well, anytime we get a character
set (of any subrange), we just allocate, say, 256 elements", or in other
words, regularize the storage requirements. In fact, this is what most
production compilers do, and what I would recommend you do, since it is
the most simple solution. What it means for practical use is that you can
never have a set where the base type contains a value > 255 (or whatever
-- I have seen one compiler that lets to "set the set" size yourself).
This is great for characters, because you can make your default set size
large enough to cover all of them. Also, 256 values is pretty good for
enumerated quantities "(one, two, )". And I have yet to see anyone really
go to town and write something like:


var x: integer;


..


      if x in [102355..934343433] then writeln('Boy, this is some compiler');


Ok, one last one. It has been done (storage technology) where sets are
implemented as virtual dynamic arrays. Then, you keep the start and end
value of every set you generate as part of the set data. Then you
typically would have routines that handle matching and "in" calculations
using said variable length sets. This scheme allows you to create sets
that use any amount of memory the machine has (meaning that "set of
integer" may now actually work ! but where do you put the program ....).


>It turned out to be quite an easy task to write the lexical, syntax and
>semantic analysers (about 24 hours work in all). There are a few nasties
>in the Pascal syntax which make it more difficult than C in places.


Nobody likes a showoff :)


--
Scott A. Moore [SAM]
samiam@netcom.com
San Jose, CA USA
408-383-9154
--

Return to the comp.compilers page.
Search the comp.compilers archives again.