Kontekstfri grammatik
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 3. januar 2022; verifikation kræver 1 redigering .Kontekstfri grammatik ( CS-grammatik , kontekstfri grammatik ) er et specialtilfælde af formel grammatik (type 2 ifølge Chomsky-hierarkiet ), hvor de venstre dele af alle produktioner er enkelte ikke -terminale (objekter, der angiver enhver essens af sproget (for eksempel: en formel, et aritmetisk udtryk, kommando) og ikke har en bestemt symbolsk betydning). Betydningen af udtrykket "kontekstfri" er, at det er muligt at anvende produktion på en ikke-terminal, og desuden uanset konteksten af denne ikke-terminal (i modsætning til det generelle tilfælde af ubegrænset Chomsky-grammatik).
Et sprog , der kan specificeres af en CFG, kaldes et kontekstfrit sprog eller CFL.
Faktisk er KS-grammatikken en anden form for BNF .
Ansøgning
COP-grammatikker har meget brug i datalogi . De sætter den grammatiske struktur af de fleste programmeringssprog , strukturerede data osv. (se grammatisk analyse )
For at parse en COP-grammatik er en push-down- automatik nok , for at parse ikke-COP-grammatikker kan det være nødvendigt med en komplet Turing-maskine .
Typer af CS-grammatikker
Genkendere
Der er to forskellige klasser af genkendere (automater til genkendelse) af CF-sprog. Deres navne er relateret til den rækkefølge, som outputtræet er bygget i. Som regel læser alle genkendere inputtegnstrengen fra venstre mod højre, da en sådan notation forventes ved skrivning af programmers kildekode.
Nedstrøms resolvere
Top-down-resolvere, der genererer outputkæder til venstre og bygger outputtræet fra top til bund.
De bruger modifikationer af algoritmen med valg af alternativer. Når du opretter dem, bruges en metode, der giver dig mulighed for entydigt at vælge ét og kun ét alternativ ved hvert trin af MP-automaten (“udkastningstrinnet i denne automat udføres altid unikt).
Stigende genkendere
Bottom-up resolvere, der afføder højrehåndede inferenskæder og bygger inferenstræet fra bund til top.
Opstrøms genkendere bruger modifikationer af shift-fold (eller shift-fold, som er den samme) algoritmen. Når du opretter dem, bruges metoder, der giver dig mulighed for entydigt at vælge mellem at udføre et "skift" ("overførsel") eller "foldning" ved hvert trin af den udvidede MP-automat, og når foldning udføres, kan du entydigt vælge reglen hvorved foldningen vil blive udført. Algoritme "shift-convolution".
Eksempler
Eksempler på SF-grammatikker og deres tilsvarende SF-sprog:
Vend ord
Givet ved formel
- Terminaler: bogstaver i alfabetet ;
- Ikke-terminal: ;
- Produkter:
- Den oprindelige ikke -terminal er .
Indlejrede parenteser
- Terminaler: og ;
- ikke-terminal: ;
- produkter: ;
- initial ikke -terminal - .
Denne grammatik specificerer sproget for indlejrede parenteser .
Dicks sprog
Aritmetisk udtryk
- Terminaler: '+', '-', '*', '/', '(', ')', 'x'
- ikke-terminaler: <udtryk>, <term>, <multiplikator>
- Produkter:
- initial ikke-terminal: <udtryk>.
Denne grammatik definerer et aritmetisk udtryk, der indeholder de enkleste aritmetiske operationer på variablen x. Hvis vi erstatter terminalen 'x' med den ikke-terminale <tal>, får vi en grammatik, der specificerer et aritmetisk udtryk bestående af addition, subtraktion, multiplikation og division af heltal.
Begrænsninger af COP-grammatikker
Ikke alle sprog kan defineres ved hjælp af CF-grammatikker. Den nemmeste måde at bevise dette på er som følger: COP-grammatikker danner et tælleligt sæt, mens kardinaliteten af sættet af alle sprog er et kontinuum . Et konstruktivt bevis for samme kendsgerning kan f.eks. opnås på baggrund af, at sproget { a n b n c n | n ≥1} er ikke kontekstfri; der synes dog ikke at være et kort bevis for sidstnævnte påstand: de offentliggjorte beviser er afhængige af vækstsætningen for kontekstfri sprog.
Generaliseringer
Træadditionsgrammatikken generaliserer den kontekstfrie grammatik, idet den elementære enhed i slutningsreglerne er træer, ikke individuelle tegn.
Se også
Litteratur
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
- Belousov A. I., Tkachev S. B. Diskret matematik. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .
| Formelle sprog og formelle grammatikker | |
|---|---|
| Generelle begreber | |
| Type 0 | |
| Type 1 |
|
| Type 2 | |
| Type 3 |
|
| parsing | |