A Closer Look At Syntax Diagrams.

Introduction

In this lesson, we take a closer look at syntax diagrams. We discuss features of syntax diagrams, consider some examples, and test your knowledge with a few exercises. The lesson covers the following concept: How to specify a language using syntax diagrams.

Choices in syntax diagrams
Sequences of items in syntax diagrams
Exercise

Generating multiple sentences

The syntax diagram in lesson 1 specifies a language consisting of only a single sentence. This is not of much use. Most languages contain an infinite number of sentences.

Before considering the infinite, we discuss how to generate two sentences by encoding a list of options, or choices, in a syntax diagram. In simple terms, the choice notation (branching arrows) allows us to follow different paths to generate different sentences. This makes the language richer, e.g., composed of more sentences.

Let us consider an example to understand the choice notation better.

Example 1:

This syntax diagram generates sentences of 3 types

1. addition (+) of 2 digits
2. subtraction (-)of 2 digits
3. multiplication (*) of 2 digits; the * is commonly used in computers in place of the traditional x for multiplication because x is a letter.

Parsing, or recognizing, a sentence:
(In other words, we determine which rules were used to generate a sentence.)

Addition of 2 digits

7 + 8

Subtraction of 2 digits

8 - 5

Invalid Sentence:

Now let us consider an example of a sentence that cannot be recognized using this grammar, ie, a sentence that cannot be parsed.

Example 2:

Let us see if we can parse the sentence 2+-3 with the above grammar.

Parsing Of Sentence:

2 + -3

There are no further options to parse the remaining portion of the sentence "-3". Thus the given sentence 2+-3 is not a sentence in the language specified by the grammar.

Generating Multiple Items In Sentences

Let us discuss another feature, namely, Sequences of Symbols. The problem we encountered in Example 2, ie, parsing more than 2 variables can be solved using this feature. The backwards-pointing arrow, or loop, indicates that the portion of the grammar so enclosed can be repeated an arbitrary number of times. Thus, sequences of symbols can be used to generate sentences of any length. In the example, the "+ Letter" sequence can be repeated by following the loop.

Example 3:

This syntax diagram produces sentences that contain multiple addition operations.

Parsing a sentence:

A + B + C

Thus this grammar can accept sentences of the form

1. A + B
2. A + B + C
3. A + B + C + D

Exercise

Ex 1:

Write Sentences ( and their derivations ) for this grammar. 

Solution

The sentences accepted by this grammar are X, AB9D, A23452, ABGFEDC, etc.; that is, any letter optionally followed by any number of letters or digits. Let us parse one of these sentences to understand the grammar better.

Parsing a sentence:

AB9D

Ex 2:

Write sentences ( and their derivations ) for this grammar.

Solution

There are 2 types of sentences for this grammar.

1. a sequence of multiplications or
2. the division of 2 numbers

Parsing a sentence:

Multiplication of numbers

47.85 * 5 * 6.7

Division of a number ( many digits ) by a number

980 / 5

From this exercise we also learn how to construct a number containing many digits.

Back -------- Next