DCG nyelvtanok, használatuk elemzésre
Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.
Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.
Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót
- fejezetek: 4.12.1, 4.12.2
A DCG elemzés
Bináris számok nyelvtana:
<szám> ::= <jegy> <számmaradék> <számmaradék> ::= <jegy> <számmaradék> | ε <számjegy> ::= 0 | 1
Ugyanez Prolog DCG szintaxissal (nem szabványos, de a legtöbb Prolog rendszer támogatja)
szám --> számjegy, számmaradék. számmaradék --> számjegy, számmaradék | "". számjegy --> "0" | "1".
A paraméter nélküli nemterminálisoknak egy kétargumentumú Prolog eljárás felel meg.
Az eljárás első argumentuma egy karakterkód lista lesz, és azt várjuk tőle, hogy sikerüljön, ha ennek a listának egy kezdőszelete kielemezhető az adott nemterminálisnak megfelelő szabályok szerint; egyébként hiúsuljon meg.
Siker esetén elvárjuk, hogy a második argumentumban adja vissza a bemenő listának a kielemzett kódsorozat elhagyásával keletkező zárószeletét. Ekkor úgy mondjuk, hogy a bemenő listáról leemelhető az adott nemterminális és marad a kimenő lista.
szám(L0, L) :- jegy(L0, L1), számmaradék(L1, L). számmaradék(L0, L) :- ( jegy(L0, L1), számmaradék(L1, L) ; L=L0 ). számjegy(L0, L) :- ( 'C'(L0, 48, L) ; 'C'(L0, 49, L) ).
Az akkumulátorpárok láncolását rábízzuk a Prolog fordítóprogramra. A definit klóz nyelvtani szabályokat a Prolog rendszer a program beolvasása során Prolog szabályokká alakítja. A 'C' eljárás az alapértelmezett akkumulálási lépést végzi. 'C'(L0, Char, L) jelentése: =L0=[Char|L]=.
A DCG elemző futtatása:
| ?- szám("101", "").
yes
| ?- szám("102", L).
L = [50] ; % "2"
L = [48, 50] ; % "02"
no
DCG használata listák akkumulálására
DCG nyelvtannal hagyományos Prolog eljárások is leírhatók. A lefordított program nem csak elemzésre, hanem lista generálására is használható. Az elemi akkumulálási lépést a 'C'/3 adja. Például:
% anbn(N, L1, L2): L1-L2 N db a, majd N db b elemből áll.
anbn(0) --> !.
anbn(N) --> {N>0, N1 is N-1}, [a], anbn(N1), [b].
A második DCG szabály kifejtve:
anbn(N, L0, L) :- N>0, N1 is N-1, L0=[a|L1], anbn(N1, L1, L2), L2=[b|L].
DCG nyelvtani szabályok szerkezete, összefoglalás
- *nemterminális*: tetszőleges hívható kifejezés (atom vagy struktúra).
- *terminális*: tetszőleges Prolog kifejezés; a 0, 1 vagy több terminális sorozata
listaként helyezhető el a DCG szabályokban. Az üres terminálist ""-gel vagy []-val jelölik. A string karakterkódok listájára fordul.
- *feltételek*: tetszőleges Prolog hívás elhelyezhető {} zárójelekbe zárva. A vágót nem kell zárójelbe tenni.
- *A DCG szabály alakja*: baloldal --> jobboldal.
- *baloldal*: egy nemterminális, amit opcionálisan terminálisok listája követhet.
- *jobboldal*:
- konjunkció (egymás után írás) (,)
- diszjunkció (;) vagy (|)
- ha-akkor és ha-akkor-egyébként (->) és
- negáció (\+)
