000206921 001__ 206921
000206921 005__ 20190317000134.0
000206921 037__ $$aREP_WORK
000206921 245__ $$aTowards Automating Grammar Equivalence Checking
000206921 269__ $$a2015
000206921 260__ $$c2015
000206921 300__ $$a15
000206921 336__ $$aReports
000206921 520__ $$aWe consider from practical perspective the (generally undecidable) problem of checking equivalence of context-free grammars. We present both techniques for proving equivalence, as well as techniques for finding counter-examples that establish non-equivalence. Among the key building blocks of our approach is a novel algorithm for efficiently enumerating and sampling words and parse trees from arbitrary context-free grammars; the algorithm supports polynomial time random access to words belonging to the grammar. Furthermore, we propose an algorithm for proving equivalence of context-free grammars that is complete for LL grammars, yet can be invoked on any context-free grammar, including ambiguous grammars. Our techniques successfully find discrepancies between different syntax specifications of several real-world languages, and is capable of detecting fine-grained incremental modifications performed on grammars. Our evaluation shows that our tool improves significantly on the existing available state of the art tools. In addition, we used these algorithms to develop an online tutoring system for grammars that we then used in an undergraduate course on computer language processing. On questions involving grammar constructions, our system was able to automatically evaluate the correctness of 95% equivalence questions: it disproved 74% of cases and proved 21% of them. This opens up the possibility of using our tool in massive open online courses to introduce grammars to large populations of students.
000206921 6531_ $$aContext-free Grammar
000206921 6531_ $$aEquivalence
000206921 6531_ $$aEnumeration
000206921 6531_ $$aCompilation
000206921 6531_ $$aVerification
000206921 700__ $$0247192$$g222382$$aKandhadai Madhavan, Ravichandhran
000206921 700__ $$0247526$$g183900$$aMayer, Mikael
000206921 700__ $$aGulwani, Sumit
000206921 700__ $$0240031$$g177241$$aKuncak, Viktor
000206921 8564_ $$uhttps://infoscience.epfl.ch/record/206921/files/main_2.pdf$$zn/a$$s383128$$yn/a
000206921 909C0 $$xU11739$$0252019$$pLARA
000206921 909CO $$qGLOBAL_SET$$pIC$$ooai:infoscience.tind.io:206921$$preport
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 917Z8 $$x222382
000206921 937__ $$aEPFL-REPORT-206921
000206921 973__ $$aEPFL
000206921 980__ $$aREPORT