No Detail Found!

LL(1) Parser versus GNF inducted LL(1) Parser on Arithmetic Expressions Grammar: A Comparative Study

Author(s)
Hassan Ali Department of Computer Science and Information technology, University of Balochistan,Sariab Road, Quetta,Pakistan
Muhammad Shumail Naveed Department of Computer Science and Information technology, University of Balochistan,Sariab Road, Quetta,Pakistan
Dilawar Naseem Department of Computer Science and Information technology, University of Balochistan,Sariab Road, Quetta,Pakistan
Jawaid Shabbir Department of Computer Engineering, Sir Syed University of Engineering & Technology,Karachi,Pakistan
Abstract
The prime objective of the proposed study is to determine the induction of Greibach Normal Form (GNF) in Arithmetic Expression Grammars to improve the processing speed of conventional LL(1) parser. Conventional arithmetic expression grammar and its equivalent LL(1) is used in the study which is converted. A transformation method is defined which converts the selected grammar into a Greibach normal form that is further converted into a GNF based parser through a method proposed in the study. These two parsers are analyzed by considering 399 cases of arithmetic expressions. During statistical analysis, the results are initially examined with the Kolmogorov-Smirnov and Shapiro-Wilk test. The statistical significance of the proposed method is evaluated with the Mann-Whitney U test. The study described that GNF based LL(1) parser for arithmetic take fewer steps than conventional LL(1) grammar. The ranks and asymptotic significance depict that the GNF based LL(1) method is significant than the conventional LL(1) approach. The study adds to the knowledge of parsers itself, parser expression grammars (PEG's), LL(1) grammars, Greibach Normal Form (GNF) induced grammar structure, and the induction of Arithmetic PEG's LL(1) to GNF based grammar.
Publication Details
Page(s) 89-101
DOI DOI not available
Published Journal: Quaid-e-Awam University Research Journal of Engineering, Science and Technology, Volume: 18, Issue: 2, Year: 2020

Request the full text from PASTIC

Keywords
Parsing, compiler, Greibach normal form, top-down parsing, LL(1) parsing
0

Citations

0

Downloads

108

Views