4 ms·

A long time ago I did a pair of articles about recursive descent parsing [1] [2], from very basic theory to a crappy programming language. As a side effect I al

A long time ago I did a pair of articles about recursive descent parsing [1] [2], from very basic theory to a crappy programming language. As a side effect I also made a cantankerous parser generator [3] that produces a backtracking recursive descent parser from EBNF. [1] https://reindeereffect.github.io/2018/12/08/index.html https://reindeereffect.github.io/2018/12/08/index.html [2] https://reindeereffect.github.io/2019/01/16/index.html https://reindeereffect.github.io/2019/01/16/index.html [3] https://github.com/reindeereffect/tools-from-blog/tree/master/yakety https://github.com/reindeereffect/tools-from-blog/tree/maste...

fjfaase 4y ago
About 20 years ago, I too started working on a back-tracking recursive descent parser. I wrote it in C. In started with an interpretter that would just take the EBNF rules. It could parse a preprocessed C file using the C grammar (almost taken verbatim from The Book), but it was rather slow. My first idea was to turn the interpretter in a code generator that would generate C code. It produced a massive file, which took very long to compile and to my surprise, was slower than the interpretter. This might be due many missed cache hits. Next, I decided to implement some caching, simply remembering at each point of the input which non-terminals were parsed or not. This gave a huge performance improvement. I also added some mechanism to let it generate a Abstract Syntax Tree. Later, I wrote a C++ version that also included an unparser, based on the input grammar. Instant pretty-printer and 'unifier'. Recently, I developed a JavaScript version (with a simple caching strategy), which turned out to be still fast enough to follow key strokes for small inputs. (Just parsing the whole input on each key stroke.) See: https://fransfaase.github.io/ParserWorkshop/Online_inter_parser.html https://fransfaase.github.io/ParserWorkshop/Online_inter_par...

fjfaase 4y ago

About 20 years ago, I too started working on a back-tracking recursive descent parser. I wrote it in C. In started with an interpretter that would just take the EBNF rules. It could parse a preprocessed C file using the C grammar (almost taken verbatim from The Book), but it was rather slow. My first idea was to turn the interpretter in a code generator that would generate C code. It produced a massive file, which took very long to compile and to my surprise, was slower than the interpretter. This might be due many missed cache hits. Next, I decided to implement some caching, simply remembering at each point of the input which non-terminals were parsed or not. This gave a huge performance improvement. I also added some mechanism to let it generate a Abstract Syntax Tree. Later, I wrote a C++ version that also included an unparser, based on the input grammar. Instant pretty-printer and 'unifier'. Recently, I developed a JavaScript version (with a simple caching strategy), which turned out to be still fast enough to follow key strokes for small inputs. (Just parsing the whole input on each key stroke.) See: https://fransfaase.github.io/ParserWorkshop/Online_inter_parser.html https://fransfaase.github.io/ParserWorkshop/Online_inter_par...