Programming language design Problem

1. Design a naïve and simple programming language which consists of the following primitive five statement types as program constructs, beside the declaration statements: These program constructs are powerful enough to write almost every algorithm for finding a solution of any given problem. [Throughout the rest of this semester, we will continue to expand this primitive programming language by adding other features, such as some data types, function or recursive call.]

Declaration statements; (e.g., int x; float x; int array A[1..n-1]; float array A[1..n-1]; char x; )

read and write statement;

assignment statement;

if-then-else statement and if-then statement; and

while-do statement;

Composition statement; i.e., statement; statement(s);

For example, I can use these program constructs to input (such as read) and output (such as write) any given integers, find the sum of these given integers, and output their total.

program sum

begin

int x, sum;

sum := 0;

while (not end of file) do

{read x;

write x;

sum := sum + x;

}

write sum;

end

Using these program constructs I can write binary search algorithm, mergeSort algorithm, ...

You are free to create the descriptive details of these statements, which allow define a set of grammar rules (also called syntax rules) for these statements. You also can add other features. However, you are advise to make it as simple as possible.

In addition to other reserved words, you can use begin and end as reserved words and {

Statements } for defining a block-structured language. For your reference, some of the grammar rules are given as follows: The notation < ... > is used to denote nonterminal symbols. Otherwise, they are terminal symbols (e.g., the entire program sum ... end are terminal symbols, consisting tokens/identifiers/variables, constant, assignment operators, relation operator such as not, and <, and many reserved words).

=> begin end

=> |

| { }

=> |

| | { Statements }

=> while () do ;

=> if ( ) then ;

| if ( ) then else ;

=> : = ;

=> | +

=> | *

=> | | ( )

=> |

=> A|B| ...|X| Y | Z | a | b | ....| x | y | z | 0 | 1 | 2 | ... | 8 | 9 |

=> |

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

Note that { ... } for declaring block of statements, which could be nested, such as

begin ... { ... { .... } ... { ... { .... } ...} .... } end.

These grammar rules are not complete. You are free to develop a complete set of grammar rules for these statements. You are advised to expand the following grammar rules to cover most of the basic properties/features for the statements for developing a program for any given problem.

2. Construct a finite state machine M that accepts these variables, constants, assignment operators and others, as well as all the reserved words for this primitive programming language that you are defined in Problem 1.

3. Construct a pushdown automata N for accepting or rejecting any given program which is written based on these program constructs, developed in Problem 1.