Concepts of Programming Language: Building a Parser

Example Pseudocode

Problem: Given a sorted array a with n elements (i.e., a[0] <= a[1] <= … a[n-1]) and a number m, find if m is in the array.

1. Main pseudo code

data

given data

n: the number of integers given

a[0], …, a[n-1]: the given integers

m: given integer (to check if it is in a)

unknown data: N.A.

intermediate data:

found: indicating if m is found from a

plan

// get array a, n from user input (numbers in a must be ordered).

n = getseries(a)

// find if m is in array a from index 0 to n-1

found = search(a, 0 , n-1, m)

if found print m is found in a.

Otherwise print m is not found in a.

(Pseudo code for all functions used in the main pseudocode)

2. Pseudo code for search function

Function name: search

input:

a: an array of numbers

bottom, top: bottom and top index

m: the number to search from a[bottom] to a[top]

output:

b: 1 if m is in a a[bottom] to a[top], 0 otherwise

Data

mid: middle index of the array

plan:

if (bottom > top) b = 0 and stop.

find the mid point mid of the array between bottom and top

if (a[mid] == m) b = 1

else if (m > a[mid])

P2.1 // find if m is in a from mid+1 to top:

b = search(a, mid+1, top, m)

else P2.2 // find if m is in a from bottom to mid-1

b = search(a, bottom, mid-1,m)

3. Pseudo code for getSeries function

omitted here