3b. LMD & RMD.pdf

LMD & RMD

1. Derivation and Ambiguity
1
Course Name: Compiler Design
Course Code: CSE331
Level:3, Term:3
Department of Computer Science and Engineering
Daffodil International University

2. Derivation
Aderivationisbasicallyasequenceofproductionrules,inordertogetthe
inputstring.Duringparsing,wetaketwodecisionsforsomesententialform
ofinput:
•Decidingthenon-terminalwhichistobereplaced.
•Decidingtheproductionrule,bywhich,thenon-terminalwillbereplaced.
•Todecidewhichnon-terminaltobereplacedwithproductionrule,wecan
havetwooptions.
2

3. Derivation Types
•Left-mostDerivation
Ifthesententialformofaninputisscannedandreplacedfromleftto
right,itiscalledleft-mostderivation.Thesententialformderivedbytheleft-
mostderivationiscalledtheleft-sententialform.
•Right-mostDerivation
Ifwescanandreplacetheinputwithproductionrules,fromrightto
left,itisknownasright-mostderivation.Thesententialformderivedfromthe
right-mostderivationiscalledtheright-sententialform.
3

4. 4
•Production rules:
E → E + E
E → E * E
E → id
The left-most derivation is:
E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id
The right-most derivation is:
E → E + E
E → E + E * E
E → E + E * id
E → E + id * id
E → id + id * id
Input string: id + id * id
Example

5. Parse Tree
•A parse tree is a graphical depiction of a derivation.
•It is convenient to see how strings are derived from the start symbol.
•The start symbol of the derivation becomes the root of the parse tree.
5

6. Constructing the Parse Tree
6
•Step 1:
E → E * E
Step 2:
E → E + E * E

7. •Step 3:
E → id + E * E
Constructing the Parse Tree …
Step 4:
E → id + id * E
7

8. •In a parse tree:
-All leaf nodes are terminals.
-All interior nodes are non-terminals.
-In-order traversal gives original input string
Step 5:
E → id + id * id
Constructing the Parse Tree …
8

9. Ambiguity
•AgrammarGissaidtobeambiguousifithasmorethanoneparsetree(leftorright
derivation)foratleastonestring.
Example: E→E+E
E→E–E
E→id
Forthestringid+id–id,theabovegrammargeneratestwoparsetrees:
9

10. •Parsing that we have seen so far.
Top-Down Parsing
10

11. •Parsingistheprocessofdeterminingifastringoftokenscanbegeneratedbya
grammar.
•Foranycontext-freegrammarthereisaparserthattakesatmostΟ(n
3
)timeto
parseastringofntokens.
•Top-downparsersbuildparsetreesfromthetop(root)tothebottom(leaves).
•Twotop-downparsingaretobediscussed:
oRecursiveDescentParsing
oPredictiveParsingAnefficientnon-backtrackingparsingcalledforLL(1)
grammars.
Top-Down Parsing
11

12. Considerthegrammar
S→cAd
A→ab|a
Inputstringw=cad
Toconstructaparsetreeforthisstringusingtop-downapproach,
initiallycreateatreeconsistingofasinglenodelabeledS.
Example of Top-Down Parsing
12

13. Example of Top-Down Parsing
S → cAd
A → ab | a
Input string w = cad
13

14. Procedure of Top-down Parsing
•Aninputpointerpointstoc,thefirstsymbolofw.
•ThenusethefirstproductionforStoexpandthetreeandobtainthetree.
•Theleftmostleaf,labeledc,matchesthefirstsymbolofw.
•Nextinputpointertoa,thesecondsymbolofw.
•Considerthenextleaf,labeledA.
•ExpandAusingthefirstalternativeforAtoobtainthetree.
14

15. •Nowhaveamatchforthesecondinputsymbol.Thenadvancetothenext
inputpointerd,thethirdinputsymbolandcomparedagainstthenextleaf,
labeledb.Sincebdoesnotmatchd,reportfailureandgobacktoAtosee
whetherthereisanotheralternative.(Backtrackingtakesplace).
•IfthereisanotheralternativeforA,substituteandcomparetheinputsymbol
withleaf.
•RepeatthestepforallthealternativesofAtofindamatchusingbacktracking.
Ifmatchfound,thenthestringisacceptedbythegrammar.Elsereportfailure.
•Aleft-recursivegrammarcancausearecursive-descentparser,evenonewith
backtracking,togointoaninfiniteloop.
•Asdiscussedabove,aneasywaytoimplementarecursivedescentparsingwith
backtrackingistocreateaprocedureforeachnon-terminals.
Procedure of Top-down Parsing
15

16. Transition Diagram for Predictive Parsers
16

17. Example: Build the parse tree for the arithmetic expression 4 + 2 * 3 using the expression grammar:
E → E + T | E -T | T
T → T * F | F
F → a | ( E )
where a represents an operand of some type, be it a number or variable. The trees are grouped by height.
17

18. E → E + T | E -T | T
T → T * F | F
F → a | ( E )
18

19. Grammer:
E → E+E | a
E ⇒E+Ě
⇒Ě+E+E
⇒a+Ě+E
⇒a+a+Ě
⇒a+a+a
19
Derivation:

20. Example: Build the parse tree for the arithmetic expression “a+a+a” using the
expression grammar:
E → E+E | a
20

21. Consider again, the grammar specifying only addition in expression:
E → E+E | a
E ⇒Ě+E
⇒Ě+E+E
⇒a+Ě+E
⇒a+a+Ě
⇒a+a+a
E ⇒E+Ě
⇒E+E+Ě
⇒E+Ě+a
⇒Ě+a+a
⇒a+a+a
AMBIGUOUS
21
Left Most Derivation(LMD):
Right Most Derivation(LMD):

22. The grammar is: S ⇾S S| (S) | ε
Consider the string "()()"
S ⇒Š S
⇒( S ̌) S
⇒( ) Š
⇒( ) ( S ̌)
⇒( ) ( )
S ⇒S Š
⇒S ̌( S )
⇒( S ) ( Š )
⇒( Š ) ( )
⇒( ) ( )
NOT AMBIGUOUS
22
UNAMBIGUOUS

23. The grammar is: S ⇾S S| (S) | ε
Consider the string "(())()"
S ⇒ŠS
⇒(Š)S
⇒((Š))S
⇒(())Š
⇒(())(Š)
⇒(())()
S ⇒ŠS
⇒SŠS
⇒S(Š)S
⇒S((Š))S
⇒S(())Š
⇒S(())(Š)
⇒Š(())()
⇒(())()
AMBIGUOUS
23

24. 24
THANK YOU