Top-Down Translation

Prosedur eliminasi left recursion

Untuk rekursi kiri yang tidak langsung (non-immediate), copy bagian kanan dari non-terminal beserta dengan semantic action-nya.

Untuk rekursif langsung, misalnya bagian produksi yang rekursif kiri adalah:

A1→ A2 α  {A1.s:=A2.s, α }

Dan bagian yang non rekursif adalah

A→β {A.s:=g(β)}

Buat non-terminal baru Q. Produksi yang baru menjadi

A→βQ
Q1→αQ2
Q→ε

Bersama dengan semantic action-nya menjadi:

A→β    {Q.i:=g(β)} Q {A.s:=Q.s}
Q1→α    {Q2.i:=f(Q1.i,α )} Q2 {Q1.s:=Q2.s}
Q2→ε    {Q.s:=Q.i}

Contoh:

Diketahui produksi berikut ini:

E1→E2 +T      {E1.s:=E2.s+T.s}
E→T                {E.s:=T.s}

Hilangkan rekursif kirinya.

Dalam hal ini A.s adalah E2.s dan α adalah +T.s:(A.s, α) adalah E2.s+T.s. Pada produksi kedua, bagian yang non-rekursif β adalah T.s dan g(β) adalah juga T.s, sehingga bila dihilangkan rekursif kirinya adakan menjadi:

E→T    {Q.i:=T.s)} Q {E.s:=Q.s}

Q1→T    {Q2.i:=Q1.i+T.s )} Q2 {Q1.s:=Q2.s}
Q2→ε    {Q.s:=Q.i}

Review: A A B

diubah menjadi

A R

R R

Rumus tersebut digunakan untuk mengubah translation schemes berikut:
(Perhatikan bahwa simbol yang digunakan berbeda)

E→E1 +T    {E.val:=E1.val + T.val}
E→E1-T      {E.val:=E1.val - T.val}

E→T            {E.val:=T.val}

T→(E)          {T.val:=E.val}

T→num        {T.val:=num.val}

Menjadi:

E→T            {R.i:=T.val}

R                  {E.val:=R.s}

R→ +
T      {R1.i:=R.i + T.val}

R1    {R.s:=R1.s}

R→ -
T       {R1.i:=R.i - T.val}

R1     {R.s:=R1.s}

R→ ε  {R.s:=R1}

T→    (

          E

           )          {T.val:=E.val}

T→ num        {T.val:=num.val}

Urutan evaluasi untuk input 9-5+2

Mengubah syntax directed definition menjadi translation scheme:

Production    Semantic Rules

E→E1 +T    E.nptr:= mknode ('+',E1.ntpr) E.nptr := mknode('-',E1.ntpr, T.ntpr)E.nptr:=T.nptr
E→E1-T      T.nplr:=E.nptr

E→T            T.nptr:=mkleaf(id, id.entry)

T→(E)         T.nptr:=mkleaf(num, num.val)

T→num        

Translation scheme untuk simbol E:

E→E1 +T    {E.nptr:= mknode ('+',E1.ntpr, T.ntpr)}
E→E1-T      {E.nptr:= mknode ('-',E1.ntpr, T.ntpr)}

E→T            {E.nptr:=T.nptr}

Sesudah eliminasi left recursion, menjadi:

E→  T            { R.i:=T.nptr}

        R            { E.nptr:=R.s}

R→ +            

T                    {R1.i:=mknode('+',R.i, T.nptr)}

R1                  {R.s:=R1.s}

R→ -            

T                    {R1.i:=mknode('-',R.i, T.nptr)}

R1                  {R.s:=R1.s}

R→ε               {R.s:=R.i}

T→(

E

)                        {T.nptr:=E.nptr}

T→id        {T.nptr:=mkleaf(id, id.entry)}

T→num        {T.nptr:=mkleaf(num, num.val)}

Proses pembentukan syntax tree dari translation scheme tersebut untuk input a - 4 + c: