Syntax and semantics

The text of a program, also called its code, is composed of words and punctuation. There are three types of words in every language: keywords are words reserved by the language that have always the same meaning; identifiers or names are words that are freely chosen by a programmer to designate abstract values or things; and literal strings are words that represent themselves.

How does one distinguish keywords from identifiers? Text editors will often automatically recognize keywords and give them a different color, like in the example above. Usually, a programming language only has very few keywords so it is possible to learn them by heart.

For example, in the program above, “while” is a keyword, “len” and “print” are identifiers chosen by programmers whom you likely haven't met, “a”, “m” and “i” are identifiers chosen by myself, and “"Maximum is"” is a literal string that represents the text “Maximum is”.

The meaning of a program, also called its semantics, is given by rules in the programming language. The semantic rules in a programming language are rules that associate a general meaning to every program fragment that use a particular syntax form.

Example semantic rules

To start, the language Python has a semantic rule that looks like this:

1. Assignment:

   Syntax: <identifier> = <expression>

   Semantics: a statement of this form, when encountered during execution, will assign the value of the expression on the right side of “=” to the variable designated by the name on the left side. If the variable does not exist yet, it is created automatically.

Using this rule, we can give meaning to a construct like “m = 0”: when this line is reached during execution, the value 0 is assigned to the variable designated by m. Since no such variable exists yet, it is created at that point. Likewise, for “i = i + 1”: when this line is reached during execution, the value computed by i + 1 is stored in the variable designated by i, which was created by i = 0 a few steps earlier.

What is a variable? A variable is a location in the computer's memory where you can store values. In most cases, variables can be modified: the value stored “in the variable” can be changed by the program over time. Changing the value of a variable is what is called an “assignment”.

The other semantic rules that are key to understand the example program above are:

2. Addition:

   Syntax: <expression> + <expression>

   Semantics: the expressions on both sides are first evaluated; the value of the combined expression is the result of adding the value of the expression on the left side to the value of the expression on the right side.

3. Comparison:

   Syntax: <expression> < <expression>

   Semantics: the expressions on both sides are first evaluated; the value of the combined expression is true if and only if the value of the expression on the left side is strictly lower than the value of the expression on the right side.

4. Repetition

   Syntax:

   while <expression> :

   <block>

   Semantics: the block is executed repeatedly as long as the expression on the first line evaluates to true.

5. Indexing

   Syntax: <identifier> [ <expression> ]

   Semantics: the expression between the square brackets is evaluated, then its value is used as index to one element of the array (table) identified by the name on the left.

6. Function call

   Syntax: <identifier> ( <expression> _[ , <expression> _]* )

   Semantics: when evaluating an expression of this form, first the expressions between parentheses are evaluated; then the function designated by the name on the right is invoked using the value of the expressions between parentheses as input arguments; when it completes execution, its return value becomes the value of the entire expression.

   Note

   The syntax for this last rule uses the notation _{[ ]*} to indicate zero or more repetitions of the syntax between _[]. Thanks to this, the rule applies to both len(a) and print("Maximum is", m).

7. Conditional execution

   Syntax:

   if <expression> :

   <block>

   Semantics: the expression is evaluated; then the block is executed if and only if the resulting value is true.

Program decomposition

Using these rules, we can decompose the meaning of a program by recognizing which semantic rule apply to each syntax form:

• the 1st line, by rule #1, is an assignment; it creates a variable called “a” and assigns the table of 6 values [1.55556, 3.2123, 3.11, 1, 0, 2] to it.
• the 2nd line, by rule #1, is also an assignment; it creates a variable called “m” and assigns the value 0 to it.
• the 3rd line, by rule #1, is also an assignment; it creates a variable called “i” and assigns the value 0 to it.
• the 4th line to the 7th line, as a whole, are a repetition due to rule #4. The block formed by lines 5-7 is repeated as long as the expression i < len(a) evaluates to true.
• the form i < len(a), is a comparison due to rule #3; it compares the current value of the variable designed by i to the value of len(a).
• the form len(a) is a function call due to rule #6; it invokes the function len on the value of the variable named a, which is the table of 6 elements. As the Python documentation then reveals, len returns the number of elements in the array, so it is always 6 in this program.
• the 5th and 6th lines, together, are a conditional execution due to rule #7. It evaluates the condition m < a[i] then executes m = a[i] if and only if the condition is true.
• m < a[i] is a comparison as per rule #3. See above.
• a[i] is an indexing as per rule #5; it retrieves the element in the array/table named a at the position indicated by i.
• m = a[i] is an assignment as per rule #1. See above.
• i = i + 1 is an assignment as per rule #1. See above. In turn it uses i + 1 which is an addition as per rule #2.
• print("Maximum is ", m) is a function call as per rule #6.

Once the program is decomposed, we can reconstruct its overall meaning by reading aloud the meaning of the individual lines:

1. create a variable a and set it to the table of 6 values;
2. create a variable m and set it to 0;
3. create a variable i and set it to 0;
4. repeat steps 5-7 below as long as i is strictly smaller than 6:
5. if m is strictly lower than the item in a at position i, then do step 6; otherwise go directly to 7;
6. set m to the item in a at position i;
7. set i to the sum of the (previous) value of i and 1;
8. print the text “Maximum is ” followed by the value of m.

Do you recognize it? This example program computes the maximum value in the table of 6 values.

This intellectual step where you recognize the overall meaning of a program fragment from a step-wise, piecemeal decomposition is called reverse-engineering. This task is not easy initially, but it becomes easier with practice. Also, in many cases the programs you will read will contain comments and annotations by their original writer, to help you understand the program code.