Gentree of Tool for Syntactic Analysis Based On Younger Cocke Kasami Algorithm
DOI:
https://doi.org/10.33633/jais.v2i1.1387Abstract
Syntactic analysis is a series of processes in order to validate a string that is received by a language. Understanding the process of reduction rules to become a tree is the part that is difficult to explain. This paper describes the results of the design tool to automate an input string into a decrease in the rules to trees in the visualized with images either in the form of files or display, performance evaluation tools and analysis of students' understanding of the tool by the algorithm Cocke Younger Kasami (cyk) was selected as one of the cases for parsing techniques in the Context Free Grammar (CFG) in the form of Chomsky Normal Form (CNF). These results indicate that the model successfully implemented into the application named genTree (Generator Tree), application performance gained a significant number of measurements of the variations in the complexity of the grammar and the input string by 29.13% with the complexities 7 and 8:50% with the complexity of 20, while for long input string against time processing algorithm can be a value of 3.3 and 66.98% as well as 29 and 6:19%, also obtained differences in the ability of the t-test on a group of students control against the experimental group with a value of t = 5.336 with df 74, p value of 0.001 , on the level of signfikansi 0.05% (5%). Also terapat increase in the percentage of correct answers was 58% in the variation of difficulty, 83% of the variation was easy. Sebalikanya wrong answer decline by 60% in difficult variation, the variation was 100% and 57% for easy variation. Recently there is a change decrease in the percentage of students who are not doing as much as 60% in the variation of difficulty, 44% of the variation was 13% on the variations easily can be concluded that the applications run efficiently and optimally, but also can effectively improve students' understanding in beajar automata with case cyk algorithm. Keywords—Tool, Analysis, Syntax, Algorithms, TreesReferences
S. H. Wantah Satria, "Pembuatan Media Pembelajaran Untuk Proses Konversi Pada Finite Automata Berbasis Multimedia," Jurnal Sarjana Teknik Informatika e-ISSN: 2338-5197, vol. 1, no. 1, 2013.
A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation and Compiling, New York: Prentice Hall Englewood Cliffs, 1973.
A. W. Appel and M. Ginsburg, Modern Compiler Implementation In C, New York: CAMBRIDGE UNIVERSITY PRESS, 1998.
D. Grune and C. J. Jacobs, Parsing Techniques - A Practical Guide, New York: Springer, 2008.
J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, New York: Addison-Wesley, 2001.
A. V. Aho, M. S. Lam, R. Sethi and J. D. Ullman, Compiler: Principles, Techniques, and Tools, New York: Pearson Educating Addison Wesly, 2007.
J. V. Neumann, "The General and Logical Theory of Automata," Cerebral Mechanisms in Behavior, vol. 1, no. 51, pp. 288-326, 1951.
D. A. Watt and D. F. Brown, Programming Language Processors in Java, Compiler and Intepreter., New York: Pearson Education, Addison Wesly, 2000.
P. Skrzypczak, "Parallel Parsing of Context-Free Grammars," Master Thesis MCS, Blekinge Institute of Technology, Karlskorna, 2011.
T. Parr, Language Implementation Patterns Create Your Own Domain-Specific and General Programming Languages, Raleigh, North Carolina Dallas, Texas: The Pragmatic Bookshelf, 2010.
T. Parr and K. Fisher, "LL(*): the foundation of the ANTLR parser generator," ACM SIGPLAN Notices - PLDI, vol. 11, 2011.
A. Shamshad , "CYK Algorithm," International Journal of Scientific Research Engineering & Technology (IJSRET) , vol. 1, no. 5, pp. 1-4, 2012.
J. Cocke and J. T. Schwartz, "Programming Languages And Their Compilers," Courant Institute of Mathematical Sciences, New York University, New York, April 1970.
K. T and K. Torii, "A Syntax-Analysis Procedure For Unambiguous Context-Free Grammars," Journal Of The Acm (JACM), vol. 16, no. 3, 1969.
D. M. Younger , "Recognition And Parsing Of Context-Free Languages In Time n3," Information And Control, vol. 10, pp. 189-208, 1967.
I. Somerville, Software Engineering, Boston, Massachusetts.: Pearson Education, Addison-Wesly, 2011.
E. Gansner, "Graphviz - Graph Visualization Software, Envisioning connections," AT&T Labs-Research, - - -. [Online]. Available: http://www.graphviz.org. [Accessed 2 April 2016].
L. Szathmary, "GraphViz Java API," GraphViz Java API, 4 December 2003. [Online]. Available: https://github.com/jabbalaci/graphviz-java-api. [Accessed 2 April 2016].
Sugiyono, Metode Penelitian Kuantitatif, Kualitatif dan R &F, Bandung: Alfabeta, 2010.
A. Sudijono, Pengantar Statistik Pendidikan, Jakarta: Rajawali Press, 2010.
M. Lange and H. Leiß, "To CNF or not to CNF? An Efficient Yet," Informatica Didactica, vol. 8, 2009.
N. Bodenstab, "Efficient Implementation Of The CKY Algorithm," Computational Linguistics, Final Project Paper, 2009.
Journal of Applied Intelligent System (e-ISSN : 2502-9401 | p-ISSN : 2503-0493)
Vol. 2 No. , April 2017, pp. 37 – 51
S. A. Blythe, M. C. James, and S. H. Rodger, "LLparse and LRparse: Visual and Interactive Tools for Parsing," in Proceedings of the Twenty-fifth SIGCSE Technical Symposium on Computer Science Education, 1994.
Downloads
Published
Issue
Section
License
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
