Van Roy Peter, Haridi Seif Concepts, Techniques, and Models of Computer Programming

Podobne

Cytat

Do celu tam się wysiada. Lec Stanisław Jerzy (pierw. de Tusch-Letz, 1909-1966)
A bogowie grają w kości i nie pytają wcale czy chcesz przyłączyć się do gry (. . . ) Bogowie kpią sobie z twojego poukładanego życia (. . . ) nie przejmują się zbytnio ani naszymi planami na przyszłość ani oczekiwaniami. Gdzieś we wszechświecie rzucają kości i przypadkiem wypada twoja kolej. I odtąd zwyciężyć lub przegrać - to tylko kwestia szczęścia. Borys Pasternak
Idąc po kurzych jajach nie podskakuj. Przysłowie szkockie
I Herkules nie poradzi przeciwko wielu.
Dialog półinteligentów równa się monologowi ćwierćinteligenta. Stanisław Jerzy Lec (pierw. de Tusch - Letz, 1909-1966)

[ Pobierz całość w formacie PDF ]
.2 gives the data structures: the single-assignment store andits contents, partial values and dataflow variables. Section 2.3 defines the kernel language syntax. Section 2.4 defines the kernel language semantics in terms of a simpleabstract machine.The semantics is designed to be intuitive and topermit straightforward reasoning about correctness and complexity." Section 2.5 defines a practical programming language on top of the kernellanguage." Section 2.6 extends the declarative model with exception handling, whichallows programs to handle unpredictable and exceptional situations." Section 2.7 gives a few advanced topics to let interested readers deepen theirunderstanding of the model.Copyright � 2001-3 by P.Van Roy and S.Haridi.All rights reserved.2.1 Defining practical programming languages 33[f u n { F a c t N } \n i f sequence of N = = 0 t h e n 1 \n e l s echaracters N * { F a c t N - 1 } e nd \n e n d]Tokenizer[ fun { Fact N } if N == 0 thensequence of else N * { Fact N - 1 } endtokens end ]ParserfunFact N ifparse treerepresentinga statement == 1 *N 0 N Fact-N 1Figure 2.1: From characters to statements2.1 Defining practical programming languagesProgramming languages are much simpler than natural languages, but they canstill have a surprisingly rich syntax, set of abstractions, and libraries.This isespecially true for languages that are used to solve real-world problems, which wecall practical languages.A practical language is like the toolbox of an experiencedmechanic: there are many different tools for many different purposes and all toolsare there for a reason.This section sets the stage for the rest of the book by explaining how wewill present the syntax ( grammar ) and semantics ( meaning ) of practical pro-gramming languages.With this foundation we will be ready to present the firstcomputation model of the book, namely the declarative computation model.Wewill continue to use these techniques throughout the book to define computationmodels.2.1.1 Language syntaxThe syntax of a language defines what are the legal programs, i.e., programs thatcan be successfully executed.At this stage we do not care what the programs areactually doing.That is semantics and will be handled in the next section.Copyright � 2001-3 by P.Van Roy and S.Haridi.All rights reserved.34 Declarative Computation ModelGrammarsA grammar is a set of rules that defines how to make sentences out of words.Grammars can be used for natural languages, like English or Swedish, as well asfor artificial languages, like programming languages.For programming languages, sentences are usually called statements and words are usually called tokens.Just as words are made of letters, tokens are made of characters.This gives ustwo levels of structure:statement ( sentence ) = sequence of tokens ( words )token ( word ) = sequence of characters ( letters )Grammars are useful both for defining statements and tokens.Figure 2.1 givesan example to show how character input is transformed into a statement.Theexample in the figure is the definition of Fact:fun {Fact N}if N==0 then 1else N*{Fact N-1} endendThe input is a sequence of characters, where � � represents the space and �\n�represents the newline.This is first transformed into a sequence of tokens andsubsequently into a parse tree.The syntax of both sequences in the figure is com-patible with the list syntax we use throughout the book.Whereas the sequencesare flat , the parse tree shows the structure of the statement.A program thataccepts a sequence of characters and returns a sequence of tokens is called a to-kenizer or lexical analyzer.A program that accepts a sequence of tokens andreturns a parse tree is called a parser.Extended Backus-Naur FormOne of the most common notations for defining grammars is called ExtendedBackus-Naur Form (EBNF for short), after its inventors John Backus and Pe-ter Naur.The EBNF notation distinguishes terminal symbols and nonterminalsymbols.A terminal symbol is simply a token.A nonterminal symbol representsa sequence of tokens.The nonterminal is defined by means of a grammar rule,which shows how to expand it into tokens.For example, the following rule definesthe nonterminal digit :digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9It says that digit represents one of the ten tokens 0, 1,., 9.The symbol | is read as or ; it means to pick one of the alternatives.Grammar rules canthemselves refer to other nonterminals.For example, we can define a nonterminalint that defines how to write positive integers:int ::= digit { digit }Copyright � 2001-3 by P.Van Roy and S.Haridi.All rights reserved.2.1 Defining practical programming languages 35- Is easy to read and understandContext-free grammar(e.g., with EBNF)- Defines a superset of the language+- Expresses restrictions imposed by the languageSet of extra conditions (e.g., variables must be declared before use)- Makes the grammar context-sensitiveFigure 2.2: The context-free approach to language syntaxThis rule says that an integer is a digit followed by zero or more digits.Thebraces {.} mean to repeat whatever is inside any number of times, includingzero.How to read grammarsTo read a grammar, start with any nonterminal symbol, say int.Reading thecorresponding grammar rule from left to right gives a sequence of tokens accordingto the following scheme:" Each terminal symbol encountered is added to the sequence." For each nonterminal symbol encountered, read its grammar rule and re-place the nonterminal by the sequence of tokens that it expands into." Each time there is a choice (with |), pick any of the alternatives.The grammar can be used both to verify that a statement is legal and to generatestatements.Context-free and context-sensitive grammarsAny well-defined set of statements is called a formal language, or language forshort.For example, the set of all possible statements generated by a grammarand one nonterminal symbol is a language.Techniques to define grammars canbe classified according to how expressive they are, i.e., what kinds of languagesthey can generate.For example, the EBNF notation given above defines a class ofgrammars called context-free grammars.They are so-called because the expansionof a nonterminal, e.g., digit , is always the same no matter where it is used.For most practical programming languages, there is usually no context-freegrammar that generates all legal programs and no others.For example, in manylanguages a variable has to be declared before it is used.This condition cannotbe expressed in a context-free grammar because the nonterminal that uses theCopyright � 2001-3 by P.Van Roy and S.Haridi.All rights reserved.36 Declarative Computation Model* +24+ *3 4 2 3Figure 2.3: Ambiguity in a context-free grammarvariable must only allow using already-declared variables.This is a context de-pendency.A grammar that contains a nonterminal whose use depends on thecontext where it is used is called a context-sensitive grammar.The syntax of most practical programming languages is therefore defined intwo parts (see Figure 2.2): as a context-free grammar supplemented with a set ofextra conditions imposed by the language.The context-free grammar is kept in-stead of some more expressive notation because it is easy to read and understand [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

trendy-girls.htw.pl