Re: Functional Symbol Tables

"A.T.Hofkamp" <>
Fri, 13 Jul 2007 11:05:39 +0200

          From comp.compilers

Related articles
Functional Symbol Tables (bison) (2007-07-09)
Re: Functional Symbol Tables (2007-07-13)
Re: Functional Symbol Tables (A.T.Hofkamp) (2007-07-13)
Re: Functional Symbol Tables (2007-07-18)
| List of all articles for this month |

From: "A.T.Hofkamp" <>
Newsgroups: comp.compilers
Date: Fri, 13 Jul 2007 11:05:39 +0200
Organization: Compilers Central
References: 07-07-039 07-07-048
Keywords: functional, symbols
Posted-Date: 15 Jul 2007 16:26:31 EDT

On 2007-07-09, bison <> wrote:
  > I'm trying to figure out a way to implement symbol tables in a
  > functional style, but I can't figure out a way to do that. The only
  > way I can think to do it is to keep track of names during parsing for
  > each scope and upon entering a scope add these bindings to the
  > existing table.

Sorry, but I am not sure that I understand your problem.

Let me explain what I did with symbol tables in the functional-style
transformation formalism ASF+SDF:

My nested symbol tables are defined like (edited to make it look like BNF).

Symbol-layer ::= "single" "{" Symbol* "}" Symbol-layer
                                | "null" "{" "}"

Symbol-layer is a nested list of scopes. At the bottom in a "null" scope
without symbols (between the curly brackets). The null-scope is prefixed by a
stack of "single" scopes, each with a list of Symbols (Symbol*) in it.
(in reality, I have two other forms of scopes, hence the keyword "single").

On this syntax, I defined a number of functions for creating and deleting scopes:

"new-null-layer" -> Symbol-layer
"new-single-layer" ( Symbol-layer ) -> Symbol-layer
"del-layer" ( Symbol-layer ) -> Symbol-layer

and some functions for adding and getting symbols to these scopes:

"may-add-symbol" ( Symbol-layer, Symbol ) -> Boolean
"add-symbol" ( Symbol-layer, Symbol ) -> Symbol-layer
"get-symbol" ( Symbol-layer, Identifier ) -> Symbol

(slightly simplified w.r.t. reality). Note that Symbol contains the name of
the symbol, so it can be added to the table without specifying an Identifier.

  > I read somewhere that you can pass around your ST through arguments.

With functional programming, you don't have global variables, everything is a
parameter of the function that is executed.

  > My thought about that is that if you are using recursion, you will
  > lose all of your mappings once that call is returns. Does anyone have
  > any thoughts on this?

Euh, I guess so. Normally, you return any interesting results (such as the
modified symbol table) as return value from the function call, and recurse
into the next phase, passing the table as argument, like

"compile" ( text ) -> code

could be implemented as (extremely simplified)

[] compile(text) = code
when ast := parse(text),
            sym := new-single-layer(new-null-layer),
            sym2, ast2 := typecheck(sym, ast),
            code := codegen(sym2, ast2)

ie, to execute "compile(text)", first do "ast := parse(text)", then "sym :=
new-single-layer(new-null-layer)", etc, until you have done "code :=
codegen(sym2, ast2)". Finally, return the code by "= code" at the first line.

Each successive call takes arguments returned as results by the previous call.

Does this answer your question?


Post a followup to this message

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