Is this a syntax error or a semantic error?

Question

I came across the following question

The error in the expression " if x>y x=2; " is detected by

a. Syntax analyzer b. Lexical analyzer c. semantic analyzer

I know that the parentheses of x>y are missing, but it is not syntax error right? as all the syntaxes are correct, but we are missing a pair of parenthesis.. so is this a semantic error?

The correct answer is given as a.

Answer 1

As vonbrand points out, the lexical/syntactic/semantic division is artificial. We use it because it's convenient, but languages can easily blur the lines.

The most substantial division in the set is between lexical/syntactic errors and semantic errors. Lexical and syntactic errors can be identified by logical operations on the text of your program itself, while semantic errors are cases where the program doesn't do what you meant it to do. For example:

if (x);
    y();

In C++, that is a perfectly valid program. It will check to see if x is true. If it is, it does the statement which follows... which is the empty statement ending in the first semicolon. Then, regardless of the value of x, it runs the next line, which is y(). The result is a valid program, but you almost certainly intended to write

if (x)
    y();

Which only executes y() if x is true. Given how I indented my lines in both cases, it's pretty clear that I intended the second case. If I intended the first case, I'd write something like

if (x)
    ; // do nothing - this is a placeholder to fill in later
y();

Which has the exact same semantic meaning as the first example, I just wrote it in a way that makes it clear what I meant.

The lexical error vs. syntactic error is a bit more difficult. Long story short, lexers (which have lexical errors) turn a stream of characters into a stream of tokens, while parsers (which have syntax errors) turn a stream of tokens into a syntax tree. The difference is almost always along the lines of Chomsky's language hierarchy. Lexers are typically Type 3 (regular languages) while parsers are typically Type 2 (context-free).

Why divide it this way? Well it turns out that it's easy to write a regular language (Type 3) and have it do what you want, but they aren't all that expressive. It's much harder to write a context-free language (Type 2), but they have the expressiveness we need. When you're writing a context-free language, it's a pain to have to include all the fiddly-bits needed to build the language up character by character. For example, context-free languages often need to look ahead a bit to figure out the next step. Done right, most languages can be parsed by looking no more than one token ahead. However, if we did things by characters, rather than tokens, we may have to look an arbitrary number of characters ahead (such as if the next token would have been a string literal).

The solution is that we bootstrap the context-free language with a regular language. We use a regular language to turn a stream of characters into a stream of tokens, and then we build our context-free language around those tokens. We have found that this generally does a good job of managing the languages we care about.

So in your case, the program in question is if x>y x=2;. The first thing I'd do is see whether there's a lexical error here. To do that, I'd chop it up into tokens. Now I'm assuming this language is similar to most languages I know, so the lexing would break this up as:

if  KEYWORD_IF
    (space)
x   IDENTIFIER
>   GREATER_THAN
y   IDENTIFIER
    (space)
x   IDENTIFIER
=   ASSIGNMENT
2   INTEGER
;   SEMICOLON

There's no issues with lexing here. The lexer was able to tokenize the string without any issue (assuming this is a garden variety lexer which "does what I think it should do").

A lexer error might be something like if x<y x="Dangling string literal.... That particular program has a lexer error because the regular expression that matches string literals expects to see a closing quote, but there was none.

So now we have a string of tokens. But can we make it into a syntax tree without a syntax error?

Once again, assuming something about the language, it looks C like. In C, the construction for an if block is

KEYWORD_IF OPEN_PAREN expression CLOSE_PAREN statement

There's no way to match the string of tokens against that grammar rule, because there's no OPEN_PAREN following KEYWORD_IF in the token stream. Thus, there's a syntax error.

If this is a language that doesn't need parenthesis (e.g. Python), then there will also almost certainly be a syntax error at "if x<y x=2;" Very few languages include a language rule which has two identifiers back to back like y x. So there would be a syntax error there.

At this point, we can stop. If there's an error at one level, we cannot continue on, so we can't have errors at the next level. Since there is a syntax error, it is meaningless to address the question of whether there is a semantic error or not. Thus, as your answer key states, the correct answer is (a)

Answer 2

The classification as lexical/syntax/semantic error is largely artificial, governed by separate parts of your compiler: it the "lexical analysis" phase detects the error, it is deemed lexical; if the parsing (syntax analysis) phase does, it is classified as "syntax error", others are reported as "semantic errors" (or just pass through without detection, giving rise to a runtime error). This is more am implementation detail than a firm distinction. It is e.g. possible to do away with separate lexical analysis and do all as parsing, some "syntax errors" aren't really parsing errors, but undefined variables, some semantic problems can be detected when parsing. Some languages (infamously C++) are complex enough that checking syntax requires checking much beyond context free grammar aspects to catch "syntax errors".