Earley lentelinė sintaksinė analizė
Baigtinės bekontekstės gramatikos atveju lentelėje Iⱼ saugomos taisyklės su tašku [A→β·γ,k], kur k yra pradžios pozicija.
Esminės žinios
Baigtinės bekontekstės gramatikos atveju lentelėje Iⱼ saugomos taisyklės su tašku [A→β·γ,k], kur k yra pradžios pozicija. Prognozuokite visas kito neterminalo taisykles, nuskaitykite atitinkančius terminalus ir užbaigtus neterminalus įtraukite į jų pradžios pozicijose laukiančius elementus. Kartokite prognozavimo ir užbaigimo operacijas, kol nebeatsiras naujų elementų. Priimkite n ilgio įvestį tada ir tik tada, kai [S′→S·,0]∈Iₙ.
Sąlygos ir taikymo ribos
- Naudokite naują pradžios simbolį S′, pašalinkite pasikartojančius elementus ir kiekvieną lentelę papildykite iki soties, įskaitant užbaigimus su epsilon.
- Fiksuotos gramatikos atveju kruopščiai įgyvendintos lentelinės analizės vykdymo trukmė yra O(n³); naiviai išsamiai sintaksinės analizės medžių paieškai ši riba netaikoma.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Kornelio universiteto CS4120 skyrius apie Earley algoritmą: elemento apibrėžtis, inicializavimas, nuskaitymo, prognozavimo ir užbaigimo taisyklės, epsilon apdorojimas ir kubinė riba.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi 241 glaustai suformuluotas teiginys, prielaidos, atskirai pateiktos lygtys bei sutartiniai žymėjimai ir visos 596 iš šių įrašų išeinančios semantinės sąsajos; peržiūrėta visa autoriaus tikslių šaltinių patikros matrica, apimanti 241 įrašą, ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tiksliniai nepriklausomai peržiūrėti pirminių šaltinių skyriai; tai NEREIŠKIA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus specialisto patvirtinimas, išsamus vadovėlio atkūrimas ar eksperimentinis atkartojimas. Patvirtinimo įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-earley-context-free-parsing
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra