Formell grammatik

Formell grammatik eller bara grammatik i teorin om formella språk är ett sätt att beskriva ett formellt språk, det vill säga att välja en viss delmängd från uppsättningen av alla ord i något ändligt alfabet . Det finns generativa och igenkännande (eller analytiska ) grammatiker - den första sätter reglerna med vilka du kan bygga vilket ord som helst i språket, och den andra låter dig avgöra från ett givet ord om det ingår i språket eller inte.

Villkor

Terminalen (terminalsymbol) är ett objekt som är direkt närvarande i orden på det språk som motsvarar grammatiken och har en specifik, oföränderlig betydelse (en generalisering av begreppet "bokstäver"). I formella språk som används på en dator, tas alla eller delar av standard ASCII-tecken - latinska bokstäver, siffror och specialtecken - vanligtvis som terminaler .
Non-terminal (icke-terminal symbol) är ett objekt som betecknar någon språkenhet (till exempel: en formel, ett aritmetiskt uttryck, ett kommando) och har inte ett specifikt symboliskt värde.

Generativa grammatiker

Orden för språket som ges av grammatiken är alla sekvenser av terminaler som matas ut (genereras) från den initiala icke-terminalen enligt reglerna för utdata.

För att ställa in grammatiken måste du ställa in alfabeten för terminaler och icke-terminaler, en uppsättning slutledningsregler, och även välja den första i uppsättningen av icke-terminaler.

Så grammatik definieras av följande egenskaper:

$\Sigma$ — uppsättning ( alfabet ) av terminalsymboler
N är en uppsättning ( alfabet ) av icke-terminala symboler
P är en uppsättning regler av formen: "vänster sida" "höger sida", där: $\höger pil$
- "vänster sida" är en icke-tom sekvens av terminaler och icke-terminaler som innehåller minst en icke-terminal
- "höger sida" - valfri sekvens av terminaler och icke-terminaler
S är startsymbolen (eller initial) för grammatiken från uppsättningen icke-terminaler.

Slutsats

En utgång är en sekvens av linjer som består av terminaler och icke-terminaler, där den första raden är en linje som består av en startande icke-terminal, och varje efterföljande rad erhålls från den föregående genom att ersätta någon delsträng enligt en (valfri) av reglerna. Den sista strängen är en sträng som helt består av terminaler och är därför ett ord i språket.

Förekomsten av en härledning för ett visst ord är ett kriterium för dess tillhörighet till det språk som definieras av den givna grammatiken.

Typer av grammatik

Enligt Chomsky-hierarkin är grammatik indelad i 4 typer, var och en av dem är en mer begränsad delmängd av den föregående (men också lättare att analysera):

typ 0. obegränsad grammatik - alla regler är möjliga
typ 1. kontextkänslig grammatik - den vänstra delen kan innehålla en icke-terminal omgiven av en "kontext" (sekvenser av tecken som finns i samma form i den högra delen); själva icke-terminalen ersätts av en icke-tom sekvens av tecken på höger sida.
typ 2. sammanhangsfria grammatiker — den vänstra delen består av en icke-terminal.
typ 3. vanliga grammatiker är enklare, motsvarande finita automater .

Dessutom finns det:

Icke-förkortande grammatiker . Varje regel i en sådan grammatik har formen där . Längden på den högra sidan av regeln är inte mindre än längden på den vänstra [1] . $\alpha \högerpil \beta$ $|\alpha |\leqslant |\beta |$
Linjär grammatik . Varje regel i en sådan grammatik har formen , eller , det vill säga den högra sidan av regeln kan inte innehålla mer än en förekomst av en icke-terminal [2] . $A\högerpil uBv$ $A\högerpil u$

Applikation

Kontextfria grammatiker används i stor utsträckning för att definiera grammatisk struktur i grammatisk analys .
Reguljära grammatiker (i form av reguljära uttryck ) används i stor utsträckning som mallar för textsökning, nedbrytning och substitution, inklusive i lexikal analys .

Ett exempel är aritmetiska uttryck

Tänk på ett enkelt språk som definierar en begränsad delmängd av aritmetiska formler som består av naturliga tal , parenteser och aritmetiska tecken. Det är värt att notera att här i varje regel på vänster sida av pilen finns det bara en icke-terminal symbol. Sådana grammatiker kallas sammanhangsfria . $\höger pil$

Terminalalfabet:

\Sigma

= {'0','1','2','3','4','5','6','7','8','9','+','-', '*','/','(',')'}

Icke-terminalt alfabet:

{ FORMEL, TECKN, NUMMER, NUMMER }

Regler:

1. FORMEL FORMEL TECKN FORMEL

\till

(en formel har två formler förbundna med ett tecken) 2. FORMELNUMMER (

\till

formeln är ett tal) 3. FORMEL ( FORMEL )

\till

(en formel är en formel inom parentes) 4. TECKNA + | - | * | /

\till

(tecknet är plus eller minus, eller multiplicera eller dividera) 5. NUMMERSIFRA (

\till

ett nummer är ett tal) 6. NUMMER NUMMER SIFFROR

\till

(ett nummer är ett tal och ett tal) 7. NUMMER 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

\till

(siffran är 0 eller 1, eller ... 9)

Initial icke-terminal:

FORMEL

Slutsats :

Låt oss härleda formeln (12+5) med hjälp av de angivna slutledningsreglerna. För tydlighetens skull visas sidorna av varje utbyte parvis, i varje par är den ersatta delen understruken.

FORMEL (FORMEL)

{\stackrel {3}{\to ))

( FORMEL ) ( FORMELTECKNFORMEL )

{\stackrel {1}{\to ))

(FORMELTECKNFORMEL ) ( FORMEL + FORMEL)

{\stackrel {4}{\to ))

( FORMEL + FORMEL ) ( FORMEL + TAL )

{\stackrel {2}{\to ))

( FORMEL + TAL ) ( FORMEL + TAL )

{\stackrel {5}{\to ))

( FORMEL + TAL ) ( FORMEL + 5 )

{\stackrel {7}{\to ))

( FORMEL + 5) ( NUMMER + 5)

{\stackrel {2}{\to ))

( NUMMER + 5) ( NUMMER + 5)

{\stackrel {6}{\to ))

( NUMMER SIFFROR + 5) ( SIFFROR + 5)

{\stackrel {5}{\to ))

( DIGIT DIGIT + 5) ( 1 DIGIT + 5)

{\stackrel {7}{\to ))

(1 SIFFRA + 5) (1 2 + 5)

{\stackrel {7}{\to ))

Analytiska grammatiker

Generativ grammatik är inte den enda typen av grammatik, men de är vanligast i programmeringsapplikationer. Till skillnad från generativ grammatik definierar analytisk (igenkännande) grammatik en algoritm som låter dig avgöra om ett givet ord tillhör språket. Till exempel kan vilket vanligt språk som helst kännas igen med hjälp av en grammatik som definieras av en tillståndsmaskin , och vilken kontextfri grammatik som helst kan kännas igen med en stackbaserad automat . Om ett ord tillhör ett språk, konstruerar en sådan automat dess utdata i en explicit form, vilket gör det möjligt att analysera semantiken i detta ord.

Se även

JFLAP - simulator av automater, Turing-maskiner, grammatik
analysera
Tvetydig grammatik
Det minsta grammatikproblemet
Grammatik med frasstruktur

Anteckningar

↑ Diskret matematik, 2006 , sid. 486.
↑ Diskret matematik, 2006 , sid. 487.

Litteratur

Belousov A. I., Tkachev S. B. Diskret matematik. — M .: MGTU , 2006. — 743 sid. — ISBN 5-7038-2886-4 .
Gladkiy A. V. Formella grammatiker och språk. — M .: Nauka, 1973.
Kasyanov VN Föreläsningar om teorin om formella språk, automater och beräkningskomplexitet. - Novosibirsk: NGU, 1995. - 112 sid.
Chomsky N., Miller J. Introduktion till den formella analysen av naturliga språk // Cybernetisk samling / Ed. A.A. Lyapunova och O.B. Lupanova. — M .: Mir, 1965.
Gross M., Lanten A. Formell grammatiks teori. — M .: Mir, 1971. — 296 sid.

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