No Detail Found!

Induction of Chomsky Normal Form in Con- text-Free Grammar of LL(1) Parser: Some Initial Results

Author(s)
Dilawar Naseem University of Balochistan,Quetta Country,Pakistan
Muhammad Shumail Naveed University of Balochistan,Quetta Country,Pakistan
Hassan Ali University of Balochistan,Quetta Country,Pakistan
Samra Riaz Sardar Bahadur Khan Women University,Quetta Country,Pakistan
Abstract
Parsing is to analyze the input lexeme and compilers have dificulty in processing due to human language structure, improvement in parsing processing can improve compiler speed. The paper aims at improving parsing by the introduction of Chomsky Normal Form (CNF) to Context-Free Grammar (CFG). For this research study, conventional English grammar in CFG is used and the conventional conversion method is used thoroughly. The grammar is converted into LL(1) form with the help of the LL(1) conversion algorithm and for the confirmation of successful conversion parsing table of LL(1) is conferred. For the analysis of LL (1) grammar input stack of 50 lexeme is verified by parsing clinched with the LL (1) grammar. The conventional LL(1) English grammar is induced with Chomsky Normal Form (CNF) and the resultant CNF converted LL (1) grammar is parsed with an input stack of 50 lexeme that are used for the LL(1) grammar. The study concluded that the introduction of CNF into LL(1) does not show significant improvement after the introduction of CNF into conventional LL(1) parser Introduction of CNF into LL(1) brings out parsing dificulty in processing the input stack of LL(1) into CNF introduced LL(1)
Publication Details
Page(s) 30-39
DOI DOI not available
Published Journal: Journal of Information & Communication Technology (JICT), Volume: 15, Issue: 1, Year: 2021

Request the full text from PASTIC

Keywords
compiler, Parsing, LL (1) Parsing, top-down parsing, Chomsky Normal Form
References
Williams P. K.,Lacerda K. A.,Stevens F.,Lindblom K. N.,B. K. N. .1992 .Linguistic experience alters phonetic perception in infants by 6 months of age. Science, 255(5044) : 606-608.
Andruski P. K.,Chistovich J. E.,Chistovich I. A.,Kozhevnikova L. A.,Ryskina E. V.,Lacerda V. L.,F. V. L. .1997 .Cross-language analysis of phonetic units in language addressed to infants. Science, 277(5326) : 684-686.
Meduna .,A. . .2014 .. Formal Languages and Computation: Models and Their Applications, : 233.
N. .1956 .Three Models for the Description of Language. , 113 : 123.
N. .1957 .Syntactic Structures: The Hague. , : .
J. .2006 .. , : .
Naveed H.,Naseem M.,Shabbir D.,J. D.,Quaid- D. .2020 .LL (1) Parser versus GNF inducted LL (1) Parser on Arithmetic Expressions Grammar: A Comparative Study. , 18(2) : 89-101.
.2017 .“The Impact of Terminal Prefixing on LL (1) Parsing”. J. Appl. Environ. Biol. Sci, 7(5) : 64-76.
Axel-Tobias Schreiner ,Casinghino S.,Fisher C.,Roux K.,C. K. .2019 .Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. In 10th International Conference on Interactive Theorem Proving (ITP, 11 : .
R. .1978 .A theory of type polymorphism in programming. Journal of computer and system sciences, 17(3) : 348-375.
Muhlenbein M.,Mevenkamp H.,M. H.,C. H.,Parsers H.,Issue I). .1984 .A Language Independent Error Recovery Method for LL (1. , 14 : .
J. J. .1993 .Incremental LL (1) parsing in language-based editors. IEEE transactions on software engineering, 19(9) : 935-940.
Quong T. J.,R. W. T. J. .1995 .ANTLR: A predicated-LL (k) parser generator. Software: Practice and Experience, 25(7) : 789-810.
J. A. .1986 .LPARSER, an LL (1) parser generator (Master's thesis. , : .
0

Citations

0

Downloads

9

Views