4 ms·

Or you can replace the escape sequences right in the source text: it works since no escape sequence is shorter than the text it represents.

ksaj 3y ago
What about \n, which decodes to 0x0ah - two bytes to one byte? I can't think of any others like that, but newline in different OS's get represented in various different ways (like DOS's famous CRLF, which adds an 0x0dh to the recipe). Operating systems that use 0x0ah alone could very well be the only example.
- dietr1ch 3y ago
  Note that while in your compiler you don't really care about the representation that the OS expect in real files. It's ok for your intermediate, in-memory representation to be meaningless to the OS. Also, maybe it's not a literal character for character replacement. Since lengths are probably changing, your pre-processed input might be shorter (or longer if you truly need to expand some escaped chars (and you have a program that just wants to break your compiler by abusing that escape sequence :P))
  - ksaj 3y ago
    Yes, but some OS's use 0x0ah alone, which is half the bytes of \n representation. People from the 90's will easily remember navigating the ^M (which is the 0x0dh showing up) showing up at the end of every line in a DOS text file when viewing them under a Linux text editor.
    - dietr1ch 3y ago
      This is a different problem around how to interpret new lines from a Windows file (\r\n) or maybe an old Mac version (\n\r to keep things incompatible I guess). If you are not happy with the OS's choice for new lines, you can pre-process that when reading the input as the very first stage. This is what I meant when I said that your compiler doesn't really care about the OS's semantics once the file is in memory, you only need to respect them if you are writing intermediate state to files (like some IR). The article is talking about how to handle escaped characters in the source, like literal `\n` you can see on `let hi = "Hello\nWorld\nfrom my compiler!"` using your average text editor (0x5c+0x6e in ASCII), and how to build an efficient string type that mostly borrows views from the in-memory version of the source file (which could be a pre-processed version of the raw file if you hate odd line breaks).
      - zarzavat 3y ago
        FWIW the Classic Mac line ending is \r. \n\r was used by Acorn, apparently.
    - Joker_vD 3y ago
      Before the UNIX had the bright idea to represent newlines as single LFs in disk files and then write a bunch of code in the kernel for the tty driver to convert LF to and from CRLF pairs (which is what ttys actually used), everybody else used CRLF pair to indicate a linebreak. That's why almost all network protocols use CRLF, and not because Microsoft invented the time machine and travelled into the seventies to hinder the UNIX adoption.
      - jfk13 3y ago
        > everybody else used CRLF pair to indicate a linebreak Almost everybody... https://en.wikipedia.org/wiki/Newline#Representation https://en.wikipedia.org/wiki/Newline#Representation mentions a couple that apparently used LFCR.
- chrismorgan 3y ago
  Reread the suggestion, you’ve got it back to front: > no escape sequence is shorter than the text it represents The idea is that you unescape immediately, and if necessary shuffle the remainder back, leaving a blank space at the end, but able to reuse the initial allocation. Also, I don’t even know of anything that actually turns a \n into {CARRIAGE RETURN, LINE FEED}; if you want that, you’ll need \r\n. (A very few situations are a bit fuzzy about it, e.g. \r and \n are a bit wonky in Vim’s :substitute, but that’s all I can think of).
- lelanthran 3y ago
  Isn't the two byte escape sequence not shorter than the one byte newline? I do inline replacement of escaped values all the time, because the sequence is always longer than the replacement.
  - hansvm 3y ago
    And exponentially shorter with nested escapes.
dietr1ch 3y ago
I was wondering the same thing, you can probably mess a bit with the input if you can deal with the drawbacks (which seem mild, pre-processed input might be shorter and column numbers might be off).
deleted 3y ago
[deleted]
kelnos 3y ago
The downside is that you lose the original and can't refer to it anymore. If (like OP) you are writing a compiler, you may need to spit out error messages, and will want to be able to say "line X, column Y", or even just print out the original line itself. And no, you can't re-escape your unescaped text, as you can't do so losslessly in all cases. For some, the unescaped text might not obviously need re-escaping (e.g. the original text had a unicode escape for an emoji; you'll "forget" that after you unescape it).
- Joker_vD 3y ago
  Well, that's a trade-off, as most things in the parser design. You can go the way of the compilers of the yore and report only the line numbers. Or you can maintain column numbers only for a single line, everything in the previous lines will get only a line number. Or you can store the column numbers in the tokens which works better if you lexer emits them one at a time and the parser is fine with that.
  - alpaca128 3y ago
    Storing column numbers for every token just in case there might be an error likely weighs out the string allocation reduction. But for error messages it might suffice to output just the line number together with a snippet of the line at the error location. Most people probably don't care about the exact column number, though it might be bad for other tools.
    - Joker_vD 3y ago
      > Storing column numbers for every token just in case there might be an error likely weighs out the string allocation reduction. Only if you store all of the tokens before starting the parsing, which would arguably be the bigger fish to fry in terms of conserving memory. But it actually slows down the lexer: by an insignificant amount if the lexer is the traditionally written one, or by quite a lot if it's one of those new-fangled ones that use SIMD-instructions speed up finding the token boundaries... but such lexers also benefit wrom the ability to re-use unneeded parts of the source input (like quotes or spaces) for storing auxillary data.
chubot 3y ago
You can also be lazy about it -- store the quoted string with 1 escape as 3 separate (fixed-size) tokens/spans, and don't actually allocate or decode strings until you need to. In an interpreter there may be many string constants that aren't used (e.g. docstrings in Python). And probably in a compiler too, since you may import a ton of library code and only use 1 function. Storing escapes as tokens also lets you point to them in warnings. I think most compilers warn about bad octal escapes like \777 these days.
- Joker_vD 3y ago
  You can, but see, the actual contents of the strings are really only used at the code-gen stage, where it's put verbatim in the .rodata section. Arguably, it could have been discarded by the dead-code elimination pass by that time but that's unlikely: most of the string constants do actually see use in the program. Pushing that part of the lexer's task so late on the off-chance it probably won't be needed IMHO only makes sense if you're writing a parser for an IDE/LSP in which case you don't need to unescape the string at all.
  - chubot 3y ago
    If the string contents are only used at the code-gen stage, then I see that as an argument FOR being lazy. On the other hand, the principle of validating your input up front suggests that you should at least recognize the escapes, if not store their decoded from. That is, you can be lazy by only parsing \\ and \" to find the closing quote, and producing 1 token. But that's nearly the same thing as doing a full-decoding. The downsides are that it allows invalid input deeper into the compiler, and it doesn't alert the user to errors as quickly as possible. most of the string constants do actually see use in the program [citation needed] :) I don't see how that can possibly hold across languages (Go, Java, Swift, etc.), and I'm not even sure that's true for C/C++. only makes sense if you're writing a parser for an IDE/LSP in which case you don't need to unescape the string at all. Clang's front end is used both for LSP and for code gen, so that distinction doesn't apply in all cases. It seems like most projects want to reuse their front ends these days. And again the LSP will want to warn about invalid escapes like \777 and \u{9999999}. ---- EDIT: Although I guess in C, emitting all the errors up front, and then storing the decoded form in place, is probably about the same cost. If there's no allocation, then I might treat eager decoding as "free". I think the problem is that you lose info, and most languages have more structure in their string literals, e.g. Swift has \(var) interpolation, and IDEs in Rust want to do things with {} format! strings, etc.

ksaj 3y ago

What about \n, which decodes to 0x0ah - two bytes to one byte? I can't think of any others like that, but newline in different OS's get represented in various different ways (like DOS's famous CRLF, which adds an 0x0dh to the recipe). Operating systems that use 0x0ah alone could very well be the only example.

dietr1ch 3y ago
Note that while in your compiler you don't really care about the representation that the OS expect in real files. It's ok for your intermediate, in-memory representation to be meaningless to the OS. Also, maybe it's not a literal character for character replacement. Since lengths are probably changing, your pre-processed input might be shorter (or longer if you truly need to expand some escaped chars (and you have a program that just wants to break your compiler by abusing that escape sequence :P))
- ksaj 3y ago
  Yes, but some OS's use 0x0ah alone, which is half the bytes of \n representation. People from the 90's will easily remember navigating the ^M (which is the 0x0dh showing up) showing up at the end of every line in a DOS text file when viewing them under a Linux text editor.
  - dietr1ch 3y ago
    This is a different problem around how to interpret new lines from a Windows file (\r\n) or maybe an old Mac version (\n\r to keep things incompatible I guess). If you are not happy with the OS's choice for new lines, you can pre-process that when reading the input as the very first stage. This is what I meant when I said that your compiler doesn't really care about the OS's semantics once the file is in memory, you only need to respect them if you are writing intermediate state to files (like some IR). The article is talking about how to handle escaped characters in the source, like literal `\n` you can see on `let hi = "Hello\nWorld\nfrom my compiler!"` using your average text editor (0x5c+0x6e in ASCII), and how to build an efficient string type that mostly borrows views from the in-memory version of the source file (which could be a pre-processed version of the raw file if you hate odd line breaks).
    - zarzavat 3y ago
      FWIW the Classic Mac line ending is \r. \n\r was used by Acorn, apparently.
  - Joker_vD 3y ago
    Before the UNIX had the bright idea to represent newlines as single LFs in disk files and then write a bunch of code in the kernel for the tty driver to convert LF to and from CRLF pairs (which is what ttys actually used), everybody else used CRLF pair to indicate a linebreak. That's why almost all network protocols use CRLF, and not because Microsoft invented the time machine and travelled into the seventies to hinder the UNIX adoption.
    - jfk13 3y ago
      > everybody else used CRLF pair to indicate a linebreak Almost everybody... https://en.wikipedia.org/wiki/Newline#Representation https://en.wikipedia.org/wiki/Newline#Representation mentions a couple that apparently used LFCR.
chrismorgan 3y ago
Reread the suggestion, you’ve got it back to front: > no escape sequence is shorter than the text it represents The idea is that you unescape immediately, and if necessary shuffle the remainder back, leaving a blank space at the end, but able to reuse the initial allocation. Also, I don’t even know of anything that actually turns a \n into {CARRIAGE RETURN, LINE FEED}; if you want that, you’ll need \r\n. (A very few situations are a bit fuzzy about it, e.g. \r and \n are a bit wonky in Vim’s :substitute, but that’s all I can think of).
lelanthran 3y ago
Isn't the two byte escape sequence not shorter than the one byte newline? I do inline replacement of escaped values all the time, because the sequence is always longer than the replacement.
- hansvm 3y ago
  And exponentially shorter with nested escapes.

dietr1ch 3y ago

I was wondering the same thing, you can probably mess a bit with the input if you can deal with the drawbacks (which seem mild, pre-processed input might be shorter and column numbers might be off).

deleted 3y ago

[deleted]

kelnos 3y ago

The downside is that you lose the original and can't refer to it anymore. If (like OP) you are writing a compiler, you may need to spit out error messages, and will want to be able to say "line X, column Y", or even just print out the original line itself. And no, you can't re-escape your unescaped text, as you can't do so losslessly in all cases. For some, the unescaped text might not obviously need re-escaping (e.g. the original text had a unicode escape for an emoji; you'll "forget" that after you unescape it).

Joker_vD 3y ago
Well, that's a trade-off, as most things in the parser design. You can go the way of the compilers of the yore and report only the line numbers. Or you can maintain column numbers only for a single line, everything in the previous lines will get only a line number. Or you can store the column numbers in the tokens which works better if you lexer emits them one at a time and the parser is fine with that.
- alpaca128 3y ago
  Storing column numbers for every token just in case there might be an error likely weighs out the string allocation reduction. But for error messages it might suffice to output just the line number together with a snippet of the line at the error location. Most people probably don't care about the exact column number, though it might be bad for other tools.
  - Joker_vD 3y ago
    > Storing column numbers for every token just in case there might be an error likely weighs out the string allocation reduction. Only if you store all of the tokens before starting the parsing, which would arguably be the bigger fish to fry in terms of conserving memory. But it actually slows down the lexer: by an insignificant amount if the lexer is the traditionally written one, or by quite a lot if it's one of those new-fangled ones that use SIMD-instructions speed up finding the token boundaries... but such lexers also benefit wrom the ability to re-use unneeded parts of the source input (like quotes or spaces) for storing auxillary data.

chubot 3y ago

You can also be lazy about it -- store the quoted string with 1 escape as 3 separate (fixed-size) tokens/spans, and don't actually allocate or decode strings until you need to. In an interpreter there may be many string constants that aren't used (e.g. docstrings in Python). And probably in a compiler too, since you may import a ton of library code and only use 1 function. Storing escapes as tokens also lets you point to them in warnings. I think most compilers warn about bad octal escapes like \777 these days.

Joker_vD 3y ago
You can, but see, the actual contents of the strings are really only used at the code-gen stage, where it's put verbatim in the .rodata section. Arguably, it could have been discarded by the dead-code elimination pass by that time but that's unlikely: most of the string constants do actually see use in the program. Pushing that part of the lexer's task so late on the off-chance it probably won't be needed IMHO only makes sense if you're writing a parser for an IDE/LSP in which case you don't need to unescape the string at all.
- chubot 3y ago
  If the string contents are only used at the code-gen stage, then I see that as an argument FOR being lazy. On the other hand, the principle of validating your input up front suggests that you should at least recognize the escapes, if not store their decoded from. That is, you can be lazy by only parsing \\ and \" to find the closing quote, and producing 1 token. But that's nearly the same thing as doing a full-decoding. The downsides are that it allows invalid input deeper into the compiler, and it doesn't alert the user to errors as quickly as possible. most of the string constants do actually see use in the program [citation needed] :) I don't see how that can possibly hold across languages (Go, Java, Swift, etc.), and I'm not even sure that's true for C/C++. only makes sense if you're writing a parser for an IDE/LSP in which case you don't need to unescape the string at all. Clang's front end is used both for LSP and for code gen, so that distinction doesn't apply in all cases. It seems like most projects want to reuse their front ends these days. And again the LSP will want to warn about invalid escapes like \777 and \u{9999999}. ---- EDIT: Although I guess in C, emitting all the errors up front, and then storing the decoded form in place, is probably about the same cost. If there's no allocation, then I might treat eager decoding as "free". I think the problem is that you lose info, and most languages have more structure in their string literals, e.g. Swift has \(var) interpolation, and IDEs in Rust want to do things with {} format! strings, etc.