12
$\begingroup$

I'm currently working on a protobuf parser and I'm trying to preserve the comments in the AST. However, there many non-trivial cases and I was wondering if there was an already existing algorithm/data structure for this kind of problem.

Here is an example of most of the possible comments:

message Comments {
  int32 foo = 1;  // Comment attached to foo.
  // Comment attached to bar.
  int32 bar = 2;

  string baz = 3;
  // Comment attached to baz.
  // Another line attached to baz.

  // Comment attached to moo.
  //
  // Another line attached to moo.
  double moo = 4;

  // Detached comment for corge. This is not leading or trailing comments
  // to moo or corge because there are blank lines separating it from
  // both.

  // Detached comment for corge paragraph 2.

  string corge = 5;
  /* Block comment attached
   * to corge. */
  /* Block comment attached to
   * grault. */
  int32 grault = 6;

  optional int32 another = 7;
  // attached to funny, not trailing comment for another
  optional int32 funny = 8;

  // ignored detached comments.
}

Note that this is important for my AST to determine leading comments (just before a statement), leading detached comments (look at the comments before corge, they are detached because separated by blank newlines), and trailing comments (just after statements).

Edit

As it was not clear, I want to mention that I'm writing a parser by hand and I also wrote a lexer that provides tokens for comment and spaces.

$\endgroup$
2
  • $\begingroup$ thanks for editing, do you have parsing functions like parseField() or parseVariable() that you call from e.g. parseMessage()? or do you have a callback that is called on each token, that you pass down to some state machine? can you tell us more about your current strategy and how it makes it difficult to parse comments etc. ? $\endgroup$
    – coredump
    Jul 11, 2023 at 12:46
  • $\begingroup$ I have parseField and parseMessage functions. I'm afraid the rest is a little bit specific to Protobuf but basically, I need to record locations of each message and field in the code. These locations are the start and end of each construct in the language. Now, because I'm currently only doing 1 pass, It is hard to know if a comment is leading, trailing or detached. Hope that clarifies a little. $\endgroup$ Jul 12, 2023 at 2:45

3 Answers 3

12
$\begingroup$

However, there many non-trivial cases and I was wondering if there was an already existing algorithm/data structure for this kind of problem.

Yes there is, but you are absolutely correct that there are a lot of cases to consider and there is no one slam-dunk-obviously-correct algorithm.

Roslyn -- the C# and VB compilers we designed in the early 2010s -- uses "full fidelity parsing" -- that is, every character in the original source code is assigned a unique location in the lex and parse, whether that character is whitespace, comment or program text proper. The reason for this was primarily to facilitate refactoring engines and code formatters. That is, when you highlight the call to Bar and click "create explanatory variable":

Foo(/* blah is known to be frobby */ Bar(blah), Baz(qux));

then we would probably like the refactoring tool to produce something like:

var bar = /* blah is known to be frobby */ Bar(blah); 
Foo(bar, Baz(qux));

And not

var bar = Bar(blah); 
Foo(/* blah is known to be frobby */ bar, Baz(qux));

And similarly there are situations where you want to know the spacing so as to preserve it or modify it according to rules in your code formatter, or warning pass, or whatever.

The way we did this was: every node in the parse tree knows the exact location in the token stream of the tokens, and every token has three parts: the "leading trivia list", the token itself, and the "trailing trivia list". "Trivia" is comments, spaces, tabs, newlines and so on.

Your question then is essentially what algorithm do we use to decide what trivia is "leading" of the next token instead of "trailing" of the previous token, and we just tried a whole bunch of different options until we found one that worked most of the time. If I recall correctly -- and this was over ten years ago so maybe don't trust me on this -- the simple solution we arrived at was trivia usually belongs to the token which follows it, so most trivia is leading trivia. The special case is trivia following the last token on a line is trailing trivia of that token.

That simple approach is likely not sophisticated enough for your use cases.

$\endgroup$
4
$\begingroup$

In your case you may want to add tokens in your lexer for comments and whitespace (e.g. empty-line, block-comment, line-comment) which retains most of the original formatting.

Then if you define a grammar you explicitly say that a field in protobuf is either an actual-field followed possibly by a line-comment (without empty-line) or a list of comment non-terminals followed by an actual-field.

This requires that you explicitly specify all the places where comments can happen, which is different from some possible implementation where the lexer just skips over comment sections.

$\endgroup$
2
  • $\begingroup$ Forgot to mention that I already have such token for comment and spaces. I'm mostly looking for an algorithm to distinguish between these different comments. $\endgroup$ Jul 11, 2023 at 8:41
  • 2
    $\begingroup$ So what is not clear to me now is how you process your tokens, do you write a parser by hand or do you have a parser generator based on a grammar ? Maybe you can edit the question to add more details about that part :) $\endgroup$
    – coredump
    Jul 11, 2023 at 9:02
3
$\begingroup$

Usually, you'd put comment-like tokens in a different category and link them to the adjacent real tokens. In your case, you might also need to add them to a global list so that you can distinguish between consumed comments and ones that have not been consumed. The consumption would happen in the parse rule either by consuming all comments before or after your anchor token. Based on your example, I guess that you will end up with looking in both directions and a complex rule on what to consume based on token kind and begin and end locations.

For input languages of code generators, it might not be correct to treat comments as comments. I have an example from a similar project for a serialization code generator that is also hand-written: https://github.com/serialization/ogss/blob/master/src/main/scala/ogss/frontend/skill/FileParser.scala

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .