At this point, I am working on the code for refactoring Antlr grammars in Antlrvsix. While I plan to use Piggy to implement these refactorings, I will first implement them in C# code so I can get a clear picture of what to do with Piggy, make any changes, then rewrite the refactorings using Piggy templates.
Here is a preliminary list of some transformations I plan to write:
- Convert string literals in parser with lexer token types.
- Remove useless productions.
- Move start symbol to the top of parser grammar.
- Order parser rules (a) alphabetically, (b) DFS traversal, or (c) BFS traversal.
- Separate/combine lexer and parser grammars.
- Convert parser rules to fragment lexer rules and vice versa.
- Move lexer fragment rules to top/bottom.
- Order modes in alphabetic order.
- Remove left recursion.
The first three transformations have already been added to Antlrvsix. Here are some clips on how they work.
Additionally, there are a number of papers to check out.
- Halupka, Ivan, and Ján Kollár. “Catalog of grammar refactoring patterns.” Central European Journal of Computer Science 4.4 (2014): 231-241.
- Kollár, Ján, et al. “pLERO: Language for grammar refactoring patterns.” 2013 Federated Conference on Computer Science and Information Systems. IEEE, 2013.
- Porubän, Jaroslav, and Milan Nosáľ. “Practical experience with task-driven case studies.” 2014 IEEE 12th IEEE International Conference on Emerging eLearning Technologies and Applications (ICETA). IEEE, 2014.
- Kraft, Nicholas A., Edward B. Duffy, and Brian A. Malloy. “Grammar recovery from parse trees and metrics-guided grammar refactoring.” IEEE Transactions on Software Engineering 35.6 (2009): 780-794.
- Sarbo, Janos J. “Grammar transformations for optimizing backtrack parsers.” Computer Languages 20.2 (1994): 89-100.
- Lior Zur-Lotan and Avi Hayoun, Lecture notes “Transforming grammars to LL(1)”.
- Soisalon-Soininen, Eljas, and Esko Ukkonen. “A method for transforming grammars into LL (k) form.” Acta Informatica 12.4 (1979): 339-369.
- Smith, James. “Eliminating Left Recursion without the Epsilon.” arXiv preprint arXiv:1908.10888 (2019).
- Johnson, Mark, and Brian Roark. “Compact non-left-recursive grammars using the selective left-corner transform and factoring.” arXiv preprint cs/0008021 (2000).
- Moore, Robert C. “Removing left recursion from context-free grammars.” Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference. Association for Computational Linguistics, 2000.
–Ken