En parser , eller ganske enkelt parser , er et dataprogram som analyserer en streng med symboler i henhold til reglene for en formell grammatikk. Begrepet kommer fra det latinske pars , som betyr del (av tale). Den bruker vanligvis en kompilator , i så fall transformerer den en inngang til et avledningssyntakstre. [ 1 ] [ 2 ]
Parsing konverterer inndatateksten til andre strukturer (vanligvis trær), som er mer nyttige for videre parsing og fange opp det implisitte hierarkiet til input. En leksikalsk analysator lager tokens fra en sekvens av inndatategn, og det er disse tokenene som behandles av parseren for å bygge datastrukturen, for eksempel et parse-tre eller abstrakte syntakstrær .
Naturlig språk. Den brukes til å generere diagrammer for språk som bruker grammatisk bøyning, for eksempel de romanske språkene eller latin. Språkene som vanligvis gjenkjennes av parsere er kontekstfrie språk . Merk at det er en formell begrunnelse for at kontekstfrie språk er de som kan gjenkjennes av en stabelautomat , slik at enhver parser som gjenkjenner et kontekstfritt språk er beregningsmessig ekvivalent med en stabelautomat.
Syntaktiske analysatorer ble grundig studert i løpet av 1970-tallet, og oppdaget en rekke driftsmønstre i dem, noe som gjorde det mulig å lage programmer som genererer syntaktiske analysatorer fra en spesifikasjon av språksyntaksen i Backus-Naur-form , for eksempel, slik som yacc , GNU bison og javaCC .
Noen oversettelses- eller naturlig språkbehandlingssystemer blir leksikalsk analysert av dataprogrammer . Setninger er ikke lett parsable på grunn av tvetydighetsbelastningen som eksisterer i strukturen til menneskelig språk. For å behandle menneskelig språk må forskere først bli enige om grammatikken som skal brukes, og denne beslutningen er påvirket av språklige og beregningsmessige kriterier, for eksempel bruker noen analysesystemer leksikalsk-funksjonelle grammatikker. Men generelt er det å analysere grammatikk av denne typen NP-fullstendig .
Den "hodedrevne frasestrukturgrammatikken" er en annen formalisme som har vært populær i samfunnet, men forskningsinnsatsen har fokusert på mindre komplekse algoritmer som Penn Treebanks . Lysanalysen "Shallow parsing" er bare ansvarlig for å finne hovedkomponentene i setningen som substantiv eller verb. En annen populær strategi for å unngå språklig kontrovers er avhengighetsgrammatikken.
De fleste moderne analysatorer er i det minste delvis statistiske , noe som betyr at de er basert på treningsdata som har blitt analysert for hånd. Denne tilnærmingen lar systemet samle informasjon om hvor ofte visse konstruksjoner forekommer i en spesifikk kontekst. Noen av disse tilnærmingene har inkludert probabilistiske kontekstfrie grammatikker , maksimale entropisystemer og nevrale nettverk .
De mest vellykkede systemene bruker leksikalsk statistikk, det vil si at de får den grammatiske kategorien til ordene, disse systemene er sårbare fordi de ender opp med å ha et for stort antall parametere og til slutt krever forenklinger.
Parsingalgoritmer for naturlig språk kan ikke baseres på grammatikk som har gode funksjoner slik det gjøres med designet grammatikk, for eksempel for programmeringsspråk . Noen grammatiske formalismer er svært vanskelige å analysere beregningsmessig , så generelt brukes en kontekstfri tilnærming selv om strukturen i seg selv ikke er kontekstfri for å oppnå en første forenkling.
Algoritmer som bruker kontekstfrie grammatikker er ofte basert på en eller annen variant av Cocke-Younger-Kasami (CYK) algoritmen og heuristikker for beskjæring av mislykkede analyser. I alle fall, noen tilnærminger ofrer hastighet for nøyaktighet ved å bruke for eksempel lineære versjoner av skiftreduseringsalgoritmen . Nylig utviklede tilnærminger bruker én algoritme som genererer fra flere analyser og en annen som velger det beste alternativet.
Den vanligste bruken av parsere er som en del av parsingsfasen til kompilatorer . Så de må analysere kildekoden til språket. Programmeringsspråk har en tendens til å være basert på kontekstfrie grammatikker , fordi raske og effektive parsere kan skrives for dem.
Kontekstfrie grammatikker har begrenset uttrykksevne og kan bare uttrykke et begrenset sett med språk. Uformelt er årsaken til dette at minnet til et slikt språk er begrenset, grammatikken kan ikke huske tilstedeværelsen av en konstruksjon i en vilkårlig lang inndata, og dette er nødvendig i et språk hvor for eksempel en variabel må deklareres før den kan refereres . Mer komplekse grammatikk kan ikke analyseres effektivt. Av disse grunnene er det vanlig å lage en permissiv parser for en kontekstfri grammatikk som aksepterer et supersett av språket (godtar noen ugyldige konstruksjoner), etter den første parsingen kan de ukorrekte konstruksjonene filtreres ut.
Normalt er det lett å definere en kontekstfri grammatikk som aksepterer alle konstruksjonene til et språk, men omvendt er det praktisk talt umulig å bygge en kontekstfri grammatikk som bare aksepterer de ønskede konstruksjonene. I alle fall bygges de fleste analysatorer ikke for hånd, men bruker automatiske generatorer.
Følgende tilfelle viser et vanlig tilfelle av å analysere et programmeringsspråk med to nivåer av grammatikk, leksikalsk og syntaktisk.
Den første tilstanden er generering av tokens eller leksikalsk analyse, i denne prosessen brytes inndatastrengen inn i meningsfulle symboler definert av en regulær uttrykksgrammatikk, for eksempel et kalkulatorprogram med følgende input: "12*(3+4 )^2 ", jeg vil dele det inn i følgende tokens 12, *, (, 3, +, 4, ), ^ og 2, hver av disse tokenene har en betydning i sammenheng med det aritmetiske uttrykket . Parseren vil inneholde regler som indikerer at symbolene *, +, ^, ( og ) indikerer begynnelsen av et nytt token, slik at andre tokens som ikke gir mening som 12 eller 13 ikke vil bli generert.
Den neste tilstanden er parsing, som betyr å sjekke at tokens danner et gyldig uttrykk.Dette gjøres vanligvis ved hjelp av en kontekstfri grammatikk som rekursivt definerer komponenter som kan vises i et uttrykk og rekkefølgen de må vises i. Reglene som definerer et programmeringsspråk kan ikke alltid uttrykkes med kun kontekstfri grammatikk, for eksempel typevalidering og korrekt deklarasjon av identifikatorer. Disse reglene kan uttrykkes formelt ved hjelp av attributtgrammatikk.
Den siste fasen er den semantiske analysen , som arbeider med implikasjonene av det allerede validerte uttrykket og utfører de relevante handlingene. Når det gjelder kalkulatoren, er handlingen å evaluere uttrykket. En kompilator på den annen side vil generere kode . Attributtgrammatikk kan også brukes til å definere disse handlingene.
En annen metode for å analysere er å bruke avhengighetsgrammatikker, som har dukket opp som et alternativ til frasestrukturer . [ 3 ] Generelt sett definerer disse grammatikkene et avhengighetsforhold mellom hvert element i en konstruksjon (vanligvis setninger, men kan også bare være fraser) og dets "hode" (eller hode ). [ 4 ] Disse elementene kan være ord, tokens, slagord eller til og med skilletegn. I tillegg kalles et element 0 eller "rot" øverst i hovedbestanddelen, vanligvis hovedverbet i setningen. Det er viktig å ikke forveksle avhengigheter med bestanddeler, siden avhengighetsrelasjoner genererer unike og ordnede par.
Kriteriene for å bestemme hodet H til en avhengig D i en konstruksjon C er følgende: [ 4 ] [ 5 ]
Imidlertid kan disse kriteriene generere motsetninger eller inkonsistens med morfologiske eller semantiske kriterier , og det er ikke alltid klart om de avhengige er valgfrie eller ikke.
Oppgaven til avhengighetsanalysatorer er, gitt en setning, å bestemme hodene og typen avhengighet for hvert av elementene. Fordelen med å bruke denne typen analyse er at visse problemer kan unngås i språk med løs ordrekkefølge. Det er mange forskjellige måter å klassifisere avhengighetstyper på, men CoNLL (Conference on Computational Natural Language Learning) [ 6 ] har laget et format for universell bruk i avhengighetsanalyse: CoNLL-U
Resultatene av de nyeste systemene i forskjellige parsing-tester er kompilert på den delte oppgavesiden , i 2017 var oppgaven å lage en flerspråklig parser, det vil si i stand til å analysere forskjellige språk.
Den essensielle oppgaven til en parser er å bestemme om en gitt inngang kan utledes fra det innledende symbolet, ved å bruke reglene for en formell grammatikk, og hvordan du gjør dette, det er i hovedsak to måter:
Andre typer analysatorer er: