Semantics-preserving Transformation of Context-free Grammars into LL(1) Form
summary
Proposes a concrete method to convert any context-free grammar into LL(1) while keeping the original semantics by encoding rules as typed tree nodes and pairing each node with a semantic function and a parsing function written in continuation-passing style. Demonstrates on an EQL subset: left recursion and common-prefix conflicts become function-returning nodes that are later applied to the saved prefix so the generated fluent API and parser preserve original AST structure. Prototype and paper provide working implementation; performance remains future work.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:10Fluent APIs and DSLs in Java
- 4:00Generating DSLs from grammars
- 8:46Fluent API limitations
- 12:08Fluent API generation state
- 13:54Transforming grammars to LL(1)
- 16:02Preserving semantics
- 17:05Semantic-preserving example
- 23:28Building APIs and parsers
- 27:27Summary
- 28:10Q&A
related talks
15mDetecting and explaining (in-)equivalence of context-free grammars
29mSemantic Transformation Framework for Rewriting Rules
01h 05mAll the Languages Together
01h 07mBack to the Future: A Fresh Look at Linear Temporal Logic
15mFaster Reachability Analysis for LR(1) Parsers
19mContext-Free Language Reachability via Skewed Tabulation
15mA Semantic Framework for PEGs
53mSemantics-based program manipulation in the age of LLMs