3 ms·

I had wondered about why the split is useful, and this article has answered the question to some degree. The general idea seems to be "it's easier to split it"

I had wondered about why the split is useful, and this article has answered the question to some degree. The general idea seems to be "it's easier to split it" and "you help reduce ambiguity in the parser by taking care of that in the lexer". To those knowledgeable in lexing and parsing, I pose a question: How do you determine what should be part of the lexing phase and what should be part of the parsing phase? Do you choose arbitrarily and move things from one phase to another if it's simpler one way or another? Or is there a better way?

School-Cotton 3y ago
Roughly lexing handles things that can be recognized with regexes (i.e., that don't have recursively nested structure).
kryptiskt 3y ago
Lexing should be strictly local and possible to do as a state machine that is reset after each token. So if something depends on the context, save it for the parser.
- justin_oaks 3y ago
  Yes, that makes sense. Chunks of text that don't depend on context is for the lexter, and context sensitive (i.e. "{" needs a matching "}" ) is for the parser
alwaysbeconsing 3y ago
Lexing translates raw characters into non-semantic tokens. Punctuation is a good way to demonstrate what I mean by non-semantic. Take Rust, which uses `{` for both blocks and closure literal expressions; and uses `<` for generic parameter/argument wrappers, and also a binary operator. While lexing, you don't try to determine whether `{` is opening a closure or a block, or whether `<` is a binary operator. You just turn them into the tokens `LeftCurlyBrace` and `LeftAngleBracket`. It's the parser's responsibility to take those tokens and their neighbors and figure out what they're being used for. The benefit is that this keeps each stage much simpler: lexing doesn't have to do much if any lookaround, and parsing mostly doesn't have to do anything character-wise.
- justin_oaks 3y ago
  Thanks. That clears it up a lot. The example of using the same tokens but for different purposes makes it clear that the lexer shouldn't be in the business of assigning meaning (semantics) to the tokens, and the parser shouldn't be in the business of fiddling with characters when it's something the lexer can do.
  - cellularmitosis 3y ago
    If you have half an hour, this is worth a watch as well: https://www.destroyallsoftware.com/screencasts/catalog/a-compiler-from-scratch https://www.destroyallsoftware.com/screencasts/catalog/a-com...
emoII 3y ago
The lexer groups individual characters into building blocks, tokens, that the language is made of. From keywords such as "if", "for", "function" and symbols like "{", to arbitrary identifiers that doesn't contribute to the actual meaning or structure of the program, i.e. "foo". The parser groups the tokens into meaningful statements, it implements the grammar. If the parser sees an "if", it expects some condition next (depending on the grammar of course). If the parser detects statements that are not consistent with the grammar of the language, it should reject the program. Tldr they work on different levels, lexers just finds the individual building blocks, the parser builds the program
- justin_oaks 3y ago
  The part I was missing was the idea of keeping ALL meaning/structure in the parser, and the lexer is used to identify chunks of characters that can be used to construct the meaning/structure of the program.
matheusmoreira 3y ago
> How do you determine what should be part of the lexing phase and what should be part of the parsing phase? Recursion. If your thing can contain other things, it requires a full parser. Otherwise a lexer can handle it. In other words, use a lexer when a regular language is sufficient to describe the input and a parser when it's not. Lexer: 12345 Parser: [123 [45]]

School-Cotton 3y ago

Roughly lexing handles things that can be recognized with regexes (i.e., that don't have recursively nested structure).

kryptiskt 3y ago

Lexing should be strictly local and possible to do as a state machine that is reset after each token. So if something depends on the context, save it for the parser.

justin_oaks 3y ago
Yes, that makes sense. Chunks of text that don't depend on context is for the lexter, and context sensitive (i.e. "{" needs a matching "}" ) is for the parser

alwaysbeconsing 3y ago

Lexing translates raw characters into non-semantic tokens. Punctuation is a good way to demonstrate what I mean by non-semantic. Take Rust, which uses `{` for both blocks and closure literal expressions; and uses `<` for generic parameter/argument wrappers, and also a binary operator. While lexing, you don't try to determine whether `{` is opening a closure or a block, or whether `<` is a binary operator. You just turn them into the tokens `LeftCurlyBrace` and `LeftAngleBracket`. It's the parser's responsibility to take those tokens and their neighbors and figure out what they're being used for. The benefit is that this keeps each stage much simpler: lexing doesn't have to do much if any lookaround, and parsing mostly doesn't have to do anything character-wise.

justin_oaks 3y ago
Thanks. That clears it up a lot. The example of using the same tokens but for different purposes makes it clear that the lexer shouldn't be in the business of assigning meaning (semantics) to the tokens, and the parser shouldn't be in the business of fiddling with characters when it's something the lexer can do.
- cellularmitosis 3y ago
  If you have half an hour, this is worth a watch as well: https://www.destroyallsoftware.com/screencasts/catalog/a-compiler-from-scratch https://www.destroyallsoftware.com/screencasts/catalog/a-com...

emoII 3y ago

The lexer groups individual characters into building blocks, tokens, that the language is made of. From keywords such as "if", "for", "function" and symbols like "{", to arbitrary identifiers that doesn't contribute to the actual meaning or structure of the program, i.e. "foo". The parser groups the tokens into meaningful statements, it implements the grammar. If the parser sees an "if", it expects some condition next (depending on the grammar of course). If the parser detects statements that are not consistent with the grammar of the language, it should reject the program. Tldr they work on different levels, lexers just finds the individual building blocks, the parser builds the program

justin_oaks 3y ago
The part I was missing was the idea of keeping ALL meaning/structure in the parser, and the lexer is used to identify chunks of characters that can be used to construct the meaning/structure of the program.

matheusmoreira 3y ago

> How do you determine what should be part of the lexing phase and what should be part of the parsing phase? Recursion. If your thing can contain other things, it requires a full parser. Otherwise a lexer can handle it. In other words, use a lexer when a regular language is sufficient to describe the input and a parser when it's not. Lexer: 12345 Parser: [123 [45]]