- Adress. Funktionell enhet som konverterar virtuell adress(eng. Virtuell adress) in riktig adress.
- Dialog. Ger användning av ett programmeringsspråk i tidsdelningsläge.
- Multipass. Genererar en objektmodul i flera vyer originalprogram.
- Tillbaka. Samma som detranslator. Se även: dekompilerare, disassemblerare.
- Enkelt pass. Bildar en objektmodul i en sekventiell visning av källprogrammet.
- Optimerande. Utför kodoptimering i den genererade objektmodulen.
- Syntaktiskt orienterad (syntaktiskt driven). Får som indata en beskrivning av syntax och semantik för språket och texten på det beskrivna språket, som översätts i enlighet med den givna beskrivningen.
- Testa. En uppsättning makrokommandon för assemblerspråk som låter dig ställa in olika felsökningsprocedurer i program skrivna i assemblerspråk.
Syftet med sändningen- konvertera text från ett språk till ett annat, vilket är förståeligt för mottagaren av texten. När det gäller översättarprogram är adressaten teknisk anordning(processor) eller tolkprogram.
Språket för processorer (maskinkod) är vanligtvis på låg nivå. Det finns plattformar som använder maskinspråk hög nivå(till exempel iAPX-432), men de är ett undantag från regeln på grund av deras komplexitet och höga kostnad. En översättare som konverterar program till maskinspråk mottas och exekveras direkt av processorn anropas kompilator.
Kompileringsprocessen består vanligtvis av flera steg: lexikal, syntaktisk och semantisk analys (engelsk semantisk analys), generering av mellankod, optimering och generering av den resulterande maskinkoden. Dessutom beror programmet vanligtvis på tjänster som tillhandahålls av operativsystemet och tredjepartsbibliotek (till exempel, fil I/O eller GUI), och programmets maskinkod måste vara associerad med dessa tjänster. Länkning med statiska bibliotek görs av en länkare eller länkare (som kan vara ett separat program eller del av en kompilator), medan länkning till operativsystemet och dynamiska bibliotek görs när laddaren börjar köra programmet.
Fördelen med kompilatorn: programmet kompileras en gång och inga ytterligare transformationer krävs varje gång det exekveras. Följaktligen krävs inte en kompilator på målmaskinen för vilken programmet är kompilerat. Nackdel: Ett separat kompileringssteg saktar ner skrivning och felsökning och gör det svårt att köra små, enkla eller engångsprogram.
En annan metod för implementering är när programmet körs med hjälp av tolk ingen sändning alls. Tolkmjukvaran modellerar en maskin vars hämtnings-exekveringscykel fungerar på instruktioner på högnivåspråk snarare än på maskininstruktioner. Sådan mjukvarumodellering skapar virtuell maskin, som implementerar språket. Detta synsätt kallas ren tolkning. Ren tolkning används vanligtvis för språk med en enkel struktur (till exempel APL eller Lisp). Tolkar kommandorad processkommandon i skript i UNIX eller batchfiler(.bat) i MS-DOS är också vanligtvis i rent tolkningsläge.
Fördelen med en ren tolk: frånvaron av mellanliggande åtgärder för översättning förenklar implementeringen av tolken och gör den mer bekväm att använda, inklusive i dialogläge. Nackdelen är att en tolk måste finnas på målmaskinen där programmet ska köras.
Det finns kompromisser mellan kompilering och ren tolkning vid implementering av programmeringsspråk, när tolken, innan programmet körs, översätter det till ett mellanspråk (till exempel till bytekod eller p-kod), mer bekvämt för tolkning (det vill säga, vi pratar om en tolk med en inbyggd översättare) . Denna metod kallas blandad implementering. Ett exempel på en blandad språkimplementering är Perl. Detta tillvägagångssätt kombinerar både fördelarna med en kompilator och tolk (hög exekveringshastighet och enkel användning) och nackdelar (översättning och lagring av ett program på ett mellanspråk kräver ytterligare resurser; En tolk måste vara närvarande för att köra programmet på målmaskinen.) Dessutom, som i fallet med en kompilator, kräver en blandad implementering att källkoden är fri från fel (lexikaliska, syntaktiska och semantiska) före exekvering.
Utsända Och tolkning- olika processer: översättning handlar om översättning av program från ett språk till ett annat, och tolkning ansvarar för genomförandet av programmen. Men eftersom syftet med översättning vanligtvis är att förbereda programmet för tolkning, betraktas dessa processer vanligtvis tillsammans. Till exempel karakteriseras programmeringsspråk ofta som "kompilerade" eller "tolkade", beroende på om sammanställning eller tolkning dominerar användningen av språket. Dessutom nästan alla programmeringsspråk låg nivå och tredje generationen, såsom assembler, C eller Modula-2, kompileras, med mera språk på hög nivå, som Python eller SQL, tolkas.
Å andra sidan finns det en interpenetration av översättnings- och tolkningsprocesser: tolkar kan kompilera (inklusive dynamisk kompilering), och översättare kan kräva tolkning för (till exempel för makron i assemblerspråk, villkorlig kompilering i C eller för mallar i C++).
Dessutom kan samma programmeringsspråk både översättas och tolkas, och måste i båda fallen finnas allmänna stadier analys och igenkänning av källspråkets konstruktioner och direktiv. Detta gäller både mjukvaru- och hårdvaruimplementeringar - till exempel x86-familjens processorer, innan de exekverar maskinspråksinstruktioner, utför deras avkodning, markering i operanderfälten för operander (register, minnesadresser, omedelbara värden), bitdjup, etc., och i Pentium-processorer med NetBurst-arkitekturen översätts maskinkoden i allmänhet till en sekvens av mikrooperationer innan den lagras i den interna cachen.
Varje dator har sitt eget programmeringsspråk - kommandospråk eller maskinspråk - och kan köra program endast skrivna på detta språk. I princip kan vilken algoritm som helst beskrivas med maskinspråk, men programmeringskostnaderna blir extremt höga. Detta beror på det faktum att maskinspråk låter dig beskriva och bearbeta endast primitiva datastrukturer - bitar, bytes, ord. Programmering i maskinkoder kräver överdriven detaljering av programmet och är väl bara tillgängligt för programmerare kunnig om enheten och drift av datorn. Språk på hög nivå (Fortran, PL/1, Pascal, C, Ada, etc.) med utvecklade datastrukturer och metoder för bearbetning som inte beror på språket på en viss dator gjorde det möjligt att övervinna denna svårighet.
Algoritmiska språk på hög nivå gör det möjligt för programmeraren att enkelt och bekvämt beskriva algoritmer för att lösa många tillämpade problem. Denna beskrivning kallas originalprogram, och språket på hög nivå är inmatningsspråk.
Språkprocessorär ett maskinspråksprogram som tillåter dator förstå och köra program på inmatningsspråket. Det finns två huvudtyper av språkbehandlare: tolkar och översättare.
Tolkär ett program som accepterar ett program i inmatningsspråket som indata och, allt eftersom inmatningsspråkskonstruktionerna känns igen, implementerar dem och producerar utdata från beräkningar som föreskrivs av källprogrammet.
Översättareär ett program som accepterar ett originalprogram som indata och genererar ett program vid dess utgång som är funktionellt likvärdigt med originalet, kallat objekt. Ett objektprogram är skrivet på ett objektspråk. I ett särskilt fall kan maskinspråk fungera som ett objektspråk, och i detta fall kan programmet som erhålls vid utgången av översättaren omedelbart exekveras på en dator (tolkas). I det här fallet är datorn en tolk av ett objektprogram i maskinkod. I allmänhet behöver inte ett objektspråk vara maskin eller något nära det (autokod). Som objektsspråk kan tjäna några mellanspråk– ett språk som ligger mellan inmatnings- och maskinspråken.
Om ett mellanspråk används som objektspråk är två alternativ för att konstruera en översättare möjliga.
Det första alternativet är för mellanspråk Det finns (eller håller på att utvecklas) en annan översättare från mellanspråket till maskinspråket, och den används som det sista blocket i den designade översättaren.
Det andra alternativet för att bygga en översättare med ett mellanspråk är att bygga en tolk för mellanspråkskommandon och använda den som det sista blocket i översättaren. Fördelen med tolkar manifesteras i felsöknings- och dialogöversättare, som säkerställer att användaren kan arbeta i ett interaktivt läge, upp till att göra ändringar i programmet utan att helt omsätta det.
Tolkar används också i programemulering - exekvering på en teknisk maskin av program som kompilerats för en annan (objekt) maskin. Detta alternativ, i synnerhet, används vid felsökning av program på en dator för allmänt ändamål som kommer att köras på en specialiserad dator.
En översättare som använder ett språk nära maskinspråk (autokod eller assembler) som inmatningsspråk kallas traditionellt assemblerare. En översättare för ett högnivåspråk kallas kompilator.
Att bygga en kompilator för senaste åren Betydande framsteg har gjorts. De första kompilatorerna använde sk metoder för direktsändning– det här är övervägande heuristiska metoder, där, baserat på den allmänna idén, för varje språkkonstruktion utvecklades en egen översättningsalgoritm till en maskinekvivalent. Dessa metoder var långsamma och ostrukturerade.
Designmetoden för moderna kompilatorer är baserad på kompositionssyntaktiskt driven metod språkbehandling. Kompositionell i den meningen att processen att konvertera ett källprogram till ett objektprogram implementeras genom sammansättningen av funktionellt oberoende mappningar med explicit identifierade in- och utdatastrukturer. Dessa mappningar är konstruerade utifrån att betrakta källprogrammet som en sammansättning av huvudaspekterna (nivåerna) av beskrivningen av inmatningsspråket: vokabulär, syntax, semantik och pragmatik, och identifiera dessa aspekter från källprogrammet under dess sammanställning. Låt oss överväga dessa aspekter för att få en förenklad kompilatormodell.
Grunden för alla naturliga eller konstgjort språkär alfabet– en uppsättning elementära tecken som är tillåtna i språket (bokstäver, siffror och servicetecken). Skyltar kan kombineras till ord– elementära konstruktioner av språket, betraktade i texten (programmet) som odelbara symboler som har en viss betydelse.
Ett ord kan också vara ett enda tecken. Till exempel i Pascal-språket är ord identifierare, nyckelord, konstanter och avgränsare, särskilt aritmetik och logiska operationer, parentes, kommatecken och andra symboler. Ett språks vokabulär, tillsammans med en beskrivning av hur de representeras, utgör ordförråd språk.
Ord i ett språk kombineras till mer komplexa strukturer - meningar. I programmeringsspråk är den enklaste meningen en operatör. Meningar är byggda av ord och enklare meningar enligt syntaxens regler. Syntax språk är en beskrivning av korrekta meningar. Beskrivning av meningars betydelse, d.v.s. betydelser av ord och deras interna anslutningar, är semantik språk. Dessutom noterar vi att ett specifikt program har viss inverkan på översättaren - pragmatism. Sammantaget syntax, semantik och pragmatism av språkform semiotik språk.
Att översätta ett program från ett språk till ett annat består i allmänhet av att ändra alfabetet, ordförrådet och syntaxen för programspråket samtidigt som dess semantik bibehålls. Processen att översätta ett källprogram till ett objektprogram är vanligtvis uppdelad i flera oberoende delprocesser (översättningsfaser), som implementeras av motsvarande översättningsblock. Det är lämpligt att överväga lexikal analys, syntaktisk analys, semantisk analys och
objektprogramsyntes. Men i många riktiga kompilatorer är dessa faser uppdelade i flera underfaser, och det kan också finnas andra faser (till exempel objektkodoptimering). I fig. Figur 1.1 visar en förenklad funktionsmodell av översättaren.
Enligt denna modell är ingångsprogrammet i första hand föremål för lexikal bearbetning. Syftet med lexikal analys är att översätta källprogrammet till kompilatorns interna språk, där nyckelord, identifierare, etiketter och konstanter reduceras till ett enda format och ersätts med villkorliga koder: numeriska eller symboliska, som kallas deskriptorer. Varje deskriptor består av två delar: tokens klass (typ) och en pekare till minnesadressen där information om den specifika tokenen lagras. Vanligtvis är denna information organiserad i tabeller. Samtidigt med översättningen av källprogrammet till det interna språket, i skedet av lexikal analys, lexikal kontroll- identifiera oacceptabla ord i programmet.
Parsern tar utdata från den lexikala analysatorn och översätter sekvensen av symboliska bilder till formen av ett mellanprogram. Ett mellanprogram är i huvudsak en representation av syntaxträdet för ett program. Det senare speglar strukturen i det ursprungliga programmet, d.v.s. ordning och förbindelser mellan dess operatörer. Under konstruktionen av ett syntaxträd, syntaktisk kontroll– identifiera syntaxfel i programmet.
Den faktiska utdatan från parsern kan vara den sekvens av kommandon som behövs för att bygga mellanvaran, komma åt katalogtabeller och utfärda ett diagnostiskt meddelande vid behov.
Ris. 1.1. Förenklad funktionell modell av översättaren
Syntesen av ett objektprogram börjar som regel med distribution och allokering av minne för huvudprogramobjekten. Varje mening i källprogrammet undersöks sedan och semantiskt ekvivalenta meningar i objektspråket genereras. Som mata in information den använder programmets syntaxträd och utdatatabellerna för den lexikaliska analysatorn - en tabell med identifierare, en tabell med konstanter och andra. Trädanalys tillåter oss att identifiera sekvensen av genererade kommandon i ett objektprogram, och med hjälp av tabellen med identifierare bestämmer vi vilka typer av kommandon som är giltiga för värdena för operanderna i de genererade kommandona (till exempel vilka kommandon måste genereras: fast eller flyttal, etc.).
Själva genereringen av ett objektprogram föregås ofta av semantisk analys vilket ingår olika sorter semantisk bearbetning. En typ är att kontrollera semantiska konventioner i ett program. Exempel på sådana konventioner: den unika beskrivningen av varje identifierare i programmet, definitionen av en variabel görs innan den används, etc. Semantisk analys kan utföras i senare faser av översättningen, till exempel i programoptimeringsfasen, som också kan inkluderas i översättaren. Målet med optimering är att minska tid eller resurser random access minne krävs för att köra objektprogrammet.
Dessa är de viktigaste aspekterna av översättningsprocessen från högnivåspråk. Mer information om organisationen av sändningens olika faser och relaterade frågor praktiska sätt deras matematiska beskrivningar diskuteras nedan.
Skicka ditt goda arbete i kunskapsbasen är enkelt. Använd formuläret nedan
Studenter, doktorander, unga forskare som använder kunskapsbasen i sina studier och arbete kommer att vara er mycket tacksamma.
Postat på http://www.allbest.ru
Introduktion
1.1 Top-down analys
1.2 Bottom-up-analys
1.2.1 LR(k) - grammatik
1.2.1.1 LR(0) - grammatik
1.2.2 LALR(1) - grammatik
2. Översättarutveckling
2.1 Kravanalys
2.2 Design
2.2.1 Designa en lexikalanalysator
2.2.4 Programimplementering av parsern
2.3 Kodning
2.4 Testning
Slutsats
Lista över använda källor
Bilaga A. Listning programtextöversättare
Bilaga B. Testresultat
Bilaga B. Översättarprogramdiagram
Introduktion
Länge borta är de dagar då man, innan man skrev ett program, var tvungen att förstå och komma ihåg dussintals maskininstruktioner. En modern programmerare formulerar sina uppgifter i programmeringsspråk på hög nivå och använder assemblerspråk endast i undantagsfall. Som bekant blir algoritmiska språk tillgängliga för programmeraren först efter skapandet av översättare från dessa språk.
Programmeringsspråk skiljer sig ganska mycket från varandra i syfte, struktur, semantisk komplexitet och implementeringsmetoder. Detta ålägger sina egna specifika egenskaper för utvecklingen av specifika översättare.
Programmeringsspråk är verktyg för att lösa problem inom olika ämnesområden, vilket bestämmer detaljerna i deras organisation och skillnader i syfte. Exempel är språk som Fortran, som är inriktat på vetenskapliga beräkningar, och C, som är avsett för systemprogrammering,Prolog, som effektivt beskriver slutledningsproblem, Lisp, som används för rekursiv listbearbetning. Dessa exempel kan fortsätta. Varje ämnesområde ställer sina egna krav på själva språkets organisation. Därför kan vi notera olika former av representation av operatorer och uttryck, skillnaden i uppsättningen av grundläggande operationer, minskningen av programmeringseffektivitet när man löser problem som inte är relaterade till ämnesområde. Språkliga skillnader återspeglas också i översättarnas struktur. Lisp och Prolog exekveras oftast i tolkningsläge på grund av att de använder dynamisk generering av datatyper under beräkningar. Fortran-översättare kännetecknas av aggressiv optimering av den resulterande maskinkoden, vilket blir möjligt på grund av den relativt enkla semantiken hos språkkonstruktioner - i synnerhet på grund av frånvaron av mekanismer för alternativa namngivning av variabler genom pekare eller referenser. Närvaron av pekare i C-språket ställer specifika krav på dynamisk minnesallokering.
Ett språks struktur kännetecknar de hierarkiska relationerna mellan dess begrepp, vilka beskrivs av syntaktiska regler. Programmeringsspråk kan skilja sig mycket från varandra i organisationen av enskilda begrepp och relationerna mellan dem. Programmeringsspråket PL/1 tillåter godtycklig kapsling av procedurer och funktioner, medan i C måste alla funktioner vara på den yttre kapslingsnivån. C++-språket tillåter att variabler deklareras när som helst i programmet innan det används första gången, medan i Pascal måste variabler definieras i ett speciellt deklarationsområde. Att ta detta ännu längre är PL/1, som gör att en variabel kan deklareras efter att den har använts. Eller så kan du utelämna beskrivningen helt och hållet och använda standardreglerna. Beroende på beslut fattat, kan översättaren analysera programmet i ett eller flera pass, vilket påverkar översättningshastigheten.
Programmeringsspråkens semantik varierar kraftigt. De skiljer sig inte bara i implementeringsfunktionerna för enskilda operationer, utan också i de programmeringsparadigm som bestämmer grundläggande skillnader inom mjukvaruutvecklingsmetoder. Det specifika med genomförandet av operationer kan gälla både strukturen på de uppgifter som behandlas och reglerna för behandling av samma typer av uppgifter. Språk som PL/1 och APL stöder matris- och vektoroperationer. De flesta språk arbetar främst med skalärer, och tillhandahåller procedurer och funktioner skrivna av programmerare för bearbetning av arrayer. Men även när man utför operationen att lägga till två heltal, kan språk som C och Pascal bete sig annorlunda.
Tillsammans med traditionell procedurprogrammering, även kallad imperativ, finns det sådana paradigm som funktionell programmering, logisk programmering och objektorienterad programmering. Strukturen för språkens begrepp och objekt beror starkt på det valda paradigmet, vilket också påverkar implementeringen av översättaren.
Även samma språk kan implementeras på flera sätt. Detta beror på det faktum att teorin om formell grammatik tillåter olika metoder analysera samma meningar. I enlighet med detta, översättare olika sätt kan få samma resultat ( objektprogram) baserat på den ursprungliga källtexten.
Samtidigt har alla programmeringsspråk ett antal gemensamma egenskaper och parametrar. Denna gemensamhet avgör också principerna för att organisera översättare som är lika för alla språk.
Programmeringsspråk är designade för att göra programmering enklare. Därför är deras operatörer och datastrukturer mer kraftfulla än de i maskinspråk.
För att öka tydligheten i program, istället för numeriska koder, symboliska eller grafiska representationer språkstrukturer som är mer bekväma för människans uppfattning.
För alla språk definieras:
- många symboler som kan användas för att skriva korrekta program (alfabet), grundläggande element,
- många korrekta program (syntax),
- "betydelsen" av varje korrekt program (semantik).
Oavsett språkets särdrag kan vilken översättare som helst betraktas som en funktionell omvandlare F, som ger en unik mappning från X till Y, där X är ett program på källspråket, Y är ett program på utmatningsspråket. Därför kan själva översättningsprocessen formellt representeras ganska enkelt och tydligt: Y = F(X).
Formellt var och en rätt program X är en sträng av tecken från något alfabet A, omvandlat till dess motsvarande sträng Y, sammansatt av tecken från alfabetet B.
Ett programmeringsspråk som vilket som helst ett komplext system, definieras genom en hierarki av begrepp som definierar relationerna mellan dess element. Dessa begrepp är sammanlänkade i enlighet med syntaktiska regler. Vart och ett av programmen byggda enligt dessa regler har en motsvarande hierarkisk struktur.
I detta avseende kan följande gemensamma funktioner dessutom särskiljas för alla språk och deras program: varje språk måste innehålla regler som tillåter generering av program som motsvarar detta språk eller erkänner överensstämmelsen mellan skrivna program och ett givet språk.
Annan karaktäristiskt drag av alla språk är deras semantik. Det bestämmer innebörden av språkoperationer och korrektheten av operanderna. Kedjor som har samma syntaktiska struktur i olika språk programmering kan skilja sig åt i semantik (som t.ex. observeras i C++, Pascal, Basic). Kunskap om ett språks semantik gör att du kan separera det från dess syntax och använda det för konvertering till ett annat språk (för att generera kod).
Syftet med detta kursarbete är att utveckla en pedagogisk översättare från en given förenklad textspråk hög nivå.
1. Metoder för grammatikanalys
Låt oss titta på de grundläggande metoderna för grammatisk analys.
1.1 Top-down analys
När man analyserar uppifrån och ner rör sig mellanled längs trädet i riktning från roten till löven. I det här fallet, när du tittar på kedjan från vänster till höger, kommer vänsterhänta slutsatser naturligtvis att erhållas. Vid deterministisk analys kommer problemet att vara vilken regel som ska tillämpas för att lösa den icke-terminala delen längst till vänster.
1.1.1 LL(k) - språk och grammatik
Betrakta slutledningsträdet i processen att erhålla den vänstra utmatningen av kedjan. Den mellanliggande kedjan i slutledningsprocessen består av en kedja av terminaler w, den längst till vänster icke-terminala A, den under-infererade delen x:
-S--
/ \
/ -Yxa-\
/ | \
-w---u----
Figur 1
För att fortsätta tolka är det nödvändigt att ersätta det icke-terminala A enligt en av reglerna i formen A:y. Om du vill att analysen ska vara deterministisk (inga returer) måste denna regel väljas på ett speciellt sätt. En grammatik sägs ha egenskapen LL(k) om det, för att välja en regel, räcker att endast ta hänsyn till wAx och de första k tecknen i den ogranskade strängen u. Den första bokstaven L (vänster) hänvisar till att se ingångskedjan från vänster till höger, den andra hänvisar till den vänstra utgången som används.
Låt oss definiera två uppsättningar av kedjor:
a) FIRST(x) är uppsättningen terminalsträngar härledda från x, förkortade till k tecken.
b) FOLLOW(A) - en uppsättning terminalkedjor förkortade till k tecken, som omedelbart kan följa A i de utgående kedjorna.
En grammatik har egenskapen LL(k) om, från existensen av två kedjor av vänster slutledningar:
S:: vax: wzx:: wu
S:: vax: wtx:: wv
från villkoret FIRST(u)=FIRST(v) följer z=t.
I fallet med k=1, för att välja en regel för A, räcker det att bara känna till det icke-terminala A och a - det första tecknet i kedjan u:
- regel A:x ska väljas om a ingår i FIRST(x),
- Regel A:e ska väljas om a ingår i FÖLJ(A).
Egenskapen LL(k) lägger ganska starka begränsningar på grammatiken. Till exempel, LL(2) grammatik S: aS | a har inte egenskapen LL(1), eftersom FIRST(aS)=FIRST(a)=a. I det här fallet kan du minska värdet på k med "faktorisering" (ta faktorn ur parentes):
S: aA
A: S | e
Varje LL(k)-grammatik är entydig. En vänsterrekursiv grammatik tillhör inte klassen LL(k) för någon k. Ibland är det möjligt att konvertera en icke-LL(1) grammatik till en ekvivalent LL(1) grammatik genom att eliminera vänsterrekursion och faktorisering. Problemet med förekomsten av en ekvivalent LL(k)-grammatik för en godtycklig icke-LL(k)-grammatik är emellertid oavgjord.
1.1.2 Rekursiv descentmetod
Den rekursiva härkomstmetoden är inriktad på de fall då kompilatorn är programmerad på ett av högnivåspråken, då användningen av rekursiva procedurer är tillåten.
Huvudidén med rekursiv härkomst är att varje icke-terminal i grammatiken har en motsvarande procedur som känner igen alla kedja som genereras av denna icke-terminala. Dessa procedurer anropar varandra vid behov.
Rekursiv härkomst kan användas för vilken LL(1) grammatik som helst. Varje icke-terminal i grammatiken har en motsvarande procedur, som börjar med en övergång till den beräknade etiketten och innehåller kod som motsvarar varje regel för denna icke-terminal. För de inmatningssymboler som hör till urvalsuppsättningen för en given regel, överför den beräknade övergången kontrollen till koden som motsvarar den regeln. För de återstående inmatningssymbolerna överförs kontrollen till felhanteringsproceduren.
Koden för en regel innehåller operationer för varje tecken som ingår i höger sida regler. Operationerna är ordnade i den ordning som symbolerna visas i regeln. Efter den senaste operationen innehåller koden en retur från proceduren.
Att använda rekursiv nedstigning på ett högnivåspråk gör programmering och felsökning enklare.
1.2 Bottom-up-analys
Låt oss överväga att analysera nerifrån och upp, där mellanstiften flyttas längs med trädet mot roten. Om du läser tecknen i strängen från vänster till höger kommer analysträdet att se ut så här:
-S--
/ \
/-x-\
/ | \
--w--b--u-
figur 2
Mellanutgången har formen xbu, där x är en kedja av terminaler och icke-terminaler, från vilken den visade delen av terminalkedjan w utmatas, bu är den ovisade delen av terminalkedjan, b är nästa symbol. För att fortsätta analysen kan du antingen lägga till tecknet b till den visade delen av kedjan (utför ett så kallat "skifte") eller välja i slutet av x en sådan kedja z (x=yz) att en av reglerna för grammatiken B:z kan tillämpas på z och ersätta x till kedjan yB (utför den så kallade "faltningen"):
-S-- -S--
/ \ / \
/-x-b-\ /yB-\
/ | \ / | \
--w--b--u- --w--b--u-
Figur 3 - Efter växling Figur 4 - Efter faltning
Om faltning endast tillämpas på sista tecknen x, då får vi rätt utdata från kedjan. Denna analys kallas LR, där symbolen L (vänster, vänster) hänvisar till att se kedjan från vänster till höger, och R (höger, höger) hänvisar till de resulterande utsignalerna.
Sekvensen av skift- och vikoperationer är väsentlig. Därför kräver deterministisk analys att man väljer mellan skift och faltning (och olika faltningsregler) i varje ögonblick.
1.2.1 LR(k) - grammatik
Om det, i processen för LR-parsning, är möjligt att fatta ett deterministiskt beslut om skift/reduktion, med hänsyn till endast strängen x och de första k tecknen i den osynliga delen av inmatningssträngen u (dessa k tecken kallas för förskottssträngen ), sägs grammatiken ha egenskapen LR(k).
-S--
/ \
/-x-\
--w----u--
Figur 5
Skillnaden mellan LL(k) och LR(k) grammatik i termer av ett slutledningsträd:
-S-
/ | \
/A\
/ / \ \
-w---v---u-
Bild 6
I fallet med LL(k)-grammatik kan regeln som tillämpas på A bestämmas unikt av w och de första k tecknen i vu, och i fallet med LR(k)-grammatik, av w,v och den första k karaktärer av u. Detta icke rigorösa resonemang visar att LL(k)-språk< LR(k)-языки (при k > 0).
1.2.1.1 LR(0) - grammatik
Låt oss först överväga de enklaste grammatikerna i denna klass - LR(0). När du tolkar en sträng på ett LR(0)-språk behöver du inte alls använda förskottskedjan - valet mellan shift och fold görs baserat på kedjan x. Eftersom det bara ändras från den högra änden under parsningen, kallas det en stack. Låt oss anta att det inte finns några onödiga symboler i grammatiken och att den initiala symbolen inte visas på höger sida av reglerna - då signalerar faltning till den initiala symbolen att analysen är klar. Låt oss försöka beskriva uppsättningen av kedjor av terminaler och icke-terminaler som visas på stacken under all LR-parsning (med andra ord, alla högerhänta slutsatser från grammatiken).
Låt oss definiera följande uppsättningar:
L(A:v) - vänsterkontext för regel A:v - uppsättning stacktillstånd omedelbart före v viks till A under alla lyckade LR-analyser. Uppenbarligen slutar varje kedja i L(A:v) på v. Om svansen v på alla sådana kedjor skärs av, får vi uppsättningen kedjor som uppträder till vänster om A under alla framgångsrika högerhänta slutsatser. Låt oss beteckna denna uppsättning som L(A) - det vänstra sammanhanget för det icke-terminala A.
Låt oss konstruera en grammatik för mängden L(A). Terminalerna i den nya grammatiken kommer att vara terminalerna och icke-terminalerna i den ursprungliga grammatiken kommer att betecknas med;
och lägg till regler till den nya grammatiken:
: - L(B) inkluderar L(A)
: B - L(C) inkluderar L(A) B
: B C d - L(E) inkluderar L(A) B Cd
Den resulterande grammatiken har en speciell form (sådana grammatiker kallas vänsterlinjära), därför uppsättningar av vänsterhänta sammanhang
- regelbundet. Det följer att huruvida en sträng tillhör den vänstra kontexten av en icke-terminal kan beräknas induktivt med hjälp av en finita tillståndsmaskin, som skannar strängen från vänster till höger. Låt oss beskriva denna process konstruktivt.
Låt oss kalla en LR(0)-situation för en grammatikregel med en markerad position mellan symbolerna på regelns högra sida. Till exempel för grammatiken S:A; A:aAA; A:b följande LR(0)-situationer existerar: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (positionen indikeras med ett understreck).
Vi kommer att säga att kedjan x överensstämmer med situationen A:b_c om x=ab och a tillhör L(A). (Med andra ord kan LR-utgången fortsätta x_... = ab_...:: abc_...:: aA_...:: S_.) I dessa termer är L(A:b) mängden av strängar som överensstämmer med situationen A:b_, L(A)
- kedjor som överensstämmer med situation A:_b, för varje regel A:b.
Låt V(u) vara uppsättningen av situationer som överensstämmer med u. Låt oss visa att funktionen V är induktiv.
Om mängden V(u) inkluderar situationen A:b_cd, så tillhör situationen A:bc_d V(uc). (c - terminal eller icke-terminal; b, d - sekvenser (kan vara tomma) av terminaler och icke-terminaler). Det finns inga andra situationer av formen A:b_d, med icke-tomt b i V(uc). Det återstår att lägga till situationer av formen C:_... till V(uc), för varje icke-terminal C vars vänstra kontext innehåller uc. Om situation A:..._C... (C-icketerminal) tillhör mängden V(uc), så tillhör uc L(C) och V(uc) inkluderar situationer av formen C:_... för alla C- grammatikregler.
V(e) innehåller situationer S:_... (S-starttecken), samt situationer A:_... om det icke-terminala A inträffar omedelbart efter _ i situationer som redan ingår i V(e).
Slutligen är vi redo att definiera en LR(0) grammatik. Låt u vara innehållet i stacken under LR-parsning, och V(u) vara uppsättningen av LR(0)-situationer som överensstämmer med u. Om V(u) innehåller en situation av formen A:x_ (x-sekvens av terminaler och icke-terminaler), så tillhör u L(A:x) och faltningen av x till A är tillåten ) innehåller situationen A:..._a .. (a-terminal), då tillåts ett skift. En skift-reduktionskonflikt sägs existera om både skift och faltning är tillåtna för samma kedja u. En faltningsreduktionskonflikt sägs föreligga om faltningar enligt olika regler är tillåtna.
En grammatik kallas LR(0) om det inte finns några skift-minska eller vik-reducerande konflikter för alla stacktillstånd under LR-inferens.
1.2.1.2 LR(k) - grammatik
Endast stackens tillstånd används för att välja mellan skiftning och vikning i LR(0)-parsning. LR(k)-parsning tar också hänsyn till de första k tecknen i den osynliga delen av inmatningskedjan (den så kallade förskottskedjan). För att motivera metoden bör du noggrant upprepa resonemanget i föregående stycke och göra ändringar i definitionerna.
Vi kommer också att inkludera en förskottskedja i reglernas vänstra sammanhang. Om den högra utgången använder utgången wAu: wvu, så tillhör paret wv,FIRSTk(u) Lk(A:v), och paret w,FIRSTk(u) tillhör Lk(A). Uppsättningen av vänsterkontexter, som i fallet med LR(0), kan beräknas med hjälp av induktion på den vänstra kedjan. Låt oss kalla en LR(k)-situation för ett par: en grammatikregel med en markerad position och en framstegskedja av längd högst k. Vi kommer att separera regeln från förskottskedjan med en vertikal linje.
Vi kommer att säga att kedjan x överensstämmer med situationen A:b_c|t om det finns en LR-utgång: x_yz = ab_yz:: abc_z:: aA_z:: S_, och FIRSTk(z) = t. Reglerna för induktiv beräkning av uppsättningen av tillstånd Vk är följande:
Vk(e) innehåller situationer S:_a|e för alla regler S:a, där S är starttecken. För varje situation A:_Ba|u från Vk(e), varje regel B:b och kedja x tillhörande FIRSTk(au), är det nödvändigt att lägga till situation B:_b|x till Vk(e).
Om Vк(w) inkluderar situationen A:b_cd|u, kommer situationen A:bc_d|u att tillhöra Vk(wc). För varje situation A:b_Cd|u från Vk(wc), varje regel C:f och kedja x tillhörande FIRSTk(du) är det nödvändigt att lägga till situation C:_f|x till Vk(wc).
Vi använder de konstruerade uppsättningarna av LR(k)-tillstånd för att lösa problemet med skift-faltning. Låt u vara innehållet i högen och x vara uppkedjan. Uppenbarligen kan faltning enligt regel A:b utföras om Vk(u) innehåller situationen A:b_|x. Att avgöra om ett skifte är tillåtet kräver noggrannhet om grammatiken innehåller e-regler. I situationen A:b_c|t (c är inte tom) är ett skift möjligt om c startar från en terminal och x tillhör FIRSTk(ct). Informellt sett kan du trycka symbolen längst till vänster på den högra sidan av regeln på stapeln och förbereda den efterföljande faltningen. Om c börjar med en icke-terminal (situationen ser ut som A:b_Cd|t), är det bara möjligt att trycka en symbol på stacken som förberedelse för faltning till C om C inte genererar en tom kedja. Till exempel, i tillståndet V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a det finns inga tillåtna skift, eftersom När man härleder terminalkedjor från A, krävs i något steg att regeln A:e tillämpas på den icke-terminala A som finns i kedjans vänstra ände.
Låt oss definiera mängden EFFk(x), som består av alla element i mängden FIRSTk(x), under vars härledning den icke-terminala delen i den vänstra änden av x (om det finns en) inte ersätts av en tom kedja. I dessa termer är en förskjutning tillåten om det i mängden Vk(u) finns en situation A:b_c|t, c inte är tom och x tillhör EFFk(ct).
En grammatik kallas en LR(k)-grammatik om inget LR(k)-tillstånd innehåller två situationer A:b_|u och B:c_d|v så att u tillhör EFFk(dv). Ett sådant par motsvarar en vik-reduceringskonflikt om d är tom och en skift-veckkonflikt om d inte är tom.
I praktiken används inte LR(k)-grammatik för k>1. Det finns två skäl till detta. Först: mycket stort antal LR(k) anger. För det andra: för alla språk som definieras av en LR(k)-grammatik, finns det en LR(1)-grammatik; Dessutom, för alla deterministiska KS-språk finns det en LR(1)-grammatik.
Antalet LR(1)-tillstånd för praktiskt intressanta grammatiker är också ganska stort. Sådana grammatiker har sällan egenskapen LR(0). I praktiken används oftare en metod mellan LR(0) och LR(1), känd som LALR(1).
1.2.2 LALR(1) - grammatik
Dessa två metoder bygger på samma idé. Låt oss konstruera en uppsättning kanoniska LR(0)-tillstånd i grammatiken. Om denna uppsättning inte innehåller konflikter kan LR(0)-parsern användas. Annars kommer vi att försöka lösa de konflikter som har uppstått genom att överväga en enkaraktärs förskottskedja. Med andra ord, låt oss försöka bygga en LR(1)-parser med många LR(0)-tillstånd.
LALR(1)-metoden (Look Ahead) är som följer. Låt oss introducera en ekvivalensrelation för uppsättningen av LR(1)-situationer: vi kommer att betrakta två situationer ekvivalenta om de skiljer sig endast i sina ledande kedjor. Till exempel är situationerna A:Aa_Ab|e och A:Aa_Ab|a ekvivalenta. Låt oss konstruera en kanonisk uppsättning LR(1)-tillstånd och kombinera tillstånden som består av en uppsättning ekvivalenta situationer.
Om den resulterande uppsättningen av tillstånd inte innehåller LR(1)-konflikter och därför tillåter konstruktionen av en LR(1)-tolkare, sägs grammatiken ha egenskapen LALR(1).
2. Översättarutveckling
2.1 Kravanalys
I denna kursarbete det är nödvändigt att utveckla en pedagogisk översättare i form av en tolk från ett språk som definieras av motsvarande formella grammatik. Det finns fyra huvudsteg i utvecklingen av en tolk:
Designa en lexikalanalysator;
Design av en varuautomat;
Mjukvaruimplementering parser;
Utveckling av en tolkningsmodul.
Utvecklingen kommer att utföras med operativsystemet Windows XP på en personlig IBM dator PC med Intel-processor Pentium IV.
Baserat på mjukvaruutvecklingstrender valdes programmeringsspråket C# för att implementera den pedagogiska översättaren i miljön Visuell Studio 2010.
2.2 Design
2.1.1 Designa en lexikalanalysator
Lexikalisk analys innebär att skanna det översatta (käll)programmet och känna igen de lexem som utgör meningarna i källtexten. Tokens inkluderar i synnerhet nyckelord, operationstecken, identifierare, konstanter, specialtecken, etc.
Resultatet av arbetet med en lexikalanalysator (skanner) är en sekvens av tokens, där varje token vanligtvis representeras av någon kod med fast längd (till exempel ett heltal), såväl som generering av meddelanden om syntaktiska (lexikala) fel , om någon. Om token till exempel är ett nyckelord, ger dess kod all nödvändig information. I fallet med till exempel en identifierare krävs dessutom namnet på den igenkända identifieraren, vilket vanligtvis registreras i en tabell med identifierare, organiserad som regel med hjälp av listor. En liknande tabell behövs för konstanter.
Ett lexem kan beskrivas med två huvuddrag. En av dem är att lexem tillhör en viss klass (variabler, konstanter, operationer, etc.) Det andra attributet definierar ett specifikt element i denna klass.
Den specifika formen av symboltabellen (datastrukturen) spelar ingen roll för lexern eller parsern. Båda behöver bara ge möjligheten att få ett index som unikt identifierar till exempel en given variabel och returnera indexvärdet för att fylla på information om ett givet variabelnamn i symboltabellen.
Att visa ID-tabellen utför två huvudfunktioner:
a) registrera ett nytt namn i tabellen vid bearbetning av variabelbeskrivningar;
b) söka efter ett namn som tidigare registrerats i tabellen.
Detta gör att du kan identifiera felaktiga situationer som flera beskrivningar av en variabel och förekomsten av en obeskriven variabel.
Utvecklingen av en lexikalanalysator är delvis en fråga om modellering olika maskiner att känna igen identifierare, konstanter, reserverade ord etc. Om polletterna olika typer börja med samma tecken eller samma sekvens av tecken, kan det vara nödvändigt att kombinera deras igenkänning.
Genom att köra lexikalanalysatorn delar vi upp vårt program i tokens, varefter varje token klarar en längdkontroll (en token får inte vara mer än 11 tecken). Efter att ha slutfört detta steg kontrollerar vi den korrekta platsen för tokens (sökord var, börja, slut, för, att, göra, slut_för). Sedan analyserar vi variabla lexem - de ska inte innehålla siffror i sin beskrivning och ska inte upprepas. På Sista stadiet Vi kontrollerar rätt stavning av lexem (sökord, okända identifierare). Om minst en av kontrollerna misslyckas, skriver den lexikaliska analysatorn ut ett fel.
Diagrammet för det lexikaliska analysprogrammet visas i bilaga B i figur B.1.
2.2.2 Design av en varuautomat
Låt oss definiera följande grammatik:
G: (Vt, Va, I, R),
där Vt är uppsättningen terminalsymboler, Va är uppsättningen icke-terminalsymboler, I är grammatikens initiala tillstånd, R är uppsättningen grammatikregler.
För denna grammatik definierar vi uppsättningar av terminala och icke-terminala symboler:
Låt oss sammanställa reglerna för vår grammatik G och presentera dem i Tabell 1.
Tabell 1 - Grammatikregler
|
Regel nr. |
Vänster sida av regeln |
Höger sida av regeln |
|
|
f ID = EX t EX d LE n; |
|||
|
Fortsättning av tabell 1. |
|||
|
Regel nr. |
Vänster sida av regeln |
Höger sida av regeln |
|
Beteckningarna på lexem, översättningen av lexem till koder och en lista över grammatiska beteckningar ges i tabellerna 2, 3, 4, respektive.
Tabell 2 - Beteckningar på lexem
|
Tokenbeteckning |
||
|
sökord "börja" (början av beskrivningen av åtgärder) |
||
|
sökord "slut" (beskrivning av åtgärdens slut) |
||
|
nyckelord "var" (variabelbeskrivning) |
||
|
nyckelord "läs" (datainmatningsoperator) |
||
|
nyckelord "write" (datautgångsoperator) |
||
|
nyckelord "för" (loopsats) |
||
|
nyckelord "till" |
||
|
sökord "gör" |
||
|
nyckelord "end_case" (slut på loop-sats) |
||
|
variabeltyp "heltal" |
||
|
tilläggsoperation |
||
|
subtraktionsoperation |
||
|
multiplikationsoperation |
||
|
separatortecken ":" |
||
|
separatortecken ";" |
||
|
skiljetecken "(" |
||
|
separatortecken ")" |
||
|
separatortecken "," |
||
|
Tokenbeteckning |
||
|
skiljetecken "=" |
Tabell 3 - Översättning av lexem till koder
|
<цифра> |
||
|
<буква> |
||
Tabell 4 - Lista över grammatiksymboler
|
Beteckning |
Förklaring |
|
|
Program |
||
|
Beskrivning av beräkningar |
||
|
Beskrivning av variabler |
||
|
Lista över variabler |
||
|
Operatör |
||
|
Uppdrag |
||
|
Uttryck |
||
|
Underuttryck |
||
|
Binära operationer |
||
|
Unära operationer |
||
|
Lista över uppdrag |
||
|
Identifierare |
||
|
Konstant |
Låt oss bygga en deterministisk bottom-up-igenkännare.
Betrakta följande relationer för att konstruera en deterministisk bottom-up-igenkännare:
a) Om det finns en symbol för grupp B så att någon grammatikregel inkluderar kedjan AB och det finns en symbol xFIRST"(B), så kommer vi att anta att relationerna x EFTER A bestäms mellan symbolerna x och A
b) Om det i en given grammatik finns en regel B -> bAb A, BV a, b så bestäms relationen A COVER x mellan A och x.
All vår grammatik förblir densamma, det vill säga:
G: (Vt, Va, I, R),
och reglerna för grammatik G ges i tabell 5.
Tabell 5 - Grammatikregler
|
Regel nr. |
Vänster sida av regeln |
Höger sida av regeln |
|
|
f ID = EX t EX d LE n;? |
|||
|
Fortsättning av tabell 5. |
|||
|
Regel nr. |
Vänster sida av regeln |
Höger sida av regeln |
|
Var? - markör för slutet av kedjan.
Låt oss definiera några fall:
a) ID består av många bokstäver i det latinska alfabetet, det vill säga vi kommer att anta att u = ( a, b, c, d, e, f, g, h, i, j, k, l, m, n , o, p, q, r, s, t, u, v, w, x, y, z)
b) CO-konstanten består av tal, det vill säga vi antar att k = (0,1,2,3,4,5,6,7,8,9)
För att vår grammatik ska vara en blandad prioritetsstrategi måste följande villkor vara uppfyllda:
a) Brist på e-regler
b) Finns det regler under vilka, x EFTER A? A VERT x = ?
c) A -> byYg
och det är nödvändigt att IN EFTER x? B VERT x = ?
det vill säga i grammatiken kommer de att exekveras IN EFTER x eller A EFTER x, där x är predikatsymbolen för kedjan b.
a) FIRST"(PG)=(PG?)
FIRST"(RG) = FIRST(DE) = (RG, v,:, i,;)
FIRST" (AL) = FIRST (b LE e)= (AL, b, e)
FIRST" (DE) = FIRST (v LV: i;) = (DE, v,:, i,;)
FIRST" (LV) = FIRST (ID, LV) = (LV, ID)
FIRST" (OP) =(OP, ID, CO)
FIRST" (EQ) = FIRST(ID = EX;) = (EQ, =,;)
FIRST" (EX) = (EX, SB, -)
FIRST" (BO) =(B0, +,*,-)
FIRST" (SB) = FIRST((EX)SB) ? FIRST(OP) ? FIRST(BO)=(SB, (,), OP, BO);
FIRST" (LE) = FIRST(EQ) = (LE, (,), =,;, f, t, d, n, w, r)
FIRST" (UO) = (UO,-)
FIRST" (ID)= FIRST" (u) = (u)
FIRST" (CO) = FIRST" (k) = (k)FIRST" (e) =( e)
FIRST" (b) =( b)
FIRST" (e) =( e)
FIRST" (v) =( v)
FIRST" (w) =( w)
FIRST" (r) =( r)
FIRST" (i) =( i)
FIRST" (f) =(f)
FIRST" (d) =(d)
FIRST" (n) =( n)
FIRST" (c) =( c)
FIRST" (+) =( +)
FÖRSTA" (*) =( *)
FÖRSTA" (-) =( -)
FÖRSTA" (,) =(,)
FÖRSTA" (;) =(;)
FÖRSTA" (:) =(:)
FÖRSTA" (=) = ( = )
FÖRSTA" (() =( ()
FIRST" ()) =() )
FIRST" (u) =(u)
FIRST" (k) =(k)
b) SPÅR `(AL) = (?)?
NÄSTA ` (DE) = (?)?FIRST"(AL)= (?, b, e)
NÄSTA ` (LV) = (?)?FIRST"(:)= (?,:)
NÄSTA ` (OP) = (?)?FIRST"(SB)= (?,;,), d, t, +, -, *)
SPÅR ` (EQ) = (?)?FIRST"(LE)=(?, (,),;, f, =, t, d, n,w,r )
SPÅR ` (EX) = (?)?FIRST"(t)?FIRST"(d)?FIRST"(;)?FIRST"())=(?, t,d,;,))
NÄSTA ` (BO) = (?)?FIRST"(SB)= (?, (,), OP, BO)
NÄSTA ` (UO) = (?)?FIRST"(SB)= (?, (,), OP, BO)
TRACE ` (SB) = (?)? TRACE"(EX)= (?, t,d,;,), +, *, -)
SPÅR ` (LE) = (?) ?FIRST"(e) ?FIRST"(n) = (?, e, n)
SPÅRA `(ID)= (?)? NÄSTA" (OP) ? FÖRSTA" (=) =(?,;,), d, t, +, -, *, =)
SPÅR `(CO) = (?)? SPÅR" (OP)= (?,;,), d, t, +, -, *, =)
NÄSTA ` (b) =(?)?FIRST"(LE)= (?, u, =,;)
SPÅR ` (e) =(?)?
NÄSTA ` (v) =(?)?FIRST"(LV)= (?, u)
NÄSTA ` (w) =(?)?FIRST"(()= (?, ()
NÄSTA ` (r) =(?)?FÖRST"(() = (?, ()
NÄSTA ` (i) =(?)?FIRST"(;)= (?,; )
NÄSTA ` (f) =(?)?FIRST"(ID) = (?, u)
NÄSTA ` (d) =(?)?FIRST"(LE)= (?, u, =,;)
NÄSTA ` (n) =(?)?FIRST"(i) = (?, i)
SPÅR ` (+) =(?)? SPÅR"(IN) = (?, +,*,-)
TRACE ` (-) =(?)? SPÅR"(IN) = (?, +,*,-)
SPÅR ` (*) =(?)? SPÅR"(IN) = (?, +,*,-)
TRACK ` (;) =(?)?TRACK" (DE)?TRACK `(LE1)?TRACK" (EQ) = (?, b, e, l, u)
NÄSTA ` (:) =(?)?FIRST"(i)= (?, i )
NÄSTA ` (=) = (?)?FIRST"(EX) = (? (,), u, k, +, -, *)
NÄSTA ` (() =(?)?FIRST"(DE)= (?, v,:, i,;)
SPÅR ` ()) =(?)? FÖRSTA"(;) = (?,; )
SPÅR ` (,) =(?)? FIRST"(LV) = (?, u)
SPÅR `(u) =(?)? FIRST" (ID)= (u, ?)
SPÅR `(k) =(?)? FIRST (CO)= (?, k)
c) PG ->DE AL
AL EFTER DE = (b,e) EFTER DE = ((b DE), (e DE) )
e EFTER LE = ((e LE))
LE EFTER b = ((,), =,;, f, t, d, n, w, r) EFTER b = (((b), ()b), (=b), (;b), ( f b), (t b), (d b), (n b), (w b), (r b))
;EFTER i = ((; i))
i EFTER: = ( (i:) )
: EFTER LV = ( (: LV) )
LV EFTER v = ( (ID, v) )
LV EFTER, = ((ID,))
EFTER ID = ((,u))
LE EFTER EQ = ((,), =,;, f, t, d, n, w, r ) EFTER EQ = (((EQ), () EQ), (= EQ), (; EQ), ( f EQ), (t EQ), (d EQ), (n EQ), (w EQ), (r EQ))
LE -> r (DE);
; EFTER) = ((;)))
) EFTER DE = (((DE))
DE EFTER (= (= ((v)), (:)), (i)), (;)), (e)))
(EFTER r = (((r))
LE -> w (DE);
; EFTER) = ((;)))
) LAST DE = (((DE))
DE EFTER (= ((v)), (:)), (i)), (;)), (e)))
(EFTER w = (((w))
LE -> f ID = EX t EX d LE n;
; EFTER n = ((;n))
n EFTER LE = ( (n, LE))
LE EFTER d = ((,), =,;, f, t, d, n, w, r)) ? EFTER d = (((d), ()d), (;d), (f d), (t d), (d d), (nd), (w d), (r d))
d EFTER EX = ((d, EX))
EX EFTER t = (BO, -) ? EFTER t = ((BO t), (- t))
t EFTER EX = ( t EX)
EX EFTER = = ((BO, -) ? EFTER = = ((BO =), (- =))
EFTER ID = ((= ID))
ID EFTER f = ((ID f))
EQ -> ID = EX;
; EFTER EX = ((; EX )
EX EFTER = = (BO, -) ? EFTER = = ((BO =), (- =))
EFTER u = ( (=u))
SB EFTER UO = ( (,), OP, BO ) EFTER UO = (((UO), (OP UO), (BO UO) )
) EFTER EX = ( ()EX) )
EX EFTER (= (BO, -) ? EFTER (= ((BO (), (- ())
SB->SB BO SB
SB EFTER BO = ((,), OP, BO) EFTER BO = (((BO), ()BO), (OP BO), (BO BO))
BO EFTER SB = (+,*,-) EFTER SB = ((+SB), (*SB), (-SB))
ID EFTER u = ((u, u))
G) PG ->DE AL
AL COLLECTION PG = AL COLLECTION TRACE" (PG) = ((AL ?))
e COLLECTION AL = e COLLECTION TRACE"(AL)= ((eb), (e?))
=; SAMLINGSPÅR"(DE) = ((;b), (;?))
LV COLLECTION LV = LV COLLECTION TRAIL" (LV) = ((LV:), (LV?))
ID-INSAMLING LV = ID-INSAMLINGSPÅR" (LV) = ((ID:), (ID ?))
; COLLAPSE LE =; SAMLINGSPÅR" (LE) = ((; e), (;?), (; n))
LE -> f ID = EX t EX d LE n;
; COLLAPSE LE =; SAMLINGSPÅR" (LE) = ((; e), (;?), (; n))
EQ COLLECTION LE = EQ COVER TRACE" (LE) = ((EQ e), (EQ?), (EQ n))
EQ -> ID = EX;
; COLLAPSE EQ =; SAMLINGSPÅR" (EQ) = ((; (), (;)), (;;), (;f), (;?), (;=), (;t), (;d), (; n), (;w), (;r))
SB COLLECTION EX = SB COVER TRACE" (EX) = ((SB t), (SB?), (SB d), (SB)), (SB;), (SB(), (SB=), (SBf) ), (SBn), (SBw), (SBr) )
) COLLECTION SB = SB COLLECTION TRACE" (SB) = (() t), ()?), () d), ())), ();))
OP COLLECTION SB = OP COLLECTION TRACE" (SB) = ((OP t), (OP ?), (OP d), (OP)), (OP;))
SB->SB BO SB
SB COLLECTION SB = SB COVER TRACE" (SB) = ((SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB? ) }
SAMLING UO = - SAMLINGSPÅR" (UO) = ( (-?), (--))
SAMLING BO = + SAMLINGSPÅR" (BO) = ((++), (+?), (+*), (+-))
* SAMLING BO = * SAMLINGSPÅR" (BO) = ((*+), (*?), (**), (*-))
SAMLING BO = - SAMLINGSPÅR" (BO) = ((-+), (-?), (-*), (--))
ID-INSAMLING OP = ID-TÄCKNING SPÅR" (OP) = ((ID+), (ID?), (ID*), (ID-))
CO COVER OP = CO COVER SPÅR" (OP) = ((CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))
ID-INSAMLING ID = ID-INSAMLINGSPÅR" (ID) = ((ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt) , (IDd)))
u SAMLINGS-ID = l SAMLINGSPÅR" (ID) = ((u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (ud)))
CO COVER CO = CO COVER SPÅR" (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))
k COLLECTION CO = k COLLECTION TRACE" (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k)))
En hittad konfliktsituation när reglerna kollapsar
OP ->ID och ID -> u ID
Vi anger ID1 -> ID, därför skriver vi om regeln ID1 -> u ID
Därför kommer vi att utföra faltningsoperationer.
ID1 SAMLING ID = ID1 SAMLING SPÅR" (ID) = ((ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t) , (ID1d)))
För varje par (x, A)? x EFTER A konstruerar vi en övergångsfunktion som bestämmer överföringsåtgärden??(S 0 , x, A) = (S 0 , A)
? (S0, b, DE) = (S0, DEb)
? (S0, e, DE) = (S0, DEe)
? (S0, e, LE) = (S0, LEe)
? (S0,), b) = (S0, b))
? (SO,;, b) = (SO, b;)
? (S0, (, b) = (S0, b()
? (S0, =, b) = (S0, b=)
? (S0, f, b) = (S0, bf)
? (S0, t, b) = (SO, bt)
? (S0, d, b) = (S0, bd)
? (SO, n, b) = (SO, bn)
? (S0, w, b) = (S0, bw)
? (S0, r, b) = (S0, br)
? (SO,;, i) = (SO, i;)
? (S0, i,:) = (S0, i:)
? (S0,:LV) = (S0,LV:)
? (S0, ID, v) = (S0, vID)
? (S0,ID,) = (S0,ID)
? (S0, u) = (S0, u,)
? (S0, (, EQ)= (S0, EQ()
? (S0,), EQ)= (S0, EQ))
? (S0, =, EQ)= (S0, EQ=)
? (S0,;, EQ)= (S0, EQ;)
? (S0, f, EQ)= (S0, EQf)
? (S0, t, EQ)= (S0, EQt)
? (S0, d, EQ)= (S0, EQd)
? (S0, n, EQ)= (S0, EQn)
? (S0, w, EQ)= (S0, EQw)
? (S0, r, EQ)= (S0, EQr)
? (S0,;,)) = (SO,);)
? (S0, (, DE) = (S0, DE()
? (S0, v,)) = (S0,)v)
? (S0,;,)) = (SO,);)
? (S0, i,)) = (S0,)i)
? (S0,:,)) = (S0,):)
? (S0, e,)) = (S0,)e)
? (S0, (, r) = (S0, r()
? (S0, (, w) = (S0, w()
? (SO,;, n) = (SO, n;)
? (S0, n, LE) = (S0, LEn)
? (S0, (, d) = (S0, d()
? (S0,), d) = (SO, d))
? (SO,;, d) = (SO, d;)
? (S0, f, d) = (S0, df)
? (S0, t, d) = (SO, dt)
? (S0, d, d) = (S0, dd)
? (SO, n, d) = (SO, dn)
? (S0, w, d) = (S0, dw)
? (S0, r, d) = (S0, dr)
? (S0, d, EX) = (S0, EXd)
? (SO, BO, t) = (SO, tBO)
? (SO, -, t) = (SO, t-)
? (S0, t, EX) = (S0, EXt)
? (S0, BO, =) = (S0, =BO)
? (S0, -, =) = (S0, =-)
? (S0, =, ID) = (S0, ID=)
? (S0, ID, f) = (S0, fID)
? (S0,;, EX) = (S0, EX;)
? (S0, =, u) = (S0, u=)
? (S0, (, UO) = (S0, UO()
? (S0, OP, UO) = (S0, UO OP)
? (S0, BO, UO) = (S0, UO BO)
? (S0,), EX) = (S0, EX))
? (S0, BO, () = (S0, (BO)
? (S0, BO, -) = (S0, -BO)
? (S0, (, BO) = (S0, BO()
? (S0,),BO) = (S0,)BO)
? (S0, OP, BO) = (S0, BOOP)
? (S0, +, SB) = (S0, SB+)
? (S0, *, SB) = (S0, SB*)
? (S0, -, SB) = (S0, SB-)
? (S0, u, u) = (S0, uu)
För varje par (x, A)? Och CONVERT x bygger vi en övergångsfunktion som bestämmer faltningens verkan?? * (SO, x, bA) = (SO, B), där B->bA
? * (S 0 , AL, ?) = (S 0 , PG)
? * (S 0 , e, b) = (S 0 , AL)
? * (S 0 , n, ?) = (S 0 , AL)
? * (SO ,;, b) = (SO, DE)
? * (S 0 ,;, ?) = (S 0 , DE)
? * (SO ,;, e) = (SO, DE)
? * (S 0 , LV,:) = (S 0 , LV)
? * (S 0 , LV, ?) = (S 0 , LV)
? * (S 0 , ID, ?) = (S 0 , LV)
? * (S 0 , ID, e) = (S 0 , LV)
? * (S 0 ,;, e) = (SO , LE)
? * (S 0 ,;, ?) = (S 0 , LE)
? * (S 0 ,;, n) = (SO , LE)
? * (S 0 , EQ, n) = (S 0 , LE)
? * (S 0 , EQ, e) = (S 0 , LE)
? * (S 0 , EQ, ?) = (S 0 , LE)
? * (S 0 ,;, e) = (SO , LE)
? * (S 0 ,;, ?) = (S 0 , LE)
? * (S 0 ,;, () = (S 0 , EQ)
? * (S 0 ,;,)) = (S 0 , EQ)
? * (S 0 ,;, f) = (S 0 , EQ)
? * (S 0 ,;, =) = (S 0 , EQ)
? * (S 0 ,;, t) = (S 0 , EQ)
? * (S 0 ,;, d) = (S 0 , EQ)
? * (S 0 ,;, n) = (S 0 , EQ)
? * (S 0 ,;, w) = (S 0 , EQ)
? * (S 0 ,;, r) = (S 0 , EQ)
? * (S 0 , SB, ?) = (S 0 , EX)
? * (S 0 , SB, d) = (S 0 , EX)
? * (S 0 , SB,)) = (S 0 , EX)
? * (S 0 , SB,;) = (S 0 , EX)
? * (S 0 , SB, w) = (S 0 , EX)
? * (S 0 , SB, r) = (S 0 , EX)
? * (S 0 , SB, f) = (S 0 , EX)
? * (S 0 , SB, =) = (S 0 , EX)
? * (S 0 , SB, t) = (S 0 , EX)
? * (S 0 , SB, ?) = (S 0 , SB)
? * (S 0 , SB, () = (S 0 , SB)
? * (S 0 , SB,)) = (S 0 , SB)
? * (S 0 , SB, u) = (S 0 , SB)
? * (S 0 , SB, k) = (S 0 , SB)
? * (S 0 , SB, +) = (S 0 , SB)
? * (S 0 , SB, -) = (S 0 , SB)
? * (S 0 , SB, *) = (S 0 , SB)
? * (S 0 , SB, e) = (S 0 , SB)
? * (S 0 ,), t) = (S 0 , SB)
? * (S 0 ,), ?) = (S 0 , SB)
? * (S 0 ,), t) = (S 0 , SB)
(S 0 ,),)) = (S 0 , SB)
? * (S 0 ,),;) = (S 0 , SB)
? * (S 0 , -, ?) = (S 0 , UO)
? * (S 0 , -, -) = (S 0 , UO)
? * (S 0 , +, +) = (S 0 , BO)
? * (S 0 , +, ?) = (S 0 , BO)
? * (S 0 , +, *) = (S 0 , BO)
? * (S 0 , -, +) = (S 0 , BO)
? * (S 0 , -, ?) = (S 0 , BO)
? * (S 0 , -, *) = (S 0 , BO)
? * (S 0 , -, -)) = (S 0 , BO)
? * (S 0 , *, +) = (S 0 , BO)
? * (S 0 , *, ?) = (S 0 , BO)
? * (S 0 , *, *) = (S 0 , BO)
? * (S 0 , *, -)) = (S 0 , BO)
? * (S 0 , u, +) = (S 0 , BO)
? * (S 0 , u, ?)= (S 0 , BO)
? * (S 0 , u, *) = (S 0 , BO)
? * (S 0 , u, -)) = (S 0 , BO)
? * (S 0 , k, +) = (S 0 , BO)
? * (S 0 , k, ?) = (S 0 , BO)
? * (S 0 , k, *) = (S 0 , BO)
? * (S 0 , k, -)) = (S 0 , BO)
? * (S 0 , CO, ?) = (S 0 , OP)
? * (S 0 , CO, +) = (S 0 , OP)
? * (S 0 , CO, *) = (S 0 , OP)
? * (S 0 , CO, -) = (S 0 , OP)
? * (S 0 , CO,;) = (S 0 , OP)
? * (S 0 , CO, d) = (S 0 , OP)
? * (S 0 , CO, t) = (S 0 , OP)
? * (S 0 , ID, -) = (S 0 , OP)
? * (S 0 , ID, *) = (S 0 , OP)
? * (S 0 , ID, ?) = (S 0 , OP)
? * (S 0 , ID, () = (S 0 , OP)
? * (S 0 , ID,)) = (S 0 , OP)
? * (S 0 , ID, u) = (S 0 , OP)
? * (S 0 , ID, k) = (S 0 , OP)
? * (S 0 , ID, -) = (S 0 , OP)
? * (S 0 , ID, +) = (S 0 , OP)
? * (S 0 , u,)) = (S 0 , I OP)
? * (S 0 , ID1, *) = (S 0 , ID)
? * (S 0 , ID1, ?) = (S 0 , ID)
? * (S 0 , ID1, () = (S 0 , ID)
? * (S 0 , ID1,)) = (S 0 , ID)
? * (S 0 , ID1, u) = (S 0 , ID)
? * (S 0 , ID1, k) = (S 0 , ID)
? * (S 0 , ID1, -) = (S 0 , ID)
? * (S 0 , ID1, +) = (S 0 , ID)
? * (S 0 , u,)) = (S 0 , ID)
? * (S 0 , u, ?) = (S 0 , BO)
? * (S 0 , u, k) = (S 0 , ID)
? * (S 0 , u, *)) = (S 0 , ID)
? * (S 0 , u, -)) = (S 0 , ID)
? * (S 0 , u, +)) = (S 0 , ID)
? * (S 0 , u, d)) = (S 0 , ID)
? * (S 0 , u, t)) = (S 0 , ID)
? * (S 0 , u, =)) = (S 0 , ID)
? * (S 0 , CO, ?) = (S 0 , CO)
? * (S 0 , CO, +) = (S 0 , CO)
? * (S 0 , CO, -) = (S 0 , CO)
? * (S 0 , CO, *) = (S 0 , CO)
? * (S 0 , CO,;) = (S 0 , CO)
? * (S 0 , CO, d) = (S 0 , CO)
? * (S 0 , CO, t) = (S 0 , CO)
? * (S 0 , CO,)) = (S 0 , CO)
? * (S 0 , k, +) = (S 0 , CO)
? * (S 0 , k, -) = (S 0 , CO)
? * (S 0 , k, *) = (S 0 , CO)
? * (S 0 , k,;) = (S 0 , CO)
?? * (S 0 , k, d) = (S 0 , CO)
? * (S 0 , k, t) = (S 0 , CO)
? * (S 0 , k,)) = (S 0 , CO)
? * (S 0 , k, () = (S 0 , CO)
2.2.3 Programimplementering av parsern
Den syntaktiska analysatorn (parser) läser lexemfilen som genereras av lexikalanalysatorn, utför grammatisk analys och skickar meddelanden om syntaxfel om tillgängligt, och skapar en mellanform för inspelning av originalprogrammet. Grunden för utvecklingen av en parser är designen och implementeringen av motsvarande magasinmaskin.
För bottom-up-parsning för en deterministisk bottom-up-parser efter att ha reducerat den till rätt typ Det krävs att man använder funktionerna EFTER och COVER för att designa en magasinsmaskin med detaljerad beskrivning alla övergångar inom övergångsfunktionen.
När vi utvecklade en varuautomat byggde vi övergångsfunktioner som kommer att ligga till grund för parsern. Alla övergångsfunktioner kan delas in i två typer:
Driftcykeln för en magasinsmaskin utan att läsa inmatningssymbolen (tom cykel);
Funktionstakt för en magasinsmaskin med läsning av inmatningssymbolen.
När vi implementerade lexikalanalysatorn delade vi in programmet i lexem och skrev in dem i en lista. Vi bearbetar sedan denna lista i parsern. Vi skickar vårt program (lista), startsymbolen (PG) och bottenmarkören på magasinsmaskinen (h0) till ingången, varefter vi väljer önskad funktionövergång och ett rekursivt anrop görs.
Diagrammet för parserprogrammet visas i bilaga B i figur B.2.
2.2.4 Utveckling av tolkningsmodulen
När man utvecklar en tolkningsmodul som en mellanform av det ursprungliga programmet Postfix-formen av notation används oftast, vilket gör det ganska enkelt att implementera processen att exekvera (tolka) det översatta programmet.
Låt oss överväga de grundläggande principerna för att bilda och utföra postfix-formen för skrivuttryck.
De grundläggande reglerna för att konvertera ett infix-uttryck till ett postfix-uttryck är följande.
Läsoperanderna läggs till i postfix-notationen och operationerna skrivs till stacken.
Om operationen överst i stacken har en högre (eller lika stor) prioritet än den för närvarande lästa operationen, läggs operationen på stacken till i postfix-posten och den aktuella operationen skjuts in i stacken. I annat(vid lägre prioritet) skjuts endast den aktuella operationen in i stacken.
Läsöppningsparentesen skjuts upp på stapeln.
Efter att stängningsstaget är avläst, poppas alla operationer fram till första öppningsstag från stapeln och läggs till postfix-inmatningen, varefter både öppnings- och stängstag kasseras, d.v.s. placeras inte på en postfix-post eller på stacken.
Efter att hela uttrycket har lästs läggs de återstående operationerna på stacken till postfix-posten.
Postfix-notation av ett uttryck gör att det kan beräknas enligt följande.
Om token är en operand skrivs den till stacken. Om token är en operation, utförs den angivna operationen på de sista elementen (sista elementet) som skrivits till stacken, och dessa element (elementet) ersätts på stacken av resultatet av operationen.
Om de lexikala och syntaktiska analyserna har slutförts framgångsrikt, går vi vidare till tolkning. Först gör vi meningar av orden, sedan översätter vi uttrycken till postfix-notation och beräknar.
Tolkens driftdiagram visas i bilaga B i figur B.3.
2.3 Kodning
Programmet är implementerat i C# i programmeringsmiljön Visual Studio 2010. Programmets text presenteras i Appendix A.
Programmet innehåller fem klasser. Användargränssnittet implementeras med klassen MainForn. Med klassen LexAnalysis implementeras en lexikalanalysmodul, SynAnalysis är en syntaktisk analysmodul, Interpreter är en tolkningsmodul, ProgramisciJakPolska är en hjälpklass för att översätta uttryck till omvänd polsk notation (postfix).
Syftet med de procedurer och funktioner som implementeras i programmet beskrivs i tabellerna 6,7,8.
Tabell 6 - Syfte med procedurer och funktioner för lexikal analys
Liknande dokument
Översättare som program eller tekniska medel, sänder programmet. Övervägande av huvuddragen i konstruktionen av en lexikal analysator. Introduktion till stadierna för att utveckla en översättare från en begränsad delmängd av ett högnivåspråk.
kursarbete, tillagt 2013-06-08
Lexikal och parserdesign pedagogiskt språk. Regler för att konvertera logiska uttryck till POLYZ. Bildande av triader, optimering av deras lista. Programmets logiska struktur. Testa översättare-tolkmoduler.
kursarbete, tillagd 2013-05-28
generella egenskaper och bedömning av funktionerna hos programmeringsspråket C-Sharp, dess likheter och skillnader från C++ och Java. Utveckling med av detta språk programmering av en lexikal och syntaktisk analysator. Rita upp parsningstabeller.
kursarbete, tillagt 2010-11-06
Designa ett analysprogram bestående av två delar: en lexikalanalysator som går sönder original text program för lexem och fylla i namntabellen; en parser som kontrollerar att texten överensstämmer med en given grammatik.
kursarbete, tillagd 2010-06-14
Att skriva ett program som utför lexikal och syntaktisk analys av det inmatade programmeringsspråket, genererar en tabell med lexem som anger deras typer och värden, och bygger också ett syntaxträd; texten för inmatningsspråket skrivs in från tangentbordet.
kursarbete, tillagt 2012-02-23
Metod för utveckling och partiell implementering av en översättare för C-språket med hjälp av C++-språket, som delar upp den ursprungliga kedjan av tecken i minimala odelbara språkkonstruktioner baserat på språkets vokabulär. Analys av programmets verksamhet.
kursarbete, tillagt 2012-03-19
Struktur, klassificering och krav för kompilatorimplementering. Design och implementering av den analyserande delen av C++ språkkompilatorn. Metoder för att implementera lexikal analys. Algoritm för driften av parsern. Principer för mjukvaruimplementering.
kursarbete, tillagt 2013-01-26
Skapande av en översättare som bearbetar programkod i Pascal och, med likvärdiga operatorer, genererar ett program i C. Egenheter extern specifikation och lexikalanalysatorns arbete. Programstruktur, visar resultat på skärmen.
kursarbete, tillagt 2011-02-07
Metoder för grammatisk analys. Utveckling av strukturen för en pedagogisk översättare utifrån grundläggande språk programmera Object Pascal i en objektorienterad miljö visuell programmering Borland DELPHI 6.0 med operativsystemet Windows XP.
kursarbete, tillagt 2013-12-05
Mjukvaruimplementering av en skrivbordsapplikation med programmeringsspråket C#. Design och struktur användargränssnitt, krav på det och bedömning av funktionalitet. Utveckling av en användarmanual och dess användning.
