Gramàtica lliure de context

En lingüística i informàtica, una gramàtica lliure de context (o de context lliure) és una gramàtica formal en la qual cada regla de producció és de la forma:

V → w

On V és un símbol no terminal i w és una cadena de terminals i/o no terminals. El terme lliure de context es refereix al fet que el no terminal V pot sempre ser substituït per w sense tenir en compte el context en què passi. Un llenguatge formal és lliure de context si hi ha una gramàtica lliure de context que el genera.

Les gramàtiques lliures de context permeten descriure la majoria dels llenguatges de programació, de fet, la sintaxi de la majoria de llenguatges de programació està definida mitjançant gramàtiques lliures de context. D'altra banda, aquestes gramàtiques són suficientment simples com per a permetre el disseny d'eficients algoritmes d'anàlisi sintàctica que, per a una cadena de caràcters donada determinin com pot ser generada des de la gramàtica. Els analitzadors LL i LR tracten restringits subconjunts de gramàtiques lliures de context.

La notació més freqüentment utilitzada per a expressar gramàtiques lliures de context és la forma Backus-Naur.

Definició formal

Així com qualsevol gramàtica formal, una gramàtica lliure de context pot ser definida mitjançant la 4-tupla:

$G=(V_{t},V_{n},P,S)$ on

$V_{t}$ és un conjunt finit de terminals
$V_{n}$ és un conjunt finit de no terminals
$P$ és un conjunt finit de produccions
$S\in V_{n}$ l'anomenat Símbol Inicial
Els elements de $P$ són de la forma

V_{n}\longrightarrow (V_{t}\cup V_{n})^{*}

Exemples

Exemple 1

Una simple gramàtica lliure de context és

S → aSb|ε

on | és un o lògic i és usat per a separar múltiples opcions per al mateix no terminal, ε indica una cadena buida. Aquesta gramàtica genera el llenguatge no regular $\{a^{n}b^{n}:n\geq 0\}$ .

Exemple 2

Aquí hi ha una gramàtica lliure de context per a expressions senceres algebraiques sintàcticament correctes sobre les variables x , i i z :

S → x|i|z|S+S|S - S|S * S|S/S|(S)

Generaria, per exemple, la cadena (x+i) * x - z * i/(x+x)

Exemple 3

Una gramàtica lliure de context per a un llenguatge consistent en totes les cadenes que es poden formar amb les lletres a i b , havent-hi un nombre diferent d'una que d'una altra, seria:

S → U|V

U → Tau|Tat

V → TBV|TBT

T → aTbT|bTaT|ε

T genera totes les cadenes amb la mateixa quantitat de lletres que b, O genera totes les cadenes amb més lletres a, i V totes les cadenes amb més lletres b.

Exemple 4

Un altre exemple per a un llenguatge és $\{a^{n}b^{m}c^{m+n}:n\geq 0,m\geq 0\}$ . No és un llenguatge regular, però pot ser generat per la següent gramàtica lliure de context.

S → asc|B

B → BBC|ε

Altres exemples

Les gramàtiques lliures de context no estan limitades a llenguatges matemàtics formals.

La gramàtica de Lojban, un llenguatge artificial parlat amb gran capacitat expressiva, és també lliure de context i no ambigu.

El lingüista indi Pànini va descriure el sànscrit usant una gramàtica lliure de context.^[1]

S'ha suggerit que una classe de poesia Tàmil anomenada Venpa utilitza principalment una gramàtica lliure de context.^[2]

Derivacions i arbres sintàctics

Existeixen bàsicament dues formes de descriure com en una certa gramàtica una cadena pot ser derivada des del símbol inicial. La forma més simple és llistar les cadenes de símbols consecutives, començant pel símbol inicial i finalitzant amb la cadena i les regles que han sigut aplicades. Si introduïm estratègies com reemplaçar sempre el no terminal de més a l'esquerra primer, llavors la llista de regles aplicades és suficient. D'això se'n diu derivació per l'esquerra . Per exemple, si prenem la següent gramàtica:

(1) S → S+S

(2) S → 1

i la cadena "1+1+1", la seva derivació per l'esquerra és en la llista [(1) (1) (2) (2) (2)]. Anàlogament, la derivació per la dreta es defineix com a la llista que obtenim si sempre reemplacem primer el no terminal de més a la dreta. En aquest cas, la llista de regles aplicades per a la derivació de la cadena amb la gramàtica anterior seria la [(1) (2) (1) (2) (2)].

La distinció entre derivació per l'esquerra i per la dreta és important perquè en la majoria d'analitzadors, la transformació de l'entrada és definida donant una part de codi per a cada producció que és executada quan la regla és aplicada. De manera que és important saber quina derivació aplica l'analitzador, perquè determina l'orde en el qual el codi serà executat.

Una derivació també pot ser expressada mitjançant una estructura jeràrquica sobre la cadena que està sent derivada. Per exemple, l'estructura de la derivació a l'esquerra de la cadena "1+1+1" amb la gramàtica anterior seria:

S → S+S (1)

S → S+S+S (1)

S → 1+S+S (2)

S → 1+1+S (2)

S → 1+1+1 (2)

\{\{\{1\}_{S}+\{1\}_{S}\}_{S}+\{1\}_{S}\}_{S}

on $\{...\}_{S}$ indica la subcadena reconeguda com a pertanyent a S. Aquesta jerarquia també es pot representar mitjançant un arbre sintàctic:

S
/|\
/ | \
/ | \
S '+' S
/|\ |
/ | \ |
S '+' S '1'
| |
'1' '1'

Aquest arbre és anomenat arbre de sintaxi concreta de la cadena (vegeu també arbre de sintaxi abstracta). En aquest cas, les derivacions per l'esquerra i per la dreta presentades defineixen la sintaxi de l'arbre, però, hi ha una altra derivació (per l'esquerra) de la mateixa cadena.

La derivació per la dreta:

S → S + S (1)

S → 1 + S (2)

S → 1 + S + S (1)

S → 1 + 1 + S (2)

S → 1 + 1 + 1 (2)

defineix el següent arbre sintàctic:

S 
/|\
/ | \
/ | \
S '+' S
| /|\
| / | \
'1' S '+' S
| |
'1' '1'

Si per a una cadena del llenguatge d'una gramàtica hi ha més d'un arbre possible, llavors es diu que la gramàtica és ambigua. Normalment aquestes gramàtiques són més difícils d'analitzar perquè l'analitzador no pot decidir sempre quina producció aplicar.

Formes normals

Una gramàtica que no genera la cadena buida pot ser transformada en una equivalent (que genera el mateix llenguatge) en forma normal de Chomsky o en forma normal de Greibach.

La simplicitat de les regles en forma normal de Chomsky té implicacions teòriques i pràctiques. Per exemple, donada una gramàtica lliure de context, es pot usar la seva forma normal per a construir un algorisme de cost polinomial que decideixi si una cadena forma part del llenguatge definit per la gramàtica o no (algorisme CYK).

Problemes indecidibles

Algunes de les propietats de les gramàtiques, i en general, dels llenguatges lliures del context són de naturalesa decidible, existint per tant algorismes de decisió per a resoldre'ls. No obstant això, al contrari que en el cas dels llenguatges regulars, hi ha problemes interessants per als quals s'ha mostrat la seva naturalesa indecidible, i per tant, hom no té el corresponent algorisme.

Un dels més senzills és el de decidir si una gramàtica lliure del context donada accepta el llenguatge de totes les possibles cadenes de símbols. Aquest llenguatge ve a ser una reducció del problema d'aturada d'una màquina de Turing amb una entrada particular, i per tant, un problema indecidible. La reducció usa el concepte d'història computacional, és a dir, una cadena que descrigui el procés de computació global d'una màquina de Turing, aquesta cadena podria descriure mitjançant una gramàtica lliure del context. Podem construir, per tant, una gramàtica lliure del context que generi totes les cadenes no acceptades per la màquina de Turing indicada.

Una conseqüència important és que també és indecidible la comparació entre dues gramàtiques lliures del context per comprovar si el llenguatge generat coincideix.

Per contra, el problema senzill de determinar si donada una cadena és acceptada per una determinada gramàtica lliure del context, sí que és decidible, i per tant podrà escriure el corresponent algorisme per a decidir-ho.

Propietats dels llenguatges lliures de context

Una de les definicions alternatives i equivalents de llenguatge lliure de context empra autòmats no deterministes: un llenguatge és lliure de context si pot ser acceptat per aquest autòmat.
Un llenguatge pot ser també modelat com un conjunt de totes les seqüències de terminals acceptades per la gramàtica. Aquest model ajuda a entendre les operacions de conjunts sobre llenguatges.
La unió i concatenació de dos llenguatges lliures de context és també lliure de context. La intersecció no té per què ser-ho.
L'invers d'un llenguatge lliure de context és també lliure de context, però el complement no té per què ser-ho.
Els llenguatges regulars són lliures de context perquè poden ser descrits mitjançant una gramàtica de lliure context.
La intersecció d'un llenguatge lliure de context i un llenguatge regular és sempre lliure de context.
Existeixen Gramàtiques sensibles al context que no són lliures de context.
Per a demostrar que un llenguatge donat no és lliure de context, es pot emprar el Lema del bombament per a llenguatges lliures de context.
El problema de determinar si una gramàtica sensible al context descriu un llenguatge lliure del context és indecidible.

Vegeu també

Referències

↑ Raman, Varadaraja V. Indic Visions: In an Age of Science. Xlibris Corporation, 2011, p.69. ISBN 146288363X.
↑ Baladunarman, I.; Ishwar, S.; Kumar, R. Sanjeeth. Context-free grammar for natural language constructs. An implementation for Venpa class of Tamil poetry (en anglès), 2003.

[1] Raman, Varadaraja V. Indic Visions: In an Age of Science. Xlibris Corporation, 2011, p.69. ISBN 146288363X.

[2] Baladunarman, I.; Ishwar, S.; Kumar, R. Sanjeeth. Context-free grammar for natural language constructs. An implementation for Venpa class of Tamil poetry (en anglès), 2003.

[1]

[2]