parser-state aware lexer

[ericvergnaud]

@kaby76 can you elaborate ?

[kaby76]

I recommend reading https://www-users.cse.umn.edu/~evw/pubs/vanwyk07gpce/vanwyk07gpce.pdf. While this paper discusses the problem of integrating two languages together, the problem of parser-state aware lexers occur in some languages we already try to parse (e.g., Python3). For a list of candidates that fit this description, look for grammars that have Antlr lexer modes.

This paper was selected from tree-sitter web page https://tree-sitter.github.io/tree-sitter/#underlying-research. Presumably, tree-sitter implements parser-state aware lexers.

I would like to see an option added to allow the lexing strategy to be switched to parser-aware lexing. We can keep the default to the standard Antlr algorithm: (1) Antlr picks the rule with the maximum-matching input; (2) If two or more rules match, Antlr picks the first rule.

[ericvergnaud]

Very interesting paper, thanks for that.
Am I incorrect thinking that this topic is the same as contextual tokens ?

[ericvergnaud]

I was referring to the general contextual tokens problem, not the above token comparison approach (which I believe conveniently addresses a majority of the use cases)

[KvanTTT]

@kaby76 could you give an minimal example on your topic and propose a prototype of syntax for that within ANTLR scope? Is it even possible?

[kaby76]

The paper describes the use-case pretty well. This can be applied to Antlr in two situations.

First, any grammar in grammars-v4 that use lexer modes is possibly a use-case for parser-state aware lexers, because parser-state aware lexers can replace the current syntax for lexer modes.

An example of this would be the antlr4 grammar, where there are three lexer modes: Argument, TargetLanguageAction, and LexerCharSet.

In mode Argument, there are seven lexer rules. No other lexer rules can match. Note that the rules in this mode all return ARGUMENT_CONTENT, and that parser rule argActionBlock only uses ARGUMENT_CONTENT. BEGIN_ARGUMENT pushes the lexer into the Argument mode, but this only happens under parser rule argActionBlock. Quite a bit of support code is involved to perform open and closing bracket matching because action blocks can nest brackets. But, this could be rewritten as a single token that spans the entire action block because there is an equivalent context-free rules for action blocks. The mode is popped with END_ARGUMENT. But notice this is all within the context of parsing argActionBlock.

Another example is csharp and interpolated strings. INTERPOLATION_STRING mode begins with the recognition of INTERPOLATED_REGULAR_STRING_START or INTERPOLATED_VERBATIUM_STRING_START, which is only available from parser rules interpolated_regular_string and interpolated_verbatium_string, respectively. Also, note that interpolated_regular_string_part can only derive those symbols in the lexer mode. The explicit declaration for mode INTERPOLATION_STRING can be completely eliminated by declaring an implicit mode and allowing the lexer top-level case to only allow those lexer rules that can be derived from interpolated_regular_string (i.e., the transitive closure of the symbol used).

The second use-case is combining grammars. You really don't want to pool lexer rules together because the lexer rules for each grammar don'tknow anything about the other grammars. Parser-state lexing allows each lexer to coexist.

I would propose parser-state lexers to be an option, options { parserStateAware=true; }. To implement this, the tool would need to perform a "reachability analysis" of the lexer symbols that a parser rule can derive, which is easy to do. The generated lexer would recognize only those rules in the "reach set" for the parser rule being parsed, which should be easy to implement because we already have lexer modes. The lexer mode can be named after the parser rule name.

Parser-state aware lexers just make life so much more simple. It can replace the syntax for lexer modes. And it allows for easy grammar composition.

[KvanTTT]

It seems I undertsood you. I'll try to experiment with that in my yantlr fork. I decided to write it from scratch with new teorethical basis (for instance, I'll try to get rid of ALL algorithm and runtime caching at all, but I'll try keep ANTLR grammars back compatibility as much as possible) and I started it with writing ANTLR lexer/parser by hand to figure out what I need from generated parser (as I wrote in #24).

[KvanTTT]

I'm also thinking about multitokens: maybe it makes sense to have subtokens on main token on every pushMode call. But also maybe it's not a very good idea because it turns linear tokens list into tree-structure and it makes things more complex.