Open AccessA New Top-Down Context-Free Parsing for Syntactic Pattern Recognition
Author(s) -
Mehrnoosh Bazrafkan
Publication year - 2022
Publication title -
international journal of mathematical models and methods in applied sciences
Language(s) - English
Resource type - Journals
ISSN - 1998-0140
DOI - 10.46300/9101.2022.16.4
Subject(s) - computer science , parsing , parsing expression grammar , top down parsing , natural language processing , artificial intelligence , context free grammar , bottom up parsing , s attributed grammar , parser combinator , context (archaeology) , grammar , programming language , l attributed grammar , linguistics , paleontology , philosophy , biology
The numerous different mathematical methods used to solve pattern recognition snags may be assembled into two universal approaches: the decision-theoretic approach and the syntactic(structural) approach. In this paper, at first syntactic pattern recognition method and formal grammars are described and then has been investigated one of the techniques in syntactic pattern recognition called top – down tabular parser known as Earley’s algorithm Earley's tabular parser is one of the methods of context -free grammar parsing for syntactic pattern recognition. Earley's algorithm uses array data structure for implementing, which is the main problem and for this reason takes a lots of time, searching in array and grammar parsing, and wasting lots of memory. In order to solve these problems and most important, the cubic time complexity, in this article, a new algorithm has been introduced, which reduces wasting the memory to zero, with using linked list data structure. Also, with the changes in the implementation and performance of the algorithm, cubic time complexity has transformed into O (n*R) order. Key words: syntactic pattern recognition, tabular parser, context –free grammar, time complexity, linked list data structure.