Update Grammar in Architecture

[ilslv]

I'm implementing Cucumber Expressions parser in Rust: WIP. And grammar described in the ARCHITECTURE.md really bothers me for couple of reasons.

1. Lookbehind and lookahead in alternation definition
   EBNF describes context-free grammars and (correct me if I'm wrong) shouldn't have lookaheads and lookbehinds. This also means that described grammar may have non-linear complexity.
2. Provided grammar describes superset of Cucumber Expressions and I don't really see reasons to do it.

So implementing Cucumber Expression parser according to the docs leads to unnecessary performance overhead for no obvious reasons.

Can't we just provide exact grammar for Cucumber Expressions without Note: section?

---

If I didn't miss anything provided grammar should be exact Cucumber Expressions

cucumber-expression     = (alternation
                           | optional
                           | parameter
                           | text)*
text                    = (- text-to-escape) | ('\', text-to-escape)
text-to-escape          = '(' | '{' | '/' | '\' 

alternation             = single-alternation, ('/', single_alternation)+
single-alternation      = ((text-in-alternative+, optional*) 
                            | (optional+, text-in-alternative+))+
text-in-alternative     = (- alternative-to-escape) | ('\', alternative-to-escape)
alternative-to-escape   = ' ' | '(' | '{' | '/' | '\'

optional                = '(', text-in-optional+, ')'
text-in-optional        = (- optional-to-escape) | ('\', optional-to-escape)
optional-to-escape      = '(' | ')' | '{' | '/' | '\'

parameter               = '{', name*, '}'
name                    = (- name_to_escape) | ('\', name-to-escape)
name-to-escape          = '{' | '}' | '(' | '/' | '\'

[aslakhellesoy]

How exciting to have a Rust port! ❤️

This looks good to me. Any feedback @mpkorstanje?

@ilslv would you be interested in donating your parser implementation to this repo (under a rust directory)? That way we can more easily share the same test suite, align the release cycle and keep everything in one place. We'd also set up a GitHub Action to release it as a crate whenever we make a release.

[ilslv]

@aslakhellesoy my implementation may be incompatible with test suit in this repository. As I could see tests under parser directory parse nested optionals just find and error only on expansion to the regex in matching directory. My implementation is 1-step that matches only correct Cucumber Expressions.

[aslakhellesoy]

Do you think it would be possible to make your implementation compatible with the official test suite? If not, do you think there is something we could change in the official implementation's test suite (or implementation) in order to make it easier for your implementation to be compatible?

[mpkorstanje]

@aslakhellesoy you added the EBNF phrase at 0875a40#diff-8f6366fd8e7a5fa30f7f05879999195b7cf5fa1e3d157822eb37f0e91d226cfdR7. Note that the code highlighting should still use EBNF because that makes the pseudo-grammar somewhat readable but the grammar itself is not EBNF.

[ilslv]

@aslakhellesoy

it would be possible to make your implementation compatible with the official test suite

Yes, but it would introduce some performance overhead, which we would like to avoid.

do you think there is something we could change in the official implementation's test suite (or implementation) in order to make it easier for your implementation to be compatible

It would be possible, but I don't think it costs the effort. As I mentioned only subset of the official test suite is incompatible. The most important tests for final matching and regex transformation are ok. I even think that only this test case would be incompatible. This happens because other implementations are using current ARCHITECTURE.md approach of generating AST which is wider than Cucumber Expression and error only later. My implementation generates only right Cucumber Expression from the start.
Mainly because of those difference I would hold on merging Rust implementation here. But you can still reference it using submodules or just mention it in the README.md.

[mpkorstanje]

@ilslv the grammar as written is context-sensitive and not in EBNF form (EBNF also can't express context sensitive grammars).

Provided grammar describes superset of Cucumber Expressions and I don't really see reasons to do it.

Users of Cucumbers are not typically familiar with the concepts involved in parsers or grammars. As such the typical error messages from a parser are incomprehensible. By accepting a super set of all cucumber expressions we can more clearly provide error messages for typical mistakes such as using optional parameter types, empty optionals, etc, etc by pointing the entire AST node that is in the wrong place rather then a single character.

text                    = (- text-to-escape) | ('\', text-to-escape)

This puts each character into a single AST node. This isn't great for languages with garbage collection and makes debugging much harder.

alternation             = single-alternation, ('/', single_alternation)+

It is now longer obvious that alternation is bounded by whitespace, parameter types or start/end of expression which means that we are losing some of the intention.

parameter               = '{', name*, '}'
name                    = (- name_to_escape) | ('\', name-to-escape)
name-to-escape          = '{' | '}' | '(' | '/' | '\'

The *-to-escape is pretty neat. This is definitively worth including.

Now I've only given this a cursory review but other then the issues mentioned above I don't see any immediate technical problem with the provided EBNF. Might be worth updating the documentation somewhat.

[ilslv]

@mpkorstanje

typical error messages from a parser are incomprehensible

Yes, but only if you are using some sort of parser-generator. Rust implementation has exactly the same errors, which can point at troublesome characters or range of characters. All this while preserving minimal overhead (1 dynamic allocation on every nested expression and even it can be avoided, I just don't think it costs the effort for now).

This puts each character into a single AST node. This isn't great for languages with garbage collection and makes debugging much harder.

There is no need to translate provided grammar 1-to-1. I propose adding it only to provide some formal specification for the Cucumber Expressions language.

My proposal is following: let's add formal EBNF specification for the language while preserving the old one and add documentation that it only exists only for implementation suggestion. This would allow Rust implementation (or any other one) to strictly follow it, because for now there is no way for me to reason that Rust implementation is correct, as there is no formal specification for Cucumber Expressions.
If you are on board with that idea, I will happily prepare PR documenting all this.

[mpkorstanje]

No. If we only have a formal specification without a closely matching implementation and test set in this repository we are only going to see uncontrolled drift.

Though I don't believe a formal specification has to be in EBNF. As long as the context sensitive form can be procedurally be written to EBNF it can serve as a formal specification for your purposes.

[ilslv]

@mpkorstanje

No. If we only have a formal specification without a closely matching implementation and test set in this repository we are only going to see uncontrolled drift.

It looks like there is a misunderstanding, as I never proposed to remove anything, only add a formal specification. Let me sum up everything discussed in this issue.

What are the proposed changes?

I would like to see formal specification with some context-free grammar. Original issue shows the EBNF example.

It is now longer obvious that alternation is bounded by whitespace, parameter types or start/end of expression which means that we are losing some of the intention.

It's not obvious, but alternation is still bounded by whitespace, because of following rules

text-in-alternative     = (- alternative-to-escape) | ('\', alternative-to-escape)
alternative-to-escape   = ' ' | '(' | '{' | '/' | '\'

You have to escape whitespace for it to match.

I agree that it's hard to spot. That's why I'm proposing only to add formal specification, leaving existing one as one of implementation possibilities.

Why do we need this change?

For now there as there is no formal specification, only some non-existing grammar, I can't reason why Rust implementation is correct.

Why not to use existing guidance from ARCHITECTURE.md?

1. ARCHITECTURE.md doesn't give full picture.
   There is no way to know how escaping works in different AST elements only from it. I had to dig throughout all the test cases to be sure, that I didn't miss anything. We should provide formal specification to reason about implementation correctness.
2. ARCHITECTURE.md forces to use suboptimal implementation.
   It encourages to generate middleware AST that is wider, than Cucumber Expression and that is using context-sensitive grammar with lookbehinds and lookaheads. As shown by the Rust implementation there is a way to avoid both of those overheads by generating valid Cucumber Expression from the start, basing on context-free grammar. All that while still preserving friendly error messages.

[aslakhellesoy]

@ilslv could you please send a pull request with your proposed changes?

[ilslv]

@aslakhellesoy #44

[mpkorstanje]

There is no misunderstanding.

From the discussion in cucumber-rs/cucumber-expressions#1 I see that you have asked to implement the parser in a way that closely matches the specification. You are now looking to update the specification to match your implementation.

However the proposed grammar is does not accept the superset of all Cucumber valid expressions. As such we do not have a reference implementation or test set that accurately describes it. Additionally if the EBNF can not be derived from the context-sensitive grammar it can not be said to be correct. If it can be derived from the context sensitive grammar it need not be explicitly included.

Currently the EBNF can't derived from the context sensitive grammar because it is not well specified. So I'm specifically requesting a fix to the context-sensitive grammar rather then an addition of an otherwise untested, unverified (in this repo) piece of specification.

[ilslv]

@mpkorstanje

update the specification to match your implementation

No, I'm trying to introduce formal specification as there is none yet.

does not accept the superset of all Cucumber valid expressions

Yes, thats the point to describe Cucumber Expressions through it's own formal specification, rather then relying on superset specification in non-existent grammar with number of notes on post-validation.

EBNF can not be derived from the context-sensitive

Yes, because Cucumber Expressions specification doesn't need to be context-sensitive.

it can not be said to be correct

There is no notion of correctness right now, as no formal specification exists.

fix to the context-sensitive grammar

My grammar is context-free. Can you please provide concrete examples, where my attempt at formalisation fails?

[tyranron]

@ilslv @mpkorstanje it seems to me that the discussion becomes a little bit overheated. Let's sum it up a little with facts and coclusions, to push it into a constructive direction.

The current grammar described in ARCHITECTURE.md:

1. Somewhat implementation-driven as describes some superset of Cucumber Expressions followed by post-validation rules for the sake of better spanning info and error messages in the current parser implementations.
2. Not context-free, while doesn't have to.
3. Covered with a tests suite to ensure the current implementations match it.

This imposes problems for alternative implementations:

• either to follow closely the original implementation (which is too restrictive regarding implementation approaches and performance reasoning);
• or to implement something new only pretending to call itself Cucumber Expressions, but in fact, having no ability to reason whether it's the right implementation or not (which is bad for future proofing and compatibility).

We'd really like to have implementation freedom, while preserve the ability to formally check correctness. For this purpose @ilslv proposed to add a "formal spec" grammar, which is context-free and implementation-free, but describes the actual Cucumber Expressions precise enough, so any implementation can refer to its as the source of truth.

But @mpkorstanje is against having a formal spec without an ability to verify whether implementations do follow it, as it will introduce an obvious drift between the actual spec and its implementations.

Please, correct me if I'm wrong.

So, from my point of view:
It worths, of course, to provide a precise "formal spec" grammar proposed by @ilslv. But we should also provide a generic set of tests for it which would be suitable for any implementation.
With this, we can satisfy @mpkorstanje point about "actual correctness", while also provide third-party alternative implementations (like ours) with an obvious way to verify its correctness. Having this tests suite will allow to strip out major part of existing tests, leaving only the implementation-specific ones (like spanning/errors handling, or language-dependent stuff).

Is there any arguments against this way? Or is there any issue that I do miss?