A Notation for Expressing Restricting Conditions on a Context-Free Grammar

Type of content
Theses / Dissertations
Publisher's DOI/URI
Thesis discipline
Degree name
Bachelor of Science with Honours
Publisher
University of Canterbury. Computer Science
Journal Title
Journal ISSN
Volume Title
Language
Date
1977
Authors
Lines, S. A.
Abstract

Context-Free grammars have several features which make them suitable for defining programming languages. For instance, such grammars are: “recursive, have relatively simple and well understood recognizers, and a readable notation”. However, no Context-Free grammar can completely define a language such as ALGOL 60. In the REVISED REPORT ON THE ALGORITHMIC LANGUAGE ALGOL 60[6] the language is defined by a Context-Free grammar and a set of restricting conditions. The main characteristic of all these restrictions is shown in Appendix A to be that two substrings in a sentence in the language must be either identical or different. By defining an Extended Context-Free Grammar based on the Context-Free grammar of [6], and having additionally a facility for syntactically expressing this class of restricting conditions, we endeavour to completely define a programming language by the Extended Context-Free Grammar. We take the view presented by Strachey that “it is the business of the syntax… To determine if any particular piece of text is a program in the language... And that of the semantics to... Determine what the outcome of any well-formed program should be.”. we believe that our Extended Context-Free Grammar fully defines the syntax of AGOL 60. The basis of the Extended Context-Free grammar remains the original Context-Free grammar. Thus many algorithms developed for parsins Context-Free languages can be used as the basis of any parser for an Extended Context-Free language.

Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights
Copyright S. A. Lines