Notice that the lexical analyser (lexer) and the parser together convert the input stream of data into a tree structure -- a collection of objects linked together by pointers. When we draw UML diagrams of the semantics of a language we also describing these objects and how they will be associated.

State transition diagrams (figure 4.1) are an important part of computer science, but very easy to understand and use. These diagrams express the simplest kind of theoretical computer: the finite state machine or FSA. These are machines with limited memory (finite number of states) and star in several upper division electives in our degrees. The Unified Modeling Language (UML) has a diagram called a state machine. Here [ lexer.gif ] is Figure 4.1 drawn using an UML state machine. More on the UML later.

By the way, XML documents have their detailed syntax described in a form of Extended BNF.

Assigned work due

(2) You will use XBNF in your project work. Read the attached XBNF handout. You will be using a subset of HyperText Markup Language(HTML) in the Labs. Read the handout describing a subset of the HTML. Your project will be a longer document mixing XBNF, English, and diagrams, like these two handouts. Bring copies of today's handouts on XBNF and HTML to all future classes, and laboratories. Add your own notes and bring them to the final.

(4) Study the first 8 Review Questions at the end of chapter 3 and the first 8 questions at the end of chapter 4.

(4) Hand in written copies of 3 Review Questions (any mix of chapters) at start of next class (3 points)

Your Project

• comments
• examples
• syntax
• semantics

 		a+1

 		an expression like `foo+bar` adds `foo` to `bar`.

 		additive_expression::= term #(("+" | "-") term).

More on the UML later [ 05.html ] and here are some sample LRMs for well known languages [ ../samples/algol60.syntax.html ] [ ../samples/php_intro.html ] [ ../samples/python.html ] plus the syntax from other LRMs: [ ../samples/cobol.syntax.html ] [ ../samples/pascal.syntax.html ] etc.... Also see [ ../samples/ ]

Further, these four things (comments, examples, syntax, and semantics) need to be intermingled: you should be able to see the reason for a feature(comment), plus an example or two of the feature, and the rules (syntax and semantics) that apply to that feature all on the same page. We will use the UML to also provide a visual summary of the semantics of the language.

So for each part of the language that you are defining you will need:

1. Some commentary
2. Some examples
3. Some syntax definitions using some kind of BNF
4. Some semantics....mainly English but sometimes a piece of the UML and/or math helps.

Mini-Example: LRM for Decimal Numbers

(comment): Numbers are expressed using the familiar decimal notation. A string of decimal digits represents a number. The value of the number is calculated in the normal way.
(syntax):
1. number::= digit | digit number.
   (examples):

                  1

                  512

                  8192

2. digit::= "0".."9".

    			1

   The meaning of a digit is an interger in range 0..9 using the normal encoding.

   
   (semantics): The meaning of a string of n digits d = (d[n] d[n-1] ... d[3] d[2] d[1]) is called it's value. We can model value as a map from syntactically correct numbers (see number above) into the natural numbers, including 0,

3. Nat0={0,1,2,3,4,...}. The function value is defined by:

   

   So for example,

4. value("8192") = 8*1000 + 1*100 + 9*10 + 2
5. = 8192.

Examples vs Syntax

               for(i=1; i<=n; i ++)

                             v+= d [i-1];

               for (A; B; C) S

               { A; while(B) {

                             S

                             C;

                  }

               }