Formális nyelvtan

A formális nyelvtan vagy csak a nyelvtan a formális nyelvek elméletében a formális nyelv leírásának módja, vagyis egy bizonyos részhalmaz kiválasztása valamilyen véges ábécé összes szavai közül . Léteznek generatív és felismerő (vagy elemző ) nyelvtanok – az első meghatározza azokat a szabályokat, amelyekkel a nyelv bármely szava felépíthető, a második pedig lehetővé teszi egy adott szóból annak meghatározását, hogy az szerepel-e a nyelvben vagy sem.

Feltételek

A terminál (terminális szimbólum) olyan objektum, amely közvetlenül jelen van a nyelvtannak megfelelő nyelv szavaiban, és sajátos, megváltoztathatatlan jelentéssel bír (a „betűk” fogalmának általánosítása). A számítógépen használt formális nyelveken a szabványos ASCII karakterek egészét vagy egy részét - latin betűket, számokat és speciális karaktereket - általában terminálnak tekintik .
A nem terminális (nem terminális szimbólum) egy olyan objektum, amely valamilyen nyelvi entitást jelöl (például: egy képlet, egy aritmetikai kifejezés, egy parancs), és nem rendelkezik konkrét szimbolikus értékkel.

Generatív nyelvtanok

A nyelvtan által megadott nyelv szavai mindazok a terminálok sorozatai, amelyek a kimeneti szabályok szerint a kezdeti nem terminálból kerülnek kiadásra (generálásra).

A nyelvtan beállításához be kell állítania a terminálok és a nem terminálok ábécéjét, a következtetési szabályok készletét, valamint ki kell választania a kezdőt a nem terminálok készletéből.

Tehát a nyelvtant a következő jellemzők határozzák meg:

$\Sigma$ — terminálszimbólumok halmaza ( ábécé ).
N a nem terminális szimbólumok halmaza ( ábécé ).
P a következő alakú szabályok halmaza: "bal oldal" "jobb oldal", ahol: $\jobb nyíl$
- "bal oldal": terminálok és nem-terminálisok nem üres sorozata, amely legalább egy nem-terminálist tartalmaz
- "jobb oldal" - a terminálok és a nem terminálok bármely sorozata
S a nyelvtan kezdő (vagy kezdő) szimbóluma a nem terminálok halmazából.

Következtetés

A kimenet olyan sorok sorozata, amelyek terminálokból és nem terminálokból állnak, ahol az első sor egy kezdő nem-terminálból álló sor, és minden következő sor az előzőből származik úgy, hogy valamilyen (bármely) részkarakterláncot lecserélünk. a szabályokról. Az utolsó karakterlánc egy teljes egészében terminálokból álló karakterlánc, ezért a nyelv szava.

Egy szó származékának megléte az adott nyelvtan által meghatározott nyelvhez való tartozás kritériuma.

A nyelvtan típusai

A Chomsky-hierarchia szerint a nyelvtanok 4 típusra oszlanak, mindegyik következő egy korlátozottabb részhalmaza az előzőnek (de könnyebben elemezhető):

típus 0. korlátlan nyelvtan – bármilyen szabály lehetséges
típus 1. környezetérzékeny nyelvtanok - a bal oldali rész tartalmazhat egy nem terminált, amelyet "kontextus" vesz körül (a jobb oldalon azonos formában lévő karaktersorozatok); magát a nem terminált egy nem üres karaktersorozat helyettesíti a jobb oldalon.
típusú 2. környezetfüggetlen nyelvtanok — a bal oldali rész egy nem terminálból áll.
típus 3. a reguláris nyelvtanok egyszerűbbek, ekvivalensek a véges automatákkal .

Ezen kívül vannak még:

Nem rövidítő nyelvtanok . Egy ilyen nyelvtan minden szabályának olyan alakja van , ahol . A szabály jobb oldalának hossza nem kisebb, mint a bal oldal hossza [1] . $\alpha \rightarrow \beta$ $|\alpha |\leqslant |\beta |$
Lineáris nyelvtanok . Egy ilyen nyelvtan minden szabályának alakja , vagy , azaz a szabály jobb oldala legfeljebb egy nem terminális előfordulását tartalmazhatja [2] . $A\rightarrow uBv$ $A\jobbra u$

Alkalmazás

A kontextusmentes nyelvtanokat széles körben alkalmazzák a nyelvtani struktúra meghatározására a nyelvtani elemzésben .
A reguláris nyelvtanokat ( reguláris kifejezések formájában ) széles körben használják sablonként a szöveges kereséshez, bontáshoz és helyettesítéshez, beleértve a lexikális elemzést is .

Példa erre az aritmetikai kifejezések

Vegyünk egy egyszerű nyelvet, amely természetes számokból , zárójelekből és számtani előjelekből álló számtani képletek korlátozott részhalmazát határozza meg . Érdemes megjegyezni, hogy itt minden szabályban a nyíl bal oldalán csak egy nem terminális szimbólum szerepel. Az ilyen nyelvtanokat kontextusmentesnek nevezzük . $\jobb nyíl$

Terminál ábécé:

\Sigma

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

Nem terminális ábécé:

{ FORMULA, JEL, SZÁM, SZÁM }

Szabályok:

1. FORMULA FORMULA JEL FORMULA

\nak nek

(egy képletnek két képlete van, amelyeket előjel köt össze) 2. FORMULA SZÁMA

\nak nek

(a képlet egy szám) 3. FORMULA ( FORMULA )

\nak nek

(a képlet egy zárójelben lévő képlet) 4. JEL + | - | * | /

\nak nek

(az előjel plusz vagy mínusz, vagy szorzás vagy osztás) 5. SZÁM SZÁM (

\nak nek

egy szám az egy szám) 6. SZÁMSZÁM SZÁMJEGY

\nak nek

(a szám egy szám és egy szám) 7. SZÁM 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

\nak nek

(a számjegy 0 vagy 1, vagy ... 9)

Kezdeti nem terminál:

KÉPLET

Következtetés :

Vezessük le a (12+5) képletet a felsorolt következtetési szabályok segítségével. Az érthetőség kedvéért az egyes cseredarabok oldalai párban vannak feltüntetve, minden párban aláhúzva a kicserélt alkatrész.

FORMULA (FORMULA)

{\stackrel {3}{\to ))

( FORMULA ) ( FORMULA SIGN FORMULA )

{\stackrel {1}{\to ))

(FORMULA SIGN FORMULA) (FORMULA + FORMULA)

{\stackrel {4}{\to ))

( FORMULA + FORMULA ) ( FORMULA + SZÁM )

{\stackrel {2}{\to ))

( FORMULA + SZÁM ) ( KÉPLET + SZÁM )

{\stackrel {5}{\to ))

( FORMULA + SZÁM ) ( FORMULA + 5 )

{\stackrel {7}{\to ))

( FORMULA + 5) ( SZÁM + 5)

{\stackrel {2}{\to ))

( SZÁM + 5) ( SZÁM SZÁM + 5)

{\stackrel {6}{\to ))

( SZÁM SZÁM + 5) ( SZÁMJEGY + 5)

{\stackrel {5}{\to ))

( SZÁMJEGY + 5) ( 1 SZÁMJEGY + 5)

{\stackrel {7}{\to ))

(1 SZÁMJEGY + 5) (1 2 + 5)

{\stackrel {7}{\to ))

Analitikus nyelvtanok

A generatív nyelvtan nem az egyetlen nyelvtan típus, de ezek a leggyakoribbak a programozási alkalmazásokban. A generatív nyelvtanoktól eltérően az analitikus (felismerő) nyelvtan meghatároz egy algoritmust, amely lehetővé teszi annak meghatározását, hogy egy adott szó a nyelvhez tartozik-e. Például bármely reguláris nyelv felismerhető egy állapotgép által definiált nyelvtan segítségével , és bármely környezetfüggetlen nyelvtan felismerhető egy veremalapú automata segítségével . Ha egy szó egy nyelvhez tartozik, akkor egy ilyen automata a kimenetét explicit formában konstruálja meg, ami lehetővé teszi a szó szemantikájának elemzését .

Lásd még

JFLAP - automaták, Turing-gépek, nyelvtan szimulátora
elemzése
Kétértelmű nyelvtan
A minimális nyelvtani probléma
Nyelvtan kifejezésszerkezettel

Irodalom

Belousov A. I., Tkachev S. B. Diszkrét matematika. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .
Gladkiy A. V. Formális nyelvtanok és nyelvek. - M .: Nauka, 1973.
Kasyanov VN Előadások a formális nyelvek elméletéről, az automatákról és a számítási komplexitásról. - Novoszibirszk: NGU, 1995. - 112 p.
Chomsky N., Miller J. Bevezetés a természetes nyelvek formális elemzésébe // Kibernetikai gyűjtemény / Szerk. A.A. Lyapunova és O.B. Lupanova. - M .: Mir, 1965.
Gross M., Lanten A. Formális grammatikák elmélete. — M .: Mir, 1971. — 296 p.

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus