Abstract
The paper gives another understanding of the two-level grammar formalism: any two-level grammar can be splitted into two parts — a context-free "syntax" and an equational "semantics". It has been shown that in the case of a repetition-free and regular based two-level grammar one can always solve the equations assigned to each derivation of the resulting CF grammar. This suggests an approach to the parsing problem of two-level grammars based on well known methods for CF grammars and the algorithm presented. The approach may occur efficient however, only if some restrictions are imposed on two-level grammars. One sort of restrictions we have discussed in the paper (repetition-free and regular based grammars). Others should result from the requirements of programming languages. For example, one obvious requirement is that two-level grammars should be (semanticaly) unambiguous, i.e., here — in terms of the corresponding CF grammars and equations — that each set of equations has at most one solution.
It could be promising to experiment with (fragments of) ALGOL 68 in order to better understand the described method, its complexity and feasibility with respect to the two-level programming language definitions.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cleaveland, J.C., Uzgalis, R.C.: Grammars for programming languages, Elsevier, New York 1977
Dembiński, P., Małuszyński, J.: Attribute grammars and two-level grammars: a unifying approach, Proc. of the MFCS'78 Symposium, Lecture Notes in Computer Sc., 64 143–154, Springer-Verlag 1978
Deussen, P.: A decidability criterion for Van Wijngaarden grammars, Acta Informatica 5(4), 353–375, 1975
Hesse, W.: Vollstaendige formale Beschreibung von Programmiersprachen mit zweischichtigen Grammetiken, Bericht 7623 TU Muenchen
Knuth, D.E.: Semantics of context-free languages, Math. Systems Theory. 2(2), 127–145
Koster, C.H.A.: Affix grammars, Proc. of the IFIP Working Conf. on ALGOL 68 Implementation, 95–103, North-Holland 1972
Lewis, P.H., Rosenkrantz, D.J., Stearns, R.E.: Attributed translations, JCSS 9, 279–307, 1974
Wegner, L.: On parsing two-level grammars, Bericht 7/78, TU Graz Institut fuer Informationsverarbeitung
Van Wijangaarden, A. et al.: Revised report on the algorithmic language ALGOL 68, Acta Informatica 5(1–3), 1–236, 1975
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1979 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dembiński, P., Małuszyński, J. (1979). Two level grammars: CF-grammars with equation schemes. In: Maurer, H.A. (eds) Automata, Languages and Programming. ICALP 1979. Lecture Notes in Computer Science, vol 71. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-09510-1_14
Download citation
DOI: https://doi.org/10.1007/3-540-09510-1_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-09510-1
Online ISBN: 978-3-540-35168-9
eBook Packages: Springer Book Archive