Kompilatorer och interpretatorer
torsdag 13 januari 2022
Gäller som tentamen för:
DT501A Kompilatorer och interpretatorer för civilingenjörer, provkod A001
| Hjälpmedel: | Inga hjälpmedel. |
| Poängkrav: |
Maximal poäng är 40.
För godkänt betyg krävs totalt minst 22 poäng. |
| Resultat: | Meddelas senast torsdag 3 februari 2022. |
| Återlämning av tentor: | Elektroniskt via webbportalen Studenttjänster. |
| Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070 - 73 47 013. |
A är en icke-terminal, men x och y står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.A -> A x | y
Regeln ersätts av följande två regler (eller, korrektare uttryckt, tre produktioner), som beskriver samma språk men som inte är vänsterrekursiva:
A -> y R R -> x R | empty
A är en icke-terminal, men x, y och z står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.A -> x y | x z
Skriv om till dessa tre produktioner:
A -> x R R -> y | z
a) Skriv upp vad faserna heter, och numrera dem i deras logiska ordning.
b) Vilken fas hör var och en av termerna nedan ihop med? Det kan hända att en del passar in på mer än en fas. Det kan hända att en del inte passar in på någon fas alls.
Skriv fasens nummer enligt ditt svar på a-delen vid varje term, och lämna in det här bladet tillsammans med dina övriga svar!
aktiveringspost aktuell token anropskonventioner anropsstack basic block Bison copy propagation dataflödesanalys dekorerat parse-träd dynamisk länkning eliminering av svansrekursion eliminering av vänsterrekursion FIRST()-konflikt flödesgraf Flex gemensamma deluttryck grammatik heap icke-terminal instruktionsval kontextfri grammatik Lex lexem lexikaliskt värde LL(1) lookahead loop unrolling LR(1) operatorprioritet operatorassociativitet parse-träd produktion reduce-reduce-konflikt registerallokering shift-reduce-konflikt skräpsamling startsymbol statiska data statisk länkning syntaxträd terminal token treadresskod tvetydig grammatik typkontroll typsystem vänsterrekursion Yacc
a = 1; b = 2; if (c < d * e + f * g * h) { j = 3; while (j < k) { j = j + 4 * m; k = 5; } k = 6; }
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod. (Skulle du svara på alla tre, räknas den med högst poäng bort.)
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Observera: Två av typerna, inte alla tre!
{ "förnamn" : "Emma", "efternamn" : "Svensson", "ålder" : 25, "adress" : { "gatuadress" : "Drottninggatan 47", "postort" : "Boden", "postnummer" : "96 177" }, "telefonnummer" : "070-1234567" }
Vi ska arbeta med en delmängd av JSON, som vi kan kalla Mini-JSON. Mini-JSON innehåller:
Den som känner till hur JSON ser ut på riktigt ser att vi saknar en del saker i Mini-JSON, främst arrayer, icke-hela tal, booleska värden och värdet null. Exemplet ovan är giltig Mini-JSON. Här är några ytterligare exempel på objekt som man kan uttrycka med Mini-JSON:
{ }
{ "namn" : "Örebro", "befolkning" : 126009, "latitud" : 59, "longitud" : 15 }
JSON kan skrivas på fritt format. Det sista exemplet ovan skulle också kunna skrivas så här:
{ "typ" : "rektangel", "hörn-1" : { "x" : 17, "y" : 26 }, "hörn-2" : { "x" : 220, "y" : 120 } }
{"typ":"rektangel","hörn-1": {"x" :17,"y":26},"hörn-2":{"x":220,"y":120}}
b) (2p) En del av terminalerna har inte fixa lexem, utan kan se olika ut. Skriv, för varje sådan terminal, ett reguljärt uttryck som beskriver hur den får se ut!
{ "namn" : "Örebro", "befolkning" : 126009 }