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

Gene schrieb:


> 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.


I dare to disagree. When P.x would refer to the inner x, how then would
you refer to the outer x?


Also: how would you call the inner P, from inside the outer P?
More general, how to distinguish between an recursive call, and a call
of a local subroutine, when both have the same name?


IMO qualifiers should allow to address identifiers in *external* (here:
outer) scopes, which otherwise would be hidden by a local identifier of
the same name.


A more elaborate example:


program P;
var P;
var x;
procedure P;
      var P: RecordContainingX;
      var x;
      procedure P;
          var x;
          ... P.x ...
          ... P.P.x ...
      end; //inner P
      ... P.x ... //x in var P or in outer procedure P?
      ... P() ... //recursive or local procedure call?


Some general questions:


Should we allow for nested scopes of equal names at all?
(procedure P inside program P and procedure P)


Should we allow for local names, duplicating the scope name?
(var P inside program P or procedure P)?


How to return values from functions?
(by assignment to the function name (Pascal), or to a Result variable
(Delphi), or by explicit "return <value>" statement (C) )


How to distinguish, if ever, between partial (relative) and fully
qualified (absolute) references? Relative to what?


IMO a name in an inner scope hides identifiers of the same name, in all
outer scopes. This should be perfectly allowed.


But duplicate names inside the same scope should be disallowed. This
will make a difference, depending on whether the scope name is part of
its own scope (as you suggest for P.x), or whether the name of a scope
is a member of its parent scope (with inner procedure P being a member
of the outer procedure P).




>> 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.


When we have these nested socpes:


program P
      procedure P
          procedure P
              procedure P


what (unique!?) scope ID should be assigned to each scope?


IMO this example only reveals, that nested scopes of same names tend to
*fully* hide outer scopes of the same name. I assume that you want to
bypass this restriction, by qualifier evalution from right to left. I.e.
P.x would address an x in the nearest enclosing scope P, while P.P.x
would refer to an x in the next *outer* P scope. Right?


Then an implementation had to search for in identifer x first and, when
found, successively match the next qualifiers with the names of the
containing and enclosing scopes. Very nice, indeed :-)


But then I wonder how such a resolution will fit together with (nested)
scopes of structured types. Imagine a record variable R, then R.x will
refer to the immediate member x of this record. But then R.x.y has to
refer to member y of the scope of x, what IMO means that here the
qualifiers *must* be evaluated left-to-right.


A more concrete example:


type r1 = record x:integer ... end;
type r2 = record x:r1 ... end;
type r3 = record x:r1 ... end;
var R:r2;
... R.x.x ...


Where would you place the scopes for the records, so that their "x"s are
found when starting qualifier resolution from the right? And finally,
when x.x has been matched in scope r2, how to resolve the next qualifier
"R"?


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


Did your assembler include structured types, and if so, how did you
resolve beforementioned situation?




>> 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.


Incomplete (relative) paths IMO deserve a unique evaluation order,
either RTL or LTR. Otherwise a different syntax must be used, so that
the starting point can be found out, from which evaluation can proceed
to both ends, e.g. P<-P<-R->x->y.


>> 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.


ACK, the order is O(n) for both strategies. My only objection addresses
the handling of structured types, in your model.


BTW, I once reduced the order of the search to almost O(1), by "merging"
new scopes into a single scope, with a stack for all visible
identifiers, and a hash table. The hashtable refers, after resolution of
name clashes, to the topmost (visible) identifier. When a scope is
closed, it's entries are popped off the stack, and the hashtable is
updated with the references to the next outer (now unidden) identifiers,
from a reference stored in every popped entry. It should be possible to
add qualified references into outer scopes to this model, somehow - my
implementation was for a C parser with no such requirement.


> Thanks for the discussion.


Thanks2 for the inspiration :-)


DoDi

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