How does a compiler give an immediate compilation error?

Question

I am confused. I know that compilers translate your code one time as a whole into intermediary code, but how come when I type in something improper, the IDE shoots out a compilation error immediately? What am I not understanding? I thought the whole difference between an interpreter and a compiler is that the former translates code line by line and the latter translates your source program as a whole in one go.

Answer 1

I'll talk about relatively simple (for the sake of analysis) languages, like C#/Java. There may be different approaches aside from want I describe here.

What IDE does during analysis is not compilation

The primary goal of IDE is not compilation, it's to assist you with code writing/analysis. For example, IDE helps you with auto-completion, refactorings (renames, indentation, dead code removal, simplifying the code), navigation (go to definition, find usages), code generation (overriding equals()/hashCode(), creating constructors, properties generation), and many, many other tasks. On the other hand, it doesn't care about resulting code efficiency, linking, and other compilation-related stuff, but e.g. it cares about preserving comments and spaces (compilers can simply throw them away). It means that IDE can (and will) use completely different structures to work with.

Code analysis

The code analysis can usually be split into three steps, in this order (for C++ these steps are mixed, which makes it a hard language):

• Lexical analysis: the input is split into a sequence of tokens. E.g. a + b becomes [IDENT(a), PLUS, IDENT(b)].
• Syntax analysis (or parsing; they are not exactly the same, but doesn't matter now): builds a syntax tree. E.g. a + b can be parsed as PlusExpr(left=IDENT(a), PLUS, right=IDENT(b)). c = a + b; can be parsed as AssignmentStatement(left=IDENT(c), EQ, right=PlusExpr(...), SEMICOLON).
• Semantic analysis. Surely a huge field, with a lot of tasks, but for now let's only care about name resolution (finding declarations) and type checking.

Error detection

Errors types detected by IDE correspond to code analysis steps outlined above.

• Lexical errors: e.g. you use some invalid token (e.g. 0gda) or you didn't close a string literal (e.g. "abc<EOF>). Usually, lexical analysis is lightning fast, and such errors are trivial to detect. To continue lexical analysis (to detect more errors and allow syntax analysis), bad literals can be ignored or fixed (e.g. the analysis can treat "abc as "abc").
• Syntax errors: e.g. you forgot a semicolon c = a+b<EOF>, closing parenthesis c = (a+b;, etc. Detecting the errors is simple. A tricky part is to recover from the errors. E.g. in c = (a+b; you can assume that there should be ) before ;, report error, and continue parsing. Anyway, while error recovering is nontrivial (and often requires manual handling), it's usually performed reasonably well.
• Semantic errors. I'll talk about errors like "Undefined identifier" and "wrong type" next.

Name/Type errors

In Java, there are no identifiers that come from nowhere (this is one of the reasons why Java is a relatively simple language for analysis). The sources are (as I recall):

• import statements.
• Identifiers declared in the same scope. E.g. when you define class A at the top level of the file, this class can be used anywhere in the file; when you write for (int i; ..., i can be used in the body of the loop.
• With qualifiers. E.g. if you have an object a, which has a method b, you can write a.b.

These lead to the following structures:

• For import statements, you have a global structure that analyses all source files and all linked libraries. This structure is a trie which represents a global name hierarchy. So if you've written import java.util.*, it follows the path <root>->java->util and includes all identifiers in the found node into the current file scope.

• For scopes. Consider an example:

  class A {
      int f() {
          if () {
              print(a);
          }
      }
  }
  

  In this example, when we try to resolve a, we try to find a declaration (in this order): 1) inside if-block, 2) inside f(), 3) inside class A, 4) in the file scope (i.e. because of imports). When the name is found, the search is done.

  Therefore, for scopes, it suffices to maintain a stack-like structure: each level of the stack represents a scope and has all the names defined in this scope. When trying to find a declaration, you process the stack layer-by-layer.

• For qualifiers: for a.b, when resolving b, you assume that you've already resolved a (using the above rules). Moreover, you assume that you know the type of a; it means that the above structures should maintain the types of all identifiers (which is easy to do by looking at the type at the declaration; this is another aspect that makes Java simple). Now, you simply check whether the type has a member b and which type it has.

With the above analysis, the type analysis is simple: for each identifier you know its type, and you know which type you expect: e.g. in f(x,y), if you know (after resolution) that f is a function (int, int) -> int, you know that x and y should have type int.

Why it can be done fast

All these structures can be maintained on-the-fly. In the hierarchy trie, the only modified nodes are the nodes corresponding to the current file. The scope stack and access with qualified correspond only to the current file (so you simply need to re-analyze the file). Also, some optimizations may be used to re-analyze only a portion of the file (e.g., if you make edits inside some function, there is a chance that you need to re-analyse only this function).

Actually, the slowest operations are the following:

• Building the hierarchy when the project is first opened.
• Loading the hierarchy when the project is reopened. This is indeed an issue, and a lot of efforts may be required to make this efficient.
• Rebuilding the hierarchy when a lot of files change simultaneously (e.g. because of git pull).

Solution-wide analysis

I was talking about finding errors in the current file. However, editing the current file may break something else: e.g. if you remove a method from a class, all files using this method will break (the above structures can't detect it unless you open the affected file). This requires a Solution-wide analysis, which, well, analyses your entire project in real-time. This analysis requires much more resources though (at the very least, you need to track all usages of all identifiers, and I believe there is a lot of other stuff going on there), not every machine can handle it on a large project, and it may take some time (few seconds, as I recall) for errors to be detected.