OASIcs.SLATE.2018.11.pdf
- Filesize: 389 kB
- 8 pages
Document
Non-LR(1) Precedence Cascade Grammars (Short Paper)
Author
José-Luis Sierra 
-
Part of:
Volume:
7th Symposium on Languages, Applications and Technologies (SLATE 2018)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Languages, Applications and Technologies (SLATE) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-13
File
Document Identifiers
Author Details
Cite AsGet BibTex
José-Luis Sierra. Non-LR(1) Precedence Cascade Grammars (Short Paper). In 7th Symposium on Languages, Applications and Technologies (SLATE 2018). Open Access Series in Informatics (OASIcs), Volume 62, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.SLATE.2018.11
https://doi.org/10.4230/OASIcs.SLATE.2018.11
Abstract
Precedence cascade is a well-known pattern for writing context-free grammars (CFGs) that model the syntax of expression languages. According to this method, precedence levels are represented by non-terminals, and operators' attributes are used to write syntax rules properly. In most cases, the resulting precedence cascade grammar (PCG) has neat properties that facilitate its implementation. In particular, many PCGs are LR(1) grammars, which serve as input for conventional bottom-up parser generators. However, for some cumbersome operator tables the method does not produce such neat grammars. This paper focuses on these cumbersome operator tables by identifying several conditions leading to non-LR(1) PCGs.
Subject Classification
ACM Subject Classification
- Software and its engineering → Syntax
Keywords
- grammarware
- expression grammars
- grammar patterns
- grammar ambiguity
- LR grammars
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Annika Aasa. Precedences in specifications and implementations of programming languages. Theoretical Computer Science, 142(1):3-26, 1995. URL: http://dx.doi.org/10.1016/0304-3975(95)90680-J.
- Alfred. V. Aho, Sethi Johnson, and Jeffrey D. Ullman. Deterministic parsing of ambiguous grammars. In ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pages 1-21, 1973. URL: http://dx.doi.org/10.1145/512927.512928.
-
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 2nd edition, 2006.
-
Nils Anders Danielsson and Ulf Norell. Parsing mixfix operators. In 20th International Conference on Implementation and Application of Functional Languages, pages 80-99, 2011.
- Pierre Deransart, AbdelAli Ed-Dbali, and Laurent Cervoni. Prolog syntax. In Prolog: The Standard: Reference Manual, pages 221-238. Springer, 1996. URL: http://dx.doi.org/10.1007/978-3-642-61411-8_9.
-
Donald E. Knuth. On the translation of languages from left to right. Information and Control, 8(6):607-639, 1965.
- Wafik Boulos Lotfallah. Characterizing unambiguous precedence systems in expressions without superfluous parentheses. International Journal of Computer Mathematics, 86(1):1-20, 2009. URL: http://dx.doi.org/10.1080/00207160802166499.
-
Kenneth C. Louden. Compiler Construction: Principles and Practice. PWS Publishing, 1997.
-
Simon Marlow, editor. Haskell 2010 Language Report. Haskell Community, 2010.
-
Martin Odersky. The Scala language specification, version 2.9. Technical report, Programming Methods Laboratory, EPFL, 2014.
- Simon L. Peyton Jones. Parsing distfix operators. Communications of the ACM, 29(2):118-122, 1986. URL: http://dx.doi.org/10.1145/5657.5659.
-
Kjell Post, Allen Van Gelder, and James Kerr. Deterministic parsing of languages with dynamic operators. In International Symposium on Logic Programming, pages 456-472, 1993.
-
Ravi Sethi. Programming Languages: Concepts and Constructs. Addison-Wesley, 1989.
-
Lucian Radu Teodorescu, Vlad Dumitrel, and Rodica Potolea. Flexible operators in Sparrow. International Journal of Research in Engineering and Technology, 3(17):40-45, 2014.