Programing Techniques

 

 

 

 

 

 

 

 

What the Specification says

Explain how functions, procedures and their related variables may be used to develop a program in a structured way, using stepwise refinement;

Describe the use of parameters, local and global variables as standard programming techniques; 

Explain how a stack is used to handle procedure calling and parameter passing; 

Explain the need for, and be able to create and apply, BNF (Backus-Naur form) and syntax diagrams;

Explain the need for reverse Polish notation;

Convert between reverse Polish notation and infix form of algebraic expressions using trees and stacks.

 

Notes

 

Stepwise Refinement

This is where a complex problem is broken down into smaller and smaller sub-problems until all the sub-problems can be solved easily.

 

Functions and Procedures

§  A procedure is a small section of code designed to perform a specific definable task, and may or may not return a single value.

§  A function is a block of code which performs a single task or calculation and returns a single value. They use local variables.

 

How Functions and Procedures can Develop Programs in a Structured way

§  Each module can be written as a functional procedure

§  Modules can be tested individually

§  Library routines can be used

§  The code is reusable

§  Main program consists of calls to functions/procedures which may be nested

 

Parameters

§  A parameter is (information about) an item of data supplied to a procedure or function which may be passed by reference or by value, and is used as a local variable.

 

Local Variables

§  Local variables exist only in the block which they are declared, they can only be accessed in that part.

§  The data contained in the variable is lost when the execution of that part of the program is complete

§  The same variable names can be used in different modules

§  This means that different programmers do not have to worry about variables overwriting themselves.

 

Global Variables

§  A variable that is defined at the start of a program and exists throughout program including functions/procedures.

§  Allows data to be shared between modules

§  Overridden by local variables with the same name

 

Stacks

§  When a procedure or function is called the program needs to know where to return to when the execution is complete. The return address must be known.

§  Also these functions and procedures may call more functions and procedures, all of these will have return addresses, which must be stored, along with the order.

§  This is done using a stack

§  When values are read, they are popped of the stack, but they remain in the stack.

§  The stack pointer can be moved then items are popped of or pushed on.

 

The Purpose of the Stack

§  So program can return correctly when procedure has been completed/store return address

§  Allows data to be transferred

 

Backus-Naur Form

§  BNF is to unambiguously define the syntax of a computer language

 

BNF and Syntax Diagrams Examples

 

<expression> ::= <term> | <expression> "+" <term>

<term>       ::= <factor> | <term> "*" <factor>

<factor>     ::= <constant> | <variable> | "(" <expression> ")"

<variable>   ::= "x" | "y" | "z"

<constant>   ::= <digit> | <digit> <constant>

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