Semantic analysis in compilers [closed]

Question

How is the semantic analysis done by a compiler (generally)?

I had to answer to this question during my last exam, it wasn't enough for the professor.

I included BNF (with an example) and syntactic cards in my answer, to which he asked me: "What happens when the compiler finds a statement like int i;?"

Bondwoman

Didn't he cover this material in your class? – Perrone

@IraBaxter: Yes, but superficially than what he asked during the exam. (bad bad english, sorry) – Bondwoman

This is more like a "human issue" that a "technical issue", sometimes teachers expect an answer to be much specific to what they speak in class ... – Palermo

It is reasonable for a teacher to sketch a high level, coherent overview of a topic in a class, and then insist that the students read the associated material for details. If they ask you a question on an exam that is in assigned reading material you better know that material. There are also just plain bad teachers. – Perrone

@umlcat: Yes :/ When it happens you feel like: "WTF I studied in the last two weeks?!" – Bondwoman

@IraBaxter: Of course. But when you follow a course of study with a professor (a good professor), and then you have to do the exam with a different teacher, it's a bit difficult to be prepared on all possible thing that he could ask you. :/ – Bondwoman

@uNaturhal,@Atwood: I don't kwow why Atwood closed this question. I thought it was perfectly clear, and others seemed to think so to based on my response. Sometimes the SO staff goes overboard, and it often happens with relatively new users, which I think is a disservice. The discussion on teaching here is a bit off topic, but that might be a complaint about the comments, not the question. – Perrone

@IraBaxter, Atwood: "This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form." Atwood, are you sure to know what does it mean what you wrote? I think that Ira Baxter has understood my question, in fact his answer is exactly what I needed. So it doesn't seems that it's difficult to ask. It's a pity that no one else can contribute to the post, but I had my answer so it's no longer my problem. Have fun! – Bondwoman

Answer 1

Time to read Aho&Ullman/Dragon book carefully.

Semantic analysis is the activity of a compiler to determine what the types of various values are, how those types interact in expressions, and whether those interactions are semantically reasonable. For instance, you can't reasonably multiply a string by class name, although no editor will stop you from writing

 "abc" * MyClass

To do this, the compiler must first identify declarations and scopes, and typically records the result of this step in a set of symbol tables. This tells it what specific identifiers means in specific contexts. It must also determine the types of various literal constants; "abc" is a different type than 12.2e-5.

Then it must visit all locations where identifiers and literals are used, and verify that the use of the identifier/literal, and the results computed, are compatible with the language definition (as in the above example).

As to how this is done: typically the source code is parsed, some representation of the program is constructed (syntax trees are very popular), and that representation is walked ("visited") element by element to collect/validate the semantic information. The symbol table is usually just a set of hash tables associated with the syntax tree representing a scope, hashing from identifiers to structures containing type declarations.

Perrone

I think to have understood. Could you just give me some example please? For instance, when a compiler found a declaration in a function (like long double f;), it puts in a table that f is a symbol, that occupy 8bytes, that can contain float numbers, that is defined only in the scope of the function, and his range of values? – Bondwoman

@unNatural: Yes, you have it right. The key is the association between the scope, the identifer, and the type of identifier. Other data (such as float takes 8 bytes) don't necessarily have to be in the symbol table, because that fact is likely true across the compiler for any float value. It is useful for later stages of the compiler to capture range information if it can determine it, and this is arguably a semantic analysis, but most people don't think of range analysis as "compiler semantic analysis" in the narrow range of this discussion. – Perrone

Ok, it's clear :) Excuse me if I abuse of your availability, but I have another question. According to what you said, it seems that the BNF has nothing to do with the process of semantic analysis. It's right, or I'm wrong? – Bondwoman

@unNatural: The BNF has everything to do with semantic analysis. The BNF tells you the shape of language constructs. This in turn defines the structure of the langauge, thus the declarations, scopes, expressions, you name it. You will find that the program representation (e.g., the syntax tree) and the "visit" to all of its elements are directly controlled by the BNF. In fact, entire compilers have been written using the BNF to directly control the parsing and semantic analysis, that is, the BNF plus some additional annotations are used to generate the compiler... – Perrone

@unNatural: ... in fact, the tool which process such annotate BNF has exactly the same problem as the target compiler has, e.g., must parse, do semantic analysis of the BNF/annotations, etc. thus are called "meta compilers". The reason I bring this up is because syntactic and semantic analysis are modelled directly in such compiler compiler languages. If you understand how these work, the details of compiling become much clearer. See en.wikipedia.org/wiki/Compiler-compiler But you should still read the Aho&Ull compiler book. – Perrone

Maybe you will not believe me, but I'd really like to learn how to develop a compiler or a programming language. I'm attracted by low level programming! However, thank you for your time. You have been very very clear :) – Bondwoman

Did you wrote this article too en.wikibooks.org/wiki/Compiler_Construction/Semantic_Analysis? both text seems to be the same – Keelia

I didn't write the wiki entry. Looks like "Pir Fahim Shah" did, using my text from this answer to scribble on the existing wikipedia entry (whose quality is unknown to me). I'm not sure he did us all a favor. Technically I wrote it, but SO claims rights to it. I'll let SO and Wikipedia sort it out. – Perrone

@IraBaxter You said "some representation of the program is constructed (syntax trees are very popular)". What other data structures are good candidates to represent the structure of a program? I can only think of trees. – Maestoso

"Good" representation depends on what questions you want to ask. Frankly, I can only think of 4 basic representations of programs: 1) Raw text. 2) Sequence of Lexemes 3) Trees 4) Data flow graphs. – Perrone

The BNF only possesses enough information to build a parser accepting semantically-invalid nonsense like int x = “abcd”;. Semantic analysis is absolutely required to do type checking, identifier resolution, etc. Think of semantic actions as semantic constraints or guards applied to the parser. – Alleviative