5

tl;dr-ers:

How does a lexer normally deal with none-inline statements. statements that do not end with a specified statement delimiter. Such as control flow statements?


I believe that I have a fairly good grasp on lexical analysis, and can move on in my quest for understanding lexers/parsers. I do however, understand how lexers deal with 1multi-line statements.

After reading a Wikipedia article on the Comparison of programming languages syntax, The thing that all languages have in common, is that they have a very specfic statement delimeter. Some used semicolons(;) as a statement delimiter, others use whitespace(\ws), and some used periods(.).

Using this method, i fail to see how those programming languages, are able to have functions\class\control flow, that span multiple lines. Correct me if I'm wrong, but I'm pretty sure that most of the popular programming languages(Python, Java, C, C++, C#, Javascript, etc...) Do not use their statement delimiters at the end of functions, or classes(I know that classes in C++ do use semicolons at there end, but that is besides the point), or control flow.

This means that either: A: Lexers make a special exception for statements that span multiple lines. Or B: The lexer just treats multi-line statements as a regular statement, and it is the parser's job to make sense of them.

For example, Take take this pseudo program in C++:

int exampleVar; //<-- inline statement. Delimited with a semicolon

void exampleFunc() { //<-- multi-line statement. This statement is the start of a block.
    // do things
} //<-- this is where the statement that was started above, should end?

Clearly, it's easy to see where you should end the first statement. You end it at the semicolon. But how is the second statement dealt with? Is the statement extend to include everything up until the closing curly brace?

Or I could just be misguided in my thinking. It could be that the lexer has absolutely nothing to to do with 1multi-line statements. Is this the job of the parser? That is, is it the parser's job to make sense of 1multi-line statements?

To as clear as possible, my question is: How(if they should in the first place), should a lexer deal with statements that are not inline, and cannot just be terminated as if they were. How does a lexer normally deal with none-inline statements. statements that do not end with a specified statement delimiter. Such as control flow statements?

1To be clear, I do not mean multi-line statements, in the sense of line continuation. I mean them in the sense of statements that start off a block. Such as a function declaration. When you're defining a function, you also need to know the statements that follow the function definition up to a certain block delimiter. So you can't just terminate the statement after the definition.

7

As you've already conjectured, this is not the lexer's job. It doesn't trade in terms of statements, declarations and definitions but in much more low-level entities called tokens.

For example, for the following C function,

static int
sum_plus_42(const int a, const int b)
{
  int result = a + b + 42;
  return result;
}

the lexer would produce the following sequence of tokens.

  • keyword static
  • keyword int
  • identifier sum_plus_42
  • opening parenthesis
  • keyword const
  • keyword int
  • identifier a
  • comma
  • keyword const
  • keyword int
  • identifier b
  • closing parenthesis
  • opening brace
  • keyword int
  • identifier result
  • operator =
  • identifier a
  • operator +
  • identifier b
  • operator +
  • integer literal 42
  • semicolon
  • keyword return
  • identifier result
  • semicolon
  • closing parenthesis

If there were a syntax error in the code (such as mismatched parenthesis), the lexer would happily tokenize it anyway. It would, however, detect a lexical error such as invalid characters in a numeric literal, say 123wrong456.

After the source code has been tokenized, the parser constructs the syntax tree from the token sequence.

Both, lexical and syntactic analysis are driven by a specification of a formal grammar and there is no theoretical reason why these couldn't be merged into a single one. In practice, however, it makes for cleaner and better structured code to separate the two steps. The grammar for the lexical analysis is usually much simpler and regular while the grammar used to describe the syntax of the language is context-free. In practice, the grammars are often not that clean and have more or less special-casing outside the formal rules of regular and context-free grammars.

In case this is not clear, the terminal symbols used in the grammar for the syntactic analysis are the tokens produced by the lexer, which are non terminal symbols of its own grammar.

  • 1
    I think what tripped me up is reading the wikipedia article I linked to, and thinking that the tokenizer separated the source code in statements, and then separated the statements into tokens. Sort of like a list of statements, and inside each statement list, there is a list of tokens. Thanks for the clarification though. +1 – Christian Dean Sep 28 '16 at 2:45
  • 1
    In principle, you could also build a compiler that works that way. It's not common practice, as far as I can tell, though. And I'm pretty sure it would make things a lot more complicated. – 5gon12eder Sep 28 '16 at 2:48

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.