Dinglar annat

Dingeln else är ett problem vid programmering av parsergeneratorer där en valfri else-sats i en if-then(-else) -sats resulterar i att kapslade villkor är tvetydiga. Formellt är språkets referenskontextfria grammatik tvetydig , vilket betyder att det finns mer än ett korrekt parseträd .

I många programmeringsspråk kan man skriva villkorligt exekverad kod i två former: if-then-formen och if-then-else-formen - else-satsen är valfri:

 om  a  s  om  b  s1  annars  s2 

Detta ger upphov till en tvetydighet i tolkningen när det finns kapslade påståenden, särskilt när en om-då-form visas som s1 i en om-då-else-form:

  om  a  om  b  s  annat  s2 

I det här exemplet exekveras s entydigt när a är sant och b är sant, men man kan tolka s2 som att s2 exekveras när a är falskt (därmed kopplar det andra till det första if) eller när a är sant och b är falskt (därav fästa den andra till den andra if). Med andra ord kan man se det föregående påståendet som något av följande uttryck:

 om  a  (  om  b  s)  annars  s2  om  a  (  om  b  s  annat  s2) 

Problemet med dingling else dateras till ALGOL 60 och har lösts på olika sätt på efterföljande språk. I LR-parsers är det dinglande annat det arketypiska exemplet på en skift-minska konflikt .

Undvik otydlighet samtidigt som syntaxen behålls

Detta är ett problem som ofta dyker upp i kompilatorkonstruktionen , särskilt skannerlös analys . Konventionen när man hanterar det dinglande annat är att fästa det andra till det närliggande if-påståendet, vilket möjliggör entydiga sammanhangsfria grammatiker, i synnerhet. språkets semantik, även om användningen av en parsergenerator kan leda till tvetydiga grammatiker . I dessa fall åstadkommes alternativ gruppering av explicita block, som start...slut i Pascal och {...} i C.

Beroende på kompilatorns konstruktionsmetod kan man vidta olika korrigerande åtgärder för att undvika oklarheter:

  • Om parsern produceras av en SLR-, LR(1)- eller LALR LR-parsergenerator , kommer programmeraren ofta att förlita sig på den genererade parserfunktionen att föredra shift framför reducering närhelst det finns en konflikt. Alternativt kan grammatiken skrivas om för att ta bort konflikten, på bekostnad av en ökning av grammatikens storlek (se nedan ).
  • Om tolken är handskriven kan programmeraren använda en icke-tvetydig kontextfri grammatik. Alternativt kan man förlita sig på en icke-kontextfri grammatik eller ett parsande uttrycks grammatik .

Undvik otydlighet genom att ändra syntaxen

Problemet kan också lösas genom att tydliggöra kopplingen mellan en annan och dess if, inom syntaxen. Detta hjälper vanligtvis till att undvika mänskliga fel.

Möjliga lösningar är:

  • Att ha en "slut om"-symbol som avgränsar slutet av om-konstruktionen. Exempel på sådana språk är ALGOL 68 , Ada , Eiffel , PL/SQL , Visual Basic , Modula-2 och AppleScript .
  • Att inte tillåta att påståendet efter ett "då" är ett "om" i sig (det kan dock vara ett par påståendeparenteser som bara innehåller en om-då-sats). Detta tillvägagångssätt följs av ALGOL 60 .
  • Kräver hängslen (parentesstorlek) när ett "annat" följer ett "om".
  • Kräver att varje "om" ska paras med ett "annat". För att undvika ett liknande problem rörande semantik snarare än syntax, Racket från Scheme genom att betrakta en if utan en reservsats som ett fel, vilket effektivt särskiljer villkorliga uttryck (dvs. if ) från villkorliga uttalanden (dvs. när och om inte , som inte har reservsats). klausuler).
  • Använda olika nyckelord för ett-alternativt och två-alternativt "om"-satser. S-algol använder if e do s för det en-alternativa fallet och om e1 sedan e2 else e3 för det allmänna fallet.
  • Kräver hängslen ovillkorligt, som Swift . Detta är faktiskt sant i Python eftersom dess indragsregler avgränsar varje block, inte bara de i "if"-satser.

Exempel

Konkreta exempel följer.

C

I C lyder grammatiken delvis:

påstående = ... | urvalssats urvalssats = ... | IF (uttryck)-sats | IF ( uttryck )-sats ELSE-sats

Sålunda, utan närmare regler, uttalandet

       if  (  a  )  if  (  b  )  s  ;  annat  s2  ; 

skulle tvetydigt kunna tolkas som om det vore antingen:

 

   
    
  
    
 if  (  a  )  {  if  (  b  )  s  ;  annat  s2  ;  } 

eller:

 

   
    


   if  (  a  )  {  if  (  b  )  s  ;  }  annat  s2  ; 

I praktiken i C väljs det första trädet genom att associera det andra med det närmaste om .

Undviker konflikten i LR-parsers

Ovanstående exempel kan skrivas om på följande sätt för att ta bort oklarheten:

uttalande: öppen_påstående | closed_statement ; open_statement: IF '(' uttryck ')'-sats | IF '(' uttryck ')' closed_statement ELSE open_statement ; closed_statement: non_if_statement | IF '(' uttryck ')' closed_statement ELSE closed_statement ; non_if_statement: ... ;

Alla andra uttalandensrelaterade grammatikregler kan också behöva dupliceras på detta sätt om de direkt eller indirekt kan sluta med en sats eller urvalssats som inte är terminal.

Däremot ger vi grammatik som inkluderar både if- och while-satser.

uttalande: open_statement | closed_statement ; open_statement: IF '(' uttryck ')'-sats | IF '(' uttryck ')' closed_statement ANNAT open_statement | WHILE '(' uttryck ')' open_statement ; closed_statement: enkelt_påstående | IF '(' uttryck ')' closed_statement ANNAT closed_statement | WHILE '(' uttryck ')' closed_statement ; enkel_påstående: ... ;

Slutligen ger vi grammatiken som förbjuder tvetydiga IF-uttalanden.

uttalande: öppen_påstående | closed_statement ; open_statement: IF '(' uttryck ')' simple_statement | IF '(' uttryck ')' open_statement | IF '(' uttryck ')' closed_statement ANNAT open_statement | WHILE '(' uttryck ')' open_statement ; closed_statement: enkelt_påstående | IF '(' uttryck ')' closed_statement ANNAT closed_statement | WHILE '(' uttryck ')' closed_statement ; enkel_påstående: ... ;

Med denna grammatiska analys av "if (a) if (b) c else d" misslyckas:

sats open_statement IF '(' uttryck ')' closed_statement ELSE open_statement 'if' '(' 'a' ')' closed_statement 'annat' 'd'

och sedan misslyckas analysen när man försöker matcha closed_statement med "if (b) c". Ett försök med closed_statement misslyckas på samma sätt.

Se även