A Novel Parser Design Algorithm Based on Artificial Ants

This article presents a unique design for a parser using the ant colony optimization algorithm. The paper implements the intuitive thought process of human mind through the activities of artificial ants. Traditional methods of designing parser involve calculation of different sets like FIRST, FOLLOW, GOTO, CLOSURE and parsing or precedence relation tables. Calculation of these tables and sets are both memory and time consuming. Moreover, the grammar concerned has to be converted into a context-free, non-redundant and unambiguous one. The scheme presented here uses a bottom-up approach and the parsing program can directly use ambiguous or redundant grammars. We allocate a node corresponding to each production rule present in the given grammar. Each node is connected to all other nodes (representing other production rules), thereby establishing a completely connected graph susceptible to the movement of artificial ants. Ants are endowed with some memory that they use to carry the sentential form derived from the given input string to the parser. Each ant tries to modify this sentential form by the production rule present in the node and upgrades its position until the sentential form reduces to the start symbol S. Successful ants deposit pheromone on the links that they have traversed through in inverse proportion of the number of hops required to complete a successful tour. Eventually, the optimum path is discovered by the links carrying maximum amount of pheromone concentration. The design is simple, versatile, robust and effective and obviates the calculation of the above mentioned sets and precedence relation tables. Further advantages of our scheme lie in i) ascertaining whether a given string belongs to the language represented by the grammar, and ii) finding out the shortest possible path from the given string to the start symbol S in case multiple routes exist.