Articles
| Open Access |
BEYOND OPERATOR-PRECEDENCE GRAMMARS AND LANGUAGES: A SURVEY AND FUTURE DIRECTIONS
Matteo Reghizzi , Department Of Electronics, Information And Bioengineering, Polytechnic Di Milano, Italy Ludovica Romano , Department Of Electronics, Information And Bioengineering, Polytechnic Di Milano, ItalyAbstract
Operator-precedence grammars and languages are an important class of grammars that have been widely studied in computer science and linguistics. However, there are certain limitations of operator-precedence grammars and languages that restrict their applicability to certain types of languages. In this paper, we present a survey of research on operator-precedence grammars and languages, and then discuss some recent developments in the field that go beyond operator-precedence grammars and languages. Specifically, we focus on the use of higher-order grammars and constraint-based grammars, which provide greater expressive power and can handle a wider range of languages than operator-precedence grammars and languages.
Keywords
Operator-precedence grammars, context-free grammars, parsing algorithms
References
S. CrespiReghizzi et al. Algebraic properties of operator precedence languages Inf. Control (1978)
S. CrespiReghizzi et al. Operator precedence and the visibly pushdown property J. Comput. Syst. Sci. (2012)
A. Barenghi et al.Parallel parsing made practicalSci. Comput. Program.(2015)
D. Mandrioli et al.Generalizing input-driven languages: theoretical and practical benefits
Comput. Sci. Rev. (2018)
D. KnuthA characterization of parenthesis languagesInf. Control (1967)
P. CaronFamilies of locally testable languagesTheor. Comput. Sci.(2000)
S. CrespiReghizzi et al.Toward a theory of input-driven locally parsable languagesTheor. Comput. Sci. (2017)
F.M. Luque et al.PAC-learning unambiguous k, l-NTS<= languages
R. YoshinakaIdentification in the limit of k, l-substitutable context-free languages
M. Kutrib et al.Tinput-driven pushdown, counter, and stack automataFundam. Inform. (2017)
N. Wirth et al.EULER: a generalization of ALGOL and it formal definition: part 1Commun. ACM (1966)
A. Borsotti et al.Fast deterministic parsers for transition networksActa Inform. (2018)
Y. Bar-Hillel et al.On formal properties of simple phrase structure grammarsZ. Phon. Sprachwiss. Kommun.forsch.(1961)
R. McNaughtonParenthesis grammarsJ. ACM (1967)
S. CrespiReghizzi et al.Operator precedence grammars and the noncounting propertySIAM J. Comput. (1981)
Article Statistics
Downloads
Copyright License
Copyright (c) 2023 Matteo Reghizzi, Ludovica Romano
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright and Ethics:
- Authors are responsible for obtaining permission to use any copyrighted materials included in their manuscript.
- Authors are also responsible for ensuring that their research was conducted in an ethical manner and in compliance with institutional and national guidelines for the care and use of animals or human subjects.
- By submitting a manuscript to International Journal of Computer Science & Information System (IJCSIS), authors agree to transfer copyright to the journal if the manuscript is accepted for publication.