Page 198 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes Nonterminal: A grammar symbol that can be substituted/expanded to a sequence of symbols.
Terminal: An actual word in a language; these are the symbols in a grammar that cannot be
substituted by anything else. "Terminal" is supposed to summon up the idea that it is a dead-
end-no further expansion is possible.
Production: A grammar rule that describes how to replace/exchange symbols. The general
form of a production for a nonterminal is: X  Y1Y2Y3...Y. The nonterminal X is declared
equivalent to the concatenation of the symbols Y1Y2Y3...Yn. The production means that anywhere
where we encounter X, we may replace it by the string Y1Y2Y3...Yn. Eventually we will have a
string containing nothing that can be expanded further, i.e., it will include only terminals. Such
a string is called a sentence.

Did u know? In the context of programming languages, a sentence is a syntactically accurate
and complete program.
Derivation: A sequence of applications of the rules of a grammar that generates a finished string
of terminals. A leftmost derivation is where we always alternate for the leftmost nonterminal
as we apply the rules (we can similarly define a rightmost derivation). A derivation is also
known as a parse.
Start symbol: A grammar has a single nonterminal (the start symbol) from which all sentences
derive: S  X1X2X3...Xn
All sentences are obtained from S by successive replacement by means of the productions of the
grammar.

Null Symbol:  it is sometimes functional to specify that a symbol can be replaced by nothing at
all. To specify this, we use the null symbol , e.g., A  B | .
BNF: A method of specifying programming languages by means of formal grammars and
production rules with a particular form of notation (Backus-Naur form).

Task Compare start symbol and null symbol.
12.3.2 Parse Representation

In functioning with grammars, we can signify the application of the rules to derive a sentence in
two manners. The first is a derivation as exposed previously for "This is a university" where the
rules are applied gradually and we substitute for one nonterminal at a time.
Consider a derivation as a history of how the sentence was parsed since it not only includes
which productions were applied, but also the order they were applied (i.e., which nonterminal
was chosen for expansion at each step). There can many different derivations for the same
sentence (the leftmost, the rightmost, and so on). A parse tree is the second method for
representation. It diagrams how every symbol derives from other symbols in a hierarchical
manner. Here is a parse tree for "This is a university":

192 LOVELY PROFESSIONAL UNIVERSITY