Designing a Bangla Parser using TRIE Based on Deterministic Finite Automata

We describe a new method of parsing Bangla language based on Deterministic Finite Automata (DFA) and implement the parser using a TRIE data structure. Hence we call the parser as TRIE parser. TRIE parser successfully parses sentences faster than other important parsing schemes as it needs no formal rules, no parameters and no Context Free Grammars (CFG). the scheme stores the Bangla grammar symbols or Pasts Of Speech (POS) as a state of the DFA and process a sentence following the operations of a DFA. If the set of POS symbols reaches to final state, then parsing is successful otherwise unsuccessful. The parser uses the grammar rules in compressed form hence it becomes very less space consuming. Therefore, it can be implemented in light weight fashion in main memory. The TRIE parser is compared with two other parsers and it shows that the proposed TRIE parser outperforms others in terms of processing time with an increasing number of sentences in the input paragraph. Necessary figures and examples are used to properly explain the proposed TRIE parser.