[Programming Language Week1] Programming language, Chomsky Hierarchy

1. Language and programming language

1-1. Language

• A tool to communicate among humam beings
• First written language : Sumerian
• Programming language
  : A tool for communication between literal-minded machines
  : A protocol among users to control computers

1-2. Definition of formal language

• Is a set of finite strings of atomic symbols from alphabet where alphabet is defined as a set of given symbols

1-3. Why we learn programming languages?

• To implement more effective algorithms by learning features, understanding implementations, increasing vocabulary such as Recursion, and Memory management mechanisms
• To choose better programming languages by comparing various languages for the purpose
• To learn new foreign languages more quickly and easily
  (Languages in general have similar structures and components)
• To develop better programming languages
  for better user interfaces and functions

1-4. Attributes of a Good Language?

• Orthogonality
  -- Ability to combind various features of a language
• Support for abstraction
  -- Construct to factor out reoccurring patterns
• Natural for various applications
  -- For business, mathematics, science, game, etc
• Easy of program verification and debugging
  -- Formal verification & desk checking
• Portability and Translation
  -- Minimum degree of computation and space complexity
  -- Considering various architecture

1-5. Classification of the Languages

1-6. Models of Programming Languages

• Imperative Languages(Command Driven Language)
  -- A program consists of a sequence of statement
  -- Execution of each statements causes interpreter to change the state of the system
  -- Successive machine states lead to the desired solution
  -- C, Fortran, Algol, PL/I, PASCAL

• Object Based Languages
  -- Complex objects are designed as extensions of simpler objects
  -- Inheriting of simple objects
  -- C++, Java, Small talk
  -- Gain the efficiency of imperative languages
  -- Gain the flexibility and reliability of applicative languages

• Applicative Languages(Functional Language)
  --Perform a function with its arguments to generates results
  -- Results of a function can be arguments of another function
  -- LISP and ML

• Rule-based Languages (Logical Languages)
  -- Execute an action when a certain enabling condition(predicate) is satisfied
  -- Building a matrix or table of possible conditions and appropriate actions for proofs or database search
  -- Program consists of fact, rule, and query
  -- Prolog
  ex) dog(john).
  cat(marry).
  monkey(james).
  friendly(john, james)

• Hybrid Languages: Python

2. Machine Architecture and Language

2-1. Von Neumann Computer Architecture

2-2. Conventional Computer Organization

2-3. Computer Architecture and Language Related Issues
: Major components of a computer that correspond to the six major aspects of programming languages

• Data
  -- Elementary data types and structured data
  -- Storages are high speed registers, main memory, and external files
  -- Built-in data vs. user-defined data
• Operations
  -- Set of operations to manipulate the data
  -- Arithmentic operations, testing, accessing, modifying operation
  -- Device control operation
  -- Sequence control operation
• Sequence Control
  -- Mechanisms to control the instruction sequence
  -- Use of program address register(PAR) to indicate next instruction
  -- Branch operations are used to control sequences
  -- Instruction level sequence control
  
• Data Access
  -- Mechanism to access and control the data
  -- Serial access vs. parallel access
• Storage management
  -- Mechanism to control the storage of data and instructions
  -- Imbalance due to access time, memory, and register : Buffered write uesed
• Operational environment
  -- Mechanisms for communication with external devices
  -- I/O devices (CD-ROM, Tapes, Modems ...)
• Other Factors
  -- System Architecture
  -- Von Neumann vs. Multiprocessor system
  -- RISC, SIMD, MIMD, SPMD

3. Syntax Analysis and Semantics

3-1. Syntax

• Grammar : <T, N, P, S>
  -- Terminal: A finite set of terminals
  -- Nonterminal: A finite set of non-terminals not in T
  -- Production: A finite set of production(rewriting) rules
  -- Start Symbol: An element of N the distinguished starting non-terminal
• Notations
  -- BNF (Backus-Naur Form)

4. Compilation Language & Compilation Process

5. Compiler and translation related issues

6. Language Design Issues

6-1. Binding Times
: Time to choose the properties or characteristic for programming elements

• Language definition time
• Language implementation time
• Program translation time by
  : Programmer
  : Translator
  : Loader
• Program execution time

6-2. Language Classification by translation method

• Compilation languages vs. Interpretation languages

7. Chomsky Hierarchy

7-1. Concept
: Formal Basis for describing the artificial language that we use to program computers

7-2. Type 0: Unrestricted Grammar

• Type 0: Undestricted Grammar
  -- α->ß : No restrictions applied
  -- TM is also called recursively enumerable language since the elements can be listed and hopelessly inefficient
  -- Recognized by Turing Machine (infinite r/w type)

• Process of Turing Machine
  -- Language recognizer is a procedure for definig a set of strings
  -- advance to next state, write back onto the current position, change the direction to move
  

7-3. Type 1: Context Sensitive Grammar

• Type 1: Context Sensitive Grammar
  -- α->ß where |ß| > |α| except S->ε
  -- LHS of each production must have at least one non-terminal
  -- Say A becomes ß in the context of α1 and α2
  -- Too complex for a specification of computer languages
  -- Recognized by Linear Bounded Atomaton (LBA)

7-4. Type 2: Context Free Grammar

• Type 2: Context Free Grammar
  -- A->ß where A is a variable and ß is a string from (∑ U N)*
  -- The derivations are invoked independent of what surrounds them
  -- Exactly a single non-terminal on LHS of each production
  -- Does not allow empty production except the single production with a start symbol
  -- Recognized by Push Down Automaton (PDA)
  : pops a symbol from the stack
  : push the same or other symbols into the stack
  : optionally read or advance its input tape
  

• Process of Pushdown Automata
  
  

• Limits of Context Free Grammar
  -- Modern programming languages are specified with CFG but expanded to CSG with attributes
  -- Count comparison can be done by CFG, but cannot match the same words
  -- But, cannot write CFG to match the spelling of the same word twice like abcabc

  7-5. Type 3: Regular Grammar

• Type 3: Regular Grammar
  -- A -> wB or A -> w right linear
  -- Allow one non-terminal on LHS and one or two symbols on RHS with the first be terminal symbol
  -- Too restrictive for most purpose; however, very efficient recognizer can be built
  -- Incapable of generating language structures like arbitrary deep nested parenthesis
  -- Does not allow empty production except the single production with a start symbol
  -- Recognized by Finite State Automaton

• Process of Finite State Automata
  -- Empty production vs. Empty language
  -- A language that generates empty string
  -- A language that generates no string