Abstract
To infer an abstract model from source code is one of the main tasks of most software quality analysis methods. Such abstract model is called Abstract Syntax Tree and the inference task is called parsing. A parser is usually generated from a grammar specification of a (programming) language and it converts source code of that language into said abstract tree representation. Then, several techniques traverse this tree to assess the quality of the code (for example by computing source code metrics), or by building new data structures (e.g, flow graphs) to perform further analysis (such as, code cloning, dead code, etc). Parsing is a well established technique. In recent years, however, modern languages are inherently ambiguous which can only be fully handled by ambiguous grammars.
In this setting disambiguation rules, which are usually included as part of the grammar specification of the ambiguous language, need to be defined. This approach has a severe limitation: disambiguation rules are not first class citizens. Parser generators offer a small set of rules that can not be extended or changed. Thus, grammar writers are not able to manipulate nor define a new specific rule that the language he is considering requires.
In this paper we present a tool, name InDubio, that consists of an extensible combinator library of disambiguation filters together with a generalized parser generator for ambiguous grammars. InDubio defines a set of basic disambiguation rules as abstract syntax tree filters that can be combined into more powerful rules. Moreover, the filters are independent of the parser generator and parsing technology, and consequently, they can be easily extended and manipulated. This paper presents InDubio in detail and also presents our first experimental results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The work presented in this paper is available at our repository, at https://bitbucket.org/zenunomacedo/disambiguation-filters/.
References
Afroozeh, A., Izmaylova, A.: Faster, practical GLL parsing. In: Franke, B. (ed.) CC 2015. LNCS, vol. 9031, pp. 89–108. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46663-6_5
Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison-Wesley, San Francisco (2006)
Appel, A.: Modern Compiler Implementation in ML. Cambridge University Press, Cambridge (1998)
Backus, J.W.: The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM conference. In: IFIP Congress, pp. 125–131 (1959)
van den Brand, M.G.J., Scheerder, J., Vinju, J.J., Visser, E.: Disambiguation filters for scannerless generalized LR parsers. In: Horspool, R.N. (ed.) CC 2002. LNCS, vol. 2304, pp. 143–158. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45937-5_12
Claessen, K., Hughes, J.: Quickcheck: a lightweight tool for random testing of Haskell programs. ACM Sigplan Not. 46(4), 53–64 (2011)
Fernandes, J.P., Saraiva, J., Visser, J.: Generalised LR Parsing in Haskell (2004)
Johnson, S.C.: Yacc: yet another compiler-compiler (1979)
Johnstone, A., Scott, E., Economopoulos, G.: Generalised parsing: some costs, March 2004
Lämmel, R.: Grammar adaptation. In: Oliveira, J.N., Zave, P. (eds.) FME 2001. LNCS, vol. 2021, pp. 550–570. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45251-6_32
Marlow, S., Gil, A.: Happy user guide (2001)
O’Sullivan, B.: Criterion: a Haskell microbenchmarking library (2009). http://www.serpentine.com/criterion/
Parr, T., Fisher, K.: Ll(*): the foundation of the ANTLR parser generator. In: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, pp. 425–436. ACM, New York (2011)
Parr, T., Harwell, S., Fisher, K.: Adaptive ll (*) parsing: the power of dynamic analysis. ACM SIGPLAN Not. 49(10), 579–598 (2014)
Perlis, A.J., Shaw, M., Sayward, F. (eds.): Software Metrics: An Analysis and Evaluation. MIT Press, Cambridge (1981)
Salomon, D.J., Cormack, G.V.: Scannerless NSLR(1) parsing of programming languages. In: Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation (PLDI 1989), pp. 170–178. ACM (1989)
Saraiva, J.: HaLeX: a Haskell library to model, manipulate and animate regular languages. In: Hanus, M., Krishnamurthi, S., Thompson, S. (eds.) Proceedings of the ACM Workshop on Functional and Declarative Programming in Education, pp. 133–140. University of Kiel Technical report 0210, September 2002
Saraiva, J., Swierstra, D.: Data Structure Free Compilation. In: Jähnichen, S. (ed.) CC 1999. LNCS, vol. 1575, pp. 1–16. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-540-49051-7_1
Saraiva, J., Swierstra, D.: Generic attribute grammars. In: Parigot, D., Mernik, M. (eds.) 2nd Workshop on Attribute Grammars and their Applications, WAGA 1999, pp. 185–204. INRIA Rocquencourt, March 1999
Schmidt, U., Schmidt, M., Kuseler, T.: HXT: a collection of tools for processing xml with Haskell (2016). https://github.com/UweSchmidt/hxt
Scott, E., Johnstone, A.: Gll parsing. Electron. Notes Theoret. Comput. Sci. 253(7), 177–189 (2010)
Scott, E., Johnstone, A.: Gll parse-tree generation. Sci. Comput. Program. 78(10), 1828–1844 (2013)
Tomita, M.: Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer Academic Publishers, Norwell (1985)
Tomita, M.: Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, vol. 8. Springer Science & Business Media, New York (1985)
Zhu, Z., Ko, H., Martins, P., Saraiva, J., Hu, Z.: Biyacc: roll your parser and reflective printer into one. In: Proceedings of the 4th International Workshop on Bidirectional, L’Aquila, Italy, 24 July 2015, pp. 43–50 (2015)
Zhu, Z., Ko, H.-S., Zhang, Y., Martins, P., Saraiva, J., Hu, Z.: Unifying parsing and reflective printing for fully disambiguated grammars. New Gener. Comput. 38(3), 423–476 (2020). https://doi.org/10.1007/s00354-019-00082-y
Zhu, Z., Zhang, Y., Ko, H.S., Martins, P., Saraiva, J.A., Hu, Z.: Parsing and reflective printing, bidirectionally. In: Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering, SLE 2016, pp. 2–14. ACM (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Macedo, J.N., Saraiva, J. (2020). InDubio: A Combinator Library to Disambiguate Ambiguous Grammars. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2020. ICCSA 2020. Lecture Notes in Computer Science(), vol 12252. Springer, Cham. https://doi.org/10.1007/978-3-030-58811-3_71
Download citation
DOI: https://doi.org/10.1007/978-3-030-58811-3_71
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58810-6
Online ISBN: 978-3-030-58811-3
eBook Packages: Computer ScienceComputer Science (R0)