Groups | Search | Server Info | Login | Register

Groups > comp.compilers > #172

Re: How to handle qualified identifiers such as x.y in a Pascal-like language

Show all headers | View raw

On Jun 24, 2:56 am, Hans-Peter Diettrich <DrDiettri...@aol.com> wrote:
> Gene schrieb:
>
> > When the language allows (as does yours) explicit scope paths, each
> > dictionary D should also be paired with its identifier id(D) for the
> > scope that caused it to be created, here function or program name. The
> > lookup of a qualified id reference then proceeds right-to-left.
>
> This IMO is the wrong way. Structured data types require left-to-right
> evaluation of the qualified name, i.e. for P.x an identifier P would
> be searched first, followed by a search for x in P's *local*
> dictionary.

Certainly there are lots of ways to implement. The one I proposed is
not the very best for speed. It is rather good for space, though, and
it's beautifully simple. Your proposal here though is I think
incorrect.  If we have

procedure P:
  var x;
  procedure P:
    var x;
    ... P.x ...

The P.x reference would conventionally be associated with the inner
x.  If you start searching for P.x outer scope first, you get the
wrong one.

> This is problematic with the intended approach, to refer to the
> *current* module by its name (P), because the dictionary of P will
> already be in the scope-stack, and this one does *not normally*
> include the identifier P itself.

You're right about P not being in its own dictionary.  Each dictionary
lies in a tuple (the pair I spoke of), where the other element is the
identifier of the dictionary's scope.  The identifier will also appear
in the dictionary for the enclosing scope.  The program identifier
lies in no dictionary at all because it has no enclosing scope. With
this convention I can't see a problem as long as procedure/program
names inhabit the same name space as variables.  Maybe an example
would help me see your concern.

I have actually used this technique to implement an assembler with
scopes, and it worked quite well.

> That's why e.g. C++ uses (AFAIR) "::" to denote the global (static)
> scope, not the name of any module. This allows to start the search for
> the following identifier(s) immediately in the correct scope, with no
> chance for possible mismatches with identifiers P in some other active
> scope.

You're right, but this language isn't C++.  Nested procedures are
allowed, and the s.x example shows that complete paths are not
required.

> This would require that *all* local dictionaries are in the search path,
> what IMO doesn't make sense (performance wise), because a full match of
> s.x only can occur in the s dictionary, regardless of how many other
> scopes contain an x.

The dictionaries in the path are those for the static scopes currently
open for parsing.  When parsing a procedure nested N deep, you have N
dictionaries.  In a realistic program, N is often 1, maybe 2, seldom
3, almost never 4...  In my experience id lookups are a trivial cost
of processing compared to once-per-character operations like scanning.
And in practice the most frequent case by far is simple id's in the
inner scope, which need only one dictionary lookup. So you'd be
unlikely to find this algorithm is a bottleneck.

Thanks for the discussion.

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How to handle qualified identifiers such as x.y in a Pascal-like language noitalmost <noitalmost@cox.net> - 2011-06-20 15:43 -0400
  Re: How to handle qualified identifiers such as x.y in a Pascal-like language torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-06-22 10:57 +0200
  Re: How to handle qualified identifiers such as x.y in a Pascal-like language Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2011-06-22 11:47 +0100
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language George Neuner <gneuner2@comcast.net> - 2011-06-24 18:13 -0400
      Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-06-29 12:31 -0700
        Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-07-01 12:46 -0700
        Re: How to handle qualified identifiers such as x.y in a Pascal-like language anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-07-02 17:13 +0000
          Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-07-03 13:14 -0700
            Re: How to handle qualified identifiers such as x.y in a Pascal-like language torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-07-07 10:27 +0200
            Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-07-07 04:14 -0700
        Re: How to handle qualified identifiers such as x.y in a Pascal-like language George Neuner <gneuner2@comcast.net> - 2011-07-02 16:58 -0400
  Re: How to handle qualified identifiers such as x.y in a Pascal-like language Gene <gene.ressler@gmail.com> - 2011-06-22 19:21 -0700
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2011-06-24 07:56 +0100
      Re: How to handle qualified identifiers such as x.y in a Pascal-like language Gene <gene.ressler@gmail.com> - 2011-06-24 19:19 -0700
        Re: How to handle qualified identifiers such as x.y in a Pascal-like language Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2011-06-25 11:55 +0100
          Re: How to handle qualified identifiers such as x.y in a Pascal-like language noitalmost <noitalmost@cox.net> - 2011-06-29 13:13 -0400
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language "[Linux Magazine]" <uu3kw29sb7@snkmail.com> - 2011-06-24 13:58 +0200
      Re: How to handle qualified identifiers such as x.y in a Pascal-like language George Neuner <gneuner2@comcast.net> - 2011-06-25 17:11 -0400
  Re: How to handle qualified identifiers such as x.y in a Pascal-like language noitalmost <noitalmost@cox.net> - 2011-06-23 12:43 -0400
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language Tony Finch <dot@dotat.at> - 2011-06-29 18:55 +0100
    Re: How to handle qualified identifiers such as x.y in a Pascal-like language BGB <cr88192@hotmail.com> - 2011-06-29 15:51 -0700

csiph-web