Formel grammatik

Formel grammatik eller bare grammatik i teorien om formelle sprog er en måde at beskrive et formelt sprog på, det vil sige at vælge en bestemt delmængde fra sættet af alle ord i et eller andet endeligt alfabet . Der er generative og genkendende (eller analytiske ) grammatikker - den første sætter reglerne for, at du kan bygge et hvilket som helst ord i sproget, og den anden giver dig mulighed for at bestemme ud fra et givet ord, om det er inkluderet i sproget eller ej.

Vilkår

Terminalen (terminalsymbolet) er et objekt, der er direkte til stede i ordene på det sprog, der svarer til grammatikken, og har en specifik, uforanderlig betydning (en generalisering af begrebet "bogstaver"). I formelle sprog, der bruges på en computer, tages alle eller dele af standard ASCII-tegnene - latinske bogstaver, tal og specialtegn - normalt som terminaler .
Ikke-terminal (ikke-terminal symbol) er et objekt, der angiver en sproglig enhed (for eksempel: en formel, et aritmetisk udtryk, en kommando) og har ikke en specifik symbolsk værdi.

Generative grammatikker

Ordene i sproget givet af grammatikken er alle sekvenser af terminaler, der er output (genereret) fra den oprindelige ikke-terminal i henhold til reglerne for output.

For at indstille grammatikken skal du indstille alfabeterne for terminaler og ikke-terminaler, et sæt slutningsregler og også vælge den indledende i sættet af ikke-terminaler.

Så grammatik er defineret af følgende egenskaber:

$\Sigma$ — sæt ( alfabet ) af terminalsymboler
N er et sæt ( alfabet ) af ikke-terminale symboler
P er et sæt regler af formen: "venstre side" "højre side", hvor: $\højre pil$
- "venstre side" er en ikke-tom sekvens af terminaler og ikke-terminaler, der indeholder mindst én ikke-terminal
- "højre side" - enhver sekvens af terminaler og ikke-terminaler
S er startsymbolet (eller initialt) for grammatikken fra sættet af ikke-terminaler.

Konklusion

Et output er en sekvens af linjer, der består af terminaler og ikke-terminaler, hvor den første linje er en linje bestående af én startende ikke-terminal, og hver efterfølgende linje opnås fra den foregående ved at erstatte en delstreng i henhold til en (en hvilken som helst) af reglerne. Den sidste streng er en streng, der udelukkende består af terminaler, og er derfor et ord i sproget.

Eksistensen af en afledning for et bestemt ord er et kriterium for dets tilhørsforhold til det sprog, der er defineret af den givne grammatik.

Typer af grammatik

Ifølge Chomsky-hierarkiet er grammatikker opdelt i 4 typer, hver efterfølgende er en mere begrænset delmængde af den forrige (men også lettere at analysere):

type 0. ubegrænset grammatik - alle regler er mulige
type 1. kontekstfølsomme grammatikker - venstre del kan indeholde én ikke-terminal omgivet af en "kontekst" (sekvenser af tegn, der er til stede i samme form i højre del); selve ikke-terminalen erstattes af en ikke-tom sekvens af tegn på højre side.
type 2. kontekstfri grammatik — den venstre del består af én ikke-terminal.
type 3. almindelige grammatikker er enklere, svarende til endelige automater .

Derudover er der:

Ikke-afkortende grammatikker . Hver regel i en sådan grammatik har formen , hvor . Længden af højre side af reglen er ikke mindre end længden af venstre [1] . $\alpha \rightarrow \beta$ $|\alpha |\leqslant |\beta |$
Lineære grammatikker . Hver regel i en sådan grammatik har formen , eller , det vil sige, at højre side af reglen ikke kan indeholde mere end én forekomst af en ikke-terminal [2] . $A\højrepil uBv$ $A\højrepil u$

Ansøgning

Kontekstfrie grammatikker anvendes i vid udstrækning til at definere grammatisk struktur i grammatisk analyse .
Regulære grammatikker (i form af regulære udtryk ) er meget brugt som skabeloner til tekstsøgning, opdeling og substitution, herunder i leksikalsk analyse .

Et eksempel er aritmetiske udtryk

Overvej et simpelt sprog, der definerer en begrænset delmængde af aritmetiske formler bestående af naturlige tal , parenteser og aritmetiske tegn. Det er værd at bemærke, at her i hver regel på venstre side af pilen er der kun ét ikke-terminalt symbol. Sådanne grammatikker kaldes kontekstfri . $\højre pil$

Terminal alfabet:

\Sigma

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

Ikke-terminalt alfabet:

{ FORMEL, SIGN, NUMMER, NUMMER }

Regler:

1. FORMEL FORMEL TEGN FORMEL

\til

(en formel har to formler forbundet med et tegn) 2. FORMELNUMMER ( formlen

\til

er et tal) 3. FORMEL ( FORMEL )

\til

(en formel er en formel i parentes) 4. SIGN + | - | * | /

\til

(tegnet er plus eller minus, eller gange eller dividere) 5. TALCIFTER (

\til

et tal er et tal) 6. TAL NUMMER CIFFER

\til

(et tal er et tal og et tal) 7. NUMMER 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

\til

(ciffer er 0 eller 1, eller ... 9)

Indledende ikke-terminal:

FORMEL

Konklusion :

Lad os udlede formlen (12+5) ved hjælp af de anførte inferensregler. For klarhedens skyld er siderne af hver udskiftning vist i par, i hvert par er den udskiftede del understreget.

FORMEL (FORMEL)

{\stackrel {3}{\to ))

( FORMEL ) ( FORMELTEGNFORMEL )

{\stackrel {1}{\to ))

(FORMELTEGNFORMEL ) ( 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) ( TAL + 5)

{\stackrel {2}{\to ))

( TAL + 5) ( TAL CIFFER + 5)

{\stackrel {6}{\to ))

( TAL CIFFER + 5) ( CIFFER + 5)

{\stackrel {5}{\to ))

( CIFFER + 5) ( 1 CIFFER + 5)

{\stackrel {7}{\to ))

(1 CIFFER + 5) (1 2 + 5)

{\stackrel {7}{\to ))

Analytiske grammatikker

Generative grammatikker er ikke den eneste form for grammatik, men de er de mest almindelige i programmeringsapplikationer. I modsætning til generative grammatikker definerer analytisk (genkendende) grammatik en algoritme, der giver dig mulighed for at bestemme, om et givet ord hører til sproget. For eksempel kan ethvert almindeligt sprog genkendes ved hjælp af en grammatik defineret af en tilstandsmaskine , og enhver kontekstfri grammatik kan genkendes ved hjælp af en stack-baseret automat . Hvis et ord tilhører et sprog, så konstruerer en sådan automat dets output i en eksplicit form, som gør det muligt at analysere semantikken i dette ord.

Se også

JFLAP - simulator af automater, Turing-maskiner, grammatikker
parsing
Tvetydig grammatik
Minimum grammatik problem
Grammatik med sætningsstruktur

Noter

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

Litteratur

Belousov A. I., Tkachev S. B. Diskret matematik. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .
Gladkiy A. V. Formelle grammatikker og sprog. — M .: Nauka, 1973.
Kasyanov VN Forelæsninger om teorien om formelle sprog, automater og beregningsmæssig kompleksitet. - Novosibirsk: NGU, 1995. - 112 s.
Chomsky N., Miller J. Introduktion til den formelle analyse af naturlige sprog // Kybernetisk samling / Ed. A.A. Lyapunova og O.B. Lupanova. — M .: Mir, 1965.
Gross M., Lanten A. Formel grammatiks teori. — M .: Mir, 1971. — 296 s.

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme