Práctica: Calculadora con Análisis de Ámbito

Extienda la práctica anterior para que haga un análisis completo del ámbito de las variables.

• Añada declaraciones de variable con var x, y = 1, z. Las variables podrán opcionalmente ser inicializadas. Se considerará un error usar una variable no declarada.
• Modifique la gramática para que permita el anidamiento de funciones: funciones dentro de funciones.

  var c = 4, d = 1, e;
  def g(a, b) { 
    var d, e;
    def f(u, v) { a + u + v + d }
    a * f(b, 2) + d + c 
  }
  

• Una declaración de variable en un ámbito anidado tapa a una declaración con el mismo nombre en el ámbito exterior.

  var c = 4, d = 1, e; def g(a, b) { var d, e; # esta "d" tapa la d anterior def f(u, v) { a + u + v + d } a * f(b, 2) + d + c }

  # global: var c,d,e :g.f $a, 1 $u, 0 + $v, 0 + d, 1 + return :g $a, 0 $b, 0 2 call :g.f * d, 0 # acceder a la d en el ámbito actual + c, 1 + return

• Los nombres de funciones se traducen por una secuencia anidada de nombres que indican su ámbito. Así la función f anidada en g es traducida a la función con nombre g.f. Una función h anidada en una función f anidada en g es traducida a la función con nombre g.f.h

• Las variables ademas de su nombre (dirección/offset) reciben un entero adicional 0,1,2, ...que indica su nivel de anidamiento. El número de stack frames que hay que recorrer para llegar a la variable

          $a, 1
          $u, 0
          +
          $v, 0
          +
          d, 1
          +
  

  Asi $a, 1 significa acceder al parámetro a que está a distancia 1 del stack frame/ámbito actual y $v, 0 es el parámetro v en el ámbito/stack frame actual
• El frame pointer o base pointer BP indica el nivel de anidamiento estático (en el fuente) de la rutina. Así cuando se va a buscar una variable local declarada en la rutina que anida la actual se recorre la lista de frames via BP o frame pointer tantas veces como el nivel de anidamiento indique.
  
• 1. Esto es lo que dice la Wikipedia sobre la implementación de llamadas a subrutinas anidadas:

     Programming languages that support nested subroutines also have a field in the call frame that points to the stack frame of the latest activation of the procedure that most closely encapsulates the callee, i.e. the immediate scope of the callee. This is called an access link or static link (as it keeps track of static nesting during dynamic and recursive calls) and provides the routine (as well as any other routines it may invoke) access to the local data of its encapsulating routines at every nesting level.

  2. Esto es lo que dice sobre las ventajas de tener una pila y de almacenar la dirección de retorno y las variables locales:

     When a subroutine is called, the location (address) of the instruction at which it can later resume needs to be saved somewhere. Using a stack to save the return address has important advantages over alternatives. One is that each task has its own stack, and thus the subroutine can be reentrant, that is, can be active simultaneously for different tasks doing different things. Another benefit is that recursion is automatically supported. When a function calls itself recursively, a return address needs to be stored for each activation of the function so that it can later be used to return from the function activation. This capability is automatic with a stack.

  3. Almacenamiento local:

     A subroutine frequently needs memory space for storing the values of local variables, the variables that are known only within the active subroutine and do not retain values after it returns. It is often convenient to allocate space for this use by simply moving the top of the stack by enough to provide the space. This is very fast compared to heap allocation. Note that each separate activation of a subroutine gets its own separate space in the stack for locals.

  4. Parámetros:

     Subroutines often require that values for parameters be supplied to them by the code which calls them, and it is not uncommon that space for these parameters may be laid out in the call stack.

     The call stack works well as a place for these parameters, especially since each call to a subroutine, which will have differing values for parameters, will be given separate space on the call stack for those values.

  5. Pila de Evaluación

     Operands for arithmetic or logical operations are most often placed into registers and operated on there. However, in some situations the operands may be stacked up to an arbitrary depth, which means something more than registers must be used (this is the case of register spilling). The stack of such operands, rather like that in an RPN calculator, is called an evaluation stack, and may occupy space in the call stack.

  6. Puntero a la instancia actual

     Some object-oriented languages (e.g., C++), store the this pointer along with function arguments in the call stack when invoking methods. The this pointer points to the object instance associated with the method to be invoked.

• Los parámetros se siguen prefijando de $ como en la práctica anterior
• Sigue un ejemplo de traducción:

  var c = 4, d = 1, e; def f(x) { var y = 1; x + y } def g(a, b) { var d, e; def f(u, v) { a + u + v + d } a * f(b, 2) + d + c } c = 3; f(1+c); g(3, 4)

  # global: var c,d,e # f: args x # f: var y :f 1 &y, 0 = $x, 0 y, 0 + return # g: args a,b # g: var d,e # g.f: args u,v :g.f $a, 1 $u, 0 + $v, 0 + d, 1 + return :g $a, 0 $b, 0 2 call :g.f * d, 0 + c, 1 + return :main: 4 &c, 0 = 1 &d, 0 = 3 &c, 0 = 1 c, 0 + call :f 3 4 call :g

• Puede comenzar haciendo un fork del proyecto ull-etsii-grado-pl-infix2postfix en GitHub. Esta incompleto. Rellene las acciones semánticas que faltan; la mayoría relacionadas con el análisis de ámbito.

• • Una solución completa se encuentra en el proyecto crguezl/jisoninfix2postfix.

  • [~/jison/jisoninfix2postfix(gh-pages)]$ pwd -P
    /Users/casiano/local/src/javascript/PLgrado/jison/jisoninfix2postfix
    

  • [~/jison/jisoninfix2postfix(gh-pages)]$ git remote -v
    bitbucket       ssh://git@bitbucket.org/casiano/jisoninfix2postfix.git (fetch)
    bitbucket       ssh://git@bitbucket.org/casiano/jisoninfix2postfix.git (push)
    origin  git@github.com:crguezl/jisoninfix2postfix.git (fetch)
    origin  git@github.com:crguezl/jisoninfix2postfix.git (push)
    

• Veanse:
  • Véase COMP 3290 Compiler Construction Fall 2008 Notes/Symbol Tables
  • El capítulo Symbol Table Structure del libro de Muchnick Advanced Compiler Design Implementation [5]
  • El capítulo Symbol Table Structure del libro de Basics of Compiler Design de Torben Ægidius Mogensen [6]