Geschichte der Programmiersprachen - Friedrich
Contents
1. lt arithmetic expression gt lt term gt lt adding operator gt lt term gt lt arithmetic expression gt lt adding operator gt lt term gt lt term gt lt factor gt lt term gt lt multiplying operator gt lt factor gt lt factor gt lt primary gt lt factor gt lt primary gt lt primary gt lt unsigned integer gt lt variable gt P Naur lt arithmetic expression gt 1928 lt multiplying operator gt x lt adding operator gt 1P Naur Ed Revised Report on the Algorithmic Language ALGOL 60 Communicat Associat Comput Mach 6 1 1963 pp 1 17 Numer Math 4 1963 pp 420 453 Geschichte der Programmiersprachen 6 8 Graphische Darstellungen e Kontextfreie Grammatiken erlauben eine graphische Darstellung der Satzstruktur Programmstruktur als Ableitungsbaum Parse tree Die Bl tter sind mit terminalen Symbolen die brigen Knoten mit nichtterminalen Symbolen markiert Der Baum gibt die Struktur gem der Grammatik wieder z B den Operatorenvorrang Unwesentlich verschiedene Ableitungen f hren zum gleichen Baum Gibt es zu einer Zeichenfolge zwei unterschiedliche Ableitungsb ume so ist die Grammatik mehrdeutig e Nicht alle nichtterminalen Symbole die in einer Ableitung auftreten sind zum Verst ndnis der abgeleiteten Zeichenkette erforderlich Der abstrak te Syntaxbaum konzentriert sich auf das W2. 1976 pp 191 276 Geschichte der Programmiersprachen 6 16 W Grammars Notations e Metaproductions The nonterminals of metaproductions called metanotions are writ ten in uppercase letters Their terminal strings the so called protonotions consist of lower case characters with blanks added to improve readability PLAIN int real bool MODE PLAIN ref MODE e Hyperrules A hyperrule is a blueprint to create context free productions ref MODE assignation ref MODE destination becomes symbol MODE source e Lists of identifiers lists of parameters etc ALPHA a bj c 3 Z NOTION ALPHA NOTION ALPHA NOTION list NOTION NOTION list comma symbol NOTION Geschichte der Programmiersprachen 6 17 W Grammar Defining Expressions e Hyperrules MODE PRIORITY formula LMODE PRIORITY operand LMODE and RMODE giving MODE PRIORITY operator RMODE PRIORITY plus one operand MODE PRIORITY operand MODE PRIORITY formula MODE PRIORITY plus one operand MODE expression MODE PRIORITY operand e Metaproductions LMODE MODE RMODE MODE PRIORITY priority NUMBER Report Sect 8 4 simplified Geschichte der Programmiersprachen 6 18 W Grammar Defining Expressions Cont d e Metaproductions PRIORITY priority NUMBER NUMBER one TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TWO one plus one THREE TWO plus o
3. Anmerkungen zur Geschichte der Programmiersprachen Prof Dr Hans J Schneider Department Informatik Informatik 2 Friedrich Alexander Universit t Erlangen N rnberg Wintersemester 2011 12 I Die fr he Geschichte der Programmiersprachen II Grunds tzliche Untersuchungen 6 Formale Definition der Syntax 7 Ans tze zur Compilerentwicklung 8 Typsicherheit Orthogonalit t Effizienz 9 Automatisiserung der Compilerentwicklung III Beherrschung gro er Systeme IV Erg nzungen Hans J Schneider 2011 Overview e The first languages were defined by English prose Advantage Easy to read Disadvantage Prone to ambiguities and misunderstanding e First approach to formal syntax definition Algol 60 Backus developed a notation based on Chomsky s contextfree gram mars that allow efficient parsing algorithms Each definition consisted of three sections Syntax Examples Se mantics e Static semantics Syntactic properties that are not contextfree were described under the heading Semantics In the literature this decision led to the misunderstandable noti on of static semantics since these semantic properties could be checked at compile time e Van Wijngaarden and his group extended the definition to include non contextfree properties Geschichte der Programmiersprachen 6 1 Definition of Fortran Expressions By repeated use of the followin
4. 1993 Geschichte der Programmiersprachen 6 11 Lexikalische Struktur in Fortran und C e Das urspr ngliche FORTRAN ist ein Beispiel wo Scanner und Parser nicht getrennt werden k nnen DO 99 I 1 10 DO 99 I 1 10 entsprechen den PASCAL Formulierungen D099I 1 10 for I 1 to 10 do Die Definition in C zeigt das Problem auf Blanks horizontal and vertical tabs newlines formfeeds and comments collectively white space are ignored except as they separate to kens Some white space is required to separate otherwise adjacent iden tifiers keywords and constants If the input stream has been separated into tokens up to a given character the next token is the longest string of characters that could constitute a token B W Kernighan D M Ritchie The C programming language ANSI Standard C Prentice Hall Englewood Cliffs N J 1988 Geschichte der Programmiersprachen 6 12 Cobol Syntaxbeschreibung e For some languages such as Cobol and PL I much greater conciseness of specification can be achieved by using a two dimensional layout whereby alternatives may be listed vertically within a large pair of braces Square brackets indicate optionality and denotes arbitrary repetition of the preceding unit e Beispiele COBOL ADD PL I Loop D constant constant u TO able variable variable GIVING TO expression BY expression hil j BY expression TO expression wh
5. ed however 1924 2007 A J Perlis K Samelson Preliminary Report International Algebraic Language Comm Assoc Comput Mach 1 12 1958 pp 8 22 2J W Backus The syntax and semantics of the proposed international algebraic language of the Zurich ACM Gamm conference Proc Int Conf Information Processing Oldenbourg Miinchen 1960 pp 125 132 Geschichte der Programmiersprachen 6 6 Backus Naur Form Konzept e Die Backus Naur Form anfangs auch Backus Normal Form entspricht den kontextfreien Grammatiken Die Produktionen werden durch meta linguistische Formeln codiert e Bausteine Sequences of characters enclosed in the brackets lt gt represent meta linguistic variables whose values are sequences of symbols The marks and are metalinguistic connectives Any mark in a formula which is not a variable or a connective de notes itself Juxtaposition of marks and or variables in a formula signifies juxta position of the sequences denoted e Bedeutung der expliziten Verkn pfungen bedeutet is defined as bedeutet or D E Knuth Backus Normal Form vs Backus Naur Form Communicat Assoc Comp Mach 7 12 1964 pp 735 736 2P Naur Ed Report on nthe algorithmic language ALGOL 60 Numerische Mathematik 2 1960 pp 106 136 Geschichte der Programmiersprachen 6 7 Backus Naur Form Beispiel e Definition arithmetischer Ausdriicke
6. esentliche e Anmerkung Die bersetzung zwischen beiden Darstellungen kann durch Graphersetzungsregeln formal beschrieben werden Geschichte der Programmiersprachen 6 9 Beispiel zur graphischen Darstellung ar expr ar expr add opt term ar expradd opt term term mulopt factor term factor factor primary factor primary primary var primary var uns nt err ee EN mon var var ant var var Geschichte der Programmiersprachen 6 10 Lexikalische Struktur e The lexical structure of a programming language i e the structure of its words or tokens can be considered separately from syntactic structure although in some cases it is an inextractable part of syntax e Typische Bausteinkategorien Schl sselw rter Konstanten Literale Sonderzeichen Operatoren Trennzeichen usw Bezeichner Identi fier e Probleme und L sungen FORTRAN Keine Unterscheidung zwischen Schl sselw rtern und Be zeichnern Arcor 60 Schl sselw rter fett gedruckt bzw in Apostroph einge schlossen Sp ter Schl sselw rter sind reservierte Zeichenfolgen Anfangs waren Bezeichner auf eine maximale L nge beschr nkt oder nur die ersten sechs bzw acht Zeichen dienten der Unterscheidung e Die saubere Trennung erlaubt die separate Konstruktion von Scanner und Parser 1K C Louden Programming Languages Principles and Practice PWS KENT Publ Boston
7. g rules all permissible expressions may be derived 1 Any fixed point floating point constant variable or subscripted varia ble is an expression of the same mode Thus 3 and 1 are fixed point expressions and ALPHA and A I J K are floating point expressions If E is an expression and if its first character is not or then E and E are expressions of the same mode as E Thus A is an expression but A is not If E is an expression then E is an expression of the same mode as E Thus A A A etc are expressions If E and F are expressions of the same mode and if the first character of F is not or then E F E F E F and E F are expressions of the same mode Thus A B and A B are not expressions 1 Aus dem ersten FORTRAN Manual 1956 zitiert nach J W Backus The history of Fortran I II and III ACM SIGPLAN Not 13 8 1978 pp 165 180 Geschichte der Programmiersprachen 6 2 Definition of Fortran Subscripts e Subscripts General form Let v represent any fixed point variable and c or c any unsigned fixed point constant Then a subscript is an expression of one of the forms Vv vtc c v tc C V C cx V C C V The symbol denotes multiplication The variable v must not itself be subscripted e Subscripted variables General form A fixed or floating point variable followed by parentheses enclosing 1 2 or 3 subscripts separated by commas Example
8. hmetic expression gt lt term gt lt adding operator gt lt term gt e Disadvantage obscures left associativity of operators e Alternatives are often used to define optional substructures lt if statement gt if lt condition gt then lt statement gt if lt condition gt then lt statement gt else lt statement gt replaced by lt if statement gt if lt condition gt then lt statement gt else lt statement gt Geschichte der Programmiersprachen 6 15 W Grammars e A W grammar consists of two finite sets of rules the metaproductions and the hyperrules These combine to permit the formation of a potenti ally infinite set of productions which are used to define the syntax and the context sensitive requirements e Metaproductions Metaproductions are context free productions The nonterminals of metaproductions are called metanotions Their terminal strings are called protonotions e Hyperrules A hyperrule is a blueprint from which context free productions can be obtained by replacing each metanotion by a protonotion derived from the metaproductions In making this substitution all occurrences of the same metanotion in the hyperrule must be replaced by the same protonotion 1A van Wijngaarden et al Report on the Algorithmic Language Algol 68 Numer Math 14 1969 pp 79 218 2M Marcotty et al A sampler of formal definitions ACM Comput Surveys 8 2
9. ile expression expression e I think it is fair to say that the COBOL syntactic philosophy e g few verbs with many options per verb simply could not have been carried through if we had used BNF from the beginning F G Pagan Formal Specification of Programming Languages A Panorama Primer Prentice Hall Englewood Cliffs N J 1981 2J E Sammet The early history of COBOL ACM SIGPLAN Not 13 8 1978 pp 121 161 Geschichte der Programmiersprachen 6 13 Extended Backus Naur Form e Some drawbacks of the BNF Recursive BNF rules are often used to define repetition of substruc tures Alternatives are often used to define optional substructures e Defining Pascal N Wirth developed a variant of the BNF called Extended BNF EBNF to avoid these drawbacks e Changes for more convenient notation Nonterminals no longer enclosed in lt gt N Wirth Terminals enclosed in 1934 e Adopted as a standard by the International Organization for Standardi zation ISO IEE 14977 IK Jensen N Wirth Pascal User Manual and Report Springer Berlin 1974 Geschichte der Programmiersprachen 6 14 Extended Backus Naur Form Details e Recursive BNF rules are often used to define repetition of substructures lt arithmetic expression gt lt term gt lt arithmetic expression gt lt adding operator gt lt term gt replaced by lt arit
10. ne e Hyperrules MODE PRIORITY NINE plus one operand MODE primary MODE primary MODE constant ref MODE variable open symbol MODE expression close symbol Geschichte der Programmiersprachen 6 19 Generative Power of W Grammars e A finite set of attributes can be treated by increasing both the set of nonterminal symbols and the set of productions Construct new symbols that consist of a symbol together with special values of the attributes Copy the productions for each valid combination of the new symbols e Sintzoff could show that the generative power of W grammars is the same as that of unrestricted Chomsky grammars e The word problem is undecidable e Koster proposed a restricted syntax IM Sintzoff Existence of a van Wijngaarden syntax for every recursively enumerable set Annales Soc Sci Bruxelles II 1967 pp 115 118 2C H A Koster Affix grammars in J E L Peck Ed Algol 68 implementation North Holland Amsterdam 1971 pp 95 109 Geschichte der Programmiersprachen 6 20 Extensible Languages e Galler Perlis proposed an extension to ALGOL 60 for adding new data types and operators to the language e Irons New syntactic constructs can be introduced in a program by de fining the syntax similar to an attributed version of BNF and the semantics similar to a procedure body using the base language including the extensions up to this one e Such an e
11. s ACI K 3 BETA 5 J 2 K 2 L Noe cit Geschichte der Programmiersprachen 6 3 Chomsky Grammatiken e Noam Chomsky fiihrt 1956 im Zusammenhang mit linguistischen Frage stellungen den Begriff der Phrase structure grammar ein e 1959 formalisiert er diese auf der Basis der Semi Thue Systeme und de finiert eine Hierarchie von Grammatiken und Sprachen e A phrase structure grammar consists of a finite set of rewriting rules of the form Y where amp and w are strings of symbols It contains a special initial symbol S standing for sentence and a boundary symbol indicating the beginning and end of sen tences Some of the symbols of the grammar stand for words and morphemes grammatically significant parts of words These constitute the terminal vocabulary Other symbols stand for phrases and constitute the nonterminal vocabulary S is one of these standing for the longest phrase N Chomsky 1928 IN Chomsky Three models for the description of language IRE Transactions on Information Theory 2 1956 pp 113 124 N Chomsky On certain formal properties of grammars Information and Control 2 1959 pp 137 167 Geschichte der Programmiersprachen 6 4 Chomsky Hierarchie e Die Chomsky Hierarchie schr nkt schrittweise die Form der zul ssigen Ersetzungsregeln Produktionen ein Restriction 1 If y gt y then there are A y1 Y2 w such
12. that y 91 Ayo Y y wypa and w I Restriction 2 If y gt w then there are A y1 Y2 w such that y1 Ayo w piw w I but A gt w Restriction 3 If y w then there are A 1 Y2 w a B such that y Avo Y piwp w I A gt w but w aB or ws a e Die unbeschr nkten Grammatiken entsprechen den Semi Thue Sys temen das Wortproblem ist unentscheidbar Einschr nkung 1 macht das Wortproblem entscheidbar aber mit ex ponentiellem Aufwand Einschr nkung 2 kontextfreie Grammatiken erlaubt Algorithmen mit polynomialem Zeitbedarf Einschr nkung 3 entspricht den regul ren Ausdr cken endlichen Au tomaten 1N Chomsky On certain formal properties of grammars Information and Control 2 1959 pp 137 167 Geschichte der Programmiersprachen 6 5 Das Entstehen der BNF e Ende 1958 erscheint eine erste Vorversion von Algol International Alge braic Language e Im November 1959 stellt J W Backus auf der ersten internationalen Kon ferenz ber Information Processing in Paris ein Konzept zur formalen Beschreibung der Sprache vor e Backus There must exist a precise description of those sequences of symbols which constitute legal IAL programs For every legal program there must be a pre cise description of its meaning the process or transformation which it describes if any Only the description of legal programs has been TIW B ckus complet
13. w programmers for the machine capacity we have Therefore it is desirable to eliminate the need for professional pro grammers for handling applications To put every person in communication with the computer is to speed up and make easier his ability to get his problem solved It was for just such reasons that systems such as FORTRAN were developed I simply want to extend this concept to its furthest limits Every application area has its own jargon and the less a user has to jump out of this the better off he is Only by encompassing all jargon areas which would mean all of English can we achieve this e Using English definitely involves the requirement for the computer to query the user if there is any doubt 1J E Sammet The use of English as a programming language Communicat Associat Comput Mach 9 1966 pp 228 230 Geschichte der Programmiersprachen 6 23
14. xtension is similar to a procedure declaration but it allows the programmer to use a more appropriate syntax instead of the fixed syntax of a procedure call e g find X in LIST instead of find X LIST e Irons s system treated the extensions similar to precompiled procedures and implemented the extended syntax by bootstrapping B A Galler A J Perlis A proposal for definitions in ALGOL Communicat Associat Comput Mach 10 4 1967 pp 204 219 E T Irons Experience with an extensible language Communicat Associat Comput Mach 13 1 1970 pp 31 40 Geschichte der Programmiersprachen 6 21 Example of an Extension e Example slightly modified Right hand assignment e v lt rhd ass gt lt e expression gt gt lt v identifier gt v e lt rhd ass gt Nonterminal symbol to be defined lt e expression gt e must satisfy the definition of an expression v e The semantics is the same as that of the usual assignment e Many people felt that a programming language should be extensible such that it may be used in another application area but only very few im plementations are known Geschichte der Programmiersprachen 6 22 Sammet The Use of English as a Programming Language e When I say that I wish to use English as a programming language I very definitely include mathematics or any other scientific notation e Reasons why to use English There are too fe
Download Pdf Manuals
Related Search