Grammar tests

[brson]

It would be nice to have confidence about what sort of grammar Rust has. One possible way we could do that:

• Extract EBNF from the manual
• Use a script to convert it to whatever format antlr wants
• Run the entire test suite through the both the rustc parser and antlr parser. Where one fails so should the other.

[nikomatsakis]

How many negative parsing tests do we have? I'm guessing not many... but we
could make some.

[brson]

I also would assume that coverage of failure cases in the parser is not great, so we could kill two birds with one stone.

[brson]

Speaking of coverage, today I realized that #690 is unblocked. It might be possible for us to measure test coverage.

[graydon]

Antlr is a possibility but I think it is willing to handle a lot more grammar ambiguity, and it tends to blur lexing and parsing rules. I want us to remain in the classical regular-lexing + LL(1)-parsing space.

I picked the EBNF in the manual for compatibility with llnextgen, http://os.ghalkes.nl/LLnextgen/ ; I got part way into wiring up the rules for extracting and testing the grammar but didn't finish in time for 0.1, haven't come back to it yet.

Lexical rules I figured we could feed to quex http://quex.sourceforge.net/ but other possibilities exist. It just seems like the current leader in the space we're interested in.

[brson]

We can use the fuzzer to find arbitrary numbers of random samples to feed to both parsers.

[nikomatsakis]

good idea...

[graydon]

nominating for well-defined

[emberian]

Still relevant

[fhahn]

I had a look at this issue and started working on a parser using Flex and LLnextgen (https://github.com/fhahn/rust-grammer). Right now, the parser supports only a tiny tiny bit of the Rust grammer, but I wanted to make sure my approach is valid, before continuing.

One main difference to the grammer specification in the documentation is that flex uses regular expressions for token definitions, not ebnf, so I started converting the ebnf from section 3 "Lexical structure" to regular expressions for flex.

[huonw]

Note that grammar in the manual is highly likely to be incorrect (which is presumably exactly what this issue is aiming to address).

[Kimundi]

Note that someone already completed an grammar months ago, it just never got used for anything yet. No idea where to find it though.

[emberian]

https://github.com/jbclements/rust-antlr

To the best of his knowledge, it was correct at the time.

On Sun, Sep 15, 2013 at 9:20 AM, Marvin Löbel notifications@github.life-white.ukwrote:

Note that someone already completed an grammar months ago, it just never
got used for anything yet. No idea where to find it though.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/2234#issuecomment-24471342
.

[fhahn]

I found a extract_grammer.py script in src/etc, which extracts the grammer from rust.md, but the resulting grammer does not work with LLnextgen at the moment. There is no separate lexing step. My approach is to use flex for lexical analysis (for everything in Section 3 of the manual) and use LLnextgen for the parsing.

So far, I stumbled over one part of the grammer where I think the productions in the rust.md are not LL(1).
I think there is a FIRST/FOLLOW conflict in block_comment . block_comment_body in block_comment is can be epsilon and is followed by '' and an alternative in block_comment_body starts with '', so it isn't possible to decide which production to take with look ahead of 1

block_comment : "/*" block_comment_body * '*' + '/' ;
block_comment_body : non_star * | '*' + non_slash_or_star ;

But I think ignoring comments should be done in the lexer, so this wouldn't be a problem for the Rust grammer being LL(1).

[Kimundi]

@fhahn Again, the grammar fragments in the manual are useless, what should actually be done is

• Take @jbclements existing grammar, which has already been proven correct and LL(2) at the time, and verify it against the source.
• Optionally transform it in something simpler, like EBNF.
• Update the manual with the correct grammar.

But thanks for showing interest for this work. :)

[fhahn]

What's the preferred parser generator?
Should I use antlr and build on @jbclements project or LLnextgen (combined with flex)? LLnextgen would probably be easier to integrate into the main rust repository, because it does not rely on Java (and I'm more familiar with the flex + (yacc/LLnextgen) workflow)