{"id":2594,"date":"2020-03-10T16:51:17","date_gmt":"2020-03-10T20:51:17","guid":{"rendered":"http:\/\/codinggorilla.com\/?p=2594"},"modified":"2020-03-13T07:01:21","modified_gmt":"2020-03-13T11:01:21","slug":"transformations-for-antlr-grammars","status":"publish","type":"post","link":"http:\/\/165.227.223.229\/index.php\/2020\/03\/10\/transformations-for-antlr-grammars\/","title":{"rendered":"Transformations for Antlr grammars"},"content":{"rendered":"\n<p>At this point, I am working on the code for refactoring <a href=\"https:\/\/www.antlr.org\/\" class=\"ek-link\">Antlr<\/a> grammars in <a href=\"https:\/\/github.com\/kaby76\/AntlrVSIX\" class=\"ek-link\">Antlrvsix<\/a>. While I plan to use <a href=\"https:\/\/github.com\/kaby76\/Piggy\" class=\"ek-link\">Piggy<\/a> 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.<\/p>\n\n\n\n<p>Here is a preliminary list of some transformations I plan to write:<\/p>\n\n\n\n<ul><li>Convert string literals in parser with lexer token types.<\/li><li> Remove useless productions.<\/li><li>Move start symbol to the top of parser grammar.<\/li><li>Order parser rules (a) alphabetically, (b) DFS traversal, or (c) BFS traversal.<\/li><li>Separate\/combine lexer and parser grammars.<\/li><li>Convert parser rules to fragment lexer rules and vice versa.<\/li><li>Move lexer fragment rules to top\/bottom.<\/li><li>Order modes in alphabetic order.<\/li><li>Remove left recursion.<\/li><\/ul>\n\n\n\n<p>The first three transformations have already been added to Antlrvsix. Here are some clips on how they work.<\/p>\n\n\n\n<div class=\"wp-block-media-text alignwide\"><figure class=\"wp-block-media-text__media\"><video controls src=\"http:\/\/codinggorilla.com\/wordpress\/wp-content\/uploads\/2020\/03\/2020-03-11-13-45-30.mkv\"><\/video><\/figure><div class=\"wp-block-media-text__content\">\n<p><\/p>\n<\/div><\/div>\n\n\n\n<div class=\"wp-block-media-text alignwide\"><figure class=\"wp-block-media-text__media\"><video controls src=\"http:\/\/codinggorilla.com\/wordpress\/wp-content\/uploads\/2020\/03\/2020-03-11-13-40-29.mkv\"><\/video><\/figure><div class=\"wp-block-media-text__content\">\n<p class=\"has-large-font-size\"><\/p>\n<\/div><\/div>\n\n\n\n<div class=\"wp-block-media-text alignwide\"><figure class=\"wp-block-media-text__media\"><video controls src=\"http:\/\/codinggorilla.com\/wordpress\/wp-content\/uploads\/2020\/03\/2020-03-11-13-19-01.mkv\"><\/video><\/figure><div class=\"wp-block-media-text__content\">\n<p class=\"has-large-font-size\"><\/p>\n<\/div><\/div>\n\n\n\n<p>Additionally, there are a number of papers to check out.<\/p>\n\n\n\n<ul><li><a href=\"https:\/\/link.springer.com\/article\/10.2478\/s13537-014-0212-7\" class=\"ek-link\">Halupka, Ivan, and J\u00c3\u00a1n Koll\u00c3\u00a1r. &#8220;Catalog of grammar refactoring patterns.&#8221;&nbsp;<em>Central European Journal of Computer Science<\/em>&nbsp;4.4 (2014): 231-241. <\/a><\/li><li><a href=\"https:\/\/ieeexplore.ieee.org\/abstract\/document\/6644216\" class=\"ek-link\">Koll\u00c3\u00a1r, J\u00c3\u00a1n, et al. &#8220;pLERO: Language for grammar refactoring patterns.&#8221;&nbsp;<em>2013 Federated Conference on Computer Science and Information Systems<\/em>. IEEE, 2013. <\/a><\/li><li><a href=\"https:\/\/ieeexplore.ieee.org\/abstract\/document\/7107613\" class=\"ek-link\">Porub\u00c3\u00a4n, Jaroslav, and Milan Nos\u00c3\u00a1\u00c4\u00be. &#8220;Practical experience with task-driven case studies.&#8221;&nbsp;<em>2014 IEEE 12th IEEE International Conference on Emerging eLearning Technologies and Applications (ICETA)<\/em>. IEEE, 2014. <\/a><\/li><li><a href=\"https:\/\/ieeexplore.ieee.org\/abstract\/document\/5278661\" class=\"ek-link\">Kraft, Nicholas A., Edward B. Duffy, and Brian A. Malloy. &#8220;Grammar recovery from parse trees and metrics-guided grammar refactoring.&#8221;&nbsp;<em>IEEE Transactions on Software Engineering<\/em>&nbsp;35.6 (2009): 780-794. <\/a><\/li><li><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/abs\/pii\/0096055194900167\" class=\"ek-link\">Sarbo, Janos J. &#8220;Grammar transformations for optimizing backtrack parsers.&#8221;&nbsp;<em>Computer Languages<\/em>&nbsp;20.2 (1994): 89-100.<\/a> <\/li><li><a href=\"https:\/\/www.cs.bgu.ac.il\/~comp151\/wiki.files\/ps3.html\" class=\"ek-link\">Lior Zur-Lotan and Avi Hayoun, Lecture notes &#8220;Transforming grammars to LL(1)&#8221;.<\/a><\/li><li><a href=\"https:\/\/link.springer.com\/article\/10.1007\/BF00268320\" class=\"ek-link\">Soisalon-Soininen, Eljas, and Esko Ukkonen. &#8220;A method for transforming grammars into LL (k) form.&#8221;&nbsp;<em>Acta Informatica<\/em>&nbsp;12.4 (1979): 339-369. <\/a><\/li><li><a href=\"https:\/\/arxiv.org\/abs\/1908.10888\" class=\"ek-link\">Smith, James. &#8220;Eliminating Left Recursion without the Epsilon.&#8221;&nbsp;<em>arXiv preprint arXiv:1908.10888<\/em>&nbsp;(2019). <\/a><\/li><li><a href=\"https:\/\/arxiv.org\/abs\/cs\/0008021\" class=\"ek-link\">Johnson, Mark, and Brian Roark. &#8220;Compact non-left-recursive grammars using the selective left-corner transform and factoring.&#8221;&nbsp;<em>arXiv preprint cs\/0008021<\/em>&nbsp;(2000). <\/a><\/li><li><a href=\"https:\/\/dl.acm.org\/doi\/10.5555\/974305.974338\" class=\"ek-link\">Moore, Robert C. &#8220;Removing left recursion from context-free grammars.&#8221;&nbsp;<em>Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference<\/em>. Association for Computational Linguistics, 2000. <\/a><\/li><\/ul>\n\n\n\n<p>&#8211;Ken<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/165.227.223.229\/index.php\/2020\/03\/10\/transformations-for-antlr-grammars\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Transformations for Antlr grammars&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts\/2594"}],"collection":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/comments?post=2594"}],"version-history":[{"count":0,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts\/2594\/revisions"}],"wp:attachment":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/media?parent=2594"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/categories?post=2594"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/tags?post=2594"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}