Context- Free Grammar
A Context- Free Grammar (CFG) G is a 4-tuple (N,?,R,S), where
1- N is a finite set of nonterminals or variables.
2- ? is a finite set of terminals.
3- R is a finite set of rules, each consisting of a variables ( the left- hand side) and a sentential form (the right- hand side).
4- S is the start symbol.
The binary relation ® on sentential forms is defined as follows:
Let u, v, and w be sentential forms then uAw® uvw iff A®v is a rule in R
® captures a single derivation step.
®* is the reflexive transitive closure of ®,
and L(G)={sI?* / S®* s}
Derivations
A sequence of rewritings that transforms the start variable S of a grammar G to a sentence s is called a derivation of s from G.
a derivation in which every derivation step uses the left most variable in the sentential form is called a left most derivation.
A grammar G is called ambiguous if there exist a string s with tow different left most derivations from G.
For example, the arithmetic expression grammar
E®0\1…..\9\(E)\E*E\E+E
Is ambiguous because the sentence
2+3*4
Has tow different left most derivations
E®E*E®E+E*E®2+E*E®2+3*E®2+3*4
E®E+E®2+E®2+E*E®2+3*E®2+3*4
Pars trees
Here is another grammar for arithmetic expressions:
E®T|T+E
T®F|F*T
F®0|1|…|9|(E)
When the start variable is unspecified, it is assumed to be the variable of the first rule in this case E.
This grammar is unambiguous (convince yourself of this fact)
Here is the parse tree for (3+7)*2
This is only parse tree for this sentence (using this grammar).
In contrast, consider the previous grammar
E®0|1|…|9|(E)|E*E|E+E
This grammar has two different parse trees for the sentence 3+7*2.
Previously, we said a grammar was ambiguous if there exists some sentence with two different leftmost derivations.
Equivalently, a grammar is ambiguous if there exists some sentence with two different parse tree.
Examples
L(G)={0n1n, n>=0}
S®0S1\l
the derivation of (0011) is
S®0S1®00S11®0011
L(G)={ 0n1n, n>=1} H.W
L(G)={wIS*, w=wR} where S=(a,b)
S®aSa\bSb\a\b\l
The derivation of (abaaba) is
S®aSa®abSba®abaSaba®abaaba
L(G)={aibj , i>=j} H.W
DONE
Instructor: Mohamed U. Mahdi
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .