PROGRAMMING LANGUAGES Lucian Ilie - Western University
CS342b – winter 2006PROGRAMMING LANGUAGESLucian Iliec 2006 by Lucian Ilie
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1-Introductionwhy study (concepts of) programming languagesclassification of languagesprogramming domainsevaluation criterialevels of programming languagescompilation and interpretation2
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.11.1.1-3General questionsWhy are there so many programming languages?evolution – we’ve learned better ways of doing things over timesocio-economic factors – proprietary interests, commercial advantageorientation toward special purposesorientation toward special hardwarediverse ideas about what is pleasant to use1.1.2What makes a language successful?- easy to learn (BASIC, Pascal, LOGO, Scheme)- easy to express things – easy to use once fluent – ”powerful” (C , CommonLisp, APL, Algol-68, Perl)- easy to implement (BASIC, Forth)- possible to compile to very good (fast/small) code (Fortran)- backing of a powerful sponsor (COBOL, PL/1, Ada, Visual Basic)- wide dissemination at minimal cost (Pascal, Turing, Java)
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.1.34Why do we have programming languages?– what is a language for?- way of thinking– way of expressing algorithms– from the user’s point of view- abstraction of virtual machine– way of specifying what you want the hardware to do without getting downinto the bits– from the implementor’s point of viewKnuth: “Computer Programming is the art of explaining to another humanbeing what you want the computer to do.”
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.1.45Why study programming languages?- help you choose a language– C vs Modula-3 vs C for systems programming– Fortran vs APL vs Ada for numerical computations– C vs Ada vs Modula-2 for embedded systems– Common Lisp vs Scheme vs ML for symbolic data manipulation– Java vs C/CORBA for networked PC programs- make it easier to learn new languages– some languages are similar; easy to walk down family tree– concepts have even more similarity; if you think in terms of iteration, recursion,abstraction (for example), you will find it easier to assimilate the syntax andsemantic details of a new language than if you try to pick it up in a vacuum(analogy to human languages: good grasp of grammar makes it easier to pickup new languages)
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie6- help you make better use of whatever language you use understand obscure features– in C, unions, arrays and pointers, separate compilation, variable number ofarguments, etc.– in Common Lisp, help you understand first-class functions/closures, understand implementation costs – choose between alternative ways of doingthings, based on knowledge of what will be done underneath:– use simple arithmetic equalities (use x*x instead of x**2)– use C pointers or Pascal ”with” statement to factor address calculations– avoid call by value with large data items in Pascal– avoid the use of call by name in Algol 60
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie7 figure out how to do things in languages that don’t support them explicitly– lack of suitable control structures in Fortran IV – use comments and programmer discipline for control structures– lack of recursion in Fortran 77, CSP, etc. – write a recursive algorithmthen use mechanical recursion elimination (even for things that aren’t quite tailrecursive)– lack of named constants and enumerations in Fortran – use variables thatare initialized once, then never changed– lack of modules in C and Pascal – use comments and programmer discipline- prepare for further study in language design or implementation
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.28Classification of languages declarative – what to do? functional (Scheme, ML, pure Lisp, Haskell, FP)– based on lambda calculus– computational model based on recursive definition of functions– a program a function from inputs to outputs logic, constraint-based (Prolog, VisiCalc, RPG)– based on propositional logic– computation is an attempt to find values that satisfy certain specifiedrelationships using goal-directed search through a list of logical rules imperative – how to do? von Neumann (Fortran, Pascal, Basic, C, .)– computing via side effects– statements that influence subsequent computation by changing the valuesof memory object-oriented (Smalltalk, Eiffel, C , Java)– computation interactions among objects
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.3Programming domains- scientific applications- simple data structures, large computations (Fortran, Algol 60)- bussines applications- elaborate reports, storing numbers, arithmetics (Cobol)- artificial intelligence- symbolic computations (Lisp, Prolog)- systems programming- execution efficiency (C)- special purpose languages9
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.410Evaluation of programming languages- programming- development - creation and testing of a program- maintenance - correction and changes after- good program- correct- easy to read / understand- easy to modify1.4.1Criteria- readability / writability- simplicity, orthogonality, control statements (goto), data types and structures (bool, struct), syntax, support for abstraction- reliability – type checking, exception handling- portability – standardization, system independence- generality – wide range of applications- cost – program development, maintenance, execution
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.4.2Language design trade-offs- compilation cost vs execution speed- optimization requires time- reliability vs execution cost- ex: index range checking- readability vs writability- flexibility vs safety11
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.5Brief history of programming languages Zuse’s Pankalkül - 1945- first high level programming language- never implemented- unpublished until 1972 Minimal hardware programming: pseudocodes- late 1940’s and early 1950’s- machine code - tedious and error-prone- somewhat higher-level languages - interpreted- Short Code, UNIVAC “compiling” system FORTRAN (FORmula TRANslating system)- came with IBM 704- first language to be compiled- IBM 704 - floating-point instructions in hardware- end of interpretation- FORTRAN 0 - 1954- FORTRAN I - 1956 - already very efficient12
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie-- I/O, subroutines, if selection, do loopFORTRAN II - 1958- independently compiled subroutinesFORTRAN III - never widely distributedFORTRAN IV - 1960-62FORTRAN 77 standard FORTRAN IV- type declarations, subprograms as parametersFORTRAN 90 - ANSI, 1992 - latest version- new statements, recursiveness, modules,dynamical allocation of arrays, etc. Functional programming: LISP (LISt-Processing language)- interest in AI - mid 1950’s- the need for computers able to process symbolicdata in linked lists- IBM became interested in theorem proving- LISP - 1958, John McCarthy (MIT)- LISP dominated AI applications for 25 years- two descendants widely used now:13
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie14- Scheme and Common Lisp ALGOL 60 (ALGOrithmic Language)- effort to design a universal language- GAMM and ACM against the domination of IBM- ALGOL 58 - generalized FORTRAN- added: the concept of data type, compound statement, etc.- ALGOL 60 - block structure, pass by value/name, recursion, etc.- became (for 20 years) the sole language for publishing algorithms- every imperative language since 1960 owes something to ALGOL 60- never achieved widespread use- BNF notation introduced - now is most commonly used technique fordescribing syntax COBOL - 1960- CBL (Common Bussines Language)- designed for bussines computing- mandated by U.S. Department of Defense- widespread use but little respect BASIC (Beginner’s All-purpose Symbolic Instruction Code)
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie15- designed for introducing programming concepts to non-science students- most important aspect: designed with the idea that terminals would bethe method of for accessing computer PL/I - 1965, IBM- developed for a broad spectrum of application areas- included the best of ALGOL 60, FORTRAN IV, and COBOL 60- too large to be widely used SIMULA 67- introduced by two Norwegians- little impact- important - introduced coroutines and classes Pascal - 1971- descendent of ALGOL 60 - designed by Wirth- designed for teaching programming C - 1972- designed by Dennis Ritchie- descendant of ALGOL 68 (but not only)
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie-16originally designed for system programmingcontributed little to previous knowledge but is has been very successfulappropriate for many application areaslack of complete type checking - liked and disliked PROLOG (PROgramming LOGic) - early 1970’s- based on predicate calculus and resolution- attempt to replace imperative languages - not successful so far Ada (Augusta Ada Byron - the world’s first programmer) - 1970’s-80’s- Department of Defense mandated- history’s largest effort- included most of the concepts in the 1970’s- too large Smalltalk- Alan Kay - first ideas - 1969; versions - 1972, 1980- object-oriented programming- all program units are objects which communicate with each other- promoted also the windowing system
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie C - 1980’s- Bjarne Stroustrup- combines imperative and object-oriented features- is very (and increasingly) popular Java - 1990’s- provides much of the power and flexibility of C - is smaller, simpler, and safer- suitable for web programming17
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.6Development of languages 1950’s- machine language late 50’s and early 60’s- Fortran, Algol, Cobol 60’s- Basic, Pascal late 60’s and early 70’s- abstract data type, concurrent programming 70’s- C, object oriented programming, logic and functional programming 80’s- C , parallel programming 90’s- Java, web programming18
19CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.7Levels of programming languagesHigh level languagesCompilersAssembly languageAssemblerMachine languageCOMPUTER
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie20- machine language - 1111100100000000011001110101000[Goldstine (1972): “While this enumeration is virtually unintelligible to a human, it is exactly what the machine understands.”]
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie- assembly language- low level- names and symbols in place of the codes for machineexample1:2:3:4:5:6:7:.M [0] : 0read (M [1])if M [1] 0 then goto 5goto 7M [3] : M [0] M [1]if M [3] 0 then goto 16writeln(M [1]).21
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie22- high level language- readable familiar notations- portability machine independence(general purpose wide range of problems)- availability of program libraries- consistency checks during implementation that can detect errors[Ritchie (1973): “Although a comprehensive study of the space and time inflation due to the use of C might be interesting, it would be somewhat irrelevant,in that no matter what the results turned out to be, they would not cause usto start writing assembly language.”]
23CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.7.1Gotos vs structured stmts vs procedures vs classesread (x );2: if x 0 thengoto 8;writeln (x );4: read (next );if next x thengoto 4;x : next;goto 2;8: ;read (x );while x 6 0 dobeginwriteln (x );repeatread (next )until next 6 x;x : next;end;readentry; (e )while not endentry (e ) dobeginwriteentry (e );repeatreadentry (f )until not equalentry (e,f );copyentry (e,f );end(a) goto(b) structured stmts (c) proceduresEntry e, f;e.read ( );while not e.end ( ) dobegine.write ( );dof.read ( );while e f;e : f;end(d) classes
24CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.8Compilation and interpretation- compilation- the compiler translates into a target language and then goes away- the target program is the place of control at execution time- interpretation- the interpreter stays around at execution time- it is the place of control during executioninputsource programcompilertarget programoutputsource programinterpreterinputoutput
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie25Compilation- programs - reside in memory and executed in CPU- execution of machine code program:fetch-execute cyclerepeat foreverfetch the instruction pointed by program counterincrement program counter to point next instructiondecode the instructionexecute the instructionend repeat- von Neumann bottleneck - the connection between memory and CPU - instructions are executed faster than movedInterpretation- fetch-execute cycle with high-level statements (no translation)- advantage - easy debugging- disadvantage - execution 10 to 100 times slower
26CS342b – Programming Languages – winter 2006 – c 2006 by Lucian IlieHybrid systems - most systemssource programtranslatorintermediate codeintermediate codeinterpreteroutputinputexampleJava: intermediate code byte code - portability- some systems: byte code machine code (faster execution)examplesometimes - both compiler and interpreter- interpreter - develop and debug- compiler - at the end to increase execution speed
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie1.8.1Compilation phases- front end (analyze source)- scanning- parsing- semantic analysis- back end (build target)- intermediate code generation- code improvement- target code generation27
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2-Syntaxlexical syntaxregular grammarsfinite automatascanningconcrete syntaxcontext-free grammarsBNF formparsing – top-down and bottom-up28
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie29- syntax - describes the form of programs- semantics - describe the meaning of programs- more difficult- the state of the art: formal syntax and informal semantics2.1Lexical syntaxtokens - basic building blocks of programs- the source program (stream of characters) is read from left to right andgrouped into tokens sequences of characters having a collective meaningexamples of tokens: keywords, identifiers, numbers, punctuation marks, etc.examplethe character sequenceb b 4 ais represented by the token sequencenameb nameb number4 namealexical syntax - specifies the way tokens should be written
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.1.1Specifying lexical syntaxregular grammar – the tool for specifying lexical syntax-a set of nonterminals (symbols, letters)a set of terminals (symbols, letters)a nonterminal chosen as the starting symbola set of productions of the form:A :: aB, or A :: a s.t. A, B are nonterminals and a is terminal30
31CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 1nonterminals: S, Aterminals: 0, 1starting symbol: Sproductions: S :: 0S 0AA :: 1A 1′′:: ′ means “can be” ′ means “or”derivation: S 0S 00S 000A 0001A 00011generated words words derived (obtained) from the starting symbol byapplying productions- for example 1: the set of generated words (language) is. . . 1} n, m 1}{0n1m n, m 1} {00. . . 0} 11 {z {znm
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 2nonterminals: integerterminals: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9starting symbol: integerproductions: integer :: 0 1 2 3 4 5 6 7 8 9integer :: 0 integer 1 integer · · · 9 integerderivation: integer 7 integer 73 integer 73832
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 3nonterminals: letter, digit, name, wordterminals: a, b, . . . , z, A, B, . . . , Z, 0, 1, . . . , 9starting symbol: nameproductions: letter :: a · · · z A · · · Zdigit :: 0 1 · · · 9word :: letter digit letter word digit wordname :: letter word letterderivation:name letter word X word X digit X5example 4C comments33
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.1.234Recognizing lexical syntax- this is lexical analysis or scanning- the scanners are finite automata - machine counterpart of regular grammarsregular grammars - generate wordsfinite automata - accept wordsfinite automaton:-an alphabeta set of statesa state chosen as the initial statea subset of final statesa transition mapping which maps pairs (state, letter) to states
35CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 1b0a12a3caccepted words (language) words that take the automaton from theinitial state to a final one- the automaton in example 1 accepts the language: ab(cb) a
36CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample ,.,zA,.,Zrejecta,.,zA,.,Z0,.,90,.,9accepts: identifiers and integersscanningregular grammar - specifies the right stringsfinite automaton (the scanner) - verifies the correctness (of tokens)regular grammars and finite automata are algorithmically equivalentexample of a tool for scanners: lex - takes a regular grammar and producesan equivalent finite automaton
37CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 3 – Part of a Pascal scanner (tokens classified by final ewlinelt realconstidentifier orkey wordlp)*non )digitletter(non *le letter, gite,E*digit ,-
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.1.3Scanner implementation- when invoked, the scanner returns the longest possible token- removes comments (nested ones require special attention!)- ad hoc scanners – written by hand– (usually) using nested case statements- built automatically – by a scanner generator– (usually) using tables in the ad-hoc scanner– handling keywords– the dot-dot problem: 3.14, 3.5, 3.foo- arbitrary long look-aheadDO 5 I 1,25 – a for loopDO 5 I 1.25 – an assignmentDO 5,I 1,25 – alternate syntax for loop, F77 in the table-driven scanner– white spaces – scanner repeats main loop until finding meaningful token38
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample – a nested case scanner39
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample – table-driven scanner40
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie- lexical errors- rare (most character sequences do correspond to some token- recovery– throw away the current (invalid) token– skip forward until new possible beginning of token– restart scanner– count on the error recovery mechanism of the parser- sometimes useful to give more information– most tokens are the same: ;, while– a name might be useful for a more precise error from parser– “foo has not been declared”41
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.242Concrete syntax- describes the written representation of a language; the form of its expressions,statements, and program units- described using context-free grammarscontext-free grammar: four parts-a set of nonterminals (symbols, letters)a set of terminals (symbols, letters)a nonterminal chosen as the starting symbola set of productions of the form:A :: α, A - nonterminalα - strings of terminals and nonterminals (possibly empty)
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 1nonterminals: S, A, Bterminals: a, a, b, bstarting symbol: Sproductions: S :: ABA :: aAa aaB :: bBb bbderivation: S AB aAaB aaaaB aaaabbmlanguage: {ananbmb n, m 1}43
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie44example 2nonterminals: Sterminals: (, )starting symbol: Sproductions: S :: SS ( S ) ( )derivation:S (S) (SS) ((S)S) ((())S) ((())())example 3replace in example 2:( by begin) by endnote: none of the languages in examples 1-3 can be generated by regular grammars (finite automata) because of the finite memory
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.2.1Specifying concrete syntaxBackus-Naur Form (BNF)- nonterminals enclosed between ′h′ and ′i′- empty string: hemptyiexample 1hdigit-sequencei :: hdigiti hdigitihdigit-sequenceihdigiti :: 0 1 2 3 4 5 6 7 8 9example 2example 1 plus the following productions:hreal-numberi :: hdigit-sequencei.hdigit-sequencei .hdigit-sequencei45
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 3example 1 plus the following productions:hinteger-parti :: hdigiti hinteger-partihdigitihf ractioni :: hdigiti hdigitihf ractionihreal-numberi :: hinteger-parti.hf ractioniexample 4hexpri :: hexpri hexpri hexpri hexpri hexpri hexpri hexpri/hexpri (hexpri) hnumberi hnamei46
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian IlieExtended Backus-Naur Form (EBNF)- the same power of expressing- add to readability and writability- new metasymbols:- { and } - reprezent zero or more repetitions- [ and ] - reprezent an optional component- ( and ) are used for groupingexample 1hintegeri :: ( )hdigit-sequencei hdigit-sequencei(or hintegeri :: [ ]hdigit-sequencei)hdigit-sequencei :: hdigiti{hdigiti}example 2hexpressioni :: htermi{( )htermi}htermi :: hf actori{( /)hf actori}hf actori :: ′ (′hexpressioni′)′ hnamei hnumberi47
48CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Iliesyntax graphs (charts)- the same power of expressing- visual appealexpressionterm -termfactor*/factor(expressionnamenumber)
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian IlieParse trees- a way to describe a derivation of a word in a context-free grammarexample 1 : consider the grammar:hdigiti :: 0 1 2 3 4 5 6 7 8 9hinteger-parti :: hdigiti hinteger-partihdigitihf ractioni :: hdigiti hdigitihf ractionihreal-numberi :: hinteger-parti.hf ractionithe word 123.789 has a derivation as below:hreal-numberi hinteger-parti.hf ractioni hinteger-partihdigiti.hdigitihf ractioni hinteger-partihdigitihdigiti.hdigitihdigitihf ractioni hdigitihdigitihdigiti.hdigitihdigitihdigiti 123.78949
50CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Iliethe corresponding parse tree is: real-number integer-part integer-part integer-part digit digit 21 digit 3. fraction digit fraction 7 digit 8 fraction digit 9
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 2grammar:hexpri :: hexpri hexpri hexpri hexpri hexpri hexpri hexpri/hexpri (hexpri) hnumberi hnameiword:a 2 ba derivation:hexpri hexpri hexpri hexpri hexpri hexpri hnamei hnumberi hnamei a 2 b51
52CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Iliethe corresponding parse tree: expr expr name a expr expr number 2* expr name b
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.2.253Recognizing concrete syntax- this is syntax analysis or parsing- the parser takes the stream of tokens from lexical analysis- builds a parse tree according to the rules of the underlying grammarScanning versus Parsingscanning - verifies the correctness of each token (locally)example i#f , 30a - wrongparsing - verifies the correctness of the program as a whole (sequence of tokens;globally)examplea : b c dif if else thenare wrong but correct from the scanner
54CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.2.3Ambiguity(syntactically) ambiguous grammar a grammar for which a generatedword has (at least) two parse trees (i.e., it can be generated in at least twodifferent ways)example 1the word a 2 b has two parse trees (precedence not respected) expr expr name a expr expr expr number 2 expr * expr expr name name ba* expr expr name number 2b
55CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample 2the word 4 2 1 has two parse trees (associativity not respected) expr expr - expr expr number expr 4 number 2- expr expr expr number number 14-- expr expr number number 21
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian IlieHandling associativity′ ′ is left associative′ ′ is both left and right associative- a grammar suitable for left associative operators is:L :: L number L number number- a grammar suitable for right associative operators is:R :: number R number R number56
57CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie- the word 4 2 1 can be generated by any of the two grammars- the parse trees are:LLL--Rnumber 1number 2number 4 -number 2 -number 4goodRRnumber 14-2-1 1bad4-2-1 3
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian IlieHandling associativity and precedence′ ′ ′/′ left associative′ ′ ′ ′ left associative′: ′ right associative (increasing precedence) - a grammar suitable for these:AETF:: name : A:: E T:: T F:: (E) E E T T T /F F name numberidea - a new nonterminal is needed for any precedence level58
59CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieparse tree for the word: a : b : 7 3 2 4Anamea: TAname: AbE-ETTT*TFFFnumber4Fnumbernumbernumber327*
60CS342b – Programming Languages – winter 2006 – c 2006 by Lucian IlieDangling-else ambiguity(ambiguous) grammar:S : if E then SS : if E then S else Sword with two parse trees:if E1 then if E2 then S1 else S2the two parse trees:SSifE1 thenSif E2 then S1 else S2if E1 then S else S2if E2then S1
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieunambiguous grammar- the idea – any else matched with the nearest previous unmatched thenS : M UM : if E then M else M non-if-stmtU : if E then S if E then M else U61
62CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieparse tree for:if E1 then if E2 then S1 else S2SUif E1 then SMif E2 then M else Mnon-if-stmt non-if-stmtS1S2
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.2.463Top-down and bottom-up parsing- any context-free grammar - parser running in O(n3) – too slow- LL-grammars and LR-grammars - linear-time parserstop-down (predictive) parser:- constructs a parse tree from the root down- predicts at each step which production to used based on next token- LL-grammars - Left-to-right Leftmost derivation- discovers a leftmost derivation- LL(1) – one look-ahead tokenbottom-up (shift-reduce) parser:- constructs a parse tree from the leaves up- maintains a forest of subtrees of the parse tree- joins subtrees (from right) when recognizing a right-hand side of a production- LR-grammars - Left-to-right Rightmost derivation- discovers a rightmost derivation- LR(1) – one look-ahead token- larger class of parsers and grammar structure more intuitive
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilieexample – top-down versus bottom-up parsing (word A,B,C;)id list id id list tailid list tail , id id list tail ;64
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie- problem with the previous grammar for bottom-up parsing– all tokens are shifted before any reduction is done– for a large program, it might run out of memoryexampleid list id list prefix ;id list prefix id list prefix , id id- this grammar cannot be parsed top-down– when we see id we don’t know which production to use- it works better for bottom-up– it avoids too much shifting65
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie66
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.2.5Recursive descent parser- written by hand for simple languages- has a subroutine for every nonterminalexampleprogram stmt list stmt list stmt stmt list ǫstmt id : expr read id write exprexpr term term tailterm tail add op term term tail ǫterm factor fact tailfact tail mult op factor fact tail ǫfactor ( expr ) id literaladd op mult op * /67
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie- the parser68
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie- a parse tree forread Aread Bsum : A Bwrite sumwrite sum / 269
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie70recursive descent parsing- start with program- see read – call stmt list then attempt to match - call stmt and stmt list- stmt list appears in the right-hand side of a stmt list production – thisgives the name of the procedure- continue like this to find a left-to-right depth traversal of the parse tree error handling- build the parse tree (or syntax tree – does not include the nonterminals)- match should save information about tokens in the leavescase arm labelling- each arm represents one production- the labels (tokens) – predict the production- X predicts a production if- (i) the right-hand side produces something starting with X- (ii) the right-hand side dissapears and X may begin the yield of whatcomes next
CS342b – Programming Languages – winter 2006 – c 2006 by Lucian Ilie2.2.6-71Syntax errorsnaive approach for errors – print
CS342b - Programming Languages - winter 2006 - c 2006 by Lucian Ilie 10 1.4 Evaluation of programming languages - programming - development - creation and testing of a program - maintenance - correction and changes after - good program - correct - easy to read / understand - easy to modify 1.4.1 Criteria - readability / writability
-graphical programming languages PLC ladder diagram Classification according to programming language paradigm -procedural programming languages C, Ada83 -functional programming languages LISP -logical programming languages PROLOG -object-oriented programming languages C , Smalltalk, Ada95 Classification according to language level
1 Languages at Harvard 2014 – 2015 Why Study a Foreign Language? 2 Planning Your Language Study 5 Languages Offered 2014-2015 (by Department) 6 African Languages 7 Celtic Languages 9 Classical Languages 10 East Asian Languages 11 English 17 Germanic Languages 17 Linguistics 20 Near Eastern Languages 21 Romance La
5 There is only one contemporary reference to an author named Lucian, in Galen, de epidem. 2.6.29 (this text survives only in the 9th century Arabic translation of Hunain ibn Ishaq). Galen identifies Lucian as a writer famous for forging some works of Heraclitus. The reference is discussed
sustainability Article Sustainable Development Model for the Automotive Industry Lucian-Ionel Cioca 1,2, Larisa Ivascu 2,3,* , Attila Turi 3, Alin Artene 3,* and George Artur Găman 4 1 Department of Industrial Engineering and Management, Faculty of Engineering, Lucian Blaga University of Sibiu, Bd. Victoriei No. 10, 550024 Sibiu, Romania; lucian.cioca@ulbsibiu.ro
the bit patterns. So, these machine languages were the rst programming languages, and went hand-in-hand with general-purpose computers. So, programming languages are a fundamental aspect of general-purpose computing, in contrast with e.g., networks, operating systems, and databases. 1.1 The Pre-History of Programming Languages
The study of programming languages is valuable for a number of reasons: Increase our capacity to use different constructs Enable us to choose languages more intelligently Makes learning new languages easier Most important criteria for evaluating programming languages include: Readability, writability, reliability, cost
targeted at a particular type of programming practice. Domain-specific languages are programming languages designed for writing programs for a particular kind of work or practice. End-user programming may or may not involve such languages, since what de-fines end-user programming is the intent, not the choice of languages or tools. 2.3.
In health care in England, perceptions of value have been dominated by a mix of clinical outcomes, system targets, competition mechanisms and encouragement for single units to act autonomously and be judged as single services. What people using health services value most has not been adequately considered or captured. However, a number of recent changes are raising the question of whether the .
