3 ms·

I think the main reason why you split it is that it simply is easier to get the semantics you want, which is roughly what is being demonstrated here. Working on

by jchw 4y ago

I think the main reason why you split it is that it simply is easier to get the semantics you want, which is roughly what is being demonstrated here. Working on tokens is easier in the parser because things like the semantics of whitespace and lexical ambiguities can be handled by your algorithm of choice. Having tried to write full grammars using only parser combinators on top of raw codepoint streams, I can say: - It's completely possible - BUT the bits that would normally be handled elegantly in the lexing phase are now strewn into every single grammatical element's parser, and it's surprisingly hard to formulate composable solutions that don't lead to undesirable resolutions to ambiguous situations (or rejecting desired grammar, or accepting undesired grammar, etc.) I think it's possible that with differently defined grammars, it would be fine. For example, JSON should be completely trivial just because of how few tokens there are and how little ambiguity there is; I tend to write JSON parsers directly against the codepoints for this reason, in the odd event I have to write a JSON parser. (Yes, it comes up. Yes, I am aware JSON has some weird edge cases and I shouldn't do this.)

xyzzy_plugh 4y ago
I agree! The article addresses this fairly well. In my experience, another reason to split is to be able to manipulate the AST independently from parsing. For example, you may have multiple dialects or representations (such as a serialized form) for which you don't require the lexer, which is typical for non-toy or trivial parsers. Even if tokenization happens during parsing, there is almost always still some separation. Often times it's just semantics, where the lexer doesn't strictly emit tokens, but simply represents the token in-place. Another (more historic) reason the phases are typically separate is that it allows you to reason about them and the finite state machine. For example, you could write the state transitions by hand in the traditional form and reduce as you go, just like in the dragon book. If you want to reason about grammars then it behoves you to wield the traditional form.
- jchw 4y ago
  Yeah, on the note of benefits from the split, I'm actually curious about when the best time to implement C macro expansion is. I think after lexing but potentially before parsing might be a good answer, which I did not expect. Of course... It would be wise to take a look at what the Clang and GCC frontends do, but I haven't gotten the chance.
  - xyzzy_plugh 4y ago
    Traditionally the C Preprocessor is a separate dialect distinct from C itself, and outputs C. So, historically it would be before lexing with respect to C. It's also been used to process non-C text, but that's fairly obscure. The hint is in the name: "Preprocessor" I'm sure some modern compilers blur the stages nowadays.
    - jchw 4y ago
      Yeah, I totally hear what you are saying. At the same time, I at least do know that Clang and GCC do the preprocessing in-line with parsing, rather than forking out to an external preprocessor. In fact, I assume these days, the way it works is actually that your cpp binary would basically be the compiler except it disables the part after the preprocessor and just dumps the resulting AST. That said, I have not read a lot of compiler source code to back this thought up. I have read some, but mostly in the C++ backend side, usually to resolve curiosities about vtable implementation details.
      - kevin_thibedeau 4y ago
        The #line directive essentially requires that you either handle macros directly in the compiler or add a syntax extension to carry that info over the wall.
        wahern 4y ago
        > or add a syntax extension to carry that info over the wall. Isn't that why #line exists in the first place? A lot of online literature, including the clang and GCC manuals, are worded in a way that makes it seem like the purpose is for consumption by the preprocessor, but I'd be surprised if the original purpose wasn't to communicate line numbers from the preprocessor to the compiler. The #line directive isn't mentioned in K&R; not even in the "ANSI C" second edition, despite C89 standardizing #line. Of course, it's a preprocessor directive, but leveraging the syntax this way is a nice hack: 1) It's very simple to identify C preprocessor directives (see #2), and cheap to add a pre-pass to a C compiler to identify directives, accepting #line but throwing an error (or complaining about and discarding) any other directive. 2) There's no way to generate valid, non-preprocessor C code that might look like a directive. '#' is not and never will be an operator in C or have any other lexical role; it can only exist within comments, character literals, or string literals. 3) You can gainfully feed #line to the preprocessor, for example from the output of a different transformer like M4.

by jchw 4y ago

xyzzy_plugh 4y ago

I agree! The article addresses this fairly well. In my experience, another reason to split is to be able to manipulate the AST independently from parsing. For example, you may have multiple dialects or representations (such as a serialized form) for which you don't require the lexer, which is typical for non-toy or trivial parsers. Even if tokenization happens during parsing, there is almost always still some separation. Often times it's just semantics, where the lexer doesn't strictly emit tokens, but simply represents the token in-place. Another (more historic) reason the phases are typically separate is that it allows you to reason about them and the finite state machine. For example, you could write the state transitions by hand in the traditional form and reduce as you go, just like in the dragon book. If you want to reason about grammars then it behoves you to wield the traditional form.

jchw 4y ago
Yeah, on the note of benefits from the split, I'm actually curious about when the best time to implement C macro expansion is. I think after lexing but potentially before parsing might be a good answer, which I did not expect. Of course... It would be wise to take a look at what the Clang and GCC frontends do, but I haven't gotten the chance.
- xyzzy_plugh 4y ago
  Traditionally the C Preprocessor is a separate dialect distinct from C itself, and outputs C. So, historically it would be before lexing with respect to C. It's also been used to process non-C text, but that's fairly obscure. The hint is in the name: "Preprocessor" I'm sure some modern compilers blur the stages nowadays.
  - jchw 4y ago
    Yeah, I totally hear what you are saying. At the same time, I at least do know that Clang and GCC do the preprocessing in-line with parsing, rather than forking out to an external preprocessor. In fact, I assume these days, the way it works is actually that your cpp binary would basically be the compiler except it disables the part after the preprocessor and just dumps the resulting AST. That said, I have not read a lot of compiler source code to back this thought up. I have read some, but mostly in the C++ backend side, usually to resolve curiosities about vtable implementation details.
    - kevin_thibedeau 4y ago
      The #line directive essentially requires that you either handle macros directly in the compiler or add a syntax extension to carry that info over the wall.
      - wahern 4y ago
        > or add a syntax extension to carry that info over the wall. Isn't that why #line exists in the first place? A lot of online literature, including the clang and GCC manuals, are worded in a way that makes it seem like the purpose is for consumption by the preprocessor, but I'd be surprised if the original purpose wasn't to communicate line numbers from the preprocessor to the compiler. The #line directive isn't mentioned in K&R; not even in the "ANSI C" second edition, despite C89 standardizing #line. Of course, it's a preprocessor directive, but leveraging the syntax this way is a nice hack: 1) It's very simple to identify C preprocessor directives (see #2), and cheap to add a pre-pass to a C compiler to identify directives, accepting #line but throwing an error (or complaining about and discarding) any other directive. 2) There's no way to generate valid, non-preprocessor C code that might look like a directive. '#' is not and never will be an operator in C or have any other lexical role; it can only exist within comments, character literals, or string literals. 3) You can gainfully feed #line to the preprocessor, for example from the output of a different transformer like M4.