/ 
Parse-Eyapp-1.093
River stage one • 1 direct dependent • 4 total dependents
/ Parse::Eyapp::Scope

NAME

Parse::Eyapp::Scope - Support for Scope Analysis

SYNOPSIS

 # Fragment of the grammar in examples/Types.eyp 
 funcDef:
     $ID 
        { 
          $ids->begin_scope(); 
        }
     '('  $params  ')' 
       $block
     {
        my $st = $block->{symboltable}; 
        my @decs = $params->children(); 
        $block->{parameters} = [];
        while (my ($bt, $id, $arrspec) = splice(@decs, 0, 3)) {
            $bt = ref($bt); # The string 'INT', 'CHAR', etc.
            my $name = $id->{attr}[0];
            my $type = build_type($bt, $arrspec);
            $type{$type} = Parse::Eyapp::Node->hnew($type); 

            # control duplicated declarations
              die "Duplicated declaration of $name at line $id->{attr}[1]\n" 
            if exists($st->{$name});

            $st->{$name}->{type} = $type;
            $st->{$name}->{param} = 1;
            $st->{$name}->{line} = $id->{attr}[1];
            push @{$block->{parameters}}, $name;
        }
        $block->{function_name} = $ID;
        $block->type("FUNCTION");

        my ($nodec, $dec) = $ids->end_scope($st, $block, 'type');

        # Type checking: add a direct pointer to the data-structure
        # describing the type
        $_->{t} = $type{$_->{type}} for @$dec;

        return $block;
     }
 ;

 ...

 Primary:
     %name INUM
     INUM 
   | %name CHARCONSTANT
     CHARCONSTANT
   | $Variable 
       { 
         $ids->scope_instance($Variable); 
         return $Variable 
       }
   | '(' expression ')' { $_[2] }
   | $function_call 
       { 
         $ids->scope_instance($function_call); 
         return $function_call  # bypass
       }
 ;

Scope Analysis with Parse::Eyapp::Scope

A scope manager helps to compute the mapping function that maps the uses (instances) of source objects to their definitions. For instance, when dealing with identifier scope analysis the problem is to associate each ocurrence of an identifier with the declaration that applies to it. Another example is loop scope analysis where the problem is to associate each occurrence of a CONTINUE or BREAK node with the shallowest LOOP that encloses it. Or label scope analysis, the problem to associate a GOTO node with the node to jump to, that is, with the STATEMENT associated with the label.

To take advantage of Parse::Eyapp::Scope, the compiler writer must mark at the appropriate time (for example a new block or new subroutine for identifier scope analysis, a new loop for loop scope analysis, etc.) the beginning of a new scope calling the method begin_scope. From that point on any ocurring instance of an object (for example, variables in expressions for identifier scope analysis, breaks and continues for loop scope analysis, etc.) must be declared calling the method scope_instance. The programmer must also mark the end of the current scope at the appropriate time.

$scope->end_scope

There are two ways of calling $scope->end_scope. The first one is for Scope Analysis Problems where a symbol table is needed (for example in identifier scope analysis and label scope analysis.

$scope->end_scope with first Arg a Symbol Table

For each ocurring instance of an object $x that occurred since the last call to begin_scope the call to

$scope->end_scope(\%symboltable, $definition_node, 'attr1', 'attr2', ... )

decorates the ocurring instance $x with several attributes:

  • An entry $x->{SCOPE_NAME} is built that will reference $definition_node.

  • An entry $x->{ENTRY_NAME} is built. That entry references $symboltable{$x->key} (to have a faster access from the instance to the attributes of the object). The instantiated nodes must have a $x->key method which provides the entry for the node in the symbol table:

    pl@nereida:~/src/perl/YappWithDefaultAction/examples$ sed -ne '651,657p' Types.eyp
sub VAR::key {
  my $self = shift;

  return $self->child(0)->{attr}[0];
}

*VARARRAY::key = *FUNCTIONCALL::key = \&VAR::key;

  • For each aditional arguments attr#k an entry $x->{attr#k} will be built. That entry references $symboltable{$x->key}{attr#k}. Therefore the entry for $x in the symbol table must already have a field named attr#k.

In a list context $scope>end_scope returns two references. The first one is a reference to a list of node instantiated that weren't defined in the current scope. The second is a reference to a list of nodes that were defined in this scope. In a scalar context returns the first of these two. An instance $x is defined if, and only if, exists $symboltable{$_->key}.

$scope->end_scope for Simple Scope Analysis

Some scope analysis problems do not require the existence of a symbol table (for instance, the problem of associating a RETURN node with the FUNCTION that encloses it). For such kind of problems $scope>end_scope provides a second form of call. The second way to call $scope>end_scope is

$declared = $scopemanager->end_scope($definition_node);

The only argument is the reference to the node that controls/defines the scope. The method returns a reference to the declared nodes. Any node instanced with scope_instance since the last call to begin_scope is considered declared.

$scope->begin_scope

Marks the beginning of an scope. Example (file examples/Types.eyp):

loopPrefix:
    $WHILE '(' expression ')'
      {
        $loops->begin_scope;
        $_[3]->{line} = $WHILE->[1]; # Save the line for error diagostic
        $_[3]
      }

$scope->scope_instance

Declares the node argument to be an occurring instance of the scope:

nereida:~/doc/casiano/PLBOOK/PLBOOK/code> \
    sed -ne '375,380p' Simple6.eyp | cat -n
 1      $Variable '=' binary
 2        {
 3          my $parser = shift;
 4          $ids->scope_instance($Variable);
 5          $parser->YYBuildAST(@_); # "Manually" build the node
 6        }

Parse::Eyapp::Scope->new

Parse::Eyapp::Scope->new returns a scope managment object. The scope mapping function is implemented by Parse::Eyapp::Scope through a set of attributes that are added to the nodes involved in the scope analysis. The names of these attributes can be specified using the parameters of Parse::Eyapp::Scope->new. The arguments of new are:

  • SCOPE_NAME is the name chosen for the attribute of the node instance which will held the reference to the definition node. If not specified it will take the value "scope".

  • ENTRY_NAME is the name of the attribute of the node instance which will held the reference to the symbol table entry. By default takes the value "entry".

  • SCOPE_DEPTH is the name for an attribute of the definition node. Optional. If not specified it will not be defined.

SEE ALSO

AUTHOR

Casiano Rodriguez-Leon (casiano@ull.es)

ACKNOWLEDGMENTS

This work has been supported by CEE (FEDER) and the Spanish Ministry of Educación y Ciencia through Plan Nacional I+D+I number TIN2005-08818-C04-04 (ULL::OPLINK project http://www.oplink.ull.es/). Support from Gobierno de Canarias was through GC02210601 (Grupos Consolidados). The University of La Laguna has also supported my work in many ways and for many years.

A large percentage of code is verbatim taken from Parse::Yapp 1.05. The author of Parse::Yapp is Francois Desarmenien.

I wish to thank Francois Desarmenien for his Parse::Yapp module, to my students at La Laguna and to the Perl Community. Special thanks to my family and Larry Wall.

LICENCE AND COPYRIGHT

Copyright (c) 2006-2007 Casiano Rodriguez-Leon (casiano@ull.es). All rights reserved.

Parse::Yapp copyright is of Francois Desarmenien, all rights reserved. 1998-2001

These modules are free software; you can redistribute it and/or modify it under the same terms as Perl itself. See perlartistic.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

1 POD Error

The following errors were encountered while parsing the POD:

Around line 264:

Non-ASCII character seen before =encoding in 'I<Educación'. Assuming UTF-8