TIES448 Luento 5

Mielipiteitä kurssikirjasta

• Onko hyödyllinen?
• Jatkammeko sillä?

LR(k)-jäsennys

• left-to-right parse, rightmost derivation, k-token lookahead
• ks myös AuKi-lisämateriaali
• luentoesimerkki CUPilla ja JFlexillä

LR-jäsennysalgoritmi: tietorakenteet

• Syöte on päätesymbolijono, jota käsitellään vain kahdella operaatiolla:
  • tarkista, mikä symboli on syötteen alussa
  • poista syötteen alusta yksi päätesymboli.
• Pino sisältää tiloja (jotka yleensä on numeroitu, jolloin pinossa on vain numeroita)

LR-jäsennysalgoritmi: ohjaustaulukot

• Siirtymätaulukko (goto table) on kaksiulotteinen taulukko, jossa rivejä indeksoidaan tiloilla ja sarakkeita välikesymboleilla. Kussakin solussa on tila.
• Toimintotaulukko (action table) on kaksiulotteinen taulukko, jossa rivejä indeksoidaan tiloilla ja sarakkeita päätesymboleilla (ynnä syötteen loppumisella). Kussakin solussa on jokin seuraavista toiminnoista:
  • SHIFT n – poista syötteen ensimmäinen merkki ja lisää pinoon n;
  • REDUCE S → γ –
    1. poista pinon päältä γ:n pituuden verran tiloja
    2. hae siirtymätaulukon nykyisen tilan riviltä sekä välikesymbolin S sarakkeelta uusi tila, ja pistä tuo tila pinoon
  • ACCEPT – lopeta jäsentäminen tähän
  • REJECT – keskeytä jäsennys kielioppivirheen takia

LR-jäsennysalgoritmi

1. Laita pinoon LR-automaatin aloitustila.
2. Valitse toimintotaulukosta toiminto pinon päällimmäisen tilan ja syötteen ensimmäisen jäljellä olevan merkin mukaan ja suorita se. Toista kunnes toiminto on ACCEPT tai REJECT.

LR-asetelmat

• LR(0)-asetelma (engl. item) koostuu produktiosta ja indeksistä sen oikeaan puoleen.
• Merkitään usein niin, että indeksin paikka kirjoitetaan produktion sisään pisteenä: E → F + . E
• LR(1)- ja LALR(1)-asetelma sisältää lisäksi päätemerkin (kurkistusmerkki, engl. lookahead symbol)
• LR(k)/LALR(k):ssa kurkistusmerkin tilalla on k:n päätemerkin mittainen kurkistusjono
  • ei käytännössä esiinny, koska ei tuo lisää ilmaisuvoimaa
• LR-tilat muodostetaan LR-asetelmien joukoista eri algoritmeilla

Konfliktit

• Jos LR-automaatissa on samassa solussa useampi toimintaohje, on kyseessä konflikti.
• Shift/reduce-konflikti on tilanne, jossa samassa tilassa on sekä shift- että reduce-toimintaohje.
  • Tyypillinen esimerkki on aiemmin esitelty if-else-moniselitteisyys.
  • Yleensä korjattavissa kielioppia muokkaamalla.
  • Usein shift-toiminnon valitseminen tuottaa halutun tuloksen.
• Reduce/reduce-konflikti on tilanne, jossa samassa tilassa on kaksi eri reduce-toimintaohjetta.
  • Tällöin joko kieliopissa on bugi tai jäsennettävä kieli ei sovellut LR-jäsennykseen.
• Shift/shift-konfliktia ei esiinny

LR:n eri lajit

Ilmaisuvoimajärjestyksessä:

• LR(0) – ei kurkistusmerkkejä
• SLR – kurkistusmerkit FIRST- ja FOLLOW-joukkojen avulla
• LALR(1) eli lookahead-LR – LR(1)-jäsentimestä tilatehokkaampi ja hieman heikompi versio
• LR(1) – kurkistusmerkit LR-algoritmilla, automaatti on yleensä iso
  • LR(k), missä k > 1, ja LR(1) ovat yhtä ilmaisuvoimaiset, joten k > 1 ei ole käytössä

Ohjelmoijan toiminnot

• Sekä LL- että LR-jäsennyksessä ohjelmoija voi yleensä liittää produktioon ohjelmakoodia.
• Ohjelmakoodissa on käytettävissä produktion oikean puolen symbolien semanttiset arvot.
• Ohjelmakoodin odotetaan laskevan produktion vasemman puolen välikesymbolille semanttisen arvon.
• LL-jäsentimessä ohjelmakoodi suoritetaan produktion toteuttavan koodin lopuksi, ja laskettu semanttinen arvo palautetaan aliohjelman paluuarvona.
• LR-jäsentimessä ohjelmakoodi suoritetaan produktion REDUCEn yhteydessä, ja semanttinen arvo liitetään pinossa olevan tilaan lisätiedoksi.
  • Päätesymbolin semanttinen arvo liitetään pinon tilaan SHIFTin yhteydessä.