3 ms·
Thank you. Never really figure out how parser works but maybe I should try and write one
by charlieyu1 4y ago
Thank you. Never really figure out how parser works but maybe I should try and write one
- tgv 4y agoI've always found writing parsers very rewarding. There are different parsing methods. The article mentions top-down recursive descent parsing. That's the easiest to do by hand, but you can't parse everything that way (or not easily). Bottom-up parsing is another strategy, which works (in principle) for all unambiguous grammars. The lazy solution is backtracking (try a rule, back up if it fails), and add memoization to keep the runtime acceptable. This is the basis for the so-called PEG parsers. There's a lot of formal literature. E.g., top-down recursive descent is a class known as LL(k), bottom-up is LR(k), and there are algorithms to derive parsers from grammars. It is however not the easiest starting point.