Formala gramatiko

Formala gramatiko aŭ simple gramatiko en la teorio de formalaj lingvoj estas metodo de priskribo de formala lingvo. Ĉiu formala lingvo L bazas sur iu finkvanta alfabeto A de literoj (simboloj). Alivorte, gramatiko estas metodo (matematika aparato) de distingo de propozicioj, konstruitaj sur la bazo de alfabeto A, apartenantaj al lingvo L de ĉiuj literaj sekvencoj el alfabeto A.

Formalajn gramatikojn kaj formalajn lingvojn esploras la matematika lingvistiko, kiu disvolviĝas ekde 1950-aj jaroj.

Oni distingas:

generantajn gramatikojn (kiuj difinas regulojn de konstruaĵo de propozicioj de lingvo L);
rekonantajn (analizajn) gramatikojn (kiuj respondas, ĉu certa propozicio P apartenas al lingvo L).

Terminoj

Formala gramatiko estas kutime aro de linioj konsistantaj el simboloj, foje kun tabelo (matrico). La plej klasika kaj uzata matematika aparato por generantaj gramatikoj estas formalaj gramatikoj de Noam Chomsky, kiuj esence estas aroj de linioj. Klare, ke la gramatiko enhavas alfabeton A, el kies literoj konsistas la propozicioj. La literojn de alfabeto A oni nomas terminalaj simboloj aŭ simple terminaloj.

Krom terminalaj simboloj la gramatiko enhavas neterminalajn simbolojn (neterminalojn), kiuj diferenciĝas de terminaloj. Ĉiu neterminalo signifas aron de frazoj (gramatikan klason) de la difinita lingvo. Ekzemple por lingvo de programado iu neterminalo povas signifi "listo de argumentoj de funkcio", "aritmetika esprimo" ktp. En gramatiko de natura lingvo neterminalo povas signifi ekzemple "cirkonstanca komplemento de tempo".

Alia grava termino estas regulo de inferenco: du sekvencoj de simboloj (maldekstra kaj dekstra) dividitaj per indikilo $\Rightarrow$ . La regulo funkcias tiamaniere, ke en intermita rezulto de inferenco oni substituas la maldekstran flankon de la regulo kun ĝia dekstra flanko. La rezulto estas la sekvanta paŝo de la inferenco.

Generantaj gramatikoj

Tiun ĉi matematikan aparaton proponis la usona matematikisto Noam Chomsky. ^[1]

Difino

La formala gramatiko konsistas el

finkvanta terminala alfabeto A.
finkvanta neterminala alfabeto N.
fina nombro de reguloj R de inferenco

{M $\rightarrow$ D, kie M estas la maldekstra flanko, D estas la dekstra flanko de la regulo. La maldekstra flanko enhavas almenaŭ unu neterminalon.

elektita neterminalo S nomata starta simbolo.

La inferenco de propozicio funkcias sekvantmaniere. Unua linio de inferenco estas la neterminalo S. Ĉiun sekvantan linion oni obtenas per substitucio de ajna maldekstra flanko de ajna regulo kun ĝia dekstra flanko. La procedo daŭras ĝis la kuranta linio enhavas almenaŭ unu neterminalon. La lasta linio de inferenco, kiu enhavas nur terminalojn, estas propozicio (kutime unu el nefinita kvanto de propozicioj) de la lingvo difinita per gramatiko.

Ekzemplon de inferenco vidu sube en la paragrafo "inferenco".

Arbo de sintaksa analizo estas grafika reprezento de inferenco kiel arbo. La tronko de la arbo estas la starta neterminalo S. Post apliko de iu regulo al iu nodo de arbo aldoniĝas pendanta(j) branĉo(j) el dekstra flanko de la regulo. Kelkaj inferencoj kun diversaj ordoj de apliko de reguloj povas rezulti la saman arbon. Sekve, la arbo de sintaksa analizo estas "pli interesa" ol inferenco.

Klasifiko

Laŭ hierarĥio de Chomsky gramatikoj apartenas al 4 tipoj.

tipo 0: nelimigita gramatiko. Laŭ difino antaŭe, sen limoj por reguloj.
tipo 1: kunteksta gramatiko. La maldekstra flanko enhavas nur unu neterminalon, kiu povas havi antaŭe kaj/aŭ poste terminalojn (nomatajn kunteksto). La neterminalo mem substituiĝas kun sekvenco el almenaŭ unu simbolo en dekstra flanko.
tipo 2: senkunteksta gramatiko. La maldekstra flanko konsistas el unu neterminalo.
tipo 3: regula gramatiko aŭ aŭtomata gramatiko. Aldone la dekstra flanko povas esti
- a (iu terminalo),
- aB (en dekstra regulara gramatiko; Ba en maldekstra regulara gramatiko), B estas neterminalo aŭ
- malplena simbolo ε.

Ju pli granda estas la tipo de gramatiko, des pli limigita estas la lingvo, kiun ĝi difinas, kaj des pli facila estas la analizo de la lingvo.

Proprecoj de gramatikoj

Grava propreco de gramatiko estas ĝia unu- aŭ dusenseco. La gramatiko estas unusenca, se ĉiu propozicio havas nur unu arbon de sintaksa analizo. Alie la gramatiko estas dusenca.

Jam en komenca epoko de matematika lingvistiko estis malkovritaj gravaj teoremoj pri fundamentaj proprecoj de gramatikoj:

propozicioj de senkunteksta gramatiko estas rekoneblaj per fina aŭtomato kun senfina staka memoro. Do ne sufiĉas fina memoro. Tamen gravas, ke laŭ ĉiu senkunteksta gramatiko oni povas ŝablone konstrui komputilan programon (aŭ finan aŭtomaton kun stako), kiu rekonas propoziciojn de la lingvo difinita per tiu gramatiko. Do ĉiu generanta senkunteksta (kaj aŭtomata) gramatiko estas samtempe analiza gramatiko. Ekzistas komputilaj programoj, kiuj konstruas analizan programon laŭ ĉiu senkunteksta gramatiko. Unu de unuaj kaj plej famaj de tiuj programoj estas la programo yacc, kiun kutime enhavas ĉiu liveraĵo de operaciumo Linukso.
propozicioj de aŭtomata gramatiko estas rekoneblaj per fina aŭtomato. Do sufiĉas fina memoro.

Senkuntekstaj gramatikoj estas gravegaj en teorio de lingvoj de programado ĉar la plimulto de lingvoj de programado estas difinitaj per senkunteksta gramatiko.

Ekzemploj de gramatiko kaj inferenco

Ni konsideru lingvon de simplaj aritmetikaj esprimoj, kiuj konsistas el naturaj nombroj, parentezoj kaj signoj de aritmetikaj operacioj. Ni prezentos du ekzemplojn de senkunteksta gramatiko. Ambaŭ gramatikoj havas la saman terminalan alfabeton

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

Se maldekstraj flankoj de kelkaj reguloj estas samaj, tiujn regulojn oni skribas ofte koncize kvazaŭ unu regulon kun dekstraj flankoj separitaj per "|". Memkompreneble, tio eblas, se "|" ne estas terminala nek neterminala simbolo.

Gramatiko 1

Neterminala alfabeto:

{ Formulo, Signo, Nombro, Cifero }.

La starta simbolo Formulo estas substrekita.

Reguloj:

1.  Formulo  $\rightarrow \!\,$  Formulo Signo Formulo                 (formulo estas du formuloj kunigitaj per signo)
2.  Formulo  $\rightarrow \!\,$  Nombro                                (formulo estas nombro)
3.  Formulo  $\rightarrow \!\,$  (Formulo)                         (formulo estas formulo en parentezoj)
4.  Signo  $\rightarrow \!\,$  + | - | * | /                          (signo estas plus aŭ minus aŭ multipliki aŭ dividi)
5.  Nombro  $\rightarrow \!\,$  Cifero                                  (nombro estas cifero)
6.  Nombro  $\rightarrow \!\,$  Nombro Cifero                            (nombro estas nombro kaj cifero)
7.  Cifero  $\rightarrow \!\,$  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (cifero estas 0 aŭ 1 aŭ ... 9 )

Ekzemploj de inferenco

Ni nun inferu la formulon 12*5+3 per tiu ĉi gramatiko.

Inferenco 1.1:

Formulo starta simbolo, per apliko de regulo 1 ni obtenos la sekvan linion:
Formulo Signo Formulo regulo 1:
Formulo Signo Formulo Signo Formulo regulo 2:
Nombro Signo Formulo Signo Formulo regulo 4:
Nombro * Formulo Signo Formulo regulo 2:
Nombro * Nombro Signo Formulo regulo 4:
Nombro * Nombro + Formulo regulo 2:
Nombro * Nombro + Nombro regulo 6:
Nombro Cifero * Nombro + Nombro regulo 5:
Cifero Cifero * Nombro + Nombro regulo 7:
1 Cifero * Nombro + Nombro regulo 7:
12* Nombro + Nombro regulo 5:
12* Cifero + Nombro regulo 7:
12*3+ Nombro regulo 5:
12*3+ Cifero regulo 7:
12*3+5 fina propozocio

Jen la arbo de inferenco:

Tiu ĉi gramatiko povas produkti ankaŭ alian arbon por sama propozicio.

Inferenco 1.2:

Formulo starta simbolo, per apliko de regulo 1 ni obtenos la sekvan linion:
Formulo Signo Formulo regulo 1:

. . .

12*3+5 fina propozicio

Facile kompreneble, la arbo de analizo estas jam alia. Do tiu gramatiko estas dusenca.

Se iu kompililo uzas tiun ĉi gramatikon, la unua arbo difinas ordon de kalkulo 12*(3+5), la dua arbo (ĉi tie ne montrita) difinas ordon (12*3)+5. Klare, la unua ordo estas erara laŭ la kutima interkonsento pri aritmetikaj operacioj. Do tiu ĉi gramatiko ne estas praktika por analizo de aritmetikaj esprimoj.

Gramatiko 2

Jen la pli oportuna gramatiko, kiu difinas la saman lingvon.

La terminala alfabeto A estas la sama (vidu gramatikon 1).
Neterminala alfabeto:

{Formulo, FormulSufikso , MultDiv, AtomSufikso , Atomo, Nombro, Cifero}.

Reguloj:

Formulo $\rightarrow$ MultDiv FormulSufikso
MultDiv $\rightarrow$ Atomo AtomSufikso
Atomo $\rightarrow$ Nombro | (Formulo)
FormulSufikso $\rightarrow$ + MultDiv FormulSufikso | - MultDiv FormulSufikso | ε
AtomSufikso $\rightarrow$ *Atomo AtomSufikso | / Atomo AtomSufikso | ε

kaj la samaj reguloj por Nombro kaj Cifero

La sama starta neterminalo Formulo.

Inferenco 2.

Formulo, regulo1.
MultDiv FormulSufikso reg. 2
AtomoAtomSufikso FormulSufikso reg. 3/1
NombroAtomSufiksoFormulSufikso reg. 5/1
Nombro*Atomo AtomSufikso FormulSufikso reg. 3/1
Nombro * Nombro AtomSufiksoFormulSufikso reg. 5/3
Nombro * Nombro FormulSufikso reg. 4/1
Nombro * Nombro + MultDiv FormulSufikso reg. 2
Nombro * Nombro + AtomoAtomSufikso FormulSufikso reg. 3/1
Nombro * Nombro + Nombro AtomSufikso FormulSufikso reg. 4/3
Nombro * Nombro + Nombro FormulSufikso reg 4/3
Nombro * Nombro + Nombro plue ni obtenas la rezulton kiel en gramatiko 1:

. . .

12*3+5 fina propozicio

jen la arbo de inferenco.

La gramatiko 2 havas sekvantajn gravajn proprecojn.

. La prioritato de operacioj estas ĉiam ĝusta. Tio signifas, ke el paralelaj operacioj (+,-) kaj (*,/) la lastaj pendas en arbo ĉiam malpli alte kaj dum sintaksa analizo estas prilaborataj pli strikte.
. Inter reguloj kun kelkaj alternativoj ĉiu alternativo (eble krom la lasta) komencas kun terminalo kaj diversaj alternativoj kun diversaj terminaloj. Senkuntekstaj gramatikoj kun tiu ĉi propreco nomiĝas maldekstre faktorigitaj (angle: left factored, ruse: левофакторизованные).

Maldekstre faktorigitaj gramatikoj ebligas sintaksan analizon sen returno laŭ analizata teksto. Fakte, elekto de alternativo dum analizo estas determinita de sekvanta terminala simbolo. Estas facila transformi maldekstre faktorigitan gramatikon en rapidegan komputilan programon, kiu analizas la formalan lingvon determinatan de tiu gramatiko.

Do por konstrui analizilon estas tre grava konstrui ĝustan gramatikon. Unuflanke, la gramatiko devas aranĝi propoziciojn en dezirata strukturo (ekzemple kiel en aritmetikaj esprimoj la prioritato de operacioj). Aliflanke la gramatiko devas esti oportuna por analizo. Por seriozaj lingvoj kiel lingvoj de programado konstrui bonan gramatikon estas arto, kiun regas malmultaj da fakuloj.

Skribmaniero de Backus-Naur

Backus kaj Naur proponis por prezenti senkuntekstajn gramatikojn propran skribmanieron, kiun oni ofte uzas por publiki gramatikojn.

En formo de Backus-Naur neterminaloj estas nomoj en angulaj parentezoj. Ofte oni uzas sufiĉe longajn priskribojn de neterminaloj, ekzemple <listo de formalaj parametroj> aŭ <listo de faktaj parametroj>. La dekstra kaj maldekstra flanko de regulo estas separitaj per simboloj ::=. Krome, reguloj kun sama maldekstra flanko estas kolektitaj en unu regulo kun dekstraj flankoj separitaj per simbolo |. Ekzemple, jen reguloj por neterminalo 'Formulo en la gramatiko 1 en formo de Backus-Naur:

< Formulo> ::= <Formulo> <Signo> <Formulo> | <Nombro> | (<Formulo>)

Transformo de gramatikoj

Kiel oni vidis antaŭe, el du gramatikoj, kiuj difinas la saman lingvon, unu povas esti multe pli oportuna ol alia. Tial estas interesaj transformoj de gramatikoj, kiuj konservas la difinitan lingvon.

Ekzistas proceduroj, kiuj transformas gramatikon en maldekstre faktorigitan. Tamen ekzistas certaj teoriaj limoj por tiu transformado. Ekzemple, la komenca gramatiko devas esti unusenca. Ni konsideras en tiu ĉi paragrafo nur transformadon de senkuntekstaj gramatikoj.

La unua paŝo de transformado estas elimino de tielnomata maldekstra rekursio. La gramatiko estas maldekstre rekursia, se ĝi enhavas eĉ unu maldekstre rekursian regulon

N $\rightarrow$ Nα,

kie N estas neterminalo, α estas ajna sekvenco de simboloj enhavanta terminalo(j)n aŭ/kaj neterminalo(j)n, aŭ tian maldekstre rekursian regulon oni povas obteni el reguloj de la gramatiko per maldekstra substituado. Alivorte tio signifas, ke en la gramatiko ekzistas maldekstre rekursia maŝo. Ekzemple du reguloj

. N $\rightarrow$ Xα

. X $\rightarrow$ N β

generas rekursian maŝon ĉar du sinsekvaj aplikoj de tiuj reguloj rezultas la saman neterminalon al komenco. Apliko de regulo 2 post regulo 1 rezultas derivitan regulon

N $\rightarrow$ Nβα Tiun derivitan regulon oni obtenas, kiam oni substituas en la regulo 1 la komencan neterminalon X kun dekstra parto de la regulo Nβ. La derivita regulo estas rekte maldekstre rekursia.

Grava regulo por transformado de gramatiko estas maldekstra substituo menciita antaŭe. Ĝin ilustras sekvanta ekzemplo. Ni havu du regulojn de gramatiko

. N $\rightarrow$ aσ₁ | Xσ₂ | Xσ₃

. X $\rightarrow$ bσ₄ | Yσ₅

kie N, X kaj Y estas neterminaloj, a, b estas terminaloj kaj σ_I estas ajnaj sekvencoj de terminaloj kaj/aŭ neterminaloj. Tiam la maldekstra substitucio de neterminalo X en la regulo 1 estas la regulo

N $\rightarrow$ a σ₁ | bσ₄ σ₂ | Yσ₅σ₂ | bσ₄σ₃ | Yσ₅σ₃

Ĝenerale oni havu maldekstre rekursivan neterminalon N kaj estu ĉiuj reguloj por N kolektitaj en unu regulo kun alternativoj separitaj per simbolo |:

N $\rightarrow$ σ ₁ | σ₂ | … | σ_n

La unua paŝo estas apliko de maldekstraj substituoj por elimini maldekstrajn rekursivajn maŝojn. Rezulte oni obtenos la regulon R

N $\rightarrow$ Nα₁ | Nα₂ | … | Nα_k | β₁ | β₂ | … | β_m,

kie la alternativoj β₁,..., β_m ne komencas kun N.

Rimarku, ke m≥1, alie inferenco de N neniam finiĝos.

La sekvanta algoritmo nomiĝas Algoritmo de Hopkroft kaj Ullmann:

Novaj reguloj R1 kaj R2, kiuj anstataŭigas la regulon R estas

R1: N $\rightarrow$ β₁M | β₂M | … | β_mM | β₁ | β₂ | … | β_m

R2: M $\rightarrow$ α₁M | α₂M | ... | α_kM | α₁ | α₂ | ... | α_k

Ĉi tie M estas nova neterminalo, kiun ne enhavas la origina gramatiko.

Se tiun ĉi proceduron oni plenumas por ĉiu maldekstre rekursiva neterminalo, la gramatiko fariĝas ne-maldekstre-rekursiva (verŝajne dekstre rekursiva). Eblas transformi ĉiun maldekstre rekursivan gramatikon en ne rekursivan maldekstre.

En oniaj ekzemploj la gramatiko 1 estas maldekstre rekursiva, en la gramatiko 2 estas maldekstre rekursiva nur regulo por neterminalo Nombro (difinita samtiel, kiel en gramatiko 1) . Oni plenumu la proceduron de Hopkroft-Uhlmann por fragmento de gramatiko, kiu difinas la neterminalon Nombro:

5. Nombro $\rightarrow \!\,$ Cifero (nombro estas cifero) 6. Nombro $\rightarrow \!\,$ Nombro Cifero (nombro estas nombro kaj cifero)

Oni vidas, ke ekzistas nur rekta rekursio, sen rekursivaj maŝoj. Do unua paŝo (transformado en rektan rekursion per maldekstra substituo) ne estas necesa.

α₁ = Cifero, β₁ = Cifero

Laŭ algoritmo la novaj reguloj estas: R1: Nombro $\rightarrow$ Cifero M | Cifero

R2: M $\rightarrow$ Cifero M | Cifero,

kie M estas nova neterminalo. Hazarde la dekstraj partoj de du reguloj egalas. Tiam oni povas transformi la unuan regulon:

R1: Nombro $\rightarrow$ M

Nombro ne havas aliajn regulojn, do Nombro ne estas plu necesa por la gramatiko. Ni povas nun forigi la regulon R1 kaj substitui ĉie Nombro kun M. Fine estas oportune renomigi M en Nombro kaj R2 en R1. Do la fina rezulto estas

R1: Nombro $\rightarrow$ Cifero Nombro | Cifero

Oni sukcesis tiel simpligi la fragmenton, tiel ke en la unua alternativo de la nova regulo nur estas interŝanĝitaj la neterminaloj Cifero kaj Nombro.

Notoj

↑ Chomsky, Noam (1956). “Three Models for the Description of Language”, IRE Transactions on Information Theory 2 (2), p. 113–123. doi:10.1109/TIT.1956.1056813.

Vidu ankaŭ

Sintaksa analizo

Fontoj

[1] Chomsky, Noam (1956). “Three Models for the Description of Language”, IRE Transactions on Information Theory 2 (2), p. 113–123. doi:10.1109/TIT.1956.1056813.

[1]