Chart parser - Chart parser
Inden for datalogi er en diagramparser en type parser, der er velegnet til tvetydige grammatikker (inklusive grammatik af naturlige sprog ). Det bruger den dynamiske programmeringsmetode - delvise hypotese-resultater gemmes i en struktur kaldet et diagram og kan genbruges. Dette eliminerer backtracking og forhindrer en kombinatorisk eksplosion .
Parsing af diagrammer krediteres generelt til Martin Kay .
Typer af diagramparsere
En almindelig tilgang er at bruge en variant af Viterbi-algoritmen . Den Earley parser er en type diagram parser hovedsageligt bruges til parsing i datalingvistik , opkaldt efter sin opfinder. En anden diagramparseringsalgoritme er Cocke-Younger-Kasami (CYK) algoritmen.
Diagramparsere kan også bruges til at analysere computersprog. Især Earley-parsere er blevet brugt i compiler-compilers, hvor deres evne til at parsere ved hjælp af vilkårlige kontekstfrie grammatikker letter opgaven med at skrive grammatikken til et bestemt sprog. Imidlertid har deres lavere effektivitet ført til, at folk har undgået dem ved mest kompilatorarbejde.
Ved tovejskortparsering markeres kanterne på diagrammet med en retning, enten fremad eller bagud, og regler håndhæves i den retning, som kanterne skal pege for at blive kombineret til yderligere kanter.
I trinvis parsing af diagram konstrueres diagrammet trinvist, når teksten redigeres af brugeren, hvor hver ændring af teksten resulterer i den mindst mulige tilsvarende ændring af diagrammet.
Diagramparsere skelnes mellem top-down og bottom-up samt aktive og passive.
