Lexer hacka

Inom datorprogrammering är lexer -hacket en vanlig lösning på problemen med att analysera ANSI C , på grund av att referensgrammatiken är kontextkänslig . I C kräver klassificering av en teckensekvens som ett variabelnamn eller ett typnamn kontextuell information om frasstrukturen, vilket hindrar en från att ha en kontextfri lexer .

Problem

Problemet är att i följande kod kan den lexikaliska klassen för A inte bestämmas utan ytterligare kontextuell information:

 (  A  )  *  B

Denna kod kan vara multiplikation av två variabler, i vilket fall A är en variabel; otvetydigt skrivet:

   A  *  B

Alternativt kan det vara att gjuta det därreferenserade värdet av B till typen A , i vilket fall A är ett typedef-namn; otvetydigt skrivet:

  (  A  )  (  *  B  )

Mer detaljerat, i en kompilator , utför lexern ett av de tidigaste stegen av att konvertera källkoden till ett program. Den skannar texten för att extrahera meningsfulla tokens , som ord, siffror och strängar. Parsern analyserar sekvenser av tokens och försöker matcha dem med syntaxregler som representerar språkstrukturer, såsom loopar och variabeldeklarationer. Ett problem uppstår här om en enda sekvens av tokens tvetydigt kan matcha mer än en syntaxregel.

Denna tvetydighet kan inträffa i C om lexern inte skiljer mellan variabel- och typedef -identifierare. Till exempel, i C-uttrycket:

   (  A  )  *  B

lexern kan hitta dessa tokens:

vänster parentes
identifierare 'A'
höger parentes
operator '*'
identifierare 'B'

Problemet är just att den lexikaliska klassen för A inte kan bestämmas utan ytterligare sammanhang: parsern kan tolka detta som att variabel A multiplicerat med B eller som att typ A kastar det derefererade värdet på B . Detta är känt som "typedef-name: identifier"-problemet, på grund av namnet på den problematiska produktionsregeln .

Hacklösningen

Lösningen består i allmänhet av att mata tillbaka information från den semantiska symboltabellen till lexern. Det vill säga, snarare än att fungera som en ren enkelriktad pipeline från lexern till parsern, finns det en backkanal från semantisk analys tillbaka till lexern. Denna blandning av parsning och semantisk analys anses allmänt vara oelegant, varför den kallas ett " hack ".

Utan extra sammanhang kan lexern inte skilja typidentifierare från andra identifierare eftersom alla identifierare har samma format. Med hacket i exemplet ovan, när lexern hittar identifieraren A bör den kunna klassificera token som en typidentifierare. Språkets regler skulle förtydligas genom att specificera att typecasts kräver en typidentifierare och tvetydigheten försvinner.

Problemet finns även i C++ och parsers kan använda samma hack.

Alternativa lösningar

Detta problem uppstår inte (och behöver därför inget "hack" för att lösas) när man använder lexerless parsing- tekniker, eftersom dessa i sig är kontextuella. Dessa ses i allmänhet som mindre eleganta mönster, dock eftersom de saknar modulariteten att ha en samtidig lexer och parser i en pipeline. ^{[ citat behövs ]}

Vissa parsergeneratorer, såsom byacc -derived BtYacc ("Backtracking Yacc"), ger den genererade parsern möjligheten att prova flera försök att analysera tokens. I problemet som beskrivs här, om ett försök misslyckas på grund av semantisk information om identifieraren, kan det gå tillbaka och försöka andra regler.

Clang - parsern hanterar situationen på ett helt annat sätt, nämligen genom att använda en icke-referens lexikal grammatik. Clangs lexer försöker inte skilja mellan typnamn och variabelnamn: den rapporterar helt enkelt den aktuella token som en identifierare. Parsern använder sedan Clangs semantiska analysbibliotek för att bestämma identifierarens natur. Detta möjliggör en mycket renare separation av problem och inkapsling av lexer och parser, och anses därför av vissa kompilatorutvecklare vara en mycket mer elegant lösning än Lexer Hack. Detta är också det tillvägagångssätt som används i de flesta andra moderna språk, som inte särskiljer olika klasser av identifierare i den lexikaliska grammatiken, utan istället skjuter upp dem till analys- eller semantisk analysfas, när tillräcklig information finns tillgänglig. ^{[ exempel behövs ]}

Se även

Dinglar annat

Citat