Transcript 國立聯合大學電子工程學系蕭裕弘

Chapter 7
Program Development &
Programming Languages
國立聯合大學 電子工程學系
蕭裕弘
Chapter Goals
 介紹利用電腦解決問題的方法與開發
軟體的程序
 介紹程式語言的分類與歷史
 介紹程式語言的特性
 介紹數種常見的程式語言
 介紹語言的轉譯方式
 介紹一些不屬於程式語言的電腦語言
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 2 / 45
1. Introduction
 Problem solving

The act of finding a solution to the perplexing (令人費解的), distressing
(令人煩惱的), vexing (傷腦筋的), or unsettled question.
 To solving the problem, you must answer the following questions:

What do I know about the problem?

What is the information that I have to process in order to find the solution?

What does the solution look like?

What sort of special cases exist?

How will I recognize that I have found the solution?
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 3 / 45
Computer Problem-Solving
問題描述與分析
設計演算法
開發軟體
程式執行與維護
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 4 / 45
Problem Specification and Analysis
 Problem specification is to have a clear description of the
problem


Easily done in CS courses for small problems.
More difficult to obtain in the real world for large problems.
 Analysis is to obtain a clear understanding of the problem




Carefully state the objectives of the program
What output should the program produce
and in what format?
What is the nature and format of
the required input?
Identify the computations required
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 5 / 45
Divide and Conquer
 Break up a large problem into smaller units that we can handle.
 Example: search 15 in the following sequence
1
2
3
4
5
6
7
8
9
10
3
5
8
9
10
13
15
16
18
20
 Method 1:

Linear search from the first number

7 comparisons needed
 Method 2:

Binary search

4 comparisons needed
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 6 / 45
2. Algorithms
 We use algorithms every day





Arithmetic operations
Dialing a phone
Looking up a phone number in the phone
book
Changing a tire
…
 Usually, algorithm means a precise
method in information processing.
Start
拿起話筒
按下一個
號碼鍵
是否按了
九個號碼
？
No
Yes
Stop
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 7 / 45
Definition of Algorithm
 An algorithm is a well-defined set of instructions, finite in
number, for accomplishing some task which, given a set of
inputs, will result in some recognizable end-state.
 Every algorithm must satisfy the following criteria:





Input: there are zero or more quantities which are externally
supplied;
Output: at least one quantity is produced;
Definiteness: each instruction must be clear and unambiguous;
Finiteness: if we trace out the instructions of an algorithm, then for
all cases the algorithm will terminate after a finite number of steps;
Effectiveness: every instruction must be sufficiently basic that it can
in principle be carried out by a person using only pencil and paper.
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 8 / 45
Algorithm Design
 Algorithm design tools include



Structure charts
Flowcharts
Pseudocode
Program control
Start
Input data
Input the data;
Calculate the result;
Calculate result
Output the result;
Output result
Input
Calculate
Output
Stop
Algorithms + Data Structures = Programs
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 9 / 45
常用的流程圖符號
開始/結束
處理
決策判斷
輸入/輸出
印表機輸出
流程方向
磁碟
連結點
儲存資料
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 10 / 45
Example of Flowchart
 以迴圈 (loop) 方式計算
Start
1 + 2 + ... + N 的值。
1
 執行過程:
1 (sum = 0), 2 (N = 3), 3 (i = 0)
4 (Yes), 6 (i = 1, sum = 1),
sum = 0
2
Input N
3
i=0
4 (Yes), 6 (i = 2, sum = 3),
4 (Yes), 6 (i = 3, sum = 6),
6
4
i<N?
4 (No), 5 (sum = 6)
Yes
i=i+1
sum = sum + i
No
5
Output sum
Stop
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 11 / 45
Example of Pseudocode

Goal: find the largest number in a number list
1.
2.
3.
4.
Pretend the first number in the list is the largest number.
Look at the next number, and compare it with this largest number.
Only if this next number is larger, then keep that as the new largest number.
Repeat steps 2 and 3 until you have gone through the whole list.
Given: a list "List"
largest = List[1];
counter = 2;
while (counter <= length(List))
if (List[counter] > largest)
largest = List[counter];
counter = counter + 1;
print largest;
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 12 / 45
Software Development
 Five phases are common in software development
Problem Specification and Analysis
Software
Development
Design of solution
Life
Cycle
(SDLC)
Implementation or Coding
Testing, Execution, and Debugging
Maintenance
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 13 / 45
Software Development Methods - 1
 In the top-down model, an overview of
the system is formulated, without going
into detail for any part of it.


Each part of the system is then refined
by designing it in more detail.
Each new part may then be refined
again, defining it in yet more detail
until the entire specification is detailed
enough to begin development.
 Top down approaches emphasize
planning, and a complete understanding
of the system. It is inherent that no
coding can begin until a sufficient level
of detail has been reached on at least
some part of the system.
Command interpret system
Read
command
Evaluate
command
Parse
command
Dispatch
command
Look-up
Type file
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Display
result
Delete file
Chapter 7: Page 14 / 45
Software Development Methods - 2
 In the bottom-up design, individual parts of the system are specified in
detail, and may even be coded. The parts are then linked together to form
larger components, which are in turn linked until a complete system is
arrived at.
 Bottom up emphasizes coding, which can begin
as soon as the first module has been specified.
 However bottom-up coding runs the risk that
modules may be coded without having a clear
idea of how they link to other parts of the system,
and that such linking may not be as easy as first
thought.
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 15 / 45
Choosing a Programming Language
 Factors that may affect the decision of choosing a
programming language:

Suitability

Integration

Standards

Programmer availability

Portability

Speed
C
C++
FORTRAN
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 16 / 45
2. Programming Languages
 A programming language or computer language is a
standardized communication technique for expressing
instructions to a computer.
 A programming language is a set of syntactic and semantic
rules used to define computer programs.
 A programming language enables a programmer to precisely
specify

what data a computer will act upon

how these data will be stored/transmitted

precisely what actions to take under various circumstances
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 17 / 45
Purpose of Programming Languages
 A primary purpose of programming languages is to enable programmers to
express their intent for a computation more easily than they could with a
lower-level language or machine code.
 For this reason, programming languages are generally designed to use a
higher-level syntax, which can be easily communicated and understood by
human programmers.
 Programming languages are important tools for helping
software engineers write better programs faster.
 Understanding programming languages is crucial for
those engaged in computer science, because all types
of computation are done with computer languages today.
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 18 / 45
History of Programming Languages
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 19 / 45
Generations of Programming Languages - 1
Generations
1
Representative
Features
Examples
Numerically coded instructions to 0101011010
Machine language the CPU
Machine-specifically
2
Assembly
languages
Mnemonics for the designation of ADD, SUB,
MUL, DIV,
machine instructions
JUMP, CALL, …
 elementary math. and logs.
Functions
 branches, subroutines
Fortran, Basic
First high-level languages
3 (1st phase)
Procedural
languages
 processing of character strings,
 higher mathematical functions
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 20 / 45
Generations of Programming Languages - 2
Generations
3 (2nd phase)
Representative
Structured
languages
Features
Examples
Pascal, C
Structured programming
iterations,
case branches etc.
C++, Object
Pascal
Object-oriented programming
4
Object-oriented
languages
 data encapsulation
 inheritance
 polymorphism
Delphi, Java,
C++ Builder,
(Visual Basic)
Visual programming
5
Componentbased (visual)
languages
 components,
 events,
 two way tools (rapid
application development - RAD)
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 21 / 45
Generations of Programming Languages - 3
Generation
Year
Representative
1
1945
Machine language
2
Mid-1950s
Assembly language
3
Early 1960s High-level languages
FORTRAN, COBOL,
BASIC, C, Ada
4
Early 1970s Very-high-level languages
SQL
5
Early 1980s Natural languages
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Examples
Chapter 7: Page 22 / 45
3. Features of a Programming Language
 Each programming language can be thought of as a set of
formal specifications concerning syntax, vocabulary, and
meaning.
 These specifications usually include:

Data type and data structures

Instruction and control flow

Reference mechanisms and
re-use

Design philosophy
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 23 / 45
Data Types and Data Structures
 The particular system by which data are
organized in a program is the type system of the
programming language.

Primitive data types




Data types with which values have a one-toone correspondence to data objects stored in
computer memory.
Primitive types are also known as built-in
types or basic types.
In C: char, int, float, double
Data type
Memory used
char
1 bytes
int
2 or 4 bytes
float
4 bytes
double
8 bytes
Structured data types or composite data types



Data type made up of more primitive types.
Values with a composite type are stored in
the memory in such a way that each attribute
is followed by another attribute.
In C: array, struct, …
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 24 / 45
Variables
 In computer science, a variable is a symbol
denoting a quantity or symbolic
representation.
 A variable can be thought of as a place to
store a value in computer memory.
 When one begins using a given variable, the
char
int
float
int
int
ch;
total;
average;
chi;
eng;
ch
language interpreter or compiler typically
sets aside a space in memory to store the
total
value given to that variable.
average
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 25 / 45
Instructions and Statements
 Once data has been specified, the machine must be instructed how to
perform operations on the data.
 Elementary statements may be specified using keywords or may be
indicated using some well-defined grammatical structure.
 Each language takes units of these well-behaved statements and combines
them using some ordering system. Depending on the language, differing
methods of grouping these elementary statements exist.
total = chi + eng + ari;
average = total / 3.0;
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 26 / 45
Control Flow
 Furthermore, beyond the data manipulation instructions, other typical
instructions in a language are those used for control flow.

Branches

Loops
Score >= 60
?
Statement 1
No
Repeat?
Yes
Output ‘pass’
Statement 1
Output ‘fail’
Statement 2
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Yes
No
Statement 2
Chapter 7: Page 27 / 45
Reference Mechanisms and Re-use
 The core of the idea of reference is that there must be a method of indirectly
designating storage space.
 The most common method is through named variables.
 Depending on the language, further indirection may include references that are
pointers to other storage space stored in such variables or groups of variables.
 Similar to this method of naming storage is the method of naming groups of
instructions.

Most programming language use procedure calls or function calls as the statements
that use these names.

Using symbolic names in this way allows a program to achieve significant flexibility,
as well as a high measure of reusability.
Calls function A
Body of
function A
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Subroutine
Procedure
Function
Chapter 7: Page 28 / 45
Design Philosophy
 For different purposes, each language has been developed using a special
design or philosophy.
 Some aspect or another is particularly stressed by the way the language uses
data structures, or by which its special notation encourages certain ways of
solving problems or expressing their structure.
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 29 / 45
4. Language Translators
 Since the computer can only execute the program in machine code, the
programs written in assembly or high-level language should be translated
into machine code before execution.
Source
program
Translator
Object code
or results
 Types of language translators:

Assembler

Compiler

Interpreter
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 30 / 45
Assembler
 Assembly language is a human-readable notation for the
machine language that a specific computer architecture uses.
 Every computer architecture has its own machine language,
and therefore its own assembly language.
 An assembler is a computer program for translating assembly
language into object code.
mov al, 0x61
10110000 01100001
Instruction = Operation code + Operand(s)
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 31 / 45
Compiler
 A compiler is a computer program that
Lexical analysis
translates a computer program written in
one computer language (called the source
language) into a program written in
another computer language (called the
output or the target language).
Syntax analysis
Semantic analysis
 Most compilers translate source code
written in a high level language to object
code or machine language that may be
directly executed by a computer or a
virtual machine.
Intermediate code generation
Optimization
 The first completed compiler: 1950s
FORTRAN
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Code generation
Chapter 7: Page 32 / 45
Process of Compilation
int
a, b, c;
float d;
c = a + b;
d = (a + b) / (a - b);
int
a, b, c;
float d;
c = a + b;
d = ( a + b ) / ( a - b );
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Allocate.I
Allocate.I
Allocate.I
Allocate.F
Load
Load
Add
Store
Load
Load
Add
Sub
Div.F
Store
a
b
c
d
r1, a
r2, b
r3, r1, r2
c, r3
r4, a
r5, b
r6, r4, r5
r7, r4, r5
r8, r6, r7
d, r8
Chapter 7: Page 33 / 45
Linkage Editor
 A linker or linkage editor is a program that takes one or more
objects generated by compilers and assembles them into a
single executable program.
Source #1
Compiler
Object #1
Source #2
Compiler
Object #1
Linker
Source #n
Compiler
Object #n
Load
module
System library
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 34 / 45
Interpreter
 An interpreter is a computer
program that executes other
programs.
High-level
source
program
 Interpreting code is slower than
running the compiled code because the
interpreter must analyze each statement
in the program each time it is executed
and then perform the desired action
whereas the compiled code just
performs the action.
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Load
Source
Program
In memory
Run
Interpreter
translates
one
instruction
Machinecode
instruction
Execute
Chapter 7: Page 35 / 45
5. Popular PLs - FORTRAN
 The name is short for Formula Translator/Translation.
 Fortran is mainly used for scientific computing and numerical
analysis.
 Although originally a procedural language, recent versions of
Fortran have included some features to support object-oriented
programming.
PROGRAM HELLO
PRINT *, 'hello, world'
END
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 36 / 45
COBOL
 Its name is an acronym, for COmmon Business Oriented
Language.
 Its primary domain was in business, finance, and administrative
systems for companies and governments.
ENVIRONMENT DIVISION.
DATA DIVISION.
PROCEDURE DIVISION.
BEGIN.
DISPLAY " " LINE 1 POSITION 1 ERASE EOS.
DISPLAY "HELLO, WORLD." LINE 15 POSITION 10.
STOP RUN.
EXIT.
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 37 / 45
Pascal
 Pascal is based on the Algol programming language and is
named in honor of mathematician and philosopher Blaise
Pascal.
 Pascal is one of the landmark programming languages on
which generations of students cut their teeth and variants of
which are still widely used today.
program HelloWorld;
Begin
WriteLn('Hello World!')
end.
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 38 / 45
BASIC, Visual BASIC
 BASIC's name stands for Beginner's All-purpose Symbolic
Instruction Code.
 Originally devised as an easy-to-use tool, it became widespread
on home microcomputers in the 1980s, and remains popular to
this day in a handful of heavily evolved dialects.
 BASIC is available on nearly every microprocessor platform
made:


Interpret version
Compile version
10 PRINT “Hello World!”
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 39 / 45
C, C++, C#
 C has since spread to many other operating systems, and is one of the most
widely used programming languages.
 C is prized for its efficiency, and is the most popular programming language
for writing system software, though it is also used for writing applications.
 It is also commonly used in computer science education, despite not being
designed for novices.
#include <stdio.h>
int main(void)
{
printf("Hello, World!\n");
return 0;
}
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 40 / 45
Java
 The Java language is an object-oriented programming language created by
James Gosling and other engineers at Sun Microsystems in 1991.
 There were four primary goals in the creation of the Java language:




It is object-oriented.
It is independent of the host platform (more or less).
It contains language facilities and libraries for networking.
It is designed to execute code from remote sources securely.
import java.io.*
public class Print {
public static void main(String args[]) {
System.out.println(“Hello, World!”);
}
}
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 41 / 45
6. Other Languages - HTML
 HyperText Markup Language (HTML) is a markup language designed for
creating web pages, that is, information presented on the World Wide Web.
 HTML tags can be used to perform such tasks as:

Declaring titles for page, <TITLE>

Identifying the size of headings, <H1>, <H2>

Marking the ends of paragraphs, <P>

Establishing such text styling as italic and boldfaced type, <I>, <B>

Setting up hyperlinks to other documents, <A>

Identifying complex elements to be inserted into a document, such as
images, video clips, and sound files, <IMG>

Specifying the layout of tables and frames, <TABLE>
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 42 / 45
JavaScript
 JavaScript is an object-oriented scripting language commonly used in
websites.
 It was originally developed by Brendan Eich of Netscape Communications
under the name "Mocha" and then "LiveScript" but then renamed to
"JavaScript" and given a syntax closer to that of Sun Microsystems’ Java
language.
<HTML>
<SCRIPT LANGUAGE="JavaScript">
document.write("Hello World!");
</SCRIPT>
</HTML>
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 43 / 45
VBScript
 VBScript (short form of Microsoft's Visual Basic Scripting Edition) is a
subset of Visual Basic used in Active Server Pages and in Windows
Scripting Host as a general-purpose scripting language.
 VBScript is interpreted by a script engine:

ASP in a web environment

wscript.exe in a Windows environment

cscript.exe in a command-line environment.
msgbox "Hello world!"
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 44 / 45
PHP
 PHP (a recursive acronym for "PHP: Hypertext Preprocessor") is a widely-
used open-source programming language primarily for server-side
applications and developing dynamic web content.
 PHP's ease of use and similarity with the most common structured
programming languages – most notably C and Perl.
<HTML>
<BODY>
<?
echo "Hello World!";
?>
</BODY>
</HTML>
國立聯合大學電子工程學系 – 計算機概論 – 蕭裕弘
Chapter 7: Page 45 / 45