
## V. Advantages Of Proposed Scheme

 
 But an ant counts the number of hops it requires to move from the starting node to the ending node and deposits pheromone on the links in inverse proportion of the number of hops. It implies that ant, which arrives at S from the starting expression using minimum number of rules, deposits maximum amount of pheromone on the links that it has traversed through. As the algorithm progresses, only a few links, which are conducive in guiding the ants towards an optimal solution, receive increasing amount of pheromone which eventually leads to the exploration of the shortest possible steps to check the validity of the given string. Figure (1) shows a visual representation of the entire scheme. 

 This section highlights the advantages of our scheme over all the existing algorithms of designing a parser. The benefits are summarized below: 
1. We do not need to use up resources for calculating FIRST, FOLLOW, GOTO or CLOSURE sets or parsing or precedence relation tables which are required by more advanced types of parsers. Nor do we require to get rid of back-tracking. Since there are numerous ants, the appropriate production rule to be used is found easily. So we do not need to left-factor to eliminate back-tracking, since the elimination of back-tracking is not needed at all. We can directly work with ambiguous grammars. 

2. There is no need to eliminate left-recursion either, since one ant will invariably find the correct path; and when one does, the others will soon follow suit. So we do not require working with a context-free or a non-redundant grammar. This is a huge simplification to the parsing problem. 

3. Our scheme is based on the intuitive method of human thinking, and thus conceptually simpler, and easier to visualize. 

While it is true that the scheme 'could' have been implemented by exploring paths from ω to S randomly, the use of a stochastic optimization strategy, namely ACO is justified due to the following two conditions: 
i) if ω is NOT a legal string of L(G), it is difficult to ascertain the fact without using a systematic search policy. 

ii) using an optimization algorithm gives the shortest route from ω to S; this is essential to increase the speed of operation of the parser, especially when there are multiple routes, which is the general case, and the usual case for complex applications. 

## Vi. Conclusions And Scope Of Future Work

 The many advantages of the proposed parsing scheme point towards the fact that this approach will be suitable for parsing complex expressions, such as those encountered in natural language analysis applications. We use the very basic bottomup approach, so the scheme is conceptually simple. The use of the ACO metaheuristic ensures that we can use ambiguous and redundant grammars. In the future, we plan to use the ACO algorithm to design more advanced parser types. 

## References

[1] A. Aho, R. Sethi, J. Ullman, Compilers: Principles, Techniques and Tools, Addison-Wesley, Reading, Massachusetts, USA, 1986. 

[2] E. Black, R Garside, G. Leech, Statistically driven computer grammars of English: the IBM/Lancaster approach, Rodopi, 1993. 

[3] S. C. Johnson, "YACC - yet another compiler compiler", *Computer* Science Technical Report 32, AT&T Bell Laboratories, Murray Hill, NJ, 
USA, 1975. 

[4] J. Power, B. Malloy, "Metric-based analysis of context-free grammars", 
8th Int Workshop on Program Comprehension, IEEE Computer Society, pp 171-178, Limerick, Ireland, 2000. 

[5] T. Briscoe, J. Carroll, "Generalized probabilistic LR parsing of natural language (Corpora) with Unification-Based Grammars", *Computational* Linguistics, vol. 19, issue 1, pp. 25- 59, 1993. 

[6] D. Guha, T. Srikanthan, "Reconfigurable frame parser design for multiradio support on asynchronous microprocessor cores", *Int Conf on* Computing: Theory and Applications, pp 122-127, 2007. 

[7] W. Shao-Po, S. Boyd, "Design and implementation of a parser/solver for SDPs with matrix structure", *1996 IEEE Int Symposium on ComputerAided Control System Design*, pp 240-245, 1996 
[8] B. A. Malloy, J. T. Waldron, "Applying software engineering techniques to parser design: The Development of a C\# Parser", *Annual Conf of the* South African Institute of Computer Scientists and Information Technologists, pp 75-82, 2002. 

[9] H. T. Siegelmann, C. L. Giles, "The complexity of language recognition by neural networks", *Neurocomputing*, vol. 15, issues 3-4, pp 327-345, 1997. 

[10] C. Lyon, R. Frank, "Neural network design for a natural language parser", *International Conf on Artificial Neural Networks*, pp 105-110, 1995 
[11] M. Dorigo, C. Blum. "*Ant colony optimization theory: A survey*", 
Theoretical Comp. Sc. 344, pp. 243–278, 2005
[12] M.Dorigo, T.Stiizle, *Ant colony optimization*, MIT Press, Cambridge, MA, 2004. 

[13] M.Dorigo, L.M.Gambardella, "Ant colonies for the traveling salesman problem," *Bio Systems*, vol. 43, no.2, pp. 73-81, 1997. 

[14] D.Costa, A.Hertz, "Ants can color graphs", *Journal of the Operational* Research Society, vol. 48, no. 3, pp. 295-305, 1997. 

[15] V. Maniezzo, A. Colorni, "The ant system applied to the quadratic assignment problem", *IEEE Trans. on Knowledge and Data Engineering* vol. 11, issue 5, pp. 769 - 778, 1999. 

[16] M. Dorigo, M. Birattari, T. Stiitzle, "Ant colony optimization: artificial ants as a computational intelligence technique," *IEEE Computational* Intelligence Magazine, vol. 1, no. 4, 2006. 