uction of Chomsky Normal Form in Context-Free Grammar of LL(1) Parser: Some Initial Results

Volume 15  Issue 1    2021

Download

Author(s): Muhammad Shumail Naveed , Hassan Ali , Samra Riaz , Dilawar Naseem
Abstract Parsing is to analyze the input lexeme and compilers have difficulty 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 difficulty in processing the input stack of LL(1) into CNF introduced LL(1).
Keywords Compiler, Chomsky Normal Form, LL (1) Parsing, Parsing, Top-down parsing.
Year 2021
Volume 15
Issue 1
Type Research paper, manuscript, article
Journal Name Journal of Information & Communication Technology
Publisher Name ILMA University
Jel Classification -
DOI -
ISSN no (E, Electronic) 2075-7239
ISSN no (P, Print) 2415-0169
Country Pakistan
City Karachi
Institution Type University
Journal Type Open Access
Manuscript Processing Blind Peer Reviewed
Format PDF
Paper Link https://jict.ilmauniversity.edu.pk/journal/jict/15.1/5.pdf
Page 30-39