C2VPG: Translating Practical Context-Free Grammars into Visibly Pushdown Grammars by Order-Based Tagging
Xiaodong Jia, Gang Tan · 2025
Context-free grammars (CFGs) are widely used to specify the syntax of programming languages. However, their inherent complexity and lack of structural nesting information make them less suitable for certain parsing and analysis tasks. Visibly pushdown grammars (VPGs) address these limitations by introducing explicit call, return, and plain symbols, enabling efficient parsing and analysis of nested structures. Translating practical CFGs into VPGs remains challenging, especially with ambiguous constructs like the dangling-else issue, where the order of call and return symbols must be carefully managed to ensure correct parsing. In this paper, we present C2VPG, a tool for automatically translating practical CFGs into VPGs using a novel order-based tagging method. Our approach introduces a sound algorithm that automatically determines an order on return symbols and constructs a tagger that assigns call, return, and plain tags to terminals in a CFG based on this order. This method resolves the tagging challenge posed by the dangling-else problem, where return symbols could be optional in sentences. We evaluate our approach on 396 real-world grammars from the ANTLR repository, achieving a 61 % success rate in converting CFGs into VPGs. We discuss the challenges posed by practical grammar design that prevent C2VPG's translations. Our results demonstrate that C2VPG is both practical and efficient, and could assist language designers in creating more robust grammars.