Kontextfri grammatik

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 3 januari 2022; verifiering kräver 1 redigering .

Kontextfri grammatik ( CS-grammatik , kontextfri grammatik ) är ett specialfall av formell grammatik (typ 2 enligt Chomsky-hierarkin ), där de vänstra delarna av alla produktioner är enstaka icke -terminaler (objekt som betecknar någon essens av språket (till exempel: en formel, ett aritmetiskt uttryck, kommando) och som inte har en specifik symbolisk betydelse). Innebörden av termen "kontextfri" är att det är möjligt att tillämpa produktion på en icke-terminal, och dessutom oavsett sammanhanget för denna icke-terminala (i motsats till det allmänna fallet med obegränsad Chomsky-grammatik).

Ett språk som kan specificeras av en CFG kallas ett sammanhangsfritt språk eller CFL.

Faktum är att KS-grammatiken är en annan form av BNF .

Applikation

COP-grammatik har mycket användning inom datavetenskap . De ställer in den grammatiska strukturen för de flesta programmeringsspråk , strukturerad data, etc. (se grammatisk analys )

För att tolka en COP-grammatik räcker det med en nedtryckningsautomat , för att tolka icke-COP-grammatik kan en komplett Turing-maskin behövas .

Typer av CS-grammatik

LL grammatik
LALR grammatik (se: LALR(1) )
LR grammatik
SLR grammatik (se: SLR(1) )

Igenkännare

Det finns två olika klasser av igenkännare (automater för igenkänning) av CF-språk. Deras namn är relaterade till den ordning i vilken utdataträdet är byggt. Som regel läser alla igenkännare den inmatade teckensträngen från vänster till höger, eftersom en sådan notation förväntas för att skriva källkoden för program.

Nedströmslösare

Top-down resolvers som genererar vänster utdatakedjor och bygger utdataträdet uppifrån och ner.

De använder modifieringar av algoritmen vid valet av alternativ. När du skapar dem används en metod som gör att du unikt kan välja ett och endast ett alternativ vid varje steg av MP-automaten (”utkastningssteget” i denna automat utförs alltid unikt).

Stigande igenkännare

Bottom-up resolvers som genererar kedjor av högerhänt utdata och bygger utdataträdet från botten till toppen.

Uppströms-igenkännare använder modifieringar av skift-veck-algoritmen (eller skift-veckning, vilket är samma). När du skapar dem används metoder som gör att du entydigt kan välja mellan att utföra ett "skifte" ("överföring") eller "faltning" vid varje steg i den utökade MP-automaten, och när faltning utförs kan du entydigt välja regeln genom vilken faltningen kommer att utföras. Algoritm "shift-convolution".

Exempel

Exempel på SF-grammatik och deras motsvarande SF-språk:

Vänd ord

Givet av formel $L=\{w\in \Sigma ^{*}|w=w^{R}\}$

Terminaler: bokstäver i alfabetet ; $\Sigma$
Icke-terminal: ; $S$
Produkter: $S\högerpil \alpha S\alpha \,|\,\alpha \,|\,\varepsilon ,\alpha \i \Sigma$
Den initiala icke -terminalen är . $S$

Kapslade parenteser

Terminaler: och ; $($ $)$
icke-terminal: ; $S$
produkter: ; $S\högerpil (S)\mitt \varepsilon$
initial icke -terminal - . $S$

Denna grammatik anger språket för kapslade parenteser . $\{\left(^{n}\right)^{n}\mid n\geq 0\}$

Dicks språk

Aritmetiskt uttryck

Terminaler: '+', '-', '*', '/', '(', ')', 'x'
icke-terminaler: <uttryck>, <term>, <multiplikator>
Produkter:

<uttryck> → <uttryck> + <term>, <uttryck> → <uttryck> - <term>, <uttryck> → <term>, <term> → <term> * <multiplikator>, <term> → <term> / <multiplikator>, <term> → <multiplikator>, <multiplikator> → ( <uttryck> ), <multiplikator> → x,

initial icke-terminal: <uttryck>.

Denna grammatik definierar ett aritmetiskt uttryck som innehåller de enklaste aritmetiska operationerna på variabeln x. Om vi ersätter terminalen 'x' med icke-terminalen <tal> får vi en grammatik som specificerar ett aritmetiskt uttryck som består av addition, subtraktion, multiplikation och division på heltal.

Begränsningar för COP-grammatik

Alla språk kan inte definieras med CF-grammatik. Det enklaste sättet att bevisa detta är som följer: COP-grammatiker bildar en räknebar mängd, medan kardinaliteten i mängden av alla språk är ett kontinuum . Ett konstruktivt bevis för samma faktum kan erhållas till exempel på grundval av att språket { a n b n c n | n ≥1} är inte kontextfri; det verkar dock inte finnas ett kort bevis för det senare påståendet: de publicerade bevisen förlitar sig på tillväxtsatsen för sammanhangsfria språk.

Generaliseringar

Trädadditionsgrammatiken generaliserar den sammanhangsfria grammatiken genom att den elementära enheten i slutledningsreglerna är träd, inte enskilda tecken.

Se även

Litteratur

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion till automatteori, språk och beräkningar. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Belousov A. I., Tkachev S. B. Diskret matematik. — M .: MGTU , 2006. — 743 sid. — ISBN 5-7038-2886-4 .

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm