6
$\begingroup$

When compilers generate errors for a specific programming language, there's distinction between syntax & semantic errors. E.g. ) + f 3 has ill-formed syntax, but type checking is considered as part of semantic analysis.

My intuition tells me that, by setting more constraints on the language syntax, some semantic errors can become syntax errors. And my question is if there are any intrinsic differences between syntax and semantics? Or are they just checking performed on different levels, for example syntax checking is a rather local checking while semantic checking is global? Is there anything fundamental that makes semantics checking different from syntax checking? Is it possible to embed all semantic checking within syntax? Are there any theories related to these questions?

It may also be the case that my intuition is wrong - if that's the case, please also explain to me why that is wrong.

$\endgroup$
6
$\begingroup$

In the strictest sense, there is no real difference between syntax errors and semantics errors, at least as far as language theory is concerned: the only salient difference is the complexity of the automaton required to recognize that language, with, e.g.

  • Context-free languages only requiring pushdown automata (PDA)
  • General recursive languages requiring full Turing machines (TM)

If every "syntactic task" merely required pushdown automata and every "semantic task" something more, then the matter would be settled, but unfortunately there are many tasks that are associated with programming language syntax that cannot be handled by PDA alone, and conversely, some semantic tasks which seem to require only weak computation power. Still, the distinction provides some intuition.

Pragmatically, compilers are designed in phases, which makes managing the task of generating executable code manageable. I particularly like this diagram from the Compcert website.

Compcert Arch

Typically, the first 1-3 phases turn what is essentially a stream of bytes or tokens into something more naturally seen as a tree structure. Everything before the tree creation will be labelled as "syntax" and everything after as "semantics".

In C, the syntactic phases are typically tokenization, macro expansion and parsing, everything after that will be semantics. Again, opinions may differ, since there is no accepted formal distinction.


I think there's a larger discussion to be had about how to distinguish syntactic notions from semantic notions in the field of formal logic, but I'm not sure I feel qualified to have it.

$\endgroup$
  • $\begingroup$ Thanks for your reply! About the language theory perspective you mentioned, can I say argument like below? Since there's a compiler that accepts strings that pass syntax & semantics checking and rejects strings that don't, then it means there is such a program that can do this, which means there's a recursive language for it (even including things like type checking) $\endgroup$ – Rui Liu May 15 '18 at 20:35
  • $\begingroup$ Yes, that is a correct reasoning, any compiler which can accept or reject an input string that may represent a program is effectively a proof that the well-formed programs are a recursive language. $\endgroup$ – cody May 15 '18 at 22:24
2
$\begingroup$

It is hard to say. The boundary between "syntactic errors" and "static semantic errors" can be really blurred.

One appropriate example would be Curry-style (extrinsic typing) and Church-style (intrinsic typing) variants of the same programming language, say System F. Failing to include type annotations in the Church-style variant of the language would be a syntactic error as well as a semantic error (because types are a part of the syntax and the semantics), while failing to include them in the Curry-style variant might or might not be a semantic error (type inference for System F is undecidable, so who knows if this is an error), but never a syntax error.

Now you'd see that, in many cases, it's hard to draw the line between certain classes of static semantic and syntactic errors. We might like to think of syntactically incorrect programs as "not even wrong" and semantically incorrect programs as "meaningless", but there are certain tricky cases. You can check for re-declaration of variables in either the parsing (I'm actually not sure but theoretically should be possible) or the static semantic check phase. Is it a syntactic or semantic issue? I don't know. It depends on the formal description of syntax and semantics if there exists one, but in the absence of one it all becomes very difficult.

$\endgroup$
0
$\begingroup$

In computer science, a syntax error is an error in the syntax of a sequence of characters or tokens that is intended to be written in a particular programming language. For compiled languages, syntax errors are detected at compile-time. A program will not compile until all syntax errors are corrected. For interpreted languages, however, a syntax error may be detected during program execution, and an interpreter’s error messages might not differentiate syntax errors from errors of other kinds. If there is a semantic error in your program, it will run successfully in the sense that the computer will not generate any error messages. However, your program will not do the right thing. It will do something else. Specifically, it will do what you told it to do. The problem is that the program you wrote isn’t the program that you planned to write. The meaning of the program is wrong. Identifying semantic errors can be tricky because it requires you to work backward by looking at the output of the program and trying to figure out what it’s doing.

$\endgroup$

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.