search

dlang-community / Pegged

A Parsing Expression Grammar (PEG) module, using the D programming language.
534 stars 66 forks source link

Grammer Tester #141

Open Moondee opened 10 years ago

Moondee commented 10 years ago

Is it possible that given a PEG grammar, generate a random string that satisfies the given grammar and then test this string?

PhilippeSigaud commented 10 years ago

Pegged cannot produce the language a grammar defines, if that is what you mean.

Moondee commented 10 years ago

What I meant was suppose we have a grammar for a calculator. Can Pegged generate valid sequences for the calculator grammar? like randomly generate ' 1+2'...

PhilippeSigaud commented 10 years ago

What I meant was suppose we have a grammar for a calculator. Can Pegged generate valid sequences for the calculator grammar? like randomly generate ' 1+2'...

No, it cannot.

Hmm, I don't know of a parser generator doing that, even though grammars are supposed to be generative in nature (that is, used to produce sentences, not to parse them).

You know, even for small languages, I don't think that would be that interesting: most of the generated strings would be useless ("1", "2", "11", ..., not even reaching a '+' part), unless it iterates the grammar in a breadth-first way. And that's not even taking white spaces into account. 'Most' of the sentences thus generated would be far too simple to be of any use, in case you were thinking about generating programs from a programming language grammar.

Moondee commented 10 years ago

Thanks. I agree. Surprisingly I see several string generators for CFG like Yagg , DGL,..., though have't seen any for PEG based language.

PhilippeSigaud commented 10 years ago

Thanks. I agree. Surprisingly I see several string generators for CFG like Yagg , DGL,..., though have't seen any for PEG based language.

Do you know what people use them for? To verify the grammar they wrote indeed generates the right language?