Van Wijngaardens grammatik

Inom datavetenskap är Van Wijngaardens grammatiker (även vW-grammatiker eller W-grammars ) en formalism för att definiera formella språk som uppfanns av Adriaan van Wijngaarden i syfte att definiera programmeringsspråket ALGOL 68 . Den resulterande specifikationen förblir dess mest anmärkningsvärda tillämpning.

W-grammatik är två-nivå grammatik : de definieras av ett par grammatiker, som fungerar på olika nivåer:

hypergrammatiken är en attribut grammatik , dvs en uppsättning kontextfria grammatikregler där de icke-terminala kan ha attribut ; och
metagrammatiken är en kontextfri grammatik som definierar möjliga värden för dessa attribut .

Uppsättningen strängar som genereras av en W-grammatik definieras av en tvåstegsprocess:

inom varje hyperregel, för varje attribut som förekommer i den, välj ett värde för det som genereras av metagrammatiken; resultatet är en normal kontextfri grammatikregel; gör detta på alla möjliga sätt;
använd den resulterande (möjligen oändliga) kontextfria grammatiken för att generera strängar på normalt sätt.

Den konsekventa substitutionen som används i det första steget är densamma som substitution i predikatlogik , och stöder faktiskt logikprogrammering ; det motsvarar enande i Prolog , som noterats av Alain Colmerauer ^{[ var? ]} .

W-grammatik är Turing komplett ; därav alla beslutsproblem angående de språk de genererar, som t.ex

om en W-grammatik genererar en given sträng
om en W-grammatik inte genererar några strängar alls

är obestämbara .

Begränsade varianter, kända som affix grammatiker , utvecklades och tillämpades i kompilatorkonstruktion och för beskrivning av naturliga språk.

En annan förkortad version av W-grammars är Prolog , det logiska programmeringsspråket . ^{[ citat behövs ]}

Motivation och historia

På 1950-talet började försök att använda datorer för att känna igen, tolka och översätta naturliga språk, som engelska och ryska. Detta kräver en maskinläsbar beskrivning av frasstrukturen för meningar, som kan användas för att analysera och tolka dem och för att generera dem. Kontextfria grammatiker, ett begrepp från strukturell lingvistik , antogs för detta ändamål; deras regler kan uttrycka hur meningar är rekursivt uppbyggda av delar av tal , såsom substantivfraser och verbfraser , och i slutändan ord, såsom substantiv , verb och pronomen .

Detta arbete påverkade designen och implementeringen av programmeringsspråk , framför allt av ALGOL 60 , som introducerade en syntaxbeskrivning i Backus-Naur-form .

Kontextfria regler kan dock inte uttrycka överenskommelse eller referens ( anaphora ), där två olika delar av meningen måste överensstämma med varandra på något sätt.

Dessa kan lätt uttryckas i W-grammatik. (Se exempel nedan.)

Programmeringsspråk har de analoga begreppen typning och scoping . En kompilator eller tolk för språket måste känna igen vilka användningar av en variabel som hör ihop (se samma variabel). Detta är vanligtvis föremål för begränsningar som:

En variabel måste initieras innan dess värde används.
I starkt skrivna språk tilldelas varje variabel en typ, och all användning av variabeln måste respektera dess typ.
Ofta måste dess typ deklareras uttryckligen före användning.

W-grammatiker är baserade på idén att förse de icke-terminala symbolerna för kontextfria grammatiker med attribut (eller affix ) som skickar information mellan noderna i analysträdet, som används för att begränsa syntaxen och för att specificera semantiken.

Denna idé var välkänd på den tiden; Donald Knuth besökte t.ex. ALGOL 68 designkommittén medan han utvecklade sin egen version av den, attribut grammatik .

Genom att utöka syntaxbeskrivningen med attribut kan begränsningar som ovan kontrolleras, vilket utesluter många ogiltiga program vid kompilering. Som Van Wijngaarden skrev i sitt förord:

Mina huvudsakliga invändningar var vissa för mig onödiga begränsningar och definitionen av syntax och semantik. Egentligen producerar syntaxen som visas i MR 75 ett stort antal program, medan jag skulle föredra att ha delmängden meningsfulla program så stor som möjligt, vilket kräver en striktare syntax. [...] det stod snart klart att några bättre verktyg än Backus-notationen kunde vara fördelaktiga [...]. Jag utvecklade ett schema [...] som gör det möjligt för designen av ett språk att bära mycket mer information i syntaxen än vad som normalt bärs.

Ganska säreget för W-grammatik var deras strikta behandling av attribut som strängar, definierade av en kontextfri grammatik, på vilken sammankoppling är den enda möjliga operationen; komplexa datastrukturer och operationer kan definieras genom mönstermatchning . (Se exempel nedan.)

Efter deras introduktion i 1968 års ALGOL 68 "Slutrapport" ansågs W-grammatik allmänt vara för kraftfull och obunden för att vara praktisk. ^{[ citat behövs ]}

Detta var delvis en följd av det sätt på vilket de hade tillämpats; 1973 års ALGOL 68 "Revised Report" innehåller en mycket mer läsbar grammatik, utan att modifiera själva W-grammatikformalismen.

Samtidigt blev det tydligt att W-grammatik, när de används i sin fulla allmänhet, verkligen är för kraftfulla för sådana praktiska syften som att fungera som indata för en parsergenerator . De beskriver exakt alla rekursivt uppräknade språk , vilket gör parsning omöjlig i allmänhet: det är ett oavgörligt problem att avgöra om en given sträng kan genereras av en given W-grammatik.

Därför måste användningen av dem vara allvarligt begränsad när de används för automatisk analys eller översättning. Begränsade och modifierade varianter av W-grammatik utvecklades för att hantera detta, t.ex

Extended Affix Grammars (EAGs), tillämpade för att beskriva grammatikerna för naturligt språk som engelska och spanska;
Q-system , även tillämpat på naturlig språkbehandling;
CDL - serien av språk, tillämpade som kompilatorkonstruktionsspråk för programmeringsspråk .

Efter 1970-talet avtog intresset för tillvägagångssättet; då och då publiceras nya studier.

Exempel

Överenskommelse i engelsk grammatik

På engelska har substantiv, pronomen och verb attribut som grammatiskt nummer , gender och person , som måste överensstämma mellan subjekt , huvudverb och pronomen som hänvisar till ämnet:

Jag tvättar mig själv.
Hon tvättar sig.
Vi tvättar oss.

är giltiga meningar; ogiltiga är till exempel:

*Jag tvättar oss.
*Hon tvättar sig.
*Vi tvättar sig.

Här tjänar överenskommelsen till att betona att båda pronomenen (t.ex. jag och jag själv ) syftar på samma person.

En kontextfri grammatik för att generera alla sådana meningar:

<sentence><i>::=</i> <b>::=</b><subject><verb><object><subject> <i>::= I |</i> <b>::= jag |</b> <i>You |</i> <b>Du |</b> <i>He |</i> <b>Han |</b> <i>She |</i> <b>Hon |</b> <i>We |</i> <b>Vi |</b> <i>They</i> <b>De</b><verb> <i>::= wash |</i> <b>::= tvätta |</b> <i>washes</i> <b>tvättar</b><object> <i>::= myself |</i> <b>::= jag själv |</b> <i>yourself |</i> <b>dig själv |</b> <i>himself |</i> <b>själv |</b> <i>herself |</i> <b>själv |</b> <i>ourselves |</i> <b>oss själva |</b> <i>yourselves |</i> <b>er själva |</b> <i>themselves</i> <b>sig själva</b>

Från meningen kan vi generera alla kombinationer:

Jag tvättar mig Jag tvättar dig Jag tvättar själv [...] De tvättar er De tvättar sig själva

En W-grammatik för att generera endast de giltiga meningarna:

 <subject singularis <GENDER> 1st> ::= I <subject <NUMBER> <GENDER> 2nd> ::= Du <subject singular mane 3rd> ::= Han <subject singular female 3rd> ::= Hon <subject plural < KÖN> 1:a> ::= Vi <subjekt singular <GENDER> 3:a> ::= De

 <verb singular 1:a> ::= tvätta <verb singular 2:a> ::= tvätta <verb singular 3:a> ::= tvättar <verb plural <PERSON>> ::= tvätta

 <objekt singular <GENDER> 1:a> ::= mig själv <objekt singular <GENDER> 2:a> ::= dig själv <objekt singular hane 3:a> ::= sig själv <objekt singular hona 3:a> :: = sig själv <objekt plural <GENDER> 1:a> ::= oss själva <objekt plural <GENDER> 2:a> ::= er själva <objekt plural <GENDER> 3:a> ::= sig själva

 <NUMMER> ::== singular | plural <GENDER> ::== man |  kvinna <PERSON> ::== 1:a |  2:a |  3:a

Ett standardspråk utan sammanhang

Ett välkänt icke-kontextfritt språk är

\{a^{n}b^{n}a^{n}|n\geq 1\}.

En grammatik på två nivåer för detta språk är metagrammatiken

N ::= 1 | N1

X ::= a | b

tillsammans med grammatikschema

Start ::=

\langle a^{N}\rangle \langle b^{N}\rangle \langle a^{N}\rangle

\langle X^{N1}\rangle

::=

\langle X^{N}\rangle X

\langle X^{1 }\rangle

::= X

Kräver giltig användning av variabler i ALGOL

Den reviderade rapporten om det algoritmiska språket Algol 60 definierar en fullständig kontextfri syntax för språket.

Uppdrag definieras enligt följande (avsnitt 4.2.1):

<left part><i>::=</i> <b>::=</b><variable> <i>:= |</i> <b>:= |</b><procedure identifier> <i>:=</i> <b>:=</b><left part list> <i>::=</i> <b>::=</b><left part> <i>|</i> <b>|</b><left part list><left part><assignment statement> <i>::=</i> <b>::=</b><left part list><arithmetic expression> <i>|</i> <b>|</b><left part list><Boolean expression>

A kan vara (bland annat) en , som i sin tur definieras som:

<identifier><i>::=</i> <b>::=</b><letter> <i>|</i> <b>|</b><identifier><letter> <i>|</i> <b>|</b><identifier><digit>

Exempel (avsnitt 4.2.2):

s:=p[0]:=n:=n+1+s n:=n+1 A:=B/Cvq×S S[v,k+2]:=3-arctan(sTIMESzeta) V:=Q> Y^Z

Uttryck och tilldelningar måste typkontrolleras : t.ex.

i n:=n+1 måste n vara ett tal (heltal eller reellt);
i A:=B/Cvq×S måste alla variabler vara tal;
i V:=Q>Y^Z måste alla variabler vara av typen Boolean.

Reglerna ovan skiljer mellan och , men de kan inte verifiera att samma variabel alltid har samma typ.

Detta (icke-kontextfria) krav kan uttryckas i en W-grammatik genom att annotera reglerna med attribut som registrerar, för varje variabel som används eller tilldelas, dess namn och typ.

Denna post kan sedan föras med till alla ställen i grammatiken där typer behöver matchas, och implementera typkontroll.

På samma sätt kan den användas för att kontrollera initialisering av variabler före användning, etcetera.

Man kan undra hur man skapar och manipulerar en sådan datastruktur utan uttryckligt stöd i formalismen för datastrukturer och operationer på dem. Det kan göras genom att använda metagrammatiken för att definiera en strängrepresentation för datastrukturen och använda mönstermatchning för att definiera operationer:

<left part with <TYPED><NAME><i>>  ::=</i> <b>> ::=</b> <variable with <TYPED><NAME><i>> := |</i> <b>> := |</b> <procedure identifier with <TYPED><NAME><i>> :=</i> <b>> :=</b> <left part list <TYPEMAP1><i>>  ::=</i> <b>> ::=</b> <left part with <TYPED><NAME><i>></i> <b>></b> <where <TYPEMAP1><i>is</i> <b>är</b><TYPED><NAME> <i>added to sorted</i> <b>läggs till sorterade</b><EMPTY> <i>> |</i> <b>> |</b> <left part list <TYPEMAP2><i>></i> <b>></b> <left part with <TYPED><NAME><i>></i> <b>></b> <where <TYPEMAP1><i>is</i> <b>är</b><TYPED><NAME> <i>added to sorted</i> <b>läggs till sorterade</b><TYPEMAP2> <i>></i> <b>></b> <assignment statement <ASSIGNED TO><USED><i>>  ::=</i> <b>> ::=</b> <left part list <ASSIGNED TO><i>></i> <b>></b> <arithmetic expression <USED><i>> |</i> <b>> |</b> <left part list <ASSIGNED TO><i>></i> <b>></b> <Boolean expression <USED><i>></i> <b>></b> <where <TYPED><NAME><i>is</i> <b>är</b><TYPED><NAME> <i>added to sorted</i> <b>läggs till sorterade</b><EMPTY> <i>>>  ::=</i> <b>>> ::=</b> <where <TYPEMAP1><i>is</i> <b>är</b><TYPED1><NAME1> <i>added to sorted</i> <b>läggs till sorterade</b><TYPEMAP2> <i>>  ::=</i> <b>> ::=</b> <where <TYPEMAP2><i>is</i> <b>är</b><TYPED2><NAME2> <i>added to sorted</i> <b>läggs till sorterade</b><TYPEMAP3> <i>></i> <b>></b> <where <NAME1><i>is lexicographically before</i> <b>är lexikografiskt före</b><NAME2> <i>></i> <b>></b> <where <TYPEMAP1><i>is</i> <b>är</b><TYPED1><NAME1> <i>added to sorted</i> <b>läggs till sorterade</b><TYPEMAP2> <i>>  ::=</i> <b>> ::=</b> <where <TYPEMAP2><i>is</i> <b>är</b><TYPED2><NAME2> <i>added to sorted</i> <b>läggs till sorterade</b><TYPEMAP3> <i>></i> <b>></b> <where <NAME2><i>is lexicographically before</i> <b>är lexikografiskt före</b><NAME1> <i>></i> <b>></b> <where <TYPEMAP3><i>is</i> <b>är</b><TYPED1><NAME1> <i>added to sorted</i> <b>läggs till sorterade</b><TYPEMAP4> <i>></i> <b>></b> <where <EMPTY><i>is lexicographically before</i> <b>är lexikografiskt före</b><NAME1> <i>>  ::=</i> <b>> ::=</b> <where <NAME1><i>is</i> <b>är</b><LETTER OR DIGIT> <i>followed by</i> <b>följd av</b><NAME2> <i>></i> <b>></b> <where <NAME1><i>is lexicographically before</i> <b>är lexikografiskt före</b><NAME2> <i>>  ::=</i> <b>> ::=</b> <where <NAME1><i>is</i> <b>är</b><LETTER OR DIGIT> <i>followed by</i> <b>följd av</b><NAME3> <i>></i> <b>></b> <where <NAME2><i>is</i> <b>är</b><LETTER OR DIGIT> <i>followed by</i> <b>följd av</b><NAME4> <i>></i> <b>></b> <where <NAME3><i>is lexicographically before</i> <b>är lexikografiskt före</b><NAME4> <i>></i> <b>></b> <where <NAME1><i>is lexicographically before</i> <b>är lexikografiskt före</b><NAME2> <i>>  ::=</i> <b>> ::=</b> <where <NAME1><i>is</i> <b>är</b><LETTER OR DIGIT 1> <i>followed by</i> <b>följd av</b><NAME3> <i>></i> <b>></b> <where <NAME2><i>is</i> <b>är</b><LETTER OR DIGIT 2> <i>followed by</i> <b>följd av</b><NAME4> <i>></i> <b>></b> <where <LETTER OR DIGIT 1><i>precedes+</i> <b>föregår+</b> <LETTER OR DIGIT 2><where <LETTER OR DIGIT 1><i>precedes+</i> <b>föregår+</b><LETTER OR DIGIT 2> <i>::=</i> <b>::=</b> <where <LETTER OR DIGIT 1><i>precedes</i> <b>föregår</b> <LETTER OR DIGIT 2><where <LETTER OR DIGIT 1><i>precedes+</i> <b>föregår+</b><LETTER OR DIGIT 2> <i>::=</i> <b>::=</b> <where <LETTER OR DIGIT 1><i>precedes+</i> <b>föregår+</b> <LETTER OR DIGIT 3><where <LETTER OR DIGIT 3><i>precedes+</i> <b>föregår+</b><LETTER OR DIGIT 2><where a precedes b> <i>:==</i> <b>:==</b><where b precedes c> <i>:== [...]</i> <b>:== [...]</b><TYPED> <i>::== real |</i> <b>::== äkta |</b> <i>integer |</i> <b>heltal |</b> <i>Boolean</i> <b>Boolean</b><NAME> <i>::==</i> <b>::==</b><LETTER> <i>|</i> <b>|</b><NAME><LETTER> <i>|</i> <b>|</b><NAME><DIGIT><LETTER OR DIGIT> <i>::==</i> <b>::==</b><LETTER> <i>|</i> <b>|</b><DIGIT><LETTER OR DIGIT 1> <i>::=</i> <b>::=</b><LETTER OR DIGIT><LETTER OR DIGIT 2> <i>::=</i> <b>::=</b><LETTER OR DIGIT><LETTER OR DIGIT 3> <i>::=</i> <b>::=</b><LETTER OR DIGIT><LETTER> <i>::== a |</i> <b>::== en |</b> <i>b |</i> <b>b |</b> <i>c |</i> <b>c |</b> <i>[...]</i> <b>[...]</b><DIGIT> <i>::== 0 |</i> <b>::== 0 |</b> <i>1 |</i> <b>1 |</b> <i>2 |</i> <b>2 |</b> <i>[...]</i> <b>[...]</b><NAMES1> <i>::==</i> <b>::==</b><NAMES><NAMES2> <i>::==</i> <b>::==</b><NAMES><ASSIGNED TO> <i>::==</i> <b>::==</b><NAMES><USED> <i>::==</i> <b>::==</b><NAMES><NAMES> <i>::==</i> <b>::==</b><NAME> <i>|</i> <b>|</b><NAME><NAMES><EMPTY> <i>::==</i> <b>::==</b><TYPEMAP> <i>::== (</i> <b>::== (</b><TYPED><NAME> <i>)</i> <b>)</b><TYPEMAP><TYPEMAP1> <i>::==</i> <b>::==</b><TYPEMAP><TYPEMAP2> <i>::==</i> <b>::==</b><TYPEMAP><TYPEMAP3> <i>::==</i> <b>::==</b><TYPEMAP>

Jämfört med den ursprungliga grammatiken har tre nya element lagts till:

attribut till icke-terminalerna i vad som nu är hyperreglerna;
metarules för att specificera de tillåtna värdena för attributen;
nya hyperregler för att specificera operationer på attributvärdena.

De nya hyperreglerna är $\epsilon$ -regler: de genererar bara den tomma strängen.

ALGOL 68 exempel

ALGOL 68-rapporterna använder en något annorlunda notation utan .

ALGOL 68 som i 1968 års slutrapport §2.1

a) program: öppen symbol, standardpreludium, bibliotekspreludium, särskilt program, utgång, bibliotekspostludium, standardpostludium, stängningssymbol. b) standardpreludium: deklarationsförspelssekvens. c) bibliotekspreludium: deklarationsförspelssekvens. d) särskilt program: etikettsekvensalternativ, stark CLOSED void-klausul. e) avsluta : gå på symbol, bokstav e bokstav x bokstav i bokstav t, etikettsymbol. f) bibliotekspostlude : uttalande mellanspel. g) standardpostludium: stark tomsatssats

ALGOL 68 som i 1973 års reviderade rapport §2.2.1, §10.1.1

program : starkt tomrum ny stängd klausul A) EXTERN :: standard ; bibliotek ; systemet ; särskild. B) STOP :: etikett bokstaven s bokstav t bokstav o bokstav p. a) programtext: STYLE start token, nya LAYER1 preludier, parallell token, nya LAYER1 uppgifter PACK, STIL slut token. b) NEST1-preludier: NEST1-standardpreludium med DECS1, NEST1-bibliotekspreludium med DECSETY2, NEST1-systempreludium med DECSETY3, där (NEST1) är (ny TOM ny DECS1 DECSETY2 DECSETY3). c) NEST1 EXTERN preludium med DECSETY1: stark tomhet NEST1-serien med DECSETY1, gå på token ; där (DECSETY1) är (EMPTY), EMPTY. d) NEST1-uppgifter: NEST1-systemuppgiftslista, och även token, NEST1-användaruppgifts-PACK-lista. e) NEST1-systemuppgift: stark tomhet NEST1-enhet. f) NEST1-användaruppgift: NEST2 särskilt prelude med DECS, NEST2 speciellt program PACK, gå på token, NEST2 särskilt postlude, där (NEST2) är (NEST1 new DECS STOP). g) Speciellt NEST2-program: NEST2 ny LABSETY3 förenad etikettdefinition av LABSETY3, starkt tomrum NEST2 nya LABSETY3 ENCLOSED-sats. h) NEST-förenad etikettdefinition av LABSETY: där (LABSETY) är (EMPTY), EMPTY ; där (LABSETY) är (LAB1 LABSETY1), NEST-etikettdefinition av LAB1, NEST-förenad etikettdefinition av$ LABSETY1. i) Särskilt NEST2 postludium: stark tomhet NEST2-serien med STOP.

Ett enkelt exempel på kraften i W-grammatik är klausul

a) programtext: STYLE start token, nya LAYER1 preludier, parallell token, nya LAYER1 uppgifter PACK, STIL slut token.

Detta tillåter BEGIN ... END och { } som blockavgränsare, samtidigt som BEGIN ... } och { ... END utesluts.

Man kanske vill jämföra grammatiken i rapporten med Yacc -parsern för en delmängd av ALGOL 68 av Marc van Leeuwen.

Genomföranden

Anthony Fisher skrev yo-yo , en parser för en stor klass av W-grammatiker, med exempelgrammatiker för uttryck , eva , sal och Pascal (den faktiska ISO 7185- standarden för Pascal använder utökad Backus–Naur-form ).

Dick Grune skapade ett C- program som skulle generera alla möjliga produktioner av en W-grammatik.

Applikationer utanför ALGOL 68

De ovan nämnda tillämpningarna av EAG: er kan i praktiken betraktas som tillämpningar av W-grammatik, eftersom EAG:er ligger så nära W-grammatik.

W-grammatik har också föreslagits för beskrivning av komplexa mänskliga handlingar inom ergonomi . ^{[ citat behövs ]}

En W-Grammarbeskrivning för Ada – "W-grammatikbeskrivning av Ada är fortfarande användbar för datavetare som behöver mer än en enkel förståelse av syntaxen och rudimentär beskrivning av semantiken"

Se även

externa länkar

"Använd i Algol68", Datavetenskap , Book rags .
Pemberton, Steven , VW (handledningsintroduktion), NL: CWI .
Petersson, Kent (1990). "Syntax och semantik för programmeringsspråk" (PDF) . Utkast till föreläsningsanteckningar . Arkiverad från originalet (PDF) den 5 juni 2001.
Augusto, LM (2023). "Tvånivågrammatiker: Några intressanta egenskaper hos van Wijngaardens grammatiker" (PDF) . Omega - Tidskrift för formella språk . 1 :3–34.