WIXLIB

Software Lesson 2 8.Software Lesson 2 OutlineLanguagesIngredients of a LanguageKinds of LanguagesNatural Languages #1Natural Languages #2Natural Languages #3Natural Languages #4Programming LanguagesNatural Languages vs ProgrammingLanguagesProgramming Language HierarchyHigh Level LanguagesAssembly LanguagesMachine LanguagesConverting Between 3.24.25.26.27.28.29.30.31.32.33.34.35.36.37.Our Old Friend hello world.cCompiler DetailsCompiler Details (cont’d)Elements of a Compiler #1Elements of a Compiler #2Phases of CompilingCompiling a C StatementAssembly Code for hello world.c #1Assembly Code for hello world.c #2Machine Code for hello world.cHow to Program in Machine Language DirectlyWhy Not Do Everything in Machine Language?Why Not Do Everything in AssemblyLanguage?The Programming ProcessWhat is an Algorithm?AlgorithmsAlgorithm Example: Eating a Bowl of CornFlakesTop-Down DesignEating Cornflakes: Top LevelSoftware Lesson #2CS1313 Fall 20211

Languages What is a language?Kinds of languages Natural languagesProgramming languages (also known as Formal languages)Converting between programming languages CompilersInterpretersAssemblersSoftware Lesson #2CS1313 Fall 20212

Ingredients of a Language Symbols: a set of words and punctuation (in computing,words and punctuation are collectively known as tokens)Grammar (also known as syntax): a set of rules forputting symbols together to get valid statementsSemantics: a set of rules for interpretingthe meaning of a grammatically valid statementSoftware Lesson #2CS1313 Fall 20213

Kinds of Languages Natural languages: used in human communicationProgramming languages (also known as formal languages):used by computers (among others)Software Lesson #2CS1313 Fall 20214

Natural Languages #1 There are said to be 7000 natural languages in the anguages Examples: English, Chinese, Swahili, Navajo, Quechua, MaoriNot all natural languages arise naturally –some are created by people, on purpose.https://en.wikipedia.org/wiki/Incubus (1966 film)https://en.wikipedia.org/wiki/Jabba the Hutt kipedia.org/wiki/WorfTypically can be described by formal rules (grammar),but often aren’t rigidly governed by these rulesin everyday use:“Any noun can be verbed.”“I might could get me one o’ them there computers.”Software Lesson #2CS1313 Fall 20215

Natural Languages #2 CAN mix words from different languages – and evensyntax (elements of grammar) from different languages –in a single sentence:“Hey, amigo, is it all right by you if I kibbitzyour pachisi game while we watch your ftware Lesson #2CS1313 Fall 20216

Natural Languages #3CAN be ambiguous: “When did he say she was going?”could be interpreted as:State the time at which he said, “She was going.”OR According to him, at what time was she going? “You can’t put too much water in a nuclear reactor.”could be interpreted 17-1984-ed-asner-thekinks-s10-e6/You shouldn’t put a lot of water in a nuclear reactor.OR There’s no upper limit to how much wateryou can put in a nuclear reactor. Software Lesson #2CS1313 Fall 20217

Natural Languages #4 Plenty of flexibility regarding “correctness;” for example,“ain’t,” split infinitives, ending a sentence with a preposition.“That is something up with which I will not put.”Software Lesson #2CS1313 Fall 20218

Programming Languages Examples: C, Java, HTML, Haskell, Prolog, SASAlso known as formal languagesCompletely described and rigidly governed by formal rulesCannot mix the words of multiple languages,or the syntax of multiple languages, in the same programCannot be ambiguousWords and syntax must be EXACTLY correct in every waySoftware Lesson #2CS1313 Fall 20219

Natural Languages vs Programming LanguagesPROPERTYNAT’L PROGCompletely described and rigidly governednoYESby formal rulesCAN mix the words of multiple languages,YESnoor the syntax of multiple languages,in the same programCAN be ambiguousYESnoWords and syntax must beEXACTLY correct in every waySoftware Lesson #2CS1313 Fall 2021noYES10

Programming Language Hierarchy High Level LanguagesAssembly LanguagesMachine LanguagesSoftware Lesson #2CS1313 Fall 202111

High Level Languages Human-readableMost are standardized, so they can be used onjust about any kind of computer.Examples: C, Fortran 90, Java, HTML, Haskell, SASTypically they are designed for a particular kind of application;for example: C for operating system designFortran 90 for scientific & engineering applicationsJava for embedded systems (originally designed for interactive TV)HTML for hypertext (webpages)SAS for statisticsBut often, their uses in real life are broader their original purpose.Software Lesson #2CS1313 Fall 202112

Assembly Languages Human-readableSpecific to a particular CPU family; for example: Intel/AMD x86 (PCs, servers, some handhelds)ARM (handhelds such as cell phones and tablets)IBM POWER (server computers)So, for example, a program in x86 assembly languagecannot be directly run on a POWER or ARM machine.Set of simple commands; for example: Load a value from a location in main memoryAdd two numbersBranch to an instruction out of sequenceSoftware Lesson #2CS1313 Fall 202113

Machine Languages Not human-readable, except with immense effortBinary code that the CPU family understands directlyBinary representation of the CPU family’s assembly languageSoftware Lesson #2CS1313 Fall 202114

Converting Between LanguagesCompilers, interpreters and assemblers areprograms that convert human-readable source codeinto machine-readable executable code.Software Lesson #2CS1313 Fall 202115

Compiler Converts a human-readable high level language source codeof a program into a machine language executable programConverts an entire source code all at onceMust be done before executing the programExamples: Fortran, C, C , PascalSoftware Lesson #2CS1313 Fall 202116

Interpreter Converts a human-readable high level language source codeinto actions that are immediately performedConverts and executes one statement at a timeConversion and execution alternateExamples: Perl, HTML, SAS, Mathematica, Unix “shell”(interactive system within Unix)Software Lesson #2CS1313 Fall 202117

Assembler Converts a human-readable CPU-specific assembly codeinto CPU-specific, non-human-readable machine languageLike a compiler, but for a low level assembly languageinstead of for a high level languageSoftware Lesson #2CS1313 Fall 202118

Our Old Friend hello world.c% cat hello *********** Program: hello world****** Author: Henry Neeman (hneeman@ou.edu)****** Course: CS 1313 010 Fall 2021****** Lab: Sec 014 Fridays 2:30pm****** Description: Prints the sentence******"Hello, world!" to standard **********/#include stdio.h int main (){ /* main *//************************************ Execution Section (body) ************************************* Print the sentence to standard output* (i.e., to the terminal screen).*/printf("Hello, world!\n");} /* main */% gcc -o hello world hello world.c% hello worldHello, world!Software Lesson #2CS1313 Fall 202119

Compiler DetailsSoftware Lesson #2CS1313 Fall 202120

Compiler Details (cont’d)Software Lesson #2CS1313 Fall 202121

Elements of a Compiler #1 Lexical Analyzer: identifies program’s “word” elements: Keywords (for example, int, while)Constants (for example, 5, 0.725, "Hello, world!")User-defined identifiers (for example, addend)Operators; for example: Arithmetic: - * / %Relational: ! Logical:&& ! Software Lesson #2CS1313 Fall 2021 22

Elements of a Compiler #2 Parser: determines the program’s grammarSemantic Analyzer: determines what the program doesIntermediate Code Generator: expresses, as anassembly-like program, what the program doesOptimizer: makes code more efficient (faster)Assembly Code Generator: produces the final assembly codethat represents what the program doesSoftware Lesson #2CS1313 Fall 202123

Phases of Compiling CompilerAssembler: turns assembly code into machine codeLinker/loader: turns machine code into an executable fileBoth the assembler and the linker/loader areinvoked automatically by the compiler,so you don’t have to worry about them.Software Lesson #2CS1313 Fall 202124

Compiling a C StatementSoftware Lesson #2CS1313 Fall 202125

Assembly Code for hello world.c #1On Pentium4 Using gccpushl %ebpmovl %esp, %ebpsubl 8, %espsubl 12, %esppushl .LC0call printfaddl 16, %espleaveretOn IBM POWER4 Using gccDifferent opcodes!mflr 0stw 31,-4(1)stw 0,8(1)stwu 1,-64(1)mr 31,1lwz 3,LC.1(2)bl .printfnoplwz 1,0(1)lwz 0,8(1)mtlr 0lwz 31,-4(1)blrSoftware Lesson #2CS1313 Fall 202126

Assembly Code for hello world.c #2On Pentium4 Using gcc(GNU compiler)pushl %ebpmovl %esp, %ebpsubl 8, %espsubl 12, %esppushl .LC0call printfaddl 16, %espleaveretOn Pentium4 Using icc(Intel compiler)Different sequencesof instructions!pushl %ebpmovl %esp, %ebpsubl 3, %espandl -8, %espaddl 4, %esppush STRING.0call printfxorl %eax, %eaxpopl %ecxmovl %ebp, %esppopl %ebpretSoftware Lesson #2CS1313 Fall 202127

Machine Code for hello 00101010100101010101101010101011010.Software Lesson #2CS1313 Fall 202128

How to Program in Machine Language Directly1.2.3.4.Write the assembly code for the program directly by hand;that is, not in a high level language.For each assembly language instruction, look up the bit patternof the associated machine code.On the computer console, flip switches to match the bit patternof the machine code.Press the “Run” button.On modern computers, programming directly in machine languageis just about impossible.Software Lesson #2CS1313 Fall 202129

Why Not Do Everything in Machine Language?Incredibly tedious and ridiculously error-prone!Fun and easy!Not nearly as tedious or error-prone!Software Lesson #2CS1313 Fall 202130

Why Not Do Everything in Assembly Language?Can’t be run on any other kind of computer.May be completely obsolete in a few years.Portable to many kinds of computers.Will still be usable in 20 years(“legacy” codes).Software Lesson #2CS1313 Fall 202131

The Programming ProcessFormulateProblemCompileConstruct AlgorithmBugs?YesDebugNoChoose ProgrammingLanguageWrite ProgramRunBugs?YesNoGet an A/Impress Your Boss/Sell for Zillions!Software Lesson #2CS1313 Fall 202132

What is an Algorithm?An algorithm is: a step-by-step method that is written in a natural language (for example, English)or in pseudocode (something that sort of looks likea programming language but isn’t as precise),instead of in a programming language, that solves a well-defined (though not necessarily useful)problem, on a well-defined set of inputs (which may be empty), using finite resources (for example,computing time and storage), and that produces a well-defined set of outputs(which may be empty).Software Lesson #2CS1313 Fall 202133

AlgorithmsAn algorithm is a language-independent way of expressingthe method of solving a problem; that is, an algorithm couldbe expressed in two different languages (for example,English and Japanese) and still be the same algorithm.A program, by contrast, is a language-dependentimplementation of the method of solving a problem;that is, the same set of steps expressed intwo different programming languages would betwo different programs, even if the two programsaccomplished exactly the same result.Many programs, but not all, implement algorithms.Programs that don’t implement algorithms often implementheuristics, which typically are inexact but good enough.The word “algorithm” comes from the name of the 9th centurymathematician, Muhammad ibn Musa hmSoftware Lesson #2CS1313 Fall 202134