Gentree of Tool for Syntactic Analysis Based On Younger Cocke Kasami Algorithm

- Wijanarto, Ajib Susanto, Desi Purwanti Kusumaningrum

Abstract


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.

KeywordsTool, Analysis, Syntax, Algorithms, Trees


Full Text:

PDF

References


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.




DOI: https://doi.org/10.33633/jais.v2i1.1387

Refbacks

  • There are currently no refbacks.


Flag Counter

Journal of Applied Intelligent System (e-ISSN : 2502-9401p-ISSN : 2503-0493) is published by LPPM Universitas Dian Nuswantoro Semarang in collaboration with CORIS and IndoCEISS.

Journal of Applied Intelligent System indexed by :


This journal is under licensed of Creative Commons Attribution 4.0 International License.