ID/LP grammatik

ID/LP-grammatik är en delmängd av frasstrukturgrammatik , som skiljer sig från andra formella grammatiker genom att skilja mellan omedelbar dominans (ID) och linjär precedens (LP). Medan traditionella frasstrukturregler införlivar dominans och företräde i en enda regel, upprätthåller ID/LP Grammars separata regeluppsättningar som inte behöver bearbetas samtidigt. ID/LP-grammatik används i beräkningslingvistik .

Till exempel, en typisk frasstrukturregel som ${\ce {S -> NP \; VP}}$ , vilket indikerar att en S-nod dominerar en NP-nod och en VP-nod, och att NP föregår VP i ytsträngen. I ID/LP Grammars skulle denna regel endast indikera dominans, och ett linjärt prioritetsuttalande, såsom $NP\prec VP$ , skulle också ges.

Idén kom först fram som en del av generaliserad frasstrukturgrammatik ; ID/LP Grammatik-metoden används också i huvuddriven frasstrukturgrammatik, lexikal funktionell grammatik och andra enande grammatik.

Pågående arbete i Minimalistiska programmet försöker också skilja mellan dominans och ordning. Till exempel har nya artiklar av Noam Chomsky föreslagit att även om hierarkisk struktur är resultatet av den syntaktiska strukturbyggande operationen Merge , bestäms linjär ordning inte av denna operation, utan är helt enkelt resultatet av externisering (oralt uttal, eller, i fallet med teckenspråk, manuell signering).

Definiera dominans och företräde

Omedelbar dominans

Omedelbar dominans är det asymmetriska förhållandet mellan modernoden till ett analysträd och dess döttrar, där modernoden (till vänster om pilen) sägs omedelbart dominera dotternoderna (de till höger om pilen), men döttrar dominerar inte omedelbart modern. Dotternoderna domineras också av vilken nod som helst som omedelbart dominerar modernoden, men detta är inte en omedelbar dominansrelation.

Till exempel visar den kontextfria regeln $A\rightarrow B\ C\ D$ , att noden märkt A (modernod) omedelbart dominerar noder märkta B, C och D, (dotternoder) och noder märkta B, C och D kan omedelbart domineras av en nod märkt A.

Noden märkt A dominerar omedelbart noderna B, C och D, och noden märkt B dominerar omedelbart C' och D'. A dominerar också C' och D', men inte omedelbart

Linjär prioritet

Linjär prioritet är ordningsförhållandet för systernoder. LP-begränsningar anger i vilken ordning systernoder under samma mamma kan visas. Noder som dyker upp tidigare i strängar föregår sina systrar. LP kan visas i frasstrukturregler i formen $A\rightarrow B\ C\ D$ betyder att B föregår C föregår D, som visas i trädet nedan.

En regel som har ID-begränsningar men inte LP skrivs med kommatecken mellan dotternoderna, till exempel $A\rightarrow B,\ C,\ D$ . Eftersom det inte finns någon fast ordning för dotternoderna är det möjligt att alla tre träden som visas här genereras av denna regel.

Alternativt kan dessa samband uttryckas genom linjära prioritetssatser, såsom ${\displaystyle B\prec C} ,$ för att betyda att när som helst B och C är systrar, måste B gå före C.

Transitivitetsprincipen kan tillämpas på LP-relationer vilket innebär att om $B\prec C$ och $C\prec D$ , då $\displaystyle B\prec D}$ { också. LP-relationer är asymmetriska: om B föregår C, kan C aldrig föregå B. En LP-relation där det inte kan finnas några mellanliggande noder kallas omedelbar företräde, medan en LP där det kan finnas mellanliggande noder (de som härrör från transitivitetsprincipen) är sägs ha svag företräde.

Grammatik i ID/LP-grammatik

För att en sträng ska vara grammatisk i en ID/LP-grammatik måste den tillhöra ett lokalt underträd som följer minst en ID-regel och alla LP-satser i grammatiken. Om alla möjliga strängar som genereras av grammatiken uppfyller detta kriterium, är det en ID/LP-grammatik. Dessutom, för att en grammatik ska kunna skrivas i ID/LP-format, måste den ha egenskapen Exhaustive Constant Partial Ordering (ECPO): nämligen att åtminstone en del av ID/LP-relationerna i en regel observeras i alla andra regler. Till exempel regeluppsättningen:

(1) $A\rightarrow B\ C\ D$

(2) $B\rightarrow D\ C\ A$

har inte ECPO-egenskapen, eftersom (1) säger att C alltid måste föregå D, medan (2) säger att D alltid måste föregå C.

Fördelar med ID/LP Grammars

Eftersom LP-satser gäller oavsett ID-regelkontext, tillåter de oss att göra generaliseringar över hela grammatiken. Till exempel, givet LP-satsen ${\displaystyle V\prec DP} ,$ där V är huvudet på en VP, betyder detta att i vilken sats i vilken mening som helst kommer V alltid att dyka upp framför sin DP-syster i alla sammanhang , som framgår av följande exempel.

Lucy vann loppet.

Ava sa åt Sara att läsa en bok.

Detta kan generaliseras till en regel som gäller över engelska, ${\displaystyle X\prec YP} ,$ där X är huvudet på en fras och YP är dess komplement . Non-ID/LP Grammars kan inte göra sådana generaliseringar över hela grammatiken, och måste därför upprepa ordningsbegränsningar för varje enskilt sammanhang.

Att skilja LP-krav från ID-regler förklarar också fenomenen fri ordföljd i naturligt språk. Till exempel på engelska är det möjligt att sätta adverb före eller efter ett verb och att båda strängarna ska vara grammatiska.

John skrek plötsligt . John skrek plötsligt .

En traditionell PS-regel skulle kräva två separata regler, men detta kan beskrivas av den enda ID/LP-regeln $VP\rightarrow V,AdvP$ . Denna egenskap hos ID/LP Grammars möjliggör enklare tvärspråkliga generaliseringar genom att beskriva de språkspecifika skillnaderna i konstituerande ordning med LP-satser, separat från ID-reglerna som är likartade mellan olika språk.

Analysera i ID/LP-grammatik

Två parsningsalgoritmer som används för att analysera ID/LP-grammatiker är Earley Parser och Shiebers algoritm.

Earley Parser i ID/LP Grammars

ID- och LP-regler sätter begränsningar på meningssträngar; när man hanterar stora strängar kan dessa reglers begränsningar göra att den analyserade strängen blir oändlig, vilket gör det svårt att analysera. Earley Parser löser detta genom att ändra formatet för en ID/LP Grammar till en Context Free Grammar (CFG), dela upp ID/LP Grammar i en Ordnad Context Free Grammar (CFG) och Unordered Context Free Grammar (UCFG). Detta gör att de två algoritmerna kan analysera strängar mer effektivt; i synnerhet använder Earley Parser en punktspårningsmetod som följer en linjär bana som fastställts av LP-reglerna. I en CFG tillåter inte LP-regler upprepade beståndsdelar i den tolkade strängen, men en UCFG tillåter upprepade beståndsdelar inom de tolkade strängarna. Om ID/LP-grammatiken konverteras till en UCFG så dominerar inte LP-reglerna under tolkningsprocessen, men den följer fortfarande punktspårningsmetoden.

Earley Parsing i CFG

Efter att ID/LP Grammar har konverterats till motsvarande form inom en CFG kommer algoritmen att analysera strängen. Låt $\mathrm {X}$ stå för start och $\alpha ,\beta ,\iota$ står för elementen i strängen och det representerar också Syntaktiska kategorier . Algoritmen analyserar sedan strängen och identifierar följande:

Punktens ursprungliga position; det börjar vanligtvis med elementet längst till vänster i strängen.
Punktens nuvarande position; detta förutsäger följande element.
Tillverkningen av den färdiga strängen.

(1) $\mathrm {X} \longrightarrow \cdot \alpha \beta \iota$

(2) $\mathrm {X} \longrightarrow \alpha \cdot \beta \iota$ ( $\beta$ förutsägs)

(3) $\mathrm {X} \longrightarrow \alpha \beta \iota \cdot$

De analyserade strängarna används sedan tillsammans för att bilda en analyslista, till exempel:

$\mathrm {I} _{0}\ldots \mathrm {I} _{n}$

vilken listan hjälper till att avgöra om det färdiga produktionselementet ( ${\displaystyle \mathrm {X} \longrightarrow \alpha \beta \iota } )$ accepteras inom huvudsträngen. Den gör detta genom att se om de producerade individuella strängarna finns i Parse List. Om en eller alla individuella strängar inte hittas i Parse List, kommer den övergripande strängen att misslyckas. Om en eller alla individuella strängar finns i Parse List, kommer den övergripande strängen att accepteras.

Earley Parsing i UCFG

UCFG är den lämpliga motsvarigheten att konvertera ID/LP-grammatik till för att kunna använda Earley Parser. Denna algoritm läser strängar på samma sätt som hur den analyserar CFG, men i det här fallet upprätthålls inte ordningen på elementen; vilket resulterar i bristande efterlevnad av LP-regeln. Detta gör att vissa element kan upprepas inom de analyserade strängarna och UCFG accepterar tomma multiuppsättningar tillsammans med fyllda multiuppsättningar inom sina strängar. Till exempel:

Ursprungspositionen för punkten; det är mellan den tomma uppsättningen och den fyllda uppsättningen.
Den aktuella positionen för punkten som förutsäger följande uppsättning; elementet som punkten passerade kommer att flytta in i den tomma uppsättningen.
Tillverkningen av den färdiga strängen. I detta fall kommer positionen för de två uppsättningarna i ursprungspositionen att byta; den fyllda uppsättningen är på vänster kant och den tomma uppsättningen är på höger kant.

(1) $\mathrm {X} \longrightarrow \{\}\cdot \{\alpha ,\beta ,\iota \}$

(2) ${\displaystyle \mathrm {X} \longrightarrow \{\alpha \}\cdot \{\beta ,\iota \}} ($ { $\ displaystyle \{\beta ,\iota \}}$ förutsägs)

(3) $\mathrm {X} \longrightarrow \{\alpha ,\beta ,\iota \}\cdot \{\}$

När man analyserar en sträng som innehåller ett antal oordnade element, behandlar Earley Parser den som en Permutation , Y!, och genererar varje sträng individuellt istället för att använda en sträng för att representera de upprepade analyserade strängarna. Närhelst punkten rör sig över ett element, börjar algoritmen att generera analyserade strängar av elementen på högerkanten i slumpmässiga positioner tills det inte finns fler element i högerkantuppsättningen. Låt X ₀ representera den ursprungliga strängen och X ₁ som den första analyserade strängen; till exempel:

$\mathrm {X} _{0}:[\mathrm {X} \longrightarrow \{\}\cdot \{t, v,w,z\},0]$

$\mathrm {X} _{1}:[\mathrm {X} \longrightarrow \{t\}\cdot \{v ,w,z\},0]$

sträng X ₁ kommer att producera, 3! = 6, olika analyserade strängar i högerkantuppsättningen:

(1) $[\mathrm {X} \longrightarrow t.vwz,0]$ (4) $[\mathrm {X} \longrightarrow t.zvw,0]$

(2) $[\mathrm {X} \longrightarrow t.vzw,0]$ (5) $[\mathrm {X} \longrightarrow t.wvz,0]$

(3) $[\mathrm {X} \longrightarrow t.zwv,0]$ (6) $[\mathrm {X} \longrightarrow t.wzv,0]$

Earley Parser tillämpar varje sträng på de individuella reglerna i en grammatik och detta resulterar i mycket stora uppsättningar. De stora uppsättningarna resulterar delvis i konverteringen av ID/LP Grammar till en likvärdig grammatik, men att analysera den övergripande ID/LP grammatiken är svårt att börja med.

Shiebers algoritm

Grunden för Shiebers algoritm är baserad på Earley Parser för CFG, men det kräver inte att ID/LP-grammatiken konverteras till en annan grammatik för att kunna analyseras. ID-regler kan analyseras i en separat form, S → _ID {V, NP, S}, från LP-reglerna, V < S. Shieber jämförde analys av en CFG med en ordnad ID/LP Grammatiksträng och Barton jämförde analysen av en UCFG till en oordnad ID/LP Grammar-sträng.

Direkt analys av en beställd ID/LP-grammatik

Att analysera en ID/LP-grammatik direkt genererar en uppsättningslista som avgör om produktionen av strängen kommer att accepteras eller misslyckas. Algoritmen följer 6 steg (symbolerna som används kan också representera de syntaktiska kategorierna):

För alla ID-regler, lägg till $[S,\mathrm {T} ,\beta ,0]$ till den initiala posten i analyslistan, $\mathrm { I} _{0}$ .
Om alla element i $\mathrm {I} _{0}$ , $[\mathrm {Z} ,\lambda ,\theta ,0]$ och elementen, ${\displaystyle [\mathrm {A} ,\alpha ,\{Z\}\cup \beta ,0]} ,$ av $\mathrm { I} _{0}$ tillåter inte att Z föregås av $\beta$ , $Z\nprec \beta$ , och Z är inte ett element i $\beta$ , $Z\not \in \beta$ ; sedan kan följande sträng, $[\mathrm {A} ,\alpha Z,\beta ,0]$ läggas till $\mathrm {I} _{0 }$ .
Om alla objekt, ${\displaystyle [\mathrm {A} ,\alpha ,\{Z\}\cup \beta ,0]} , är$ element i $\mathrm {I} _{0}$ , sedan $Z\nprec \beta$ , och $Z\not \in \beta$ och hela ${\ displaystyle Z\longrightarrow _{\mathrm {ID} }\lambda }$ så kan nästa objekt läggas till i denna lista, $[Z,T,\lambda ,0]$ .
Detta steg kommer att bygga upp setlistan, ${\displaystyle \mathrm {I} _{n}},$ mer. Varje objekt, ${\displaystyle [A,\alpha ,\{q\}\cup \beta ,i]} ,$ som är ett element av ${\ displaystyle \mathrm {I} _{n-1}}$ och där $q=q_{n}$ , $q\nprec \beta$ och $q \not \in \beta$ så läggs följande objekt till, $[A,\alpha q,\beta ,i]$ , till $\mathrm { I} _{n}$ .
Om objekt, $[Z,\lambda ,\theta ,i]$ , är element av $\mathrm {I} _{n}$ och objekt, $[A,\alpha \{Z\}\cup \beta ,k]$ , är element i $\mathrm {I} _{i}$ där $Z\nprec \beta$ , och $Z\not \in \beta$ ; strängen, $[A,\alpha Z,\beta ,k]$ , läggs till $\mathrm {I} _{n}$ .
Om objekten, $[A,\alpha ,\{Z\}\cup \beta ,i]$ , är ett element i $\ mathrm {I} _{n}$ där $Z\nprec \beta$ , och $Z\not \in \beta$ ; strängen, $[Z,T,\lambda ,n]$ , läggs till $\mathrm {I} _{n}$ .

Steg 2-3 upprepas uttömmande tills inga fler nya objekt kan läggas till och fortsätt sedan till steg 4. Steg 5-6 upprepas också uttömmande tills inga fler nya objekt kan läggas till i setlistan. Strängen kommer att accepteras om en sträng beter sig eller liknar produktionen, $[S,\alpha ,\theta ,0]$ är ett element i $\mathrm {I } _{n}$ . Till exempel:

S\longrightarrow _{\mathrm {ID} }\{C,D,F\}

C\longrightarrow _{ \mathrm {ID} }\{c\}

D\longrightarrow _{\mathrm {ID} }\{d\}

F \longrightarrow _{\mathrm {ID} }\{f\}

C\prec D

Tabell 1.0
Ställ in listor	Föremål
$\mathrm {I} _{0}$	$[S,T,\{C,D,F\},0],$ $[C,T,\{c\},0],$ $[F,T,\{f \},0]$
$\mathrm {I} _{1}$	$[C,c,\emptyset ,0],$ $[S,C,\{D,F\},0],$ $[D ,T,\{d\},1],$ $[F,T,\{f\},1]$
$\mathrm {I} _{2}$	$[F,f,\emptyset ,1],$ $[S,CF,\{D\},0],$ $[D,T,\ {d\},2]$
$\mathrm {I} _{3}$	$[D,d,\emptyset ,2],$ $[S,CDF,\emptyset ,0]$

Den fullständiga produktionen av $\mathrm {I} _{3},$ $[S,CDF,\emptyset ,0],$ accepteras och producerar följande produktionssträng: $[_{S}[_{C}c][_{D}d][_{F}f] ]$ .

Direkt analys av en oordnad ID/LP-grammatik

Oordnad ID/LP-grammatik följer ovanstående, 6-stegsalgoritm, för att analysera strängarna. Den märkbara skillnaden ligger i produktionerna av varje setlista; det finns en sträng som representerar de många enskilda strängarna i en lista. Tabellen nedan visar uppsättningslistan för Tabell 1.0, $[S,T,\{C,D,F\},0],$ i en oordnad grammatik:

Tabell 2.0
Låtlista	Föremål
$\mathrm {I} _{0}$	$[S,T,C\cdot d,f,\emptyset ,0]$
$\mathrm {I} _{1}$	$[S,T\cdot c,d,f,\emptyset ,0]$
$\mathrm {I} _{2}$	$[S,T,C,d\cdot F,\emptyset ,0]$
$\mathrm {I} _{3}$	$[S,T,C,D,F\cdot \emptyset ,0]$

Den kompletta produktionssträngen, $[S,T,C,D,F\cdot \emptyset ,0],$ resulterar i en liknande sträng som den beställda ID/LP Grammatik; Men ordningen på objekten i strängen upprätthålls inte. Den sista strängen accepteras eftersom den matchar originalsträngens element.

Lägg märke till hur den oordnade versionen av ID/LP Grammar innehåller mindre strängar än UCFG; Shiebers algoritm använder en sträng för att representera flera olika strängar för upprepade element. Båda algoritmerna kan analysera beställda grammatiker lika, men Shiebers algoritm verkar vara mer effektiv när man analyserar en oordnad grammatik.

Se även