Do a correct internal parser

zimmski / tavor

A generic fuzzing and delta-debugging framework

MIT License

245 stars 10 forks source link

Do a correct internal parser #4

Open zimmski opened 10 years ago

zimmski commented 10 years ago

The current internal parser is just a quick hack to parse simple constructs. A better parser is needed to parse something like this:

+(A) A

The current version just eats all As via the repetition. We need a look-ahead parser or a back-tracking parser to really parse EVERYTHING.

zimmski commented 9 years ago

Have a look at

Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ."
Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars."

zimmski commented 9 years ago

Have a look at

https://en.wikipedia.org/wiki/Earley_parser

zimmski commented 9 years ago

We do not want a PEG (Parsing Expression grammar) as described here https://en.wikipedia.org/wiki/Parsing_expression_grammar (although Tavor implements MOST of the described features) because by default this uses a recursive descent parser parser and as described it cannot handle +(a)a as it is always greedy and does not backtrack.

zimmski commented 9 years ago

Have a look at

http://bford.info/packrat/