Final Review

Disclaimer:

  • Appearing on this page does not mean something will be on the test
  • Not appearing on this page does not mean something won't be on the test

Syntax

  • Backus-Naur Form
    • Derivations
    • Parse Trees
  • Ambiguity
    • Precedence

Parse Tree Practice:

Given the following grammar:

  • $< assign > \to < id > = < expr > $
  • $< id > \to A \, | \, B \, | \, C $
  • $< expr > \to < expr > + < expr> $
  • $\qquad \qquad | < expr > * < expr> $
  • $\qquad \qquad | \, ( < expr> ) $
  • $\qquad \qquad | < id > $

Derive and give the parse trees for:

  • A = B * B

Semantics

  • What is it
  • What are the three major proposed ways to describe it
    • Operational Semantics
    • Denotational Semantics
    • Axiomatic Semantics

Lexical Analysis

  • The first step in parsing, how a compilier or interpreter segments the code
  • Uses Regular Expressions and Deterministic Finite State Machines
    • They both describe the same thing
    • Know how to read both

Regex Practice

  • Given the following regular expression: 
    x ( (xy) | (xz) )* z
  • Are the following in or out of the langaue described
    • xxzz
    • xyxz
    • xz
    • xxyxzz

Parsing

  • Two stratagies
    • Top Down
      • What can't it handle
    • Bottom Up
      • Uses a parsing table

Imperative Languages

  • What are they?
  • Lua is the example we learned in this class
    • Simple type system makes parsing and interpretation faster
    • Only one data structure: table
    • Functions can return multiple variables

Example Lua Code

  • Given a string of numbers separated by commas, find their average
In [15]:
function avg(str)
    total = 0
    len = 0
    for i in string.gmatch(str, "%d+") do
      total = total + tonumber(i)
      len = len + 1
    end
    return total/len
end

Object Oriented Languages

  • Object Oriented Languages display 3 main properties
    • Polymorphism
    • Inheritance
    • Encapsulation
  • In this course we looked at Java
    • Java is not purely object oriented
      • int, float, char, bool, etc. are primitive types and not objects

Example Java Code

  • Given a string of numbers separated by commas, find their average
public class Final{
    public static void main(String[] args){
        String numbers = args[0];
        String[] stringArray = numbers.split(",");


        double total = 0;
        for(String s : stringArray){
            total += Integer.parseInt(s);
        } 

        System.out.println(total/stringArray.length);
    }
}

Functional Languages

  • Functions don't have side effects
    • Not 100% true in Scheme, but still a good guiding principle
  • Code and Data are the same
    • Quoting indicates if an expression is code or data
    • Eval will execute data as code

Common Functional Idioms

  • Apply a function to a list of parameters
    • (apply + '(1 2 3))
  • Apply a function to every item in a list
    • (map - '(1 2 3))
  • Recursion

Recursion

  • Recursion is the standard way of processing a list
(define foo (lambda (x)
        (
            (doSomething (car x)) 
            (foo (cdr x))

        )
    )

Example Scheme Code

  • Given a string of numbers separated by commas, find their average
(define avg (lambda (x)
   (/
    (apply +
        (map string->number (regexp-split #rx"," x))
    )
        (length (regexp-split #rx"," x))
   )    
 )
)

JavaScript

  • Originally designed for the web but now finding use in other domains
  • Is an imperative language with some basic support for OO
  • Is excellent for event-based programming
    • The programmer doesn't define an expected order of interactions, only the expected response to a given action
    • This can be used to support ansnchronicity

Event Handling JavaScript

  • Listening for events is done through the addEventListener method of javascript elements
    • This method covers all types of events from user interface events to network events
    • The method takes two parameters,
      • a string which is the name of the even to listen to
      • a function that is to be run when the event occurs

Things to Remember about Event Handling

  • Events propogate
    • If a child object and a parent object both have listeners to the same event, both will recieve the event by default
  • Events can fire hundreds of times a second
    • The programmer should implement a timeout or other system to not process every event

JavaScript Example

  • Given a string of numbers separated by commas, find their average, when the user clicks the button
In [5]:
%%html
<html>
<body>
<input id="numbers" type="text" />
<button id="calculate">Calculate Average</button>
<div id="result">
</div>
<script>
document.querySelector("#calculate").addEventListener('click',
    function(){
        var strings = document.querySelector("#numbers").value.split(',')
        var total = 0;
        for(var i=0; i < strings.length; i++)
        {
            total += Number(strings[i])
        }
        
        document.querySelector("#result").innerHTML = total/strings.length
    });
</script>
</body>
</html>

Programming for Mobile

  • Programming for mobile is not a different paradigm, but has many unique elements
    • The execution of programs is more tightly controlled
    • The access to resources is more tightly controlled
    • Is more event-based that many desktop programs
  • Android shares two similarities with HTML/JS
    • Separation of code (Java files) and layout (XML files)
    • The reliance on event listeners

Events in Android

  • As Android is based on Java, event handlers cannot simply be functions passed to a method
    • Android gets around this by having an interface for each event type, which contains one to two methods that are the handlers
    • An object that implements that event can then be passed to the event listener

Events in Android

  • Event listeners are attached in different ways in Android depending on the type of event
    • UI Events are attached through a method on the UI Object
    • Sensor Events are attached through a method of a SensorManager object
    • Location events are attched through a global static method

Logic Programming

  • Logic programming was originally intended to prove thereoms
  • It is made up of facts and rules that can then be queried
    • This uses logical inference
  • In Proglog, capitalization matters
    • Captialized strings are variables
    • Lower-cased strings are atoms

Comparing Languages: Syntax

Language Statement Ender Line Comment Character
Lua Whitespace --
Java ; (Semicolon) //
Scheme ) (Right Parentheses) ; (Semicolon)
JavaScript \n or ; //
Prolog . %

Comparing Languages: Variables

Language Variable Declaration Default Scope
Lua varName = val Global
Java type varName = val; Package-Private
Scheme (let ((varName val)) ...) N/A (Has to be define or let)
JavaScript var varName = val Global (without var)

Comparing Languages: Control Statements

Language If for-each
Lua if condition then expression end for key,value in pairs(table) do doSomething(table[key]) end
Java if(condition){ expression; } for( type t: Collection<type> c){ doSeomthing(t); }
Scheme (if (condition) (expression)) (map function list)
JavaScript if(condition){ expression; } array.forEach(function)

Comparing Languages: Functions

Language Defining a Function Calling a Function
Lua function f(x) functionBody end f(x)
Java returnType functionName(x) { } instance.functionName(x)
Scheme (define f (lambda (x) functionBody)) (f x)
JavaScript function f(x) {functionBody } f(x)

Comparing Languages: Strings

  • This chart shows how to explicitly cast a string to a number, some of the langauges perform type coercion with out a cast
Language String->Int Print String Concatentation
Lua tonumber(str) print(str) ..
Java Integer.parseInt(str); System.out.println(str); +
Scheme (string->number str) (display str) str-join
JavaScript Number(str) console.log(str)* +

Comparing Languages: Arrays

  • In this chart we use array to mean a list of objects with numerical index
Language Array Length Index Multidimensional Array
Lua #array array[i] a = {} for i,k in pairs(a) do a[i] = {}
Java array.length array[i] a = new type[len1][]
Scheme (length list) (list-ref list i) (list (list ) ... (list ) )
JavaScript array.length array[i] array = newArray() array.forEach(function(element){ return new Array()})

Comparing JS and Android: Events

  • JavaScript
    • Always uses addEventListener
    • Events are strings
    • Can't pass parameters to event listeners easily
  • Android
    • Uses different methods depending on the situation
    • Each event hass its own listener method and listener interface
    • Can pass extra parameters to the constructor of the event listener

References

Thanks for a great semester!