Abstract

Problem arising in CFG (Context Free Grammar) due to ambiguity can be trace to 1962. Even now there is no general method or procedure introduced to detect ambiguity in CFG. In parser generation and in language design, ambiguity in context free grammar, is a frequent problem as well as in application where it is used for the representation of physical structure. For creating a language it should be necessary that it is unambiguous. Ambiguity has some advantages as well as disadvantages. The aim of this study is to analyze different methods dealing with the ambiguity detection in Context Free Grammars. In this study, we will observe usefulness of Ambiguity Detection Method (ADM) in CFG with respect to ambiguity detection, assurance of termination of the process and accuracy.

Keywords:

Ambiguity, CFG, detection, review,

References

1. Basten, H.J.S., 2007. Ambiguity detection methods for context-free grammars. M.A. Thesis, Universiteit van Amsterdam, August.
   
2. Basten, H.J.S., 2009. The usability of ambiguity detection methods for context-free grammars. Electron. Notes Theor. Comput. Sci., 238(5): 35-46.
   CrossRef    
3. Bouwers, E., M. Bravenboer and E. Visser, 2008. Grammar engineering support for precedence rule recovery and compatibility checking. Electron. Notes Theor. Comput. Sci., 203(2): 85-101.
   CrossRef    
4. Brabrand, C., R. Giegerich and A. Møller, 2010. Analyzing ambiguity of context-free grammars. Sci. Comput. Program.,75(3): 176-191.
   CrossRef    
5. Cheung, B.S.N., 1994. A Theory of automatic language acquisition. Ph.D. Thesis, University of Hong Kong.
   
6. Cheung, B.S., 1995. Ambiguity in context-free grammars. Proceedings of the 1995 ACM Symposium on Applied Computing, pp: 272-276.
   CrossRef    
7. Flajolet, P., 1987. Analytic models and ambiguity of context-free languages. Lect. Notes Comput. Sc., 49(2): 283-309.
   CrossRef    
8. Gorn, S., 1963. Detection of generative ambiguities in context-free mechanical languages. J. ACM, 10(2): 196-208.
   CrossRef    
9. Jampana, S., 2005. Exploring the problem of ambiguity in context-free grammars. M.A. Thesis, Oklahoma State University, Stillwater, OK.
   
10. Kruse, M. and P. Pfahler, 2008. Ambiguity detection for context-free grammars in eli. B.A. Thesis, University of Paderborn, Paderborn, May 7th.
    
11. Mohri, M. and M.J. Nederhof, 2001. Regular Approximation of Context-free Grammars through Transformation. In: Junqua, J.C. and G. Van Noord (Eds.), Robustness in Language and Speech Technology. Kluwer Academic Publishers, the Netherlands, pp: 153-163.
    CrossRef    PMid:11499619    
12. Pandey, H.M., 2012. A case study on ambiguity detection method using some set of grammars. Pac. J. Sci. Technol., 13(1): 277-286.
    
13. Passos, L.T., M.A. da Silva Bigonha and R. da Silva Bigonha, 2007. A methodology for removing LALR(k) conflicts. J. UCS, 13(6): 737-752.
    
14. Schmid, H., 2004. Efficient parsing of highly ambiguous context-free grammars with bit vectors. Proceedings of the 20th International Conference on Computational Linguistics, (COLING, 2004). Geneva, Switzerland.
    CrossRef    
15. Schmitz, S., 2007. Conservative ambiguity detection in context-free grammars. Proceedings of the 34th International Conference on Automata, Languages and Programming (ICALP'07), pp: 692-703.
    CrossRef    
16. Simmons, R.J., B. Toninho and F. Pfenning, 2011. Distributed deductive databases, declaratively: The L10 logic programming language. Proceedings of the X10 Workshop, ACM.
    
17. Vasudevan, N. and L. Tratt, 2012. Search-based ambiguity detection in context-free grammars. Proceeding of ICCSW, pp: 142-148.
    
18. Wich, K., 2000. Exponential ambiguity of context-free grammars. Proceedings of the 4th International Conference on Developments in Language Theory, pp: 125-138.
    CrossRef    
19. Wich, K., 2005. Ambiguity functions of context-free grammars and languages. Ph.D. Thesis, University of Stuttgart.
    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.