A Notation for Expressing Restricting Conditions on a Context-Free Grammar
Type of content
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
Journal Title
Journal ISSN
Volume Title
Language
Date
Authors
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.