Treetop: Syntactic Analysis with Ruby

on YouTube ↗52m

" summary

Treetop presents a Ruby grammar engine that uses parsing expression grammars and packrat parsing so code parses without a separate lexer, trading memory for simpler composition. The demo builds an arithmetic parser and a 132-line interpreter for an extended lambda calculus, with unit tests showing the rules evaluate correctly and composition via modules working. Implementation compiles grammars to Ruby modules, instantiates syntax node objects, and accepts the cost of object allocation for clearer, reusable grammars under Treetop.

AI-written summary · about

" chapters (18)

1. 0:00Start
2. 4:52What Is a Context-Free Grammar
3. 6:45Context-Free Grammar
4. 7:58Context-Free Generative Grammar
5. 8:37Dangling Else Problem
6. 9:41Parsing Expression Grammars
7. 12:00Pumping Lemma
8. 13:31Load Grammar Declaration
9. 15:44Custom Subclass of Syntax Node
10. 17:38Parse the Language of Arithmetic
11. 19:28Defining the Arithmetic Grammar
12. 21:30Test Variables
13. 23:39Multiplication
14. 29:35Change the Operator
15. 31:22Parentheses That Override the Operator Precedence
16. 34:12Packrat Parsing
17. 35:59Lambda Calculus
18. 37:25Source Code of the Lambda Calculus Interpreter

" related talks

• 43mGrammars, Parsers, and Interpreters, In RubyMichael J. I. Jackson · RubyConf 2010
• 29mSyntax TreeKevin Newton · RubyConf Mini 2022
• 46mGrammar a BNF like Ruby DSL ParsingEric Mahurin · Lone Star Ruby Conference 2008
• 32mParsing RubyKevin Newton · RubyConf 2021
• 38mParsing Expressions in RubyMichael J. I. Jackson · MountainWest RubyConf 2011
• 44mConsuming Gherkin: One Byte at a TimeGreg Hnatiuk, Mike Sassak · RubyConf 2010
• 51mForbidden Fruit: A Test of Ruby's Parse TreeChris Wanstrath · GORUCO 2008
• 32mRuby MacrosCaleb Clausen · MountainWest RubyConf 2010