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å s om b så 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 så om b då 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 då ( om b då s) annars s2 om a då ( om b då 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
ochom 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 ochom 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.