Medlem : Logon |Registrering |Upload viden
Søg
Kontekstfri grammatik [Ændring ]
I formel sprogteori er en kontekstfri grammatik (CFG) en bestemt form for formel grammatik: Et sæt produktionsregler, der beskriver alle mulige strenge i et givet formelt sprog. Produktionsregler er enkle udskiftninger. For eksempel, reglen                    A \ \ til \ alpha}  erstatter                    A}   med                    \ alpha}  . Der kan være flere erstatningsregler for en given værdi. For eksempel,                    A \ \ til \ alpha}                      A \ \ til \ \ beta}  betyder at                    A}   kan erstattes med enten                    \ alpha}   eller                    \ beta}  .I kontekstfrie grammars er alle regler en-til-en, en-til-mange eller en-til-ingen. Disse regler kan anvendes uanset kontekst. Den venstre side af produktionsreglen er altid et ikke-terminalt symbol. Dette betyder, at symbolet ikke vises i det resulterende formelle sprog. Så i vores tilfælde indeholder vores sprog bogstaverne                    \ alpha}   og                    \ beta}   men ikke                    A}  .Regler kan også anvendes i omvendt for at kontrollere om en streng er grammatisk korrekt i henhold til grammatikken.Her er et eksempel kontekstfrit grammatik, der beskriver alle to bogstaver, der indeholder bogstaverne                    \ alpha}   og                    \ beta}.S \ \ til \ AA}                      A \ \ til \ alpha}                      A \ \ til \ \ beta}  Hvis vi starter med det ikke-terminale symbol                    S}   så kan vi bruge reglen                    S \ \ til \ AA}   At dreje                    S}   ind i                    AA}  . Vi kan så anvende en af ​​de to senere regler. For eksempel, hvis vi anvender                    A \ \ til \ \ beta}   til den første                    A}   vi får                    \ beta A}  . Hvis vi så anvender                    A \ \ til \ alpha}   til den anden                    A}   vi får                    \ beta \ alpha}  . Siden begge                    \ alpha}   og                    \ beta}   er terminalsymboler, og i kontekstfrie grammars terminalsymboler vises aldrig på venstre side af en produktionsregel, der findes ikke flere regler, der kan anvendes. Denne samme proces kan bruges, og anvende de to andre regler i forskellige ordrer for at få alle mulige strenge i vores enkle kontekstfrie grammatik.Sprog, der genereres af kontekstfrie grammars, kaldes kontekstfrie sprog (CFL). Forskellige kontekstfrie grammars kan generere det samme kontekstfrie sprog.Det er vigtigt at skelne sprogets egenskaber (egenskaber) fra egenskaberne af en bestemt grammatik (ekstrinsiske egenskaber). Spørgsmålet om sproglige ligestilling (gør to givne kontekstfrie grammars generere det samme sprog?) Er ubestrideligt.Kontekstfrie grammer opstår i lingvistikken, hvor de er vant til at beskrive sætning og sætning på et naturligt sprog, og de blev faktisk opfundet af sprogforskeren Noam Chomsky til dette formål, men har ikke rigtig levet op til deres oprindelige forventning. I modsætning til i datalogi, da brugen af ​​rekursivt definerede begreber steg, blev de brugt mere og mere. I en tidlig ansøgning bruges grammars til at beskrive strukturen i programmeringssprog. I en nyere applikation bruges de i en væsentlig del af Extensible Markup Language (XML) kaldet dokumenttype definitionen.I lingvistik bruger nogle forfattere udtrykket sætningsstruktur grammatik til at henvise til kontekstfrie grammer, hvorfra sætningsstruktur grammer er forskellige fra afhængighedsgrammer. I datalogi er en populær notation for kontekstfrie grammars en Backus-Naur form eller BNF..
[Lingvistik]
1.Baggrund
2.Formelle definitioner
2.1.Produktionsregel notation
2.2.Regel ansøgning
2.3.Gentagelsesregel ansøgning
2.4.Kontekstfrit sprog
2.5.Korrekt CFG'er
2.6.Eksempel
3.eksempler
3.1.Velformede parenteser
3.2.Velformede indlejrede parenteser og firkantede parenteser
3.3.En almindelig grammatik
3.4.Matchende par
3.5.Algebraiske udtryk
3.6.Yderligere eksempler
3.6.1.Eksempel 1
3.6.2.Eksempel 2
3.6.3.Andre eksempler
3.7.Afledninger og syntax træer
4.Normale former
5.Lukkeegenskaber
6.Beslutte problemer
7.Ubestridelige problemer
7.1.universalitet
7.2.Sproglig lighed
7.3.Inddragelse af sprog
7.4.At være i et lavere eller højere niveau af Chomsky-hierarkiet
7.5.Grammatiske tvetydighed
7.6.Sprog uoverensstemmelse
8.Udvidelser
9.underklasser
10.Sproglige applikationer
[Upload Mere Indhold ]


Copyright @2018 Lxjkh