Positive Lookbehind Support?

[snarkipus]

Maybe I missed it somewhere in the docs, but it's unclear to me whether the JS regex (or Chevrotain/regexp-to-ast?) supports positive lookbehind or not?

langium terminal:

hidden terminal HeaderComment: /(?<=(TDB|SDB)\n)([\s\S]*)(?=(REPLACE|INSERT))/;

Error Message:

Error: Unable to use "first char" lexer optimizations:

        Failed parsing: < /(?<=(TDB|SDB)\n)([\s\S]*)(?=(REPLACE|INSERT))/ >
        Using the regexp-to-ast library version: 0.5.0
        Please open an issue at: https://github.com/bd82/regexp-to-ast/issues
Warning: Warning: unable to identify line terminator usage in pattern.
        The problem is in the <HeaderComment> Token Type
         Root cause: Expected: ':' but found: '<' at offset: 3.
        For details See: https://chevrotain.io/docs/guide/resolving_lexer_errors.html#IDENTIFY_TERMINATOR

[msujew]

Hi @snarkipus,

I imagine it supports it, but it will probably require some additional input from the dev to determine the first character which actually might match this regular expression (see here). In theory, you can override the DefaultTokenBuilder.buildTerminalToken method to add/calculate this token property manually.

I'm wondering a bit though, why does your terminal require positive lookbehind? Is the start of the comment not actually part of the comment? Maybe with a bit more context, we can work out a simpler solution for this.

[snarkipus]

Thank you very much for taking a look ... glad I asked since the Chevrotain docs and regexp-to-ast stuff seemed to be at odds with each other.

Regarding the comment block itself, I don't have a hard requirement for it to be tokenized beyond the aesthetics of comment syntax highlighting. As such, I think rolling it into the BlockType terminal should work for my purposes.

A few questions:

1. I assume that the terminal parsing logic is fall-through so some thought needs to be put into what patterns get consumed by what terminal and in what order. Is this a generally correct assumption?
2. (Regex 101): What are the implications of greedy vs. non-greedy regex? sticky? <--- look it up and stop being lazy is a perfectly acceptable response
3. Reference Recommendations: Any of these in particular that you would recommend or any other resources you would suggest? I hate to clutter up the langium discussion threads with general parsing questions.

• DSLs in Action (Ghosh 2010)
• Domain-Specific Languages (Fowler 2010)
• Implementing Domain-Specific Languages with Xtext and Xtend (Bettini 2016)
• DSL Engineering (Voelter 2013)

For some reference/context, the following is the doc description of the comment text.

Following the TDB keyword, a comment may be entered. If included, the comment consists of one or more text
lines that can be used for whatever purposes the user wishes (e.g., to identify the particular TDB). This comment
block need not be initiated or terminated with the regular comment delimiters ($, $>, and <$). The
contents of the comment are echoed in output listing files, along with a time stamp, to provide an audit trail of the
processing steps that have been performed up to that point in time.

The block of comment lines is terminated by the presence of the <startup-option>, which is either INSERT-MODE
or REPLACE-MODE, and must appear on a line by itself.

Additionally, here is a snip from the overall structure.

[msujew]

I don't have a hard requirement for it to be tokenized beyond the aesthetics of comment syntax highlighting

Luckily, syntax highlighting is mostly independent of the actual terminals/parser rules, the generated text mate grammar is heuristically generated, and should only be used as some sort of getting started helper, as it can never hope to cover more language features than keywords, strings and (simple) comments. For more complex semantic higlighting, we also have a SemanticTokenProvider lsp service.

I assume that the terminal parsing logic is fall-through so some thought needs to be put into what patterns get consumed by what terminal and in what order. Is this a generally correct assumption?

Exactly, Chevrotain employs a first-match approach to lexing. We perform some rudimentary sorting on the tokens, whitespace first, then keywords (sorted by length), then any terminal rules (taken from the grammar as is, except for whitespace terminals). Consequently, terminal rules need to be in the right order so they don't conflict with each other. Your BlockType terminal for example always needs to appear in front of the ID terminal for it to be lexed at all.

What are the implications of greedy vs. non-greedy regex? sticky?

In general, a non-greedy regex will always try to match as few tokens as possible, which seems weird at first, but makes sense when we actually want to parse some delimiter (or use a lookahead), as it would swallow the delimiter if it were greedy. Sticky regexes are a bit more complicated to explain, but there's a great amount of resources on that online.

Reference Recommendations: Any of these in particular that you would recommend or any other resources you would suggest?

The DSL book on Xtext is probably quite nice, especially when looking at features which we've loaned from the framework (General parser features, validation, scoping, It covers way more than useful for Langium (we distanced ourselves from the EMF/Java mess), but I can imagine it to be a good entry point. Unfortunately I cannot give a personal recommendation, as my own DSL/language engineering knowledge comes from working on customer projects/Langium itself, rather than text books.

The block of comment lines is terminated by the presence of the , which is either INSERT-MODE
or REPLACE-MODE, and must appear on a line by itself.

Interesting, you should probably extend the BlockType terminal to include the -MODE part as well, since users might type REPLACE in their header comment, thereby accidentally terminating it.

[snarkipus]

Thanks again for taking the time to respond. It turns out that picking up JS, TS, regex, lexing, parsing, and the langium/VSCode framework simultaneously has turned out to be a bit ambitious.

I'm just waiting for a lightbulb to go on (or perhaps a particle of enlightenment). :)

[snarkipus]

Tag: @msujew

Ok, so it only took 3 months of studying to learn enough to come back to this ... I just want to make sure I understand the reccomendation.

Recap:

• Need grammar to allow for mandatory mutliline comments between two tokens which are both keywords (e.g. BlockA, TokenB)
• Positive lookbehind is not supported by chevrotain, so we need to use terminal rules
• Note: this works as expected

Simple Example

BigBlock
  BlockA
    comment text line 1
    comment text line 2
    ...
    comment text line n-1

    TokenB someName
    ...
  EndBlockA

  BlockB
    comment text line 1
    comment text line 2
    ...
    comment text line n-1

    TokenC anotherName
    ...
  EndBlockB
EndBigBlock

Recommended Solution:

Simple Grammar

BigBlock:
    'BigBlock'
    innerBlocks+=InnerBlock*
    'EndBigBlock'
;

InnerBlock:
    BlockA | BlockB
;

BlockA:
    header=BlockHeader
    TokenB name=ID
    'EndBlockA'
;

BlockB:
    header=BlockHeader
    TokenC name=ID
    'EndBlockB'
;

hidden terminal WS: /\s+/;
terminal BlockHeader: /(BlockA|BlockB)([\s\S]*?)(?=(TokenB|TokenC))/;
terminal ID: /[_a-zA-Z][\w_]*/;
terminal INT returns number: /[0-9]+/;
terminal STRING: /"[^"]*"|'[^']*'/;

The only impact is that it breaks the default highlighting aesthetics. As such, I need to implement a language-specific SemanticTokenProvider similar to what the Langium base project uses (here).

To do that, I just need to extend the AbstractSemanticTokenProvider for my language correct?

Secondarily, now that my fledgling proof-of-concept is starting to get attention, there has been some interest in non-VSCode clients (e.g. Vim, Emacs). Am I correct in assuming that any editor which implements a LSP client (generally) would be governed by the same API that VScode uses?

Thanks again for all of the help. This is turning out quite well (I think) - haven't hit any real massive obstructions yet that aren't already known.

[msujew]

To do that, I just need to extend the AbstractSemanticTokenProvider for my language correct?

Yep, you would use it the same way we use it for our own grammar language.

Am I correct in assuming that any editor which implements a LSP client (generally) would be governed by the same API that VScode uses?

Right. It seems like at least Emacs has support for this. Vim probably has too, but I couldn't find any info on that. Note that for both Emacs and Vim, the syntax based highlighting likely won't be available through textMate files, so you'll probably need something different for keyword highlighting. It's actually possible to perform keyword highlighting through the semantic token provider as well, but it's a bit of work.

[snarkipus]

Ok - so coming back to this (finally). I happened to notice that while this does work, it assigns the entire parsed section as the name of the node.

This somewhat breaks a lot of other things in the process though. For instance, I'm trying to wrap my head around how the outline/breadcrumbs would work with the symbol and name providers. Any thoughts?

Is it just a matter of hard coding the 'SDB' name into the language symbol provider? Does that seem like a reasonable solution?

Working Terminal

terminal SDBBlockHeader: /(SDB)([\s\S]*?)(?=(RANDOM-NUMBER-SEED:))/;

[msujew]

This somewhat breaks a lot of other things in the process though. For instance, I'm trying to wrap my head around how the outline/breadcrumbs would work with the symbol and name providers. Any thoughts?

I believe you can override the DefaultValueConverter#runConverter method to simply remove everything after SDB when the parser parses the SDBBlockHeader terminal:

https://github.com/langium/langium/blob/9f587815f9d14f433d22831ac11d3b9f11696d9f/packages/langium/src/parser/value-converter.ts#L42-L56

[snarkipus]

Ah - that makes perfect sense. For instance, I could implement a convertBlockHeader(input) match on the case SDBBLOCKHEADER, which returns a string slice of input(0..2) (or even hardcode it, I suppose).

For now, I don't care about preserving the comment portion of the token, but out of curiosity, how would you parse it into separate nodes in the AST? I'm mostly asking since at some point I'd love to implement the document format feature.

[msujew]

Hm, I don't think that the property can easily be set on the AST. However, you can do something similar to what we already do for the MultilineCommentHoverProvider. We dig through the CST instead to look for the nearest multiline comment (which is only a part of the CST, not the AST):

https://github.com/langium/langium/blob/9f587815f9d14f433d22831ac11d3b9f11696d9f/packages/langium/src/lsp/hover-provider.ts#L63

Similar to the comment use case, your CST preserves the whole text of the SDBBLOCKHEADER, while the AST only retains a converted value. You can then always extract the comment part from the CST node that belongs to the property.

[snarkipus]

That's a pretty good solution to put in my back pocket for sure. Thanks as usual!

I still think it would be easier if Chevrotain just supported positive lookbehind ... ;-)

For anyone else playing along ... Blocks Example Repo

Custom Converter

export class BlocksValueConverter extends DefaultValueConverter {

  override convert(input: string, cstNode: CstNode): ValueType {
    let feature: AbstractElement | undefined = cstNode.feature;
    if (isCrossReference(feature)) {
        feature = getCrossReferenceTerminal(feature);
    }
    if (isRuleCall(feature)) {
        const rule = feature.rule.ref;
        if (!rule) {
            throw new Error('This cst node was not parsed by a rule.');
        }
        if (rule.name.toUpperCase() === 'BLOCKHEADERA' || rule.name.toUpperCase() === 'BLOCKHEADERB') {
            return convertBlockHeader(input);
        } else {
          return super.runConverter(rule, input, cstNode);
        }
    }
    return input;
  }
}

export function convertBlockHeader(input: string): string {
  return input.slice(0, 'BlockA'.length);
}

Bonus: Symbol Provider Helper (since I didn't notice the expectSymbols() helper)

export interface symbolProviderResult<T extends AstNode = AstNode> {
  symbols?: DocumentSymbol[];
  document: LangiumDocument<T>;
}

export function symbolProviderHelper<T extends AstNode = AstNode>(services: LangiumServices): (input: string) => Promise<symbolProviderResult> {
  const parse = parseHelper<T>(services);
  return async (input) => {
      const document = await parse(input);
      return { document, symbols: await services.lsp.DocumentSymbolProvider?.getSymbols(document, textDocumentParams(document)) };
  };
}

[snarkipus]

Hey @msujew ,

Does #917 improve (or is it applicable) for this use case? Maybe I'm not fully understanding fully the change since the following terminal rule works today and uses positive lookahead:

terminal SDBBlockHeader: /(SDB)([\s\S]*?)(?=(RANDOM-NUMBER-SEED:))/;

[msujew]

Hey @snarkipus, the PR is supposed to bring the lookahead power of regex to the non-regex kind of terminal definition. For example, your's can be made a bit more readable by extracting it into a few terminal fragments (assuming #917 gets merged)

terminal SDBBlockHeader: 'SDB' WhiteSpace (?='RANDOM-NUMBER-SEED:');
terminal fragment WhiteSpace: [\s\S]*?