search

ptal / oak

A typed parser generator embedded in Rust code for Parsing Expression Grammars
Apache License 2.0
142 stars 14 forks source link

Testing Grammar #35

Closed Moondee closed 10 years ago

Moondee commented 10 years ago

Hello, This is very cool, though I am not sure if I get it correctly. Does it mean that we the help of rust.peg, one could generate valid input sequences for a give grammar? For example, given a grammar for a calculator, then it can randomly generate input strings like '2+3'...?

ptal commented 10 years ago

Hello and thanks for your interest :-) Sadly, the parser is not yet documented (nor finished) so I'm not surprised you didn't understand its goal.

Rust.peg is a parser, not a generator. However, this is true that the way we describe parsing grammar is similar to the way we could describe generator, and thus, rust.peg could be extended, some days, to provide a generator module. One of the first problem is to handle infinite grammar, the inputs of a PEG are not limited in size, consider the simple rule:

digits = [0-9]*

The generator could possibly generate an infinite number of word "0", "00", "000". So we need to generate outputs on the size of the input, thus "0" then "1", ... But yet, if you consider a calculator, "1" to "99" will be generated before "1+1" so we need an order between the different rules. All this is far from being trivial :-)

Note that it exists simpler kind of generator, taking the AST and outputting the corresponding string (dual operation of a parser). For example the C++ library Boost.Spirit.Karma does that.

ptal commented 10 years ago

Note that I'm willing to provide, some days, a library to easily test a grammar written with Rust.peg (and it's already partially implemented in src/test/testpeg.rs).

Moondee commented 10 years ago

I must say Rust.peg seems very progressing! Back to my earlier question: I agree! Testing a grammar with random input generation is not a trivial task. 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.

How ever when I look up on the web I can find some modules to generate valid CFG string, though I couldnt find any string generator for PEG. Does Boost.Spirit.Karma could also generate random string for a given PEG grammar?

ptal commented 10 years ago

I'm closing this. You asked this question on numerous repository and copy some answers from there in your reply without citing your source.