CS 1352 Principles of Compiler Design — Unit - 2 — — Syntax .ppt

Unit-2 : Syntax Analysis * goto operation If I is a set of LR(1) items and X is a grammar symbol (terminal or non-terminal), then goto(I,X) is defined as follows: If A ? ?.X?,a in I then every item in closure({A ? ?X.?,a}) will be in goto(I,X). * Unit-2 : Syntax Analysis * Construction of The Canonical LR(1) Collection Algorithm: C is { closure({S’?.S,$}) } repeat the followings until no more set of LR(1) items can be added to C. for each I in C and each grammar symbol X if goto(I,X) is not empty and not in C add goto(I,X) to C goto function is a DFA on the sets in C. * Unit-2 : Syntax Analysis * A Short Notation for The Sets of LR(1) Items A set of LR(1) items containing the following items A ? ?.?,a1 ... A ? ?.?,an can be written as A ? ?.?,a1/a2/.../an * Unit-2 : Syntax Analysis * Canonical LR(1) Collection -- Example S ? AaAb I0: S’ ? .S ,$ I1: S’ ? S. ,$ S ? BbBa S ? .AaAb ,$ A ? ? S ? .BbBa ,$ I2: S ? A.aAb ,$ B ? ? A ? . ,a B ? . ,b I3: S ? B.bBa ,$ I4: S ? Aa.Ab ,$ I6: S ? AaA.b ,$ I8: S ? AaAb. ,$ A ? . ,b I5: S ? Bb.Ba ,$ I7: S ? BbB.a ,$ I9: S ? BbBa. ,$ B ? . ,a S A B a b A B a b to I4 to I5 * Unit-2 : Syntax Analysis * Canonical LR(1) Collection – Example2 S’ ? S 1) S ? L=R 2) S ? R 3) L? *R 4) L ? id 5) R ? L I0:S’ ? .S,$ S ? .L=R,$ S ? .R,$ L ? .*R,$/= L ? .id,$/= R ? .L,$ I1:S’ ? S.,$ I2:S ? L.=R,$ R ? L.,$ I3:S ? R.,$ I4:L ? *.R,$/= R ? .L,$/= L? .*R,$/= L ? .id,$/= I5:L ? id.,$/= I6:S ? L=.R,$ R ? .L,$ L ? .*R,$ L ? .id,$ I7:L ? *R.,$/= I8: R ? L.,$/= I9:S ? L=R.,$ I10:R ? L.,$ I11:L ? *.R,$ R ? .L,$ L? .*R,$ L ? .id,$ I12:L ? id.,$ I13:L ? *R.,$ to I6 to I7 to I8 to I4 to I5 to I10 to I11 to I12 to I9 to I10 to I11 to I12 to I13 id S L L L R R R id id id R L * * * * I4 and I11 I5 and I12 I7 and I13