Page 199 - DCAP507_SYSTEM_SOFTWARE

Unit 12: Formal Systems and Programming Languages

Notes

Notes Even though the parse tree involves all of the productions that were applied, it does
not encode the order they were applied. For an explicit grammar, there is precisely one
parse tree for a particular sentence.

12.3.3 More Definitions

Here are some other definitions we will require, illustrated in reference to this example grammar:
S  AB
A  Ax | y
B  z

The alphabet is {S, A, B, x, y, z}. It is divided into two disjoint sets. The terminal alphabet includes
terminals, which appear in the sentences of the language:
{x, y, z}. The remaining symbols are the nonterminal alphabet; these are the symbols that occur
on the left side of productions and can be substituted throughout the course of a derivation:
{S, A, B}. Formally, we use V for the alphabet, T for the terminal alphabet and N for the
nonterminal alphabet giving us: V = T  N.

Context-free Grammar

To define a language, we require a set of productions, of the common form: u  v. In a context-
free grammar, u is a single nonterminal and v is a random string of terminal and nonterminal
symbols. When parsing, we can substitute u by v where it occurs. We shall refer to this set of
productions symbolically as P.

Formal Grammar

We officially define a grammar as a 4-tuple {S, P, N, T}. S is the start symbol and S  N, P is the
set of productions, and N and T are the nonterminal and terminal alphabets. A sentence is a
string of symbols in T obtained from S by means of one or more applications of productions in
P. A string of symbols derived from S but possibly including non-terminals is known as a
sentential form or a working string.

A production u  v is used to reinstate an occurrence of u by v. Officially, if we apply a
production p  P to a string of symbols w in V to yield a new string of symbols z in V, we say
that z obtained from w using p, written as follows: w  z. We also use: w  z z derives from w
(production unspecified).
w * z z derives from w by means of zero or more productions w +z z derives from w by
means of one or more productions equivalence. The language L(G) defined by grammar G is the
set of sentences derivable by means of G. Two grammars G and G' are said to be equivalent if the
languages they generate, L(G) and L(G'), are the similar.

Self Assessment

Fill in the blanks:
11. ............................. is a set of rules by which applicable sentences in a language are created.
12. ............................. is a grammar rule that describes how to replace/exchange symbols.

LOVELY PROFESSIONAL UNIVERSITY 193