Adaptiv grammatik

En adaptiv grammatik är en formell grammatik som uttryckligen tillhandahåller mekanismer inom formalismen för att tillåta att dess egna produktionsregler manipuleras.

Översikt

John N. Shutt definierar adaptiv grammatik som en grammatisk formalism som tillåter att regeluppsättningar (aka uppsättningar av produktionsregler) explicit manipuleras inom en grammatik. Typer av manipulation inkluderar regeltillägg, radering och modifiering.

Tidig historia

Den första beskrivningen av grammatisk adaptivitet (men inte under det namnet) i litteraturen anses allmänt vara i en artikel av Alfonso Caracciolo di Forino publicerad 1963. Nästa allmänt accepterade referens till en adaptiv formalism (extensible context-free grammatics ) kom från Wegbreit 1970 i studiet av utbyggbara programmeringsspråk , följt av den dynamiska syntaxen från Hanford och Jones 1973.

Samarbetsinsatser

Fram till ganska nyligen var mycket av forskningen om de formella egenskaperna hos adaptiv grammatik okoordinerad mellan forskare, och sammanfattades först av Henning Christiansen 1990 som svar på en artikel i ACM SIGPLAN Notices av Boris Burshteyn. Institutionen för teknik vid universitetet i São Paulo har sitt laboratorium för adaptiva språk och tekniker, som specifikt fokuserar på forskning och praktik inom adaptiv teknologi och teori. LTA har också en sida som namnger forskare inom området.

Terminologi och taxonomi

Medan tidiga ansträngningar hänvisade till dynamisk syntax och utvidgbara , modifierbara , dynamiska och anpassningsbara grammatiker, har senare användning tenderat mot användningen av termen adaptiv (eller någon variant som adaptativa , beroende på litteraturens publikationsspråk). Iwai hänvisar till hennes formalism som adaptiv grammatik , men denna specifika användning av helt enkelt adaptiva grammatiker används för närvarande inte i litteraturen utan namnkvalifikation. Dessutom har inga standardiserings- eller kategoriseringsinsatser genomförts mellan olika forskare, även om flera har gjort ansträngningar i denna riktning.

Shutt-klassificeringen (och tilläggen)

Shutt kategoriserar adaptiva grammatikmodeller i två huvudkategorier:

Imperativa adaptiva grammatiker varierar sina regler baserat på ett globalt tillstånd som förändras under tiden då ett språk skapas .
Deklarativa adaptiva grammatiker varierar sina regler endast över utrymmet för genereringen av ett språk (dvs. position i syntaxträdet för den genererade strängen).

Jackson förfinar Shutts taxonomi, hänvisar till förändringar över tid som globala och förändringar över rymden som lokala , och lägger till en hybrid tid-rymdkategori :

Tid-rymd adaptiva grammatiker ( hybrider ) varierar sina regler över antingen tiden eller utrymmet (eller båda) för genereringen av ett språk (och lokala och globala operationer särskiljs uttryckligen av notationen för sådana förändringar).

Adaptiva formalismer i litteraturen

Adaptiva formalismer kan delas in i två huvudkategorier: full grammatikformalismer (adaptiv grammatik) och adaptiva maskiner, på vilka vissa grammatikformalismer har baserats.

Adaptiva grammatikformalismer

Följande är en lista (på intet sätt fullständig) över grammatikformalismer som, enligt Shutts definition ovan, anses vara (eller har klassificerats av sina egna uppfinnare som varande) adaptiva grammatiker. De är listade i sin historiska ordning efter första omnämnande i litteraturen.

Utökningsbara sammanhangsfria grammatiker (Wegbreit)

Beskriven i Wegbreits doktorsavhandling 1970, består en utvidgbar kontextfri grammatik av en kontextfri grammatik vars regeluppsättning modifieras enligt instruktioner som matas ut av en finita tillståndsgivare vid läsning av terminalprefixet under en härledning längst till vänster. Således varierar regeluppsättningen över position i den genererade strängen, men denna variation ignorerar den hierarkiska strukturen i syntaxträdet. Utvidgbara sammanhangsfria grammatiker klassificerades av Shutt som imperativa .

Christiansen grammatik (Christiansen)

Först introducerades 1985 som generativ grammatik och senare mer utarbetad, Christiansen grammatik (uppenbarligen dubbad så av Shutt, möjligen på grund av konflikt med Chomsky generativ grammatik) är en adaptiv förlängning av attribut grammatik . Christiansens grammatiker klassificerades av Shutt som deklarativa .

Fördubblingsspråket $L=\{ww|w{\mbox{ är en bokstav}}\}$ visas på följande sätt:

 <program↓  G  > → <dcl↓  G  ↑  w  > <body↓{  w-rule  }>

 där  w-rule  = <body↓  G  '> →  w

 <dcl↓  G  ↑  ch  •  w  > → <char↓  G  ↑  ch  > <dcl↓  G  ↑  w  > <dcl↓G↑<>> → <ε> <char↓G↑a> → a

Nedifrån och upp modifierbara grammatiker, top-down modifierbara grammatiker och USSA (Burshteyn)

Först introducerades i maj 1990 och senare utökades i december 1990, modifierbara grammatiker ger uttryckligen en mekanism för tillägg och radering av regler under en analys. Som svar på ACM SIGPLAN Notices svar modifierade Burshteyn senare sin formalism och introducerade sin adaptiva Universal Syntax and Semantics Analyzer (USSA) 1992. Dessa formalismer klassificerades av Shutt som imperativa .

Rekursiva adaptiva grammatiker (Shutt)

Rekursiva adaptiva grammatiker (RAGs) introducerades 1993 och var ett försök att introducera en kraftfull Turing- formalism som bibehöll mycket av elegansen hos kontextfria grammatiker . Shutt självklassificerar RAG som en deklarativ formalism.

Dynamisk grammatik (Boullier)

Boulliers dynamiska grammatiker , som introducerades 1994, verkar vara den första adaptiva grammatikfamiljen av grammatiker som rigoröst introducerade begreppet tidskontinuum av en analys som en del av notationen av själva grammatikformalismens. Dynamiska grammatiker är en sekvens av grammatiker, där varje grammatik G _i skiljer sig på något sätt från andra grammatiker i sekvensen, över tiden. Boulliers huvudartikel om dynamisk grammatik definierar också en dynamisk parser, maskinen som utför en analys mot dessa grammatiker, och visar exempel på hur hans formalism kan hantera sådant som typkontroll , utvidgbara språk , polymorfism och andra konstruktioner som vanligtvis anses vara i programmeringsspråksöversättningens semantiska domän.

Adaptiv grammatik (Iwai)

Iwais arbete år 2000 tar den adaptiva automaten i Neto vidare genom att tillämpa adaptiva automater på sammanhangskänsliga grammatiker . Iwais adaptiva grammatik (notera kvalet vid namn) tillåter tre operationer under en analys: ? fråga (liknar i vissa avseenden ett syntaktisk predikat , men kopplat till inspektion av regler från vilka ändringar väljs), + tillägg och - radering (som den delar med sin föregångare adaptiva automater).

§-kalkyl (Jackson)

Introducerad 2000 och mest fullständigt diskuterad 2006, §-Calculus (§ här uttalas meta-ess ) tillåter explicit tillägg, radering och modifiering av produktioner inom en grammatik, samt tillhandahåller syntaktiska predikat . Denna formalism är självklassificerad av sin skapare som både imperativ och adaptiv , eller, mer specifikt, som en tids-rum adaptiv grammatikformalism, och klassificerades ytterligare av andra som en analytisk formalism.

Fördubblingsspråket $L=\{ww|w\in \{a,b\}^{+}\}$ visas enligt följande:

grammatik ww { S ::= #phi(AX<-"") R; R ::= $C('[ab]') #phi(AX<-AX C) #phi(N<=AX) N | R; };

(Anmärkning om notation: I exemplet ovan identifierar #phi(...) -satserna punkterna i produktionen R som modifierar grammatiken explicit. #phi(AX<-AX C) representerar en global modifiering (över tid) och #phi (N<=AX) -satsen identifierar en lokal modifiering (över rymden). #phi(AX<-"")- satsen i S -produktionen deklarerar effektivt en global produktion som kallas AX genom att placera den tomma strängen i den produktionen före dess referens av R .)

Adaptiva enheter (Neto & Pistori)

Först beskrevs av Neto 2001, adaptiva enheter förbättrades och utökades senare av Pistori 2003.

Adapter (Carmi)

2002 introducerade Adam Carmi en LALR(1) -baserad adaptiv grammatikformalism känd som Adapser . Detaljerna om formalismen verkar inte ha släppts.

Adaptiva CFG:er med utseendekontroll (Bravo)

2004 introducerade César Bravo idén om att slå samman konceptet med utseendekontroll med adaptiva sammanhangsfria grammatiker , en begränsad form av Iwais adaptiva grammatik, som visar dessa nya grammatiker, kallade Adaptive CFGs with Appearance Checking för att vara Turing-kraftiga .

Adaptiva maskinformalismer

Formalismer som listas nedan, även om de inte grammatikformalismer, antingen tjänar som grunden för fullständiga grammatikformalismer, eller ingår här eftersom de är adaptiva till sin natur. De är listade i sin historiska ordning efter första omnämnande i litteraturen.

Självmodifierande finita tillståndsautomater (Shutt & Rubinstein): Introducerades 1994 av Shutt och Rubinstein, och självmodifierande finita tillståndsautomater (SMFAs) har visat sig vara, i begränsad form, Turing kraftfulla .

Adaptive automata (Neto): 1994 introducerade Neto den maskin som han kallade en strukturerad pushdown-automat , kärnan i adaptiv automatateorin som eftersträvas av Iwai, Pistori, Bravo och andra. Denna formalism tillåter inspektioner ( liknande syntaktiska predikat , som noterats ovan angående Iwais adaptiva grammatik), tillägg och radering av regler.

Se även