Difference between revisions of "Mimir:Spring 2019 Lectures"

From Openitware
Jump to: navigation, search
(Week 9 - Language usage (utility, development) and the modern paradigm: OOP vs procedural)
(Week 9 - Language usage (utility, development) and the modern paradigm: OOP vs procedural)
Line 692: Line 692:
 
* <s>Comparison of the modern paradigm - OOP vs procedural.</s>
 
* <s>Comparison of the modern paradigm - OOP vs procedural.</s>
 
** <s>Structure put on language and its purpose</s>
 
** <s>Structure put on language and its purpose</s>
*** Typed languages - restricts freedom to reduce error</s>
+
*** <s>Typed languages - restricts freedom to reduce error</s>
*** how a struct (record) in procedural transformed into a class in OOP</s>
+
*** <s>how a struct (record) in procedural transformed into a class in OOP</s>
*** Fundamentals structure of OOP</s>
+
*** <s>Fundamentals structure of OOP</s>
 
**** <s>Encapsulation - reduces access to data (example)</s>
 
**** <s>Encapsulation - reduces access to data (example)</s>
 
**** <s>Inheritance - adds hierarchy to data reuse (example)</s>
 
**** <s>Inheritance - adds hierarchy to data reuse (example)</s>

Revision as of 17:53, 23 May 2019


Contents

Week 1 - Introduction: categorizing programming languages

Content author Mike Jonas

Outline

  • How to Categorize a programming language
    • by paradigm: imperative, procedural, functional, logic, visual, oop
    • by its use: development vs utility
    • by implementation: interpreted, compiled, hybrid
    • by attribute: data typed, free format, indentation driven
    • by generation: 1st, 2nd, 3rd, 4th, 5th

Categorizing programming Languages

How do we discuss programming languages? What forms do we use to analyze the effectiveness of a language, be it a newly created one or one that has been around for a long time. We'll briefly hit upon five, some standard and some more practical. Note that here we will not delve into the specifics of each of the methods a programming language can be classified, that will be left to specific lectures following on subsequent weeks. We merely introduce the notions here.

Classifying by Paradigm

We generally look to paradigms (imperative, procedural, functional, logic, visual, oop, multi) when we discuss programming languages. These are tried and true classifications that a language fits into to. However, paradigm really only focus how the programmer is impacted when developing code and says little about how the language fits into the development cycle.

Classifying by Use

A less common way to look at programming languages is by its purported use, mainly because programmers have the freedom to apply any language to any solution. However, this does not always yield optimal results. Should one use a scripting language to develop a word processor? Some languages that gain public support end up being transformed and its purpose changes. Sometimes this results in a better, more powerful language and sometimes it becomes somewhat of a mess. Python is such a language that has become popular as now a development language.

Classifying by Implementation

Languages are generally interpreted or compiled (details to follow in week 2). There are some that use a hybrid approach (Java) compiling into an intermediate form and then using a virtual machine to run them. Is that virtual machine an interpreter or an emulator? That question requires further thought, however, classifying languages by implementation is a popular means to gauge effectiveness of use by programmers.

Classifying by Attributes

It could be argued that how a language is implemented is just an attribute, we separated it out (above) because it is a profound means to look at a language. In actuality, one could look at most of what has already been discussed as an attribute of the language. So this is a catch-all for smaller distinctions that may or may not deserve their own section. One such attribute is whether a language is "typed" or not (we mean data type here). Another is whether the language is free format (most) or uses indentation (Python) to determine block structure. Is the language case sensitive?

Classifying by Generation

A much less used (and somewhat older) means of talking about a programming language. First generation languages were the processor's code (aka machine code). Second generation languages mapped this machine code to more human readable form of an Assembly Language (a one-to-one mapping of mnemonics to instructions). Third generation languages gets us to where we are now with modern high-level languages (giving a one-to-many mapping from code to instructions). There are also fourth generation classifications focusing on systems such as DB's and fifth generation classifications designed to make the computer solve a given problem without the programmer (i.e. expert systems).

Week 2 - Compilers, interpreters and BNF grammars

Content authors (Group #1) Ethan Jarzombek & Kevin Richardson

Outline

    • Tools used in Programming Languages
      • Compiler
        • what is it and how does it work (add picture)
        • pros and cons of compiler
      • Interpreter
        • what is it and how does it work (add picture)
        • pros and cons of an interpreter
      • How does an Assembler fit into this picture
        • explain what an assembler is
    • Grammars - what are their purpose
      • Backus Naur form - define and describe BNF and give examples
      • Context Free Grammars (CFG) - define and discuss
        • brief description explaining why CFG's are best for programming languages
      • Parsing - what is it and how does it relate to both grammars
        • where does it fit in with compilers and interpreter

Tools in Programming Languages

When selecting a programming language to use, there are many different factors to take into consideration. One feature that deserves some thought is whether the language compiles or interprets the source code. The way a computer interprets what you are telling it to do greatly affects the way it is executed. Both methods have their pros and cons, so it is important to know and understand the key differences before you dive right in.

COMPILERS

Compilers are distinguished by their ability to convert an entire script into executable machine code all at once to be able to run instantly on other machines. Once the source code is translated into machine code, you are left with two separate files: your original source code, and an executable file. The executable file is essentially 1's and 0's known as machine code, which can be understood by your computer, but not the human eye (without a lot of work). The source code can remain on your system, and the executable can then be used or sent to any other machine to run.

What it is and how it works

A program that compiles its source code does so in stages. The source code first runs through a preprocessor to manage all of the files' imports. A parser is then used to check if the syntax is accurate and build a parse tree. From there, the code can then be generated and optimized for execution. A linker, the last stage of the compiler, finalizes the transaction of turning the file into an executable. Once the executable has been created, it is finally ready to be run by the user.

X.png

Pros and Cons

The initial process of compiling code into an executable might take some time, but will be much faster in the long run since the executable file is ready to go whenever you run it. Having the source code compiled into an executable also allows you to keep the source code private, since only the executable file is shared (which is written in machine code). The down-side to compiling your programs means that your executable is not cross-platform compatible. This means you would have to create separate binaries (executable machine code) for each type of operating system to understand, making it less flexible or interactive than interpreters. In addition to this, compiling also requires an extra compiling step while you are developing the code, meaning every time you want to run your code for debugging purposes, it will have to be compiled. This may not seem so bad, but can prove to be quite the nuisance for larger programs that require a lot of testing.

W.png

INTERPRETERS

Interpreters are distinguished by the way they translate your source code line by line as the program is run, rather than doing it all at once as a compiler does. Sending your source code directly to the consumer, or they can then download the appropriate interpreter program for their machine to translate the program during run-time.

What it is and how it works

A program that is interpreted on a machine is translated as it runs. This means that each line of code is converted to binary machine code and executed ont he user's machine before moving to the next line of code.

Y.png

Pros and Cons

Interpreting code can be useful in that it is cross-platform compatible, meaning the programmer only needs to distribute one file for all systems, and let the interpreter program on the consumer's machine do the rest. In addition to this, debugging is made simpler since the source code does not need to be compiled every time during development. Translating code line-by-line can be useful in some situations, but may also prove to be inefficient in others. For instance, having to translate each line of code every time the program runs makes it much slower than a fully compiled executable. Also, since the source code is distributed to the users rather than an almost cryptic executable file, the source code is open free to the public.

Z.png

HOW AN ASSEMBLER FITS INTO THE PICTURE

Both compiled and interpreted programs are written in a high level fairly easy-to-read programming language, then translated into machine code to be understood by a computer. An assembler, on the other hand, takes in a low level language known as assembly language, which is essentially the first step up from binary code. It takes blocks of binary and groups them together into more manageable commands to be used by humans for coding. Simply writing machine code in itself would be near impossible due to its complex and cumbersome nature of millions of 1's and 0's, so assembly turns those bytes of unmanageable data into something easier to understand and use. Once your assembly program is written, an assembler is used to convert it to machine code for execution.

What is an assembler?

An assembler is a program that converts assembly language into machine code. It works much like a compiler in that it produces a single executable file rather than line-by-line like an interpreter. The only difference is, that assemblers can only handle low-level languages. Every processor interprets machine code differently, so there is different assembly language for every type of machine.

Grammars

Programming languages can be described by both their semantics and the syntax of the language. The semantics of a language describes the process a computer follows when executing a program in a specific language. In essence, semantics indicates the meaning of every possible construction that is possible within that particular programming language. Syntax defines the rules for arranging the structure of a programming language. While the semantics of a programing language can be described in multiple different ways, one technology is typically used to describe the syntax of a language, which are known as context free grammars.

Backus-Naur Form

Backus-Naur Form (BNF), also commonly referred to as Backus-Naur notation is a formal method of notation used to describe a programming language. The goal of Backus-Naur form is to ensure that there is absolutely no ambiguity or conflicting information when defining a programming language. Production rules, used by Backus-Naur Form grammars, resemble mathematical expressions are used to define the set of strings and symbols used in a programming language. Below is an example of BNF notation.

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

A production rule states that the symbol on the left hand side of the "::=" must be replaced with one of the alternatives on the right side. The bar symbols on the right side of the above expression separate the alternative options as to what <digit> can be.

Context Free Grammars

Context Free Grammars (CFG) are used to generate context free languages by taking sets of variables defined recursively in terms of one another by a set of production rules. Context free grammars are referred to as such because the production rules in the grammar can be applied regardless of context. Context free grammars are typically made up of the following components: terminal symbols, non-terminal symbols (also referred to as variables), production rules, and a start symbol. Terminal symbols are characters that appear in the language or strings generated by the grammar. In context free grammars terminal symbols never appear on the left side of the production rule expression and always appear on the right side. Non-terminal symbols or variables, act as placeholders for combinations of terminal symbols that can be generated by the non-terminal symbols. Typically non-terminal symbols appear on the left hand side of the production rule but can also be included on the right side of the expression as well. Production rules, as mentioned above, are the rules for replacing non-terminal symbols. A start symbol is a special non-terminal symbol that appears in the initial line of the grammar. Languages that can be generated using regular expressions can be generated by a context-free grammar as well.

Terminalnonterminal.gif

Parsing

Parsing involves analyzing a series of symbols to determine its grammatical structure with respect to a given formal grammar. A parser will then build a data structure based on these symbols and when used with a compiler or interpreter an executable program can be created. Parsing considers a grammar and a string of text and applies two essential questions. First, does the string exist in the language of the grammar? Secondly, what is the structure of the string relative to the grammar?

Week 3 (& 2) - Programming paradigms; an overview of Perl

Content authors (Group #2) Adam Harney & Daniel Scott

Outline

  • Programming Paradigms - what is a programming paradigm?
    • Define each paradigm and give language example
      • Imperative, Procedural, Functional, Logic, Visual, OOP, Multi
  • Overview of Perl - give a one paragraph introduction about the history of the language
    • A couple of paragraphs discussing its basic structure (i.e. it's a statement based/imperative language)
      • add an example to highlight that
    • Types in Perl - one paragraph discussion of three types:
      • scalar, array, hash - add an example to show syntax
    • Print statement - one paragraph discussion of what it's used for
      • add example to show syntax on how to construct printed strings via concatenation operator "."
    • Conditionals - one paragraph discussion of the two types if & if/else
      • add example to show syntax of if
      • add example to show syntax of if/else
    • Loops - one paragraph discussion of both while and for loops
      • add example to show syntax of while loop
      • add example to show syntax of for loop
    • File I/O - one paragraph discussion of file i/o
      • add example to show syntax of how to read from a file (use a while loop like we did in class)
    • Subroutines - one paragraph discussion of subroutines (i.e. what they are)
      • add example to show syntax of a subroutine, specifically how to pass parameters

Programming Paradigms - what is a programming paradigm?

Programming Paradigms are a ways in which you can classify programming languages based on several factors such as features, organization, and execution model. Programming languages do not always neatly fall into one category, and can exhibit traits of several different paradigms.

Imperative

Examples: BASIC, Perl

Imperative Programming is made up of step by step commands, which are all executed in order from beginning to end. These commands can change variable values, do math, or otherwise change the state of the program, but they do not allow you to call sub routines. An advantage of this type of language is that you have much more knowledge about how and in what order your code is being executed, although you are much more limited in what you can do.

Procedural

Examples: C, C#, COBOL

The procedural paradigm is often considered a subset of the imperative paradigm. All procedural programming languages run through one or more subroutines (aka functions).

Functional

Examples: Lisp

Functional programming is completely based on mathematical functions. Functional languages have what are called pure functions, which means functions that have no side effects and no state. This means that recursion is incredibly important for functional languages.

Logical

Examples: Mercury

Logical programming is based entirely on logical reasoning, facts, and rules. Code in this language looks more like pseudo code than languages such as C++ and Java. A valid piece of code in a logical programming language could look like "x is true if y and z are false"

Visual

Examples: Scratch

Visual programming languages are coded using visual elements, such as blocks that can be dragged and dropped or manipulatable flow charts. These languages are very useful as learning tools, as they can be used by kids, or people who have a hard time visualizing the logic of a traditional programming language.

Object-Oriented

Examples: C++, Java

Object Oriented Programming focuses more on defining and interacting with objects than traditional languages, which were just about processing commands from the top down. Object Oriented languages allow multiple objects from a single class, as well as sub classes which can inherit traits of their parent classes. This can cut down on repeated code, and help organize large programs that need to keep track of tons of data.

Multi-Paradigm

Examples: Almost all of them

Multi-Paradigm languages are simply languages that do not strictly adhere to any of the above listed paradigms. Many languages can be considered multi-paradigm.

Overview of Perl

Perl is a Unix Scripting Language invented in 1987 by Larry Wall. It was created because Wall was unhappy with the functionality of the languages available at the time such as C. Perl has gone through several iterations throughout the years, with Perl 5 being the definitive version for many years, and Perl 6 being the most recent version.

Structure

Perl is a multi-paradigm language. Older versions of the language are entirely in the imperative paradigm, meaning that functions are processed line by line. However, more recent versions of Perl have given the language features of the functional and object-oriented paradigms.

$msg = "hi";
if ($msg eq "hi")
{
    print "hello\n";
}

Here is an example of a typical piece of Perl Code

Types in Perl

Unlike most languages, Perl only utilizes three types of variables. These variables are the bare basics necessary to emulate the same functions of the variables that are not available in Perl. While a language like Python might use dictionaries, Perl can combine two different types of variables to gain the same effect (hashes and arrays.) Though they may be few in number, they distinguish themselves in their own way. Here are the distinguishing traits and syntax of Perl data types:

Scalar Variables - Always preceded by a '$', a scalar variable is used to contain simple single values. For example, a scalar variable may hold an integer, string, or Boolean.

 Ex. 
 $variable = 1

Array Variables - An ordered list of scalar values. An array is always preceded by a '@' symbol. To access a place in the list, call upon it as a scalar variable followed by the list position within brackets.

 Ex.
 @list = (1, 2, 3)
 $list[0]
 result: 
 1

Hashes - A set consisting of a key and a value. Always preceded by a '%' symbol followed by a key and the value or variable within curly braces. To initialize one, however, a key must precede a ',' and then the value assigned to it.

 Ex.
 %Identification = ("John", 12345)
 $Identification{"John"}
 result:
 12345

Print Statement

Print statements in Perl are quite similar to the print statements in other similar language. Much like in python it starts with the command which in this case is "print" then enclosed in quotes the string that the user desires to be printed. This simple and common command does almost exactly as it would in any other language, printing the string onto the screen with minimal formatting. Less common traits might include the finer details of the print statement's usage. For example, the use of single and double quotes when it comes to the content being printed. While normally, with double quotes, a line break or tab character sequence would be interpreted as it's designated action, but with single quotes, it is printed literally as the character sequence is typed.

Conditionals

The if conditional in Perl looks very similar to if conditionals in languages like C++ and Java. The token "if" is followed by code within two parentheses ( "( )" ). If this code returns "True", the following code within the { } brackets is executed.

   Ex.
   my $gas = <STDIN>;
   if ($gas > 0) {
   print "You still have gas, you are good to go!"
   }

An If/Else conditional is done in a very similar way. Simply follow the code within the { } brackets with the token "else", and then add more code within a new set of { } brackets. This code will execute when the previous "if" conditional returns false instead of true.

   Ex.
   my $gas = <STDIN>;
   if ($gas > 0) {
   print "You still have gas, you are good to go!"
   } else {
   print "Sorry, looks like your out of gas."
   }

Loops

For loops, like in other languages, are useful to execute a certain block of code for a set number of times. the syntax begins with the token "for" followed by some code in parentheses. Inside the parentheses, you create a variable, run a conditional test, and then iterate that variable. After the parentheses is a set of { } brackets which contain code that will be executed for as long as your conditional test returns true.

   Ex.
   for (my $i=0; $i < 100; $i++) {
      print "$i\n";
   }

A while loop is similar to a for loop, but you are only testing a conditional. All variables are created outside of the for loop, and you have to make sure to alter those variables inside the while loop or you may get stuck in an infinite loop.

   Ex.
   my $beer = 12;

   while ($beer > 0) {
   print "you still have beer left!";
   $beer -= 1;
   }
   print "sorry, out of beer";

File I/O

File I/O refers to editing and reading an external file within a Perl script. This is done using what are called "File Handlers". The three types of file handlers are STDIN, STDOUT, and STDERR. STDIN is in charge of inputting data from an external file, STDOUT is in charge of altering external files, and STDERR is in charge of errors. A file can be opened in read only mode by using the < symbol within the open statement, and write only mode by using the > symbol instead. Here is an example of a file being opened in read only mode.

   Ex.
   open(DATA, "<datafile.txt");

You can open a file for appending in a similar manner.

   Ex.
   open(DATA, ">datafile.txt")

The example above will completely wipe all data from the file before allowing you to append however, so it may be more useful to add a + sign before the > symbol, which allows you to simply append data to the end of the existing data within the file.

   Ex.
   open(DATA, "+<datafile.txt");

Finally, here is an example of a piece of code which reads in a data file, and prints it's contents to the screen.

   Ex.
   my $filename = 'datafile.txt';
   open(my $file, '<:encoding(UTF-8)', $filename)
   while (my $row = <$fh>) {
     chomp $row;
     print "$row\n";
   }

Subroutines

Subroutines are collections of statements which complete a task, which can be called from elsewhere in the program. You may be more familiar with the term "function", which is what they are referred to as in most modern languages such as C++ and Java. They are created by placing a "sub" token, followed by the desired name of the subroutine. After that, you must place a set of { } brackets, within which is the code that you want to execute when the subroutine is called. You can call the subroutine by writing it's name followed by a parameter list (just an opening and closing parenthesis if you are not passing any arguments).

   Ex. 
   sub countApples {
      print "$apples\n";
   }

   my $apples = <STDIN>;
   countApples();

While calling a subroutine with no arguments is basically the same as any other language, things start to get different when you start adding arguments. Unlike Java or C++, you do not define how many arguments a subroutine takes in. Also, arguments are not automatically stored as local variables, instead they are stored in an array called $_[]. Different arguments can be called by changing the index number within the brackets, with 0 being the first argument entered, 1 being the second, etc.

   Ex.
   sub printArgs {
       my $first = $_[0]
       my $second = $_[1]
       print "$here is my first variable: "
       print "$first\n";
       print "$and here's my second: "
       print "$second\n";
   }
   printArgs(10, 20);

You can use loops, such as the for loop or the foreach loop, to iterate through all passed variables. This makes subroutines in Perl more flexible than functions in Java, as you do not need to create a seperate function for every amount of arguments you may need to pass into that function.

   Ex.
   sub addSomeStuff {
       $sum = 0;
       foreach $item (@_) {
           $sum += $item;
       }
       print "All that stuff added up to $sum\n";
   }
   addSomeStuff(1, 2);
   addSomeStuff(3, 4, 5, 6);
   addSomeStuff(7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20);

Week 4 - Language concepts: statements, control flow, expressons & operators

Content authors (Group #3) George Harvey & Wesley Krol

Outline

  • Language concepts: statements, control flow and expressions
    • Statements - give definition of statement
      • How this impacts paradigms
        • i.e. imperative is statement based but others do what differently?
      • discuss implied sequential nature
        • how program only sees current line and keeps state
        • perhaps draw a picture
    • Control flow - discuss how it manipulates execution
      • Draw picture showing sequential, conditional & loop
      • discuss how this adds structure to code to avoid spaghetti logic
      • Two categories - define, provide examples and a pictorial representation
        • Conditional - represents if, if/else, switch (what else)
        • Loops - represents for, while, do/while (anything else?)
    • Expressions - define
      • Boolean - examples
      • Numeric - examples
    • operators - explain the order of operations and how it affects execution.
      • give details about PEMDAS and examples
      • contrast with other standards

Statements

A statement is a block of code that executes some action. A statement can be one or several lines and also be comprised of other embedded statements. For example a variable assignment such as num = 32; is one statement. The previous example would be written on a single, however, a statement can be multiple lines of code and contain other statements. For example lets define a method in java that assigns the value 1 to a variable.

Statements can also impact the language's paradigm. Depending if it is either a OOB, procedural, functional, imperative, logical, visual, or a multi-paradigm language can determine how statements are written for example a statement in Java is ended with a semi colon and you can place multiple statements on a single line, whereas is Python a statement is not ended with a semi colon, statements are separated by new lines and sub sequential indentation therefore you cannot have multiple statements on a single line. Below are the statements written in java and python but showing the differences.
JavaExample.png
PythonExample.png
The above two statements are both functions that, define a variable, print that variable, and then print a string. However, as you can see the way in which we write statements between different languages can differ.

Control Flow

Control is an integral part in any language as it is sequence the language executes statements. Computing languages have a fundamental practice of going sequentially, that is, line by line, however in most languages there are certain statements that adjust the control from being line to line and dictate what the languages overall control flow is. These statements can include but are not limited to, comparisons ( if, else if, else ), switches, loops (for, do while, while, repeat), goto, etc... These statements can cause the control flow to deviate from the line by line sequence and "jump around" to other sections. The first example shows a basic line by line control whereas the second shows how control flow can change with certain statements. The lines are numbered by order of execution.

Example 1:
PythonExample2.png


Example 2 ( Where the blue only gets executed if the conditional is true and the green only gets executed if the conditional is false ):
PythonExample3.png

Expressions

Expressions in programming are the comparison or computation of one or more values or variables. Expressions can be, multiplication, addition, subtraction, division, comparison and more, of two or more values. Expressions can be written as part of a statement, but the typically are not their own statement. For example an expression can be the value a variable is assigned to making that assignment statement include an expression. Expressions return a value. Below are a few examples.
5 + 10
4 * 2
16 -7
10 / 5
16 > 9
10 == 10

Operators

Operators are the symbols used used in expression to compare or compute two or more values. Below are the most commonly used operators.
'+' addition operator
'-' subtraction operator
'*' multiplication operator
'/' division operator
'>' greater than operator
'<' less than operator
'==' equals operator

Week 5 (& 4) - An overview Lisp

Content authors (Group #4) Dylan Durand & Brandon Peterson

Outline

  • Lisp - explain the paradigm and what it implies for Lisp.
    • A little history, background and application of Lisp (i.e. Artificial Intelligence).
    • Give a brief overview of the language with Lisp example of each
      • Recursion in Lisp - discuss and give a coding example (i.e. fibonacci or factorial)
      • Basic components - discuss
        • atoms, lists and s-expressions
      • Some common functions
        • Assignment: set (remind readers to quote arguments with ' to prevent evaluation)
        • Math functions: +, -, *, /
        • List functions: list, cons, append, car, cdr
        • Defining functions: defun
        • Conditional functions: cond, null
      • Examples programs in Lisp
        • factorial function
        • a reverse function
        • a function that doubles each element in list

Some Common Functions

Assignment

In LISP, variable assignment is done with SET function. The SET function takes two arguments, the symbol being assigned and what is assigned to that variable. For instance, ( set 'x 30 ) would set the symbol x to 30. It is important to note that there must be a ' in front of x, otherwise LISP will attempt to evaluate it. Because of this, there is a common shortcut in the form of the command SETQ. SETQ works just like SET, except that it puts an apostrophe in front of the first argument automatically. That means that the above code is equivalent to (setq x 30). LISP is typeless, so SET can be used to assign anything to a symbol. This includes lists, or other symbols.


Math Functions

LISP supports the four basic math operations using the operators +, -, * and /. Like all of LISP's other functions, they are called using pre-fix notation instead of the more common in-fix method. That means that an expression like 8 + 2 * 5 / 1 -10 in LISP would instead look like (- (+ 8 (/ (* 2 5) 1) ) 10 )

List Functions

Lists are one of the two most important data types in LISP. Fortunately, LISP has several functions predefined for working with and manipulating lists. These functions include list, cons, append, car and cdr. These functions may not be straightforward at first, but they each fulfill an important role in the programming language. First is list, which is fairly simple.

The list function returns the argument passed into it as a list. For instance (list 'a) returns (A). List can be given any number of arguments. If one wanted to create the list (A B C), they could use the command (list 'a 'b 'c) .

Append is another command that is easy to guess. Append adds the second list to the end of the first list passed in as arguments. Let's say that the user wants to add the symbol d to the list (A B C). Instead of creating a new list, one could type (append (list 'a 'b 'c) (list 'd)) .

The cons function is similar to append, but it has a few important distinctions. For one, cons adds the first argument to the beginning of the second argument. Secondly, it adds the entire argument instead of the contents of it. This is a subtle distinction that is best illustrated with an example. Let's see what happens when we try to create the list (A B C D) from the previous example, but this time using cons instead of append. The code (cons (list 'a 'b 'c) (list 'd) instead returns ( (A B C) D ). Cons added the list (A B C) to the list ( D ) instead of appending the contents. (car '(a b c)) The last two list functions, car and cdr, are incredibly important for iterating through lists in LISP. Using the car function on a list returns the first element in that list. For example (car '(a b c)) will print A to the console. Cdr on the other hand, does the opposite of car. Cdr returns a list containing everything except the first element of the list given as an argument. For comparison (cdr '(a b c)) returns (B C). These two functions, along with recursive function calls, allow a programmer to traverse a list in LISP.

Defining Functions

In order to define functions in Lisp, one must use the Defun command. This command is in the form of defun <function_name> (<arguments>) (<body>). Because Lisp is a symbolic language, there are no restrictions on what a function can be named. A function can have zero or more arguments. There are some additional ways to define arguments to give a function increased functionality. For instance one can specify certain parameters as &optional. This means that if the function is called with more arguments than required, they will be assigned to the symbols listed after the &optional symbol. For example, defun echo (string &optional number) ... . This defines a function called echo which takes one argument, string. If echo is called with two arguments, the second argument will be assigned to the symbol number. Otherwise, number will default to nil. If a programmer wants to change the default value of an optional parameter, they can enter a list after the &optional symbol. The list contains the symbol being assigned and the value assigned to it. For instance, defun echo (string &optional (number 10)) ... will set number to either the second parameter, or 10 if there is no second parameter. Lastly, to define a function with a variable number of arguments, one can use the &rest command. This stores any additional parameters given to the function in a list called &rest, which can be called within the body of the function. The body of the function defines what the program will execute when that function is called. By default the function will return the results of the last command executed.

Conditional Functions

Conditional functions in Lisp can be created with the command cond. This command may look strange to people used to programming in other languages, but it is actually quite simple. Cond is called in the form of cond ( (<test> <result>) ) ... . Essentially, cond takes a list of if then statements contained in a list. The first value in each list is the condition that is being checked. The second value is what will be evaluated if the previous condition is true. Cond can be given any number of arguments. In order to create a default case, one can put t as the first value in a conditional list. T stands for true, and cond will evaluate that expression of none of the previous conditions evaluate to true. This is equivalent to an else statement in other languages. Here is an example of a cond statement in Lisp. cond( ((= a 10) (- a 10)) (t (+ a 1) ) When this code runs, it will check if the symbol a evaluates to 10. If it does, it will subtract 10 from a. Otherwise it will increase a by 1.

Example Programs in Lisp

Factorial

This function takes a number and returns the factorial of that number.

   (defun fact (n)
       (cond
           ((= n 0) 1 )
           (t (* n (fact (- n 1))))
       )
   ) 

Fibonacci

This function returns the nth number in the fibonacci sequence, where fibonacci of n = (fib n-1) + (fib n-2).

   (defun fib (n)
       (cond
           ((= n 0) 0)
           ((= n 1) 1 )
           (t (+ (fib(- n 1)) (fib (- n 2))))
       )
   )

Double List

This function takes a list as input and returns a list where each element is equal to 2 the element in the original list.

   (defun double (n)
       (cond
           ((null (car n)) nil)
           (t (cons (* 2 (car n)) (double (cdr n))))
       )
   )

Week 6 (& 5) - Language concepts: variable types, scope, implementation & parameter passing

Content authors (Group #5) Miranda Thompson & Jim Canavan

Outline

  • Variables (what are variables in computer Programming?)
    • How are variables represented (it's three values: address, size, information)
  • Data Types (what does type mean for a variable and why is it important -- i.e. reserving memory)
    • Strong vs weak typed language (definition with examples)
    • Dynamic vs static typed language (definition with examples)
    • Data types (each with definition and a simple example if needed)
    • Primitive (discuss/list common ones: i.e. int, flat, char, bool)
    • Complex (i.e. structs/records, classes)
  • Scope (define and discuss scope levels)
    • Who can see a variable (define and discuss global vs local scope)
    • Local
    • Global
    • parameter
    • Variable scope in OOP (reasoning behind using local and global in OOP)
  • Parameter Passing
    • Pass by value
      • Provide example in Java
    • Pass by reference
      • Provide example in C++
    • Briefly mention others like In/out but don't discuss them

Variables

A variable is an entity that is used as a reference point for the variable's stored information. The information stored in the variable may change when needed. A good variable name will describe what information that variable contains. Variables are used in programming so that the operations of code on the variable remain the same, but the stored information of that variable may change. An easy to understand example of a variable is found in basic algebra, for example x=y+z. Both variables y & z can store different information to produce x whose stored information will also change depending on y & z.

There are (6) properties that define variables that are extremely important to memorize.

  • Name - Symbolic representation of the data being stored with the variable. Example: Name_First, Name_Last, DOB, Gender, Phone_Num
  • Type - Represents what that data stored as. Example Name_first & Name_last suggests a String data type. DOB suggests a Date data type, and Phone_Num suggests an integer data type
  • Value - What the variable literally is. Example Name_first = "programming" we know the value of Name_first is programming and that it is a string
  • Scope - Defines which functions within the code have access to variables. Scope is detailed below.
  • Life Time - Closely tied to Scope, the lifetime of a variable is when the program reaches the line of code where they are "declared". Variables "die" when the program leaves the "Scope" of the variable.
  • Location (in Memory) - The space where the variable is stored in bits.

Representing Variables

  • Addressing:

All variables are loaded into the computer's memory in segments, typically as bytes. These segments are then assigned anaddress so that the processor can access the address containing the variable. Addressing has it's own section bellow which has more detail on addressing.

  • Size :

Size refers to how many bytes are needed to allocate the specified variable to memory and address it. The built-in data types that languages provide to programmers define the amount of bytes for each data type. This is important for the compiler as the compiler will reserve the necessary bytes in order to create a variable in question.

  • Information :

Data Types

Data type is an attribute of data which tells the compiler or interpreter how the programmer intends to use that data. For example, an integer is different from a string and defining "9" attribute to be an integer allows the user and compiler/interpreter to treat "9" as an integer versus a string. There are (2) data types, Primitive & Complex

  • Primitive-

Variables that do not contain value directly, but instead reference an object. An example of a primitive variable is a boolean or a float because booleans and floats do not have values themselves they point to their assignments of a true & false for boolean, or decimal number for float. These are very basic data types, and in most languages these are built-in.

  • Complex-

A data structure that isn't a primitive provided by the language. In other words, these are variables which are composites of existing data types. Complex data types should not be confused with aggregate data types which are data types like lists & arrays. An example of this is Date Time provided in Java. Date Time has (3) primitive data structures bundled into (1) date time complex structure. It is important to note, that date time cannot be broken down into smaller units. To break down date time you would just have 3 primitive data structures.

Common Primitive Data Types in Java:

  • Integer : Whole numbers where the size of the values depend on the type of integer the programmer chooses to use.

Brave 2019-04-16 14-52-06.png

  • Floating Point : Represent numbers with a fractional part. Single precision floating point numbers occupy 4 bytes and Double precision floating point numbers occupy 8 bytes.
  • Character : Stores character constants as a size of 2 bytes.
  • Boolean : Stores values as either True or False

Scope

Scope refers to the visibility of variables given the privileges of the user interacting with the program.

  • Who can see a variable-
    • An easy to understand example of scope is how users interact with variables differently such as front-end users, administrators, and super-admins. A front-end user would see fewer variables than an admin would. An example of this might be a reporting program for a business. A front-end user using a reporting program may only be able to see their own sales numbers and may have restrictions on how that data is sliced, for example not being able to view an average cost for a product. Admins, on the other hand, are able to view this data. Another more meaningful way, with regards to programming, to think about Scope is; how do programs access these variables? An example can be a function that only accesses the Local Variable versus a Global Variable. Using functions that only manipulate local variables may be necessary as to not damage the data from the originating source. There are (3) levels of scope wich a program can apply the rules of scope to, Global, Local and Parameter
    • Global-
      • Variables that are referenced and accessible throughout the entire program.
    • Local-
      • Variables that are referenced and accessible in a function or block that in some cases may override the same variable if it were defined in a larger scope. Consider the image below, where $a is globally set to (1). It is then re-defined locally to be (2), then called. $a is called twice but takes the local variable value.



Perl-local-var.png

  • Parameter-
    • A Parameter is the symbolic name for "data" that passes through a function. Consider the mathematical problem 1 + 2. We can assign a=1, b=2 and use a function add(a, b) to get the answer 3. Within the function, a & b are parameters. Outside of the context of the function, a & b are primitive data structures. More specifically, the example demonstrates the use of a Formal Parameter being treated as local variable.

Passing Parameters

There are (3) Calling Modes in which parameters can be passed through functions or procedures. Each Mode uniquely treats how parameters are accessed, as well as different degrees of efficiency in accessing those parameters being passed which is explained in the "Stack & Address" section below.

  • Call by Value

Call by Value protects the actual parameter value. Regardless of what the subprogram does, the parameter can not be changed.

  • Call by Reference
  • Call by Name

Stack & Address

  • Stack in programming is an array or list that follows a particular order which is performed.
    • Stack Frame-
      • Stack frame is a frame that has data that gets pushed up onto the stack.

P56ru.jpg

  • Memory Access of Stack Frame-
    • Difference Between "Call by Reference" and "Call by value"

Hqdefault.jpg

Week 7 (& 6) - An overview of Scratch

Content authors (Group #6) Xavier Doyle & Yurii Gromakov

Outline

  • What is a visual Programming Language
    • paradigm
    • advantages and disadvantages of Scratch
  • A tutorial on Scratch with example
    • pictorial view of Scratch Window
    • explain Scratch block types.
      • i.e.Scratch data types.
    • functionalities of each pane: list categories and describe
      • i.e. the 8 main for 1.4 (maybe more for 2.0)
      • short code example for each category
      • Note: give a feel of the language without being complete
    • what are sprites - how do they compare to objects
    • Complexity in Scratch
      • Race Conditions
      • How to avoid Race Condition
      • Concurrency issues

What is a visual Programming Language

In computing, a visual programming language (VPL) is any programming language that lets users create programs by manipulating program elements graphically rather than by specifying them textually.

Visual Paradigm

The general goal of VPLs is to make programming more accessible to novices and to support programmers at three different levels

Syntax: VPLs use icons/blocks, forms and diagrams trying to reduce or even to completely eliminate the potential of syntactic errors helping with the arrangement of programming primitives to create well-formed programs. Non VPLs examples would be spell check in word processors underlining or even auto correcting individual words or grammar.

Semantics: VPLs may provide some mechanisms to disclose the meaning of programming primitives. This could include help functions providing documentation functions built-in to programming languages.

Advantages and Disadvantages of Scratch

Scratch has a large number of command blocks and more are added with every update, this means that Scratch can be programmed to conduct a large amount of different activities. This increases it's diversity and usability, allowing a range of unique projects to be created. A draw back to Scratch is that it is not an official version of the app available on mobile devices such as tablet computers, there is however an official version of ScratchJr as an app, although this is only available as an app and not available on desktops or laptops.

Scratch Tutorial

Scratch programming depends on objects referred to as sprites. Each sprite has the ability to move separately from each other. All scratch code relates to individual sprites to create motion and to control how each sprite interacts with other sprites on the screen. Control of the sprites is initiated when the green flag icon is clicked which executes the scratch program.

Scratchexample.png

Scratch Data Types

Motion- Controls the motion of Sprites.

Looks- Controls settings of Sprites and allows user to toggle Sprites costume changing looks. Most commonly used to create animation of Sprites.

Sound- Controls audio associated with Sprites and their motion/ controls.

Events-Event handlers, these blocks are used to initiate an action based off of a condition. Example: When Space bar is pressed, when sprite is clicked.

Control- Conditionals/ loops, these include blocks for if else statements as well as repeat loops.

Sensing- conditions. Example: Sprite touching sprite, sprite touching color.

Operators- expressions, these evaluate to true or false as well as perform the mathematical concepts in scratch as well as create random numbers.

Variables- getters and setters for variables. Also show and hide features of variables.

Myblocks- customize blocks.


Scratch Panes

Sprite pane-The Sprite Pane is an area of the graphical user interface (GUI) of the Scratch program where all sprites presented in a project can be easily accessed to customize. It is a white area located beneath the Stage with the label "Sprites" in the project header. During small stage layout, the sprite pane has a reduced width, though the sprite icons inside adjust to the new size properly.

Costume pane-The costume pane ("backdrop pane" in the Stage) is part of Scratch's built-in paint editor. The pane consists of all the costumes of the currently selected sprite. It is scrollable and highlights blue the costume that is currently being displayed on the paint editor canvas. The costume pane also includes options to create new costumes. These can be used to create the illusion of animation within scratch programs by switching between costumes while a sprite is in motion.

Sprites in Relation to Objects

Sprites, either user-created, uploaded, or found in the sprites library, are the objects that perform actions in a project. While the Stage can also be programmed in a project, most projects have at least one sprite as well because only sprites can move. In order to perform motion tasks each individually moving "object" will have to be done with a new sprite. Sprites can be compared to actually objects in object oriented languages.

Race Conditions and Concurrency

Race conditions happen in scratch when multiple control blocks implement a change to a sprite or variable at the same time. For example if if two block sets are initiated when the green flag is clicked both will execute simultaneously often causing uncertain out comes. Scratch executes linearly through the code provided. If different controls are executed immediately after an event scratch will randomly set to either one. This problem is known as concurrency issues. However if the control blocks are manipulating different items this allows for multiple code blocks to execute simultaneously increasing usability.


Race scratch.png

Week 8: SPRING BREAK

No classes


Week 9 - Language usage (utility, development) and the modern paradigm: OOP vs procedural

Content authors (Group #5) Miranda Thompson & Jim Canavan

Outline

  • Language usage - utility vs development. - Include a brief discussion of what is implied here.
    • Development - elaborate on what makes a language this
      • What makes a language transform from utility to development
    • Utility - what makes a language this
      • Usage of web development and scripting languages
  • Comparison of the modern paradigm - OOP vs procedural.
    • Structure put on language and its purpose
      • Typed languages - restricts freedom to reduce error
      • how a struct (record) in procedural transformed into a class in OOP
      • Fundamentals structure of OOP
        • Encapsulation - reduces access to data (example)
        • Inheritance - adds hierarchy to data reuse (example)
        • Polymorphism - allows generality of data (example)
    • A quick contrast with pre-procedural paradigm - imperative</s>
      • lacks structure - no subroutines</s>
      • spaghetti logic - "go-to" dilema</s>
      • An example of OOP vs Procedural would be good here </s>


Language Usage & Utility Versus Development

Utility languages are used for very specific tasks for example shell scripting or SQL. Whereas development languages like Java and Python have a myriad of uses. You would not a build a website in SQL, but you could query a database and build a website with Python however, SQL allows you more tools to query the database as it's a language that is designed for database queries.

OOP Vs. Procedural Programming

  • Object Oriented Programming uses classes and objects to create a model in the vision of a real world environment or entity. OOP makes maininting and modifying existing code easy, as well as creating new objects, this cuts down on development time considerably. In addition, this allows several programmers to understand the existing code better with the use of descriptive comments. Objects in OOP languages in some cases and be destroyed from memory when they are not in use, this allows for a better function program.
  • Procedural Programming takes a "top-down" approach where the program starts at the top and breaks the program down into sub routines. The issue in Procedural Programming is that if an edit is needed to the program, the developer must edit every line of code that corresponds to the original change in the code


Fundamentals structure of OOP

  • Ecapsulation

This provides a method in which the complexity of an object is hidden. For example, a driver of a car does not need to know the intricacies of an internal combustion engine, they just need to know gas, break, steering. The same is true in programming. This also allows for change in code to be updated more easy.

Encapsulation.jpg

  • Inheritance

Inheritance enables new classes to receive or inherit the properties and methods of existing classes. Consider the example below. The class is vehicle. Vehicles have wheels, but not all vehicles have the same amount of wheels. If we were to think about this as a programmer would, we would need create a class vehicle with an attribute wheels. Then in our code, we would use a function to assign the proper amount of wheels to each sub-class of vehicles.
Inheritance.png

  • Polymorphism

Allows the programmer to treat objects & classes as if they were other objects and classes. For example, we can have child classes of Circle, Square and Star. Each of these are separate, encapsulated classes and yet each of these are also extensions of the Shape class. This means that any function, such as a draw function, are inherited.

Week 10 - Parsing: syntax vs semantics; Tokenization - a lexical analyzer in Java

Content authors (Group #2) Adam Harney & Daniel Scott

Outline

  • Parsing - Syntax vs. Semantics - Includes a brief summary of the two.
    • Syntax - A set of rules to be followed.
      • The arrangement of words/symbols in the structure.
    • Semantics - The meaning of a text.
      • The logic concerned with its meaning in the structure
  • A Lexical Analyzer in Java.
    • What is a token?
      • Tokenization: mapping keyword to numeric value
    • Source code for Java based tokenizer written in class (use week10.zip on web page as source).
      • break into functions and discuss each purpose
      • add header and footer for class definition to make complete Parser.java class

Week 11 - Parsing: implementing a language - a recursive descent parser in Java

Content authors (Group #2) Adam Harney & Daniel Scott

Outline

  • What is a Parser
    • Types of Parsers: Top-Down vs Bottom-Up
  • Structure of a Parser
    • Parse Tree
    • Grammar in Parsing
  • A Recursive Descent parser: definition
    • Implementing SQRL
      • BNF Grammar for SQRL
      • Source code for SQRL written in class (use week11.zip on web page as source).
        • break into functions and discuss each purpose
        • group some of the one line functions into one chunk
      • some examples of SQRL in action

What is a Parser?

A parser's function is to take code and break it down into distinct parts called "tokens" (see wk 10 notes) which can be executed by another part of the compiler. There are two different approaches to the way a Parser can work, either with a Top Down structure or a Bottom Up structure.

Top Down

Top Down parsing is a very simple to understand, but has many downfalls. Top Down Parsing starts at the beginning of a piece of code and continues downwards, working as it goes. This type of Parser is what was mainly used back in the 70s and earlier. The main problem with this type of parser is that it struggles with expressions, or any piece of code that forces it to look ahead very far.

Bottom Up

Bottom Up parsing works in the opposite way of Top Down parsing. Bottom Up parsing starts at the leaf nodes of the code, and tries to work it's way up to the root. This is generally the way parsers are built nowadays. Bottom Up parsing is not just defined as one thing however, as it can be further divided into seperate structures such as LR parsers, simple LR parsers, LR look ahead parsers, shift reduce parsers, and many more.

Structure of a Parser

Parse Tree

MeParse.png
Photo source: http://interactivepython.org/runestone/static/pythonds/Trees/ParseTree.html
Parse Trees are extremely important to parsers, and are extremely important to modern programming languages. Parse Trees are ordered trees derived from the language's grammar that represent an equation or string in a way that can be interpreted by a compiler. They allow use to do many things, including writing expressions in our code, which is represented in the image above. The above image shows what a typical parse tree would look like for the expression: (7 + 3) * (5 * 2). As you can see, the tree's root is the * symbol, as it is the last part of the expression which needs to be executed. Further down the tree, we go into the parentheses to find more operators, whose leaf nodes are the integer values which they are going to operate on.

Grammar in Parsing

Another important aspect of parsers are the grammars on which they operate. A grammar can make the monumental task of creating a language with almost infinite variations of possible code much simpler, by breaking down all of those possibilites into a much smaller set of rules. These grammars are the basis for any programming language, as they define the keywords, constants, syntax, and structure of the entire language. Grammars are also helpful as a checklist when implementing a language.

A Recursive Descent parser

A recursive descent parser is a type of parser which is top-down and uses recursion on input to create it's parse tree. This is the type of parser that was used to implement our SQRL language.

Implementing SQRL

BNF Grammar for SQRL

SQRLgrammar.PNG
Our grammar for SQRL seems rather limiting at first, but there is a lot that can be done with it. It defines code as one of 5 statements, a print statement, a load statement, an input (or variable assignment) statement, an if statement, or a mathematical expression. The last of these statements, the mathematical expression, can be one of addition, subtraction, multiplication, division, or just a lone value. The grammar also expands the conditional portion of the if statement to be greater than, less than, or equals to. The rest of the grammar is simply defining characters, digits, numbers, symbols, text, strings, and values within the language.

Source code for SQRL

public Parse()

Parse1.PNG
This is the constructor for our parser. It completes the setup necessary for our parser to work. It creates a line variable which it sets to blank as a default, it creates a new Scanner called scan which will be used to read input, and it creates an array of integers 26 elements long called vars, which is used to store variable values, with each element of the array corresponding to a letter of the alphabet (a=1,b=2,...,z=26).

public void run()

SQRLParse2.PNG
run() is the first method called by SQRL after the parser has been constructed. It prints out an introductory message to the user, grabs the first token, and passes that token to parseCode().

private void parseCode(String token)

Parse3.PNG
parseCode() is the main loop of our parser. It is called from run() at the beginning of the program, and will continue to grab tokens and call parseStmt() on those tokens until it detects the . token, which is SQRL's end of code symbol.

private void parseStmt(String token)

Parse4 1.PNG
Parse4 2.PNG
parseStmt() is the main method in charge of taking tokens and performing different actions based on the content of those tokens. Many of the methods in our parser will be called from this method. This is the incomplete version of the method provided on the stem.unh.edu site, and this description only covers the functionality of the provided code.

If the token given to parseStmt is "load", the parser will take the next token as a string and pass it into the loadPgm method, which takes care of loading external files into SQRL as code. If the token given to parseStmt is "print", it will do one of two things depending on what the first character in the next token is. If that character is a quotation mark, the rest of the string will be outputted as is to the command line. Otherwise, parseExpr() will be called to handle the expression. If the token given to parseStmt is "input", the parser will check that the token is a valid variable value using the isVar() method. If this is successful, SQRL will prompt the user to give a value, which will be stored in the vars array with a location that represents the variable it is being assigned to.

private String loadPgm(String name)

Parse5.PNG
loadPgm() is in charge of executing code from a file. It will simply scan in every line from the file it is given until there are no new lines to scan.

private int parseExpr(String token)

Parse6.PNG
This method is used to evaluate mathematical expressions. The version shown here is the one provided on the stem.unh.edu site, and is incomplete, as it only performs addition, whereas the final version will perform subtraction, multiplication, and division as well. The method first takes a token, and then looks at the next token to check if it is an operator. The next token is checked in a switch statement, where it will break out of if the next token is not an operator, returning just the original token value. If the next token IS an operator, it will take one more token and perform the given operation on the two token values. The result will be returned.

private int parseVal(String token)

Parse7.PNG
This method takes in a value as a parameter and checks if it is an numeric value or a variable. If it is a numeric value it is returned as an integer. Otherwise it is passed into the parseVar() method, which is then returned.

private int parseVar(String token)

Parse8.PNG
This method is called from the parseVal() Method. It calls the isVar() Method to check if the passed token is a valid variable value. If it is not, reportError() is called. If it is, the ascii value for the variable is returned.

private boolean isVar(String token)

Parse9.PNG
This method is called from parseVar and is meant to return true if the passed token is a valid variable, or false if it is not. It checks that the token is only one character long, and that it is an alphabetical symbol, not a numeric or other symbol.

private void storeVar(String token, int val)

Parse10.PNG
This method is used to store variable values. It takes in a token and a value. The value is stored in the index number of the vars array that corresponds to the ascii value of the token.

private boolean isNumeric(String token)

Parse11.PNG
This method checks that a token is a number. It iterates through every character in the token, calling the isDigit() method to ensure that they are all numeric values. If they are, it returns true, but if there is a non-numeric symbol at any point in the token it returns false.

private boolean isDigit(char ch)

Parse12.PNG
This method is used by the isNumeric() method to check if a single character is numeric or non-numeric.

private boolean isAlpha(char ch)

Parse13.PNG
This method checks the ascii value of a character to check if it is an alphabetical or non-alphabetical character.

private String parseString(String token)

Parse14.PNG
This method is in charge of parsing strings and ensuring that values passed to it are actually valid strings. The method takes the content in between the two " marks in the token, and returns that as a string. It will throw an error if the first character in the token is not a " mark, if a second " mark is not found in the token, or if a new line character is found in the string.

private boolean isNewLine(char ch)

Parse15.PNG
This is a basic boolean method which simply takes a character as an input and checks if that character matches with one of SQRL's new line characters (\n and \r).

private boolean isBlank(char ch)

Parse16.PNG
This is a basic boolean method which takes in a character and checks if it is blank.

private boolean isDelim(char ch)

Parse17.PNG
This is a basic boolean method which takes in a character and checks if it is delimeter. Defined delimeters in SQRL are +, -, *, /, >, <, =, ", and .

private String skipLeadingBlanks(String buffer)

Parse18.PNG
This method is called every time we go to grab a new token. It's function is to eliminated blank spaces before the start of the next token. This allows us to not have to worry about an extra space confusing our parser. For example, "print", " print", and " print" will all be converted to the string "print".

private String getToken()

Parse19.PNG
This method is used to grab the next token in the code. It starts by calling skipLeadingBlanks() to skip all blank spaces in the code, until we reach a non-blank space. Once a non-blank character is detected, the method iterates until it reaches a delimiter or blank space, at which point it grabs all the characters it has iterated through and returns them as a string.

private void reportError(String token)

Parse20.PNG
This method is used to report errors in a piece of code. When it is called from another method, it will print the line where the error occurs, and add a carat symbol to show exactly where the error has occured. It will then exit out of SQRL.

SQRL in Action

Loading Files and Printing Strings

SQRLexample1.PNG
above text contained within the file test.sqrl
SQRLexample2.PNG
Here is an example of a simple SQRL program which simply prints a few strings to the command line. The file test.sqrl is located in the same folder as SQRL.java and Parse.java

Input, Math, and the . symbol

SQRLexample3.PNG
above text contained within the file test2.sqrl
SQRLexample4.PNG
Here is an example of a simple SQRL program which takes input for 2 variables, and prints the result of adding those two variables. I've also added the . symbol to the end of the program, which causes the command prompt to exit out of SQRL once the program has been executed.

Week 12 - Grammars: Chomskys Hierarchy, Context Sensitive Grammars & Regular Expressions

Content authors (Group #3) George Harvey & Wesley Krol

Outline

  • Chomsky’s hierarchy. Touch upon each type, give examples and provide the table for creating production rules given in class
    • Type 0: Recursively enumerable grammars (give example)
    • Type 1: Context-sensitive grammars (give example)
    • Type 2: Context-free grammars (give example)
    • Type 3: Regular grammars (give example)
  • BNF versus notational form
    • discuss the two ways we've represented them
    • i.e. S -> A vs <start>  ::= <rule>
  • Properties of context-sensitive languages (CSG).
    • Compare CSG to Context Free Grammars (CFG) with respect to programming languages
    • Show and expand example: a^n b^n c^n done on board
      • First show a^n and its grammar (Regular) and a^n b^n and its grammar (CFG)
      • Give the solution of the class: S -> abc S-> aSBc cB -> Bc bB -> bb
        • Explain Kuroda normal form and how it impacts that solution
  • Regular Expression Syntax
    • Character classes ([0-9], [a-z], ...)
    • Meta-characters (., ?, *, \n, \t, ...)
      • Boolean "or"
      • Anchors
      • Iteration
    • Grouping (parentheses)

Week 13 - Table driven parsing

Content authors (Group #4) Dylan Durand & Brandon Peterson

Outline

  • Explain 2 types of Parsing in detail.
    • Difference between top-down and bottom-up parsing.
      • Top-down: Recursive Descent and LL(K)
      • Bottom-up: LL(R)
      • Give parse tree example of differences
    • Explain why most programming languages are "Bottom-up"
      • What are the difficulties in parsing.
  • Explain Table-driven parser.
    • Give an example, complete with example grammar, table and parse run
      • Include algorithm to parse
      • like to see a bit of a narrative of what's going on

Top-Down vs Bottom-Up Parsing

Top-Down Parsing

Top-down parsing is the most simple way to imagine language parsing. Simply put, top-down parsers start at the beginning of an expression and construct a parse tree by performing limited look aheads. When a top-down parser encounters a token, it will attempt to match that token to a production rule. It will then use that production rule to determine what the next token should be. If the parser cannot match the available tokens to an existing production rule, it backtracks and chooses a new production rule. The parser only finishes when it either exhausts all possible production rules without finding a match, in which case it would report a syntax error, or it finds the rule that is used to produce the expression it is parsing. There are two main ways of tackling this approach to parsing. One is recursive descent and the other is LL(k).


In recursive descent parsing, the parser attempts to trace a grammar recursively. It will substitute a non-terminal with a production rule, and continue substituting until all non-terminals have been replaced with terminals. This is covered in more detail above. Recursive descent parsers are simple to conceptualize and use limited look-aheads. Another way to perform top down parsing is using a table. Each column in the table represents a possible terminal in in the grammar and each row is a non-terminal. If there is a production rule that replaces a non-terminal with a terminal, that rule is placed in the corresponding intersection in the table. During parsing, a simple algorithm is used to determine if a string is valid.

Step 0) Push the start symbol and the end symbol onto the stack and set input equal to the first symbol in the string.

Step 1), if the top of the stack and the input are both equal to the end symbol, the string is valid and the parser is finished. Otherwise, go to step 2.

Step 2) if the top of the stack is equal to the input and not the end symbol, pop the stack and get the next symbol from the string. Go to step 1). Otherwise, go to step 3.

Step 3) if the top of the stack is equal to a non-terminal, perform a look up in the parse table and the top of the stack and input. If there is a production rule the, replace the top of the stack with that rule and go to step 1).

Step 4) if none of the above are true, the string is invalid for this grammar.

This type of parsing is referred to as Left-to-right left-hand derivation k, abbreviated LL(k), where k is the number of symbols the parser needs to look ahead in order to find a production rule.

TopDownTree.png

Source: http://what-when-how.com/compiler-writing/top-down-parsing-compiler-writing-part-1/

Bottom-Up Parsing

Bottom up parsing is similar to top-down parsing, except that it works in the opposite direction. In top-down parsing, the parser starts with a string of input and uses production rules from the start symbol to construct a matching string that fits the grammar. Bottom-up parsing uses the grammar's production rules to transform the input string into the start symbol. This is called LR(K) parsing. Much like in LL(k) parsers, the first l means that the input is read from left to right. The R means that rightmost derivations are performed, instead of leftmost derivations as in top-down parsing. Once again, the K represents the number of tokens the parser must look ahead to determine the proper production rule to use.

BottomUpTree2.jpg

Week 14/15 - An overview of lex and yacc

Content authors Mike Jonas

Outline

  • add item 1
  • add item 2