9
$\begingroup$

I've written what I think is a fairly typical compiler frontend: I have a lexer that produces a list of tokens, then I give that list to a recursive-descent parser that produces the syntax tree. This works fine so far, and I have variable interpolations "Hello, $name!" working just by searching for $ within the string token value.

I want to add full embedded expressions something like "Hello ${name ?? "world"}!", but now I have a problem: my lexer can't just produce a token for the string literal any more, there has to be something more. Even figuring out where the end is is hard when there can be other interpolations nested inside. Really, I want to be parsing the expression itself when it appears anyway and not trying to retrofit it in.

How can I handle these? Is this a situation where I should replace it all with a different sort of parser instead?

$\endgroup$
4
  • 3
    $\begingroup$ This should be the same basic algorithm as balancing parens or brackets, no? $\endgroup$ Commented May 17, 2023 at 1:47
  • $\begingroup$ Well, yes and no. You can have embedded strings themselves containing nested interpolations or escaped brackets, which complicate that, but also you want to parse the body of the expression (ideally inline). I tried to make that clear; is there an edit you'd suggest to get the point across? $\endgroup$ Commented May 17, 2023 at 1:53
  • 1
    $\begingroup$ @Bbrk24 Not so simple, because balancing parens is done purely by the parser, but for string interpolation the lexer needs to know about the context, and tokenize differently based on it. $\endgroup$ Commented May 17, 2023 at 1:54
  • $\begingroup$ Instead of having separate lexer and parser phases, you could have a single parser phase, so string interpolation would no longer be a problem. This would probably have an impact on performance, though. $\endgroup$ Commented May 17, 2023 at 13:56

3 Answers 3

Reset to default
5
$\begingroup$

One option is to disallow the string's quotation character inside interpolations. So, for instance, if your language allows " and ' interchangeably as string separators, then "a${'b'}c" is fair game, but "a${"b"}c" is just a parse error.

Your lexer still has to be able to balance parentheses inside of interpolation (in case there are pairs of braces inside the interpolation), but you probably already do that in other places. But if you're ever inside of string interpolation and you find the quote character that would terminate the end of the string, you can fail confidently with a good error message. This has the added benefit of being fairly easy for IDEs to highlight, as the same basic algorithm can be applied there.

$\endgroup$
2
  • 1
    $\begingroup$ FWIW, Python's f-strings do this. $\endgroup$ Commented May 17, 2023 at 3:25
  • $\begingroup$ Having a simple rule like this has the advantage that if the user makes a mistake, there's a good chance that this will cause a syntax error around the point of the mistake. It also means that there's a simple rule that any valid expression not containing the quote character can be placed in the interpolation: for more complex syntaxes, you can typically put almost any valid expression but the exceptions can be subtle and hard to cope with when they happen. $\endgroup$ Commented May 23, 2023 at 22:08
3
$\begingroup$

I haven't implemented this in any of my own languages, but here's how I'd do it.

The lexer needs to know the context it's lexing in, in order to determine whether a } character means a regular close brace, or the resumption of a string template. You will need a stack of opening braces ─ either { or ${ ─ to keep track of this. The stack is initially empty.

  • When you see a {, push it to the context stack, and emit a { token.

  • When you see a ", start lexing a string literal until you find either a closing " or an opening ${. Either way, emit the string literal part as one token. Then if it's a ${, push it to the stack, and emit a ${ token.

  • When you see a }, emit a } token, and pop from the stack. If the popped token was a ${, then continue lexing a string part as if you had just encountered a ".

Now the lexing is complete, we have to parse it. When we are parsing an expression and we see a string literal part, do the following:

  • Create a list of template parts, initially containing just the first string literal part.
  • While there is a string literal part or a ${ token at the head of the queue:
    • Poll it from the queue.
    • If it's a string literal part, append it to the list and continue.
    • Otherwise it's a ${ token, so parse an expression, and append the expression to the list of template parts. There should now be a } token at the head of the queue (if not, report a syntax error); poll it, and continue.

Note that this will also automatically concatenate adjacent templates, like "foo" "bar" into "foobar", like Python does. If this is undesirable, then change the loop condition accordingly, so that the loop does not continue if there is a string literal part at the head of the queue and also one at the end of the parts list.

$\endgroup$
2
$\begingroup$

You can do this with a recursive descent parser and the syntax you've described. The big change will be to the lexer: instead of making a big list of tokens up front, it'll be pull-driven where the parser asks what the next token is, rather than moving an index through a list.

In the lexer

When the lexer finds a string literal, there are two cases:

  1. It's just a literal string, no interpolations. Produce a string literal token as you do now.
  2. It has ${ before the closing quote. Produce a special token that tells the parser that there is an interpolation following. This could be a different kind of token, or a flag on the string literal.

In either case, the lexer remembers its position as just after the last character, be it the closing quote or opening brace.

In the parser

When the parser encounters that special token, it switches to parsing an expression afterwards, as though it were parsing a brace-delimited block and ending when it sees the }. This will continue using the lexer and all the ordinary parsing mechanics, including recursing into further string literals.

When it finds the end of the interpolation it tells the lexer to start parsing a string literal again, from where it's at right now in the middle of the string (just using all the string-lexing code from after the opening quote again). The next token will either be a standard string token, meaning that's the end of the literal, or another interpolation token, meaning the process continues.

It's easiest to have the interpolation-parsing code handle all of this until the end of the string. Once it sees a regular string token, it can produce an AST node collating all the literal pieces and interpolated expressions. I've got a practical implementation of this approach here, which is relatively simple. In fact, a plain string literal is just treated as a degenerate interpolated string with no interpolations.

This isn't the only way to go about this. More bottom-up parsing models may support these sorts of construction "for free", and even within recursive-descent parsers there are other ways to manage it. It's fairly straightforward to incorporate this change on top of an existing parser, however.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.