0

I'm creating a very simple compiler PoC that only has

  • Procedures
  • Calls to procedures.

The syntax of the language is really simple:

Main 
{
    Call("Proc1");
}

Proc1 
{
    // Empty
}

I want to create an algorithm to get THIS STRUCTURE (that is, in fact, a directed graph)

Script
{
    Procedures:
    [#1] (Procedure)
    { 
        Name: "Main"
        Statements: 
        {
            (Call): 
            {
                Procedure: #2
            }
                
        }
    }
    [#2] (Procedure) { Name: "Proc1" }      
}

This is, a procedure "Main" that contains a call that holds a reference to the procedure "Proc1" (notice the # symbol to make this reference explicit).

Trying to do this in a simple pass end up with the popular "egg and chicken problem".

My second approach was to first do 2 passes:

  • 1st pass. Scan only the procedure definitions to create a list with them.
  • 2nd pass. Bind the actual procedures (with their call statements). When I find a call, I lookup the previously calculated list of procedure definitions, and link the call to it.

But doing so, what I end up with is calls that have a weak reference (by some indentifier) to the called procedure. But I need hard references to the procedure that is to be called. How can I achieve this?

Extra point

If possible, I would like to use immutable structures

8
  • 2
    What is your question? I guess you have something like Call(Procedure: "Proc1") and want Call(Procedure: <Reference to Proc1>)?
    – marstato
    Aug 27, 2021 at 8:30
  • @marstato exactly!
    – SuperJMN
    Aug 27, 2021 at 8:32
  • Hm, but you already said that you look up from a table of definitions, but the definition is not what you want a reference to. But what else is it? Do you create another object from the definition? If yes, why not place that one in a table as well?
    – marstato
    Aug 27, 2021 at 8:35
  • @marstato I'd like to create the directed graph represented in the OP. The table was part of my failed 2nd approach to the problem.
    – SuperJMN
    Aug 27, 2021 at 8:38
  • 1
    i edited your question. Is my edit accurate? If yes i have an answer for you :)
    – marstato
    Aug 27, 2021 at 9:55

3 Answers 3

4

We need to separate the nature of the source language. If cyclic references are forbidden, you can use a topological sort to bring your AST into an order that can be processed without encountering forward references [that haven't been materialized yet]. So i'll focus on cyclic references.

This should be the minimal example that illustrates the point in question:

SomeProc {
  Call("SomeProc")
}

For illustration purposes, this is the AST that this should yield:

Procedures:
  - Name: SomeProc
    Statements:
      - Type: Invocation
        Procedure: SomeProc

This AST already contains a cyclic reference; its just that its a logical one, not one that you can use in the compiler source code. If you want to turn that into an actual reference (one usable in the compiler program), you first need a place to store that reference. And since you cannot create both at the same time, some mutability is necessary. That's just the nature of forward references.

As to practical advise: i've written some interpreters for DSLs, and i've always taken this approach:

You have one set of classes that cleanly represents the AST, and just that. You have another set of classes that represents the semantical structure of the program (an intermediate representation/IR in compiler lingo). Instances of the IR classes created from the instances of the AST classes. Then, once you have IR instances, you resolve all references, mutably. E.g.:

class Context {
  Map<String, Procedure> procedures;
}

class IRProcedure {
  List<Statement> statements;
  
  void resolveReferences(Context context) {
    foreach (statement in statements) {
      statement.resolveReferences(context)
    }
  }
}
class Statement {
  String procedureName;
  Procedure procedure;

  void resolveReferences(Context context) {
    Procedure resolved = context.procedures.get(prcedureName);
    if (resolved == null) {
      // trigger compiler error: unknown function
    }
    this.procedure = resolved;
  }
}

The main flow of the compiler would then:

  1. parse the AST
  2. create Procedure instances for every procedure it finds.
  3. Create the context where procedures are indexed by name
  4. Call resolveReferences(context) on every procedure

And voilá, references set correctly.

Unfortunately, i don't see a way to have forward references be immutable if cyclic references are a possibility. If things get more involved (type checking, data structures, control flow, yada yada), then you can gain a lot in terms of immutability by introducing a third set of classes / another IR. But that goes beyond the scope of the question.

The number of passes

I have no clue how the number of passes are counted. I think two is reasonable if you reason like so:

  • Parsing the code into AST: Pass 1
  • Walking over the entire AST to resolve references: Pass 2

For each IR you introduce to help you deal with complexity the pass count arguably goes up by 1. But one could also argue that one walk over the AST/IR tree doesn't count as a pass, since you're only modifying the existing data structures already in memory. So if you have to restrain yourself to two passes, you can maybe use another IR with that argument.

3
  • Wonderful answer! I understand the explanation using the mutable approach. Unfortunately, I don't understand the immutable approach. Could you please give a brief example, maybe with some code of it? Thanks a million!
    – SuperJMN
    Aug 27, 2021 at 11:34
  • Something I would like to know about the immutable approach is what you have in the 2 nd pass and in the 3rd pass, because no matter how I face the problem, I always end up having to reference something that doesn't exist yet.
    – SuperJMN
    Aug 27, 2021 at 11:35
  • 1
    @SuperJMN you're welcome :) Hm, you are right. I ended up looking at some of my code, and for forward references, it is still mutable. If you were inclined you could use a topological sort and achieve practical immutability for non-cyclic references, but when they are a possibility you have to design your IR data structures with some mutability. I'll fix my answer.
    – marstato
    Aug 27, 2021 at 12:23
1

From a quick guesswork and some memory shards from a CS uni course, i'd suggest taking a look at LR parsers and the Chomsky hierarchy's last two groups (context-free grammar and regular grammar). These are usually enough for most of computer language parsing if i'm not mistaken. Since your defined language does not seem to be too extensive, i'd suggest a pen-and-paper approach for planning.
Some sources:

1

It is all about when you deal with things.

Do I do it incrementally or when I have completed parsing everything?

I can build up a table of calls that are made where I do not yet know where they go ... as I read in further functions I can fill in that table with the new functions read.

But ... this requires me to now have an "extra step" where I ensure they are all filled after.

1
  • If I understood you well, you propose to gather calls into a table, and to add the missing references to the procedures at a later stage, when, they are known, right?
    – SuperJMN
    Aug 27, 2021 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.