A Notation for Expressing Restricting Conditions on a Context-Free Grammar
Degree GrantorUniversity of Canterbury
Degree NameBachelor of Science with Honours
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 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 , 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.
- Engineering: Reports