contextual analysis (semantic analysis)

"Sproget har samme feature som fx java, med at erklæringer kan komme senere end brugen af en variabel."

Du skal erklære en variabel i java før du kan bruge den.

men det var jo ikke spørgsmålet ;) jeg er selv kun igang med AST.. så er ikke lige kommet dertil endnu.. men jeg mener at hvis du sidder med "compiler construction" -kenneth c louden, så bliver det forklaret i kapitel 6.3.

jeg kigger lige på det, så kan det være jeg vender tilbage hvis jeg har et svar.

Ja. Altså det er kun i funktioners tilfælde java tillader kald før deklaration

Jeg vil faktisk heller ikke tillade brug af variabeler før erklæring, nu du siger det!
Men funktioner skal virke som i java uden forward deklæringer!

Bare man kunne finde en dokumentation eller kode til java compileren men det kan jeg umiddelbart ikke.

jeg kender kke kenneth c louden

mit eget compiler projekt er en compiler til et subset af java

http://java.sun.com/docs/books/jls/ ( java language specification )
og http://java.sun.com/docs/books/vmspec/ (The JavaTM Virtual Machine Specification)

kan være til meget hjælp.

og så kan jeg anbefale dig
Programming for the Java™ Virtual Machine
By Joshua Engel

hvis du skal lave bytecode.

jeg kigger stadig på scope..

Hvad med en symboltabel pr. funktion - funktionernes variable er vel disjunkte selvom de har samme ID ?


Jeg vil antage at du mener:
function x()  // Scope level 1
{
  z = 12;
}

og IKKE:
function x()  // Scope level 1
{
int z;
}

(Du skriver at variable ikke skal decl før brug..)

compiler construction -kenneth c louden
"to implement nested scopes and the most closely nested rule, the symbol table insert operation must not overwrite previous declarations, but must temporarily hide them, so that lookup operation only findes the most recently inserted declaration for a name. Similary, the delete operation must not delete all declarations corrosponding to a name, but only the most recent one, uncovering any previus insert operations for all of the same names on exit from the block. In other words, the symbol table behaves in a stackline manner during the processing of nested scopes.


forslag til implementation er
nyt symbol table pr scope, link dem sammen så lookup automatisk fortsætter i et nyt table hvis det ikke finder noget i det der søges i.

Det lyder som noget ala det samme der står i min bog [Appel]. Det kan nemt håndteres med en liste.

Men man kunne også udnytte kald-stakken ved rekursive kald på AST - så kan kald-stakken håndtere scope-reglerne mere eller mindre automatisk. Så håndterede den compiler jeg har været med til at lave, scope-reglerne. Men den er så også skrevet i SML - i Java er det nok ikke så nærlæggende en løsning.. :-)

soreno/zaknafein af ren nysgerighed hvordan implementere/de i det.. sprog/værktøjer m.m? helt fra bunden eller med genetatorer.

jeg bruger selv jflex(java flex impl) og cup(java yacc impl). jeg implementerede godt nok scanneren selv men da jeg vil have en bottom-up parser hvilket ville være alt for kompiliceret/tidskrevede og valgte at bruge generator til det udskiftede jeg også min scanner da der er indbygget support i cup for jflex.

Jeg bruger sablecc en LALR(1) parser.

soreno:
Jeg mente det jeg skrev. Men variabler skal erklæres inden brug . Funktioner skal ikke.

Nested scope problemetikken er nem i sig selv.
Problemet er sammen med multi pass.

tag koden:

programStart // scope Level 0
int x = 9; // level 0 var

  function one()
  {
  int x; //level 1
  }
function two()
{
  int x = 7; // level 1
}
  function three() // level 1
  {
    for(;;) // Level 2
    {
    x = 15; // Er ikke erklæret her. Men er erklæret i level 0
    }
   
  }
programEnd

Første gang løber jeg variabel- og funktions erklæringer igennem og gemmer dem i det pågældende scope.
Symboltabel:

Level 0:
  x
Level 1_0  (1_0 for at kende forskel på 2 level 1 scopes)
x
Level 1_1  (1_1 for at kende forskel på 2 level 1 scopes)
x
Level 1_2  (her er ingen erklæringer

Level 2    (ingen erklæringer.)

Jeg godt lave en ny tabel pr scope, men problemet er at der er flere level 1 scopes.
Problemet er så i 2. gennemløb når jeg støder på brug af variablen x = 15; Så skal den kigge i nuværende scope, som styres af en scope_level integer fx. Men ydermere skal jeg har en fortløbende counter når der er flere scopes med samme level!

Så når jeg, når til x = 15; kan jeg se den ikke er i scope 1. Så ville man normalt bare kigge i et scope lavere, men det kan jeg ikke da det IKKE er gyldigt at den er erklæret i fx function 2, som jo også er højere oppe.
På en eller anden måde skal jeg vide hvilket scope der er parent, når jeg kommer til andet genmnemløb.

simonvalter:

Efter bogens [Appel] opskrift:

Lexer
  ml-lex

Parser
  ml-yacc (LALR parser)

Semantisk analyse
  scope, environment og type check
  (Et djævlsk monster-modul!)

Frame analyse
  Generering af MIPS frames
   
Intermediate repræsentation
  Træstruktur, så man slipper for n*m problematikken
  (for at kunne genbruge nogle faser af compilere)

Instruktionsselektion
  Maximal-munch (grådig) algoritme til at vælge MIPS instruktioner

Registerallokering
  Control- og Dataflow analyse
  Graffarvningsalgoritme til at vælge registre

Det var vist overblikket - set fra 10km højde.

Jeg tror du blander declarationer og flow af programmet sammen.


Som jeg forstår semantikken af dit sprog vil dit eksempel have følgende environment ved eksekvering:
{x=0} //level 0
{x=0::x} // one eksekveres
{x=0} // one er færdig
{x=0::x=7} // two eksekveres
{x=0} // two er færdig
{x=0::ø} // three eksekveres
{x=0::ø::ø} // for-løkke start
{x=15::ø} // for-løkke slut
{x=15} // three er færdig

:: betyder nyt scope


Og så kan jeg ikke se hvad problemet er ?

declarationer og flow hænger da sammen??
det er udelukkende (Semantisk analyse) fasen jeg taler om her.
(Aka contextual analysis)

Hvis jeg bare havde nested scopes og krævede at funktioner var forwadr declererede som i c++, så kunne jeg lave alt i 1 pass.

Her mener jeg:
Identificering (er brugte variabler erklæret)
Scope regler (overholdes scope-semantikken)
typecheck  (evaulerer expressions til de rigtige typer)
decoration af ast (Noder med forekomster af erklærede variabler, erstattes med referencer til erklæringen)

men problemet ligger i at jeg ikke kan afgøre om funktionerne er erklæret i et gennemkøb, da de kan være erklæret efter de bruges, i samme scope!

Du er nødt til at lave (mindst) two-pass.

ja det er også planen.
problemet er stadig at fange det scope en funktion eller variabel er erklæret i, når jeg støder på brugen af den i 2 gennemløb.

I mit indlæg 22:14:22 har jeg skrevet hvordan jeg opfatter scope under udførsel. Er det sådan det skal virke i dit sprog ?

Jeg har løst problemet på følgende måde:
i første gennemløb identificerere jeg erklæringer af variabler og funktioner, og klasser osv.
Hver gang jeg åbner et nyt scope generere jeg en unik scope streng der identificere scopet.
Strengen indeholder scope level _ unik. fx 2_2 og 2_3.

I 2 fase, checker jeg om ting der bliver brugt, er erklæret.
I anden fase kører samme funktion der generere de samme unikke scope strenge, så jeg ved hvilket scope jeg er i.

Derved kan jeg bruge variabler og funktioner før jeg erklærer dem.

Foresten det med at man i Java ikke kan bruge en variabel før man erklærer den! Det kan man godt.
fx

public class Ninja
    {
        public Ninja()
        {
        tis = 7;
        }
    int tis;
    }

Så bruges variablen før den er erklæret. Men det er jo lovligt fordi den er i et scope længere ude.

det er en klasse variabel ikke en lokal variabel.. med lokale variabler kan man ikke.

og dit første eksempel var med lokale variabler ... ;)
instance variabler skal man heller ikke erklære først.

Ja men java understøtter heller ikke frie funktioner, der står uden for klasser.
Det gør mit sprog.

Der kan man programmere ikke objektorienteret hvis man vil.
Derfor vil java eksemplet i mit sprog ikke være klasse variabler.

Ponten er at en var kan været erklæret et scope ude, men stå længere nede kode mæssigt, hvilket er det interessante set ud fra pareserens synspunkt.

den er jo lige glad med semantiske regler, den kører jo bare depth first!

Nu virker de 2 første faser med objektorienteret kode og det hele.

Så det type check fasen. Der kommer nok interessante problemer der også :)