Syntaktisk predikat

Ett syntaktisk predikat specificerar den syntaktiska giltigheten av att tillämpa en produktion i en formell grammatik och är analog med ett semantiskt predikat som specificerar den semantiska giltigheten av att tillämpa en produktion. Det är ett enkelt och effektivt sätt att dramatiskt förbättra igenkänningsstyrkan hos en LL-parser genom att tillhandahålla godtycklig framsyn. I sin ursprungliga implementering hade syntaktiska predikat formen "( α )?" och kan bara visas på vänsterkanten av en produktion. Det erforderliga syntaktiska villkoret α kan vara vilket giltigt sammanhangsfritt grammatikfragment som helst.

Mer formellt är ett syntaktisk predikat en form av produktionskorsning, som används i parserspecifikationer eller i formella grammatiker . I denna mening har termen predikat betydelsen av en matematisk indikatorfunktion . Om p ₁ och p ₂ är produktionsregler, är språket som genereras av både p ₁ och p ₂ deras uppsättning skärningspunkt.

Som typiskt definierade eller implementerade, ordnar syntaktiska predikat implicit produktionerna så att predikerade produktioner som specificerats tidigare har högre prioritet än predikade produktioner som specificeras senare inom samma beslut. Detta förmedlar en förmåga att disambiguera tvetydiga produktioner eftersom programmeraren helt enkelt kan specificera vilken produktion som ska matcha.

Parsing expression grammars (PEGs), uppfunnet av Bryan Ford, utökar dessa enkla predikat genom att tillåta "inte predikat" och tillåta ett predikat att förekomma var som helst i en produktion. Dessutom uppfann Ford packrat-parsning för att hantera dessa grammatiker i linjär tid genom att använda memoization , till priset av heap space.

Det är möjligt att stödja linjär-tidsanalys av predikat så generella som de som tillåts av PEG:er, men minska minneskostnaden förknippad med memoisering genom att undvika backtracking där en effektivare implementering av lookahead räcker. Detta tillvägagångssätt implementeras av ANTLR version 3, som använder deterministiska ändliga automater för framåtblick; detta kan kräva att man testar ett predikat för att välja mellan övergångar av DFA (kallad "pred-LL(*)"-analys).

Översikt

Terminologi

Termen syntaktisk predikat myntades av Parr & Quong och skiljer denna form av predikat från semantiska predikat (även diskuterat).

Syntaktiska predikat har kallats flerstegsmatchning , tolka begränsningar och helt enkelt predikat i olika litteratur. (Se avsnittet Referenser nedan.) Den här artikeln använder termen syntaktisk predikat genomgående för konsekvens och för att skilja dem från semantiska predikat.

Formella stängningsegenskaper

Bar-Hillel et al. visa att skärningspunkten mellan två reguljära språk också är ett reguljärt språk, det vill säga att de reguljära språken är stängda under skärningspunkten .

Skärningspunkten mellan ett reguljärt språk och ett sammanhangsfritt språk är också stängt, och det har varit känt åtminstone sedan Hartmanis att skärningspunkten mellan två sammanhangsfria språk inte nödvändigtvis är ett sammanhangsfritt språk (och därmed inte är stängd). Detta kan enkelt demonstreras med det kanoniska typ 1 -språket, $L=\{a^{n}b^{n}c^{n}:n \geq 1\}$ :

 Låt  $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1 \}$  (Typ 2) Låt  $L_{2}=\{a^{n}b^{n}c^{m} :m,n\geq 1\}$  (Typ 2) Låt  $L_{3}=L_{1}\cap L_{2}$

Med tanke på strängarna abcc , aabbc , och aaabbbccc , är det tydligt att den enda strängen som tillhör både L ₁ och L ₂ (det vill säga den enda som producerar en icke-tom skärningspunkt) är aaabbbccc .

Andra överväganden

I de flesta formalismer som använder syntaktiska predikat är syntaxen för predikatet icke-kommutativ , vilket vill säga att predikationens funktion är ordnad. Använd till exempel ovanstående exempel och överväg följande pseudogrammatik, där X ::= Y PRED Z förstås betyda: " Y producerar X om och endast om Y också uppfyller predikatet Z ":

S ::= a X X ::= Y PRED Z Y ::= a+ BNCN Z ::= ANBN c+ BNCN ::= b [BNCN] c ANBN ::= a [ANBN] b

Med tanke på strängen aaaabbbccc , i fallet där Y måste uppfyllas först (och förutsatt en girig implementering), kommer S att generera aX och X i sin tur genererar aaabbbccc , vilket genererar aaaabbbccc . I fallet där Z måste uppfyllas först, kommer ANBN inte att generera aaaabbb , och därför genereras inte aaaabbbccc av grammatiken. Dessutom, om antingen Y eller Z (eller båda) anger någon åtgärd som ska vidtas vid reduktion (vilket skulle vara fallet i många parsers), bestämmer ordningen som dessa produktioner matchar i vilken ordning dessa biverkningar inträffar. Formalism som varierar över tiden (som adaptiv grammatik ) kan förlita sig på dessa biverkningar .

Exempel på användning

ANTLR

Parr & Quong ger detta exempel på ett syntaktisk predikat:

   
      
      stat  :  (  deklaration  )  ?  förklaring  |  uttryck  ;

som är avsett att uppfylla följande informellt angivna begränsningar för C++ :

Om det ser ut som en deklaration så är det; annat
om det ser ut som ett uttryck så är det; annat
det är ett syntaxfel.

I den första produktionen av regelstat, det syntaktiska predikatet (deklarationen)? indikerar att deklaration är det syntaktiska sammanhang som måste finnas för att resten av produktionen ska lyckas. Vi kan tolka användningen av (deklaration)? som "Jag är inte säker på om deklarationen kommer att stämma; låt mig prova den och, om den inte stämmer överens, ska jag prova nästa alternativ." Således, när en giltig deklaration påträffas, kommer regeldeklarationen att kännas igen två gånger – en gång som syntaktisk predikat och en gång under själva analysen för att exekvera semantiska åtgärder.

Att notera i exemplet ovan är det faktum att varje kod som utlöses av godkännandet av deklarationsproduktionen endast kommer att inträffa om predikatet är uppfyllt.

Kanoniska exempel

Språket ${\displaystyle L=\{a^{n}b^{n}c^{n}|n\geq 1\}} kan representeras$ i olika grammatiker och formalismer enligt följande:

Analysera uttrycksgrammatik

       
     
      S  ←  &  (  A  !  b  )  a  +  B  !  c  A  ←  a  A  ?  b  B  ←  b  B  ?  c

§-Kalkyl

Använda ett bundet predikat:

 S → {A} ^B

 A → X 'c+' X → 'a' [X] 'b' B → 'a+' Y Y → 'b' [Y] 'c'

Använder två fria predikat:

   A → <'a+'> _a <'b+'> _b Ψ(  a  b  ) ^X <'c+'> _c Ψ(  b  c  ) ^Y

 X → 'a' [X] 'b' Y → 'b' [Y ] 'c'

Konjunktiv grammatik

(Obs: följande exempel genererar faktiskt $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$ , men ingår här eftersom det är exemplet som ges av uppfinnaren av konjunktiva grammatiker.):

S → AB&DC A → aA | ε B → bBc | e C → cC | ε D → aDb | ε

Perl 6 regler

  regel  S  {  <before <A> <!before b>> a+ <B> <!before c>  }  regel  A  {  a <A>? b   }  regel  B  {  b <B>? c   }

Parsers/formalismer som använder någon form av syntaktisk predikat

, använder följande tolkar och grammatikformalismer syntaktiska predikat:

ANTLR (Parr & Quong): Som ursprungligen implementerat, sitter syntaktiska predikat längst till vänster i en produktion så att produktionen till höger om predikatet görs om och endast om det syntaktiska predikatet först accepterar nästa del av ingångsströmmen. Även om de är ordnade, kontrolleras predikaten först, med analys av en sats som fortsätter om och endast om predikatet är uppfyllt, och semantiska handlingar förekommer endast i icke-predikat.
Augmented Pattern Matcher (Balmas): Balmas hänvisar till syntaktiska predikat som "multi-step matching" i sin artikel om APM. När en APM-parser tolkar kan den binda delsträngar till en variabel och senare kontrollera denna variabel mot andra regler, fortsätta att tolka om och endast om den delsträngen är acceptabel för ytterligare regler.
Analysera uttrycksgrammatik (Ford): Fords PEG:er har syntaktiska predikat uttryckta som och-predikatet och icke-predikatet .
§-Calculus (Jackson): I §-Calculus kallas syntaktiska predikat ursprungligen helt enkelt predikat , men delas senare in i bundna och fria former, var och en med olika indataegenskaper.
Raku-regler: Raku introducerar ett generaliserat verktyg för att beskriva en grammatik som kallas regler , som är en förlängning av Perl 5:s reguljära uttryckssyntax. Predikat introduceras via en lookahead-mekanism som kallas före , antingen med " <före ...> " eller " <!före ...> " (det vill säga: " inte före"). Perl 5 har också en sådan framtid, men den kan bara kapsla in Perl 5:s mer begränsade regexp-funktioner.
ProGrammar (NorKen Technologies): ProGrammars GDL (Grammar Definition Language) använder syntaktiska predikat i en form som kallas parse-begränsningar . OBS: Denna länk är inte längre giltig!
Konjunktiv och boolesk grammatik (Okhotin): Konjunktiv grammatik, som först introducerades av Okhotin, introducerar det explicita begreppet konjunktion -som-predikation. Senare behandling av konjunktiv och boolesk grammatik är den mest grundliga behandlingen av denna formalism hittills.

externa länkar