ANTLR: Deciding on how far to go with this

[RexJaeschke]

On 2020-10-03, I circulated the following paper: ANTLR and the C# Spec.docx. In that, I discussed using the ANTLR grammar notation and the non-trivial amount of work I thought it would take to get the grammar to validate using the ANTLR toolkit.

Neal has reviewed that paper and his feedback follows in a comment below, with a proposal on how we might go forward. Once we discuss (and probably agree with) his suggestion, I'll update this comment by adding the remaining questions and to keep track of our decisions on those questions .

Here are the ANTLR-related questions and their status:

Proposal #	Status	Description
1	Yes it should	Decide whether our grammar should be complete enough to validate (3 Rex's paper). Note that validation here means "get through the ANTLR tool without error," which doesn't necessarily mean that any parser generated will be complete/correct. This is especially true for semantic predicates.
2	Resolved, PRs #208, #209	Change case of lexer rule names (5.1 Rex's paper)
3	Resolved, PR #261	Expanding lexer rule alternatives of the form <...> (3 Rex's paper)
4	Resolved, PR #225	Limited use of token names (5.3 Rex's paper)
5	In-progress	Resolve Mutual Left-Recursion issue (15 Rex's paper)
6	Resolved, PR #233	How to handle the unsafe extensions
7	Resolved	Marking lexer helper rules with fragment
8	Resolved	Ultimately, revise 7.2, "Grammars" in lexical-structure.md to say what we do/don't do w.r.t full grammar validation

When you add a comment to this issue, please limit it to a single Proposal # and say which Proposal # that is.

Any decisions we make that require changes to the grammar notation will not only have to be made to the v5 grammar we're starting with in v6, but also possibly to the v6 (and v7) PRs in waiting.

[RexJaeschke]

[From Neal Gafter in private mail to Rex on 2020-11-18, after having reviewed Rex's paper.]

We should not attempt to produce a grammar that will validate using the ANTLR toolkit. There are some parts of the syntax that cannot be neatly explained in the grammar, and would result in a grammar that definitely does not validate (i.e. it is ambiguous). https://github.com/ECMA-TC49-TG2/conversion-to-markdown/blob/v6-draft/lexical-structure.md#725-grammar-ambiguities is a good example. Interpolated strings are another (separating the syntactic and lexical parts might make things less clear). See also https://github.com/ECMA-TC49-TG2/conversion-to-markdown/blob/v6-draft/expressions.md#1288-cast-expressions. I think we should use the formalism of ANTLR to document our syntax with as much rigor as we have historically used.

If we wanted to do this [validate, that is], we probably would use parser modes for async (different set of keywords inside an async method), LINQ (different set of keywords inside the query), and possibly interpolated strings.

As for unsafe, it can be written

class_modifier
    : 'unsafe'
    ;

because (if I'm not mistaken) you are allowed to have multiple rules for the same nonterminal, and they are merged. But the surrounding test should make it clear that this is in addition to other alternatives specified elsewhere.

We specify associativity and precedence by spelling out the structure of the expression grammar explicitly. We don't need to specify precedence or associativity using ANTLR features.

[Rex drafted the following text.]

Proposal 1: We should use ANTLR notation with common conventions. However, we should not spend any effort on getting the grammar to validate with the ANTLR toolkit.

Assuming we go this route, we'll need to add some appropriate text to 7.2, Grammars.

[RexJaeschke]

If we buy into Proposal 1 (#37 (comment)), we avoid the following (the numbers in parens refer to sections in Rex's paper):

• Having to convert all descriptive alternatives of the form '<...>' (3), such as the following:

Not_Slash_Or_Asterisk
    : '<Any Unicode character except / or *>'
    ;

Letter_Character
    : '<A Unicode Character of classes Lu, Ll, Lt, Lm, Lo, or Nl>'
    | '<A Unicode_Escape_Sequence representing a Char of classes Lu, Ll, …>'
    ;

• We can ignore the fragment rule name prefix (6)
• We can ignore separating the lexer and parser grammar into different files (9)
• We can ignore lexical modes (12)
• We don't need to handle ambiguities in the grammar notation itself (13)
• We can probably leave the handling of unsafe extensions as they are (14)
• We can ignore ANTLR's limits on recursive rules (15)
• We can ignore using explicit operator-associativity notation (17)

[RexJaeschke]

Proposal 2: Change the spelling of lexer rule names to use a leading uppercase letter on each word and an underscore as a word separator, as in Not_Slash_Or_Asterisk and Letter_Character.

The ANTLR convention is that a lexer rule name begins with an uppercase letter, and may be followed by uppercase and/or lowercase letters, digits, and underscores.

We do not currently begin lexer rule names with an uppercase letter, and we should. However, I think that using all-caps is distracting. And as we're used to having a dash separator in v5 and prior (and now underscore), it seems useful to continue having separators. The remaining question then is how to use case. Whatever the decisions made, it's a matter of running a set of mechanical conversions on the existing spec grammar fragments and rule names in the narrative to make these changes.

If we adopt this change, it will involve a lot of edits to the Lexical structure clause and a few in other clauses that refer to lexer rules. We can't simply use a find-and-replace-text tool as we have some lexer rule names that are commonly used English words in the spec (such as whitespace, comment, identifier, and keyword). So, we'll want to convert all lexer rule names inside a grammar block and between italic fences, as in rule_name, but not elsewhere.

Recommendation: We change to starting lexer rule names with an uppercase letter. As to whether we up-case the first letter in subsequent words is debatable. Here are the obvious styles:
• Integer_literal // first word leading cap
• Integer_Literal // all words leading cap [Rex's first choice]
• IntegerLiteral // all words leading cap, no separators

Before locking in a decision, we should look at parser rule names, and be consistent or deliberately different. Perhaps the simplest rule to follow here is “all lowercase except the initial letter of each word.” That is the style I use throughout this paper.

Resolved: During the telcon on 2021-01-13, we chose Recommendation 2, Integer_Literal, with all words having a leading uppercase letter, and words separated by underscore.

[Nigel-Ecma]

I would prefer if the ANTLR grammar was written so it would validate, I would have thought this was a key reason to switch to ANTLR notation. I haven’t looked into whether an ANTLR grammar that validates is possible, hence the “prefer” rather than “should”. That said, if the grammar does not/cannot validate than I think the Standard must state this. Expecting an ANTLR grammar to validate is, at minimum, reasonable given the purpose of ANTLR; so the Standard should make it clear that ANTLR is used as a notation only – and then leave it at that as it does beg the question why the Standard uses a notation that cannot describe the language's syntax, and we probably shouldn’t raise that in the Standard text! Note that if the limitations of ANTLR are restricted to such things as specifying “any character in Unicode class X” then that looks like a reasonable extension to ANTLR that could be defined (think of the various extended BNFs that exist, I’ve defined one myself when the need arose – though I’ve long since forgotten what that need was just that I had to write a document on the grammar notation! ;-)), but the Standard may not want to go there.

…

On 21/11/2020, at 10:36 am, Rex Jaeschke ***@***.***> wrote: [From Neal Gafter in private mail to Rex on 2020-11-18, after having reviewed Rex's paper.] We should not attempt to produce a grammar that will validate using the ANTLR toolkit. There are some parts of the syntax that cannot be neatly explained in the grammar, and would result in a grammar that definitely does not validate (i.e. it is ambiguous). https://github.com/ECMA-TC49-TG2/conversion-to-markdown/blob/v6-draft/lexical-structure.md#725-grammar-ambiguities <https://github.com/ECMA-TC49-TG2/conversion-to-markdown/blob/v6-draft/lexical-structure.md#725-grammar-ambiguities> is a good example. Interpolated strings are another (separating the syntactic and lexical parts might make things less clear). See also https://github.com/ECMA-TC49-TG2/conversion-to-markdown/blob/v6-draft/expressions.md#1288-cast-expressions <https://github.com/ECMA-TC49-TG2/conversion-to-markdown/blob/v6-draft/expressions.md#1288-cast-expressions>. I think we should use the formalism of ANTLR to document our syntax with as much rigor as we have historically used. If we wanted to do this [validate, that is], we probably would use parser modes for async (different set of keywords inside an async method), LINQ (different set of keywords inside the query), and possibly interpolated strings. As for unsafe, it can be written class_modifier : 'unsafe' ; because (if I'm not mistaken) you are allowed to have multiple rules for the same nonterminal, and they are merged. But the surrounding test should make it clear that this is in addition to other alternatives specified elsewhere. We specify associativity and precedence by spelling out the structure of the expression grammar explicitly. We don't need to specify precedence or associativity using ANTLR features. [Rex drafted the following text.] Proposal 1: We should use ANTLR notation with common conventions. However, we should not spend any effort on getting the grammar to validate with the ANTLR toolkit. Assuming we go this route, we'll need to add some appropriate text to 7.2, Grammars. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#37 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABSYVW2O2VXDE3TLU62P2BDSQ3ONTANCNFSM4T5ICDNA>.

[Nigel-Ecma]

After the previous comment I glanced quickly at the ANTLR docs thinking it surely must handle Unicode character classes and it does, see https://github.com/antlr/antlr4/blob/master/doc/lexer-rules.md.

[Nigel-Ecma]

I've taken a brief look at ANTLR and I beleive the rules Rex quotes above can be written:

Not_Slash_Or_Asterisk
    : ~[*/] // Any Unicode character except / or *
    ;

Letter_Character
    : [\p{Lu}\p{Ll}\p{Lt}\p{Lm}\p{Lo}\p{Nl}] // A Unicode Character of classes Lu, Ll, Lt, Lm, Lo, or Nl
    | Unicode_Escape_Sequence { IsLetterCharacter() }? // as previous but using an escape sequence
    ;

The last rule includes a semantic predicate, { IsLetterCharacter() }? this a way context-sensitive or other semantic checks can be included in the syntactical grammar. If the function IsLetterCharacter() returns false the alternative is "unviable". Semantic predicates can be included in both parser and lexer rules. The predicates themselves can be defined in the same file as the grammar; are written in Java, C++, Javascript or any other language ANTLR supports; and have access to the source being parsed/lexed.

The above doesn't tell us that all the content-sensitive/semantic needs of the C# grammar can be supported, but I think we should find out – I have a certain unease in publishing a language Standard with a known invalid/incomplete grammar.

[jskeet]

I'm definitely fine with making it clear that the grammar doesn't validate. If there's no way we can make it validate, for reasons expressed before (e.g. interpolated string literals and the grammar ambiguities in 7.2.5) I would be interested to know how feasible it would be to make it "nearly validate" - is there anything we can do to ensure that we don't create invalid rules by mistake? If ANTLR can list the ways in which it's invalid, and if that's a small-but-sensible list, we could perform validation within a GitHub action and compare the result against the expected set of failures.

[jskeet]

Resolutions from Dec 16, 2020 meeting:

• We should follow not just the syntax but conventions of ANTLR, and that can be a medium-term goal
• We will not immediately try to make the grammar completely valid, but that's something we might do in the future (and may well be a good task for a contributor - we should reach out to Terence Parr once the first bullet is done)
• We will add a GitHub Action to extract and validate the grammar, with a known set of existing issues

[RexJaeschke]

During the Dec 2020 teleconference, I took an action item to identify the ANTLR convention changes we could/should use. As a result, I have updated the first entry in this issue (#37 (comment)). My recommendations are shown with TBD in the table's Status column.