NDLI: A Novel Parser Design Algorithm Based on Artificial Ants

Content Provider	IEEE Xplore Digital Library
Author	Maiti, D. Acharya, A. Konar, A. Ramadoss, J.
Copyright Year	2008
Description	Author affiliation: Dept. of Electron. & Telecommun. Eng., Jadavpur Univ., Kolkata (Maiti, D.; Acharya, A.; Konar, A.) \|\| Dept. of Inf. Technol., Jaya Eng. Coll., Chennai (Ramadoss, J.)
Abstract	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.
Starting Page	247
Ending Page	250
File Size	282378
Page Count	4
File Format	PDF
ISBN	9781424428991
DOI	10.1109/ICIAFS.2008.4783925
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-12-12
Publisher Place	Sri Lanka
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Process design Ant Colony Optimization Ant colony optimization Design methodology Redundancy Humans Information technology Parser Design context-free grammar Design engineering Production Robustness ambiguous grammar redundancy Intuitive thought process
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Niching for Population-Based Ant Colony Optimization

Ant Colony Algorithm Research Based on Pheromone Update Strategy

Ant colony clustering by expert ants

Ant colony optimization approach to heterogeneous redundancy in multi-state systems with multi-state components

Novel path planning of robots based on bidirectional ant colony algorithm

A mixed ant colony algorithm for function optimization

Application methods of ant colony algorithm

Design SAC of ship with ant colony optimization algorithm

Debugging ants: How ants find the shortest route

A Novel Parser Design Algorithm Based on Artificial Ants

Similar Documents

Niching for Population-Based Ant Colony Optimization

Ant Colony Algorithm Research Based on Pheromone Update Strategy

Ant colony clustering by expert ants

Ant colony optimization approach to heterogeneous redundancy in multi-state systems with multi-state components

Novel path planning of robots based on bidirectional ant colony algorithm

A mixed ant colony algorithm for function optimization

Application methods of ant colony algorithm

Design SAC of ship with ant colony optimization algorithm

Debugging ants: How ants find the shortest route

A Novel Parser Design Algorithm Based on Artificial Ants