Oblig-faq

Denne siden inneholder svar p? ofte stilte sp?rsm?l om obligene og verkt?y i INF5110 v?ren 2006.

Innhold

1. Oppgaven
   1. Omskriving av grammatikken
      1. Rekkef?lge
      2. Korrigere assosiativitet
   2. Utskrift
      • Hvordan skrive ut noder som ikke er vist i Canonical.ast?
   3. Hva betyr "!"? Er det en logisk NOT-operator?
2. Antlr
   1. Generelt
      • Store og sm? bokstaver i identifikatorer
      • Er det noen gode eksempler i Antlr-distribusjonen?
   2. Vokabularer
      1. Mystiske parserfeil
   3. Skanning
      1. Begrense lengden av terminaler
   4. Lookahead
      1. Syntaktisk lookahead er f?lsomt for rekkef?lge

1. Oppgaven

1.1 Omskriving av grammatikken

1.1.1 Hvilken rekkef?lge b?r man foreta omskrivingene i?

1. Presedenskaskade (se 3.4 i Louden)
2. Skriv om til riktig assosiativitet (se. 3.4.2 i Louden)
3. Fjerne venstrerekursjon (se 4.2.3 i Louden)
4. [Skriv om til EBNF] (vanligvis er EBNF ? foretrekke, se ogs? spm. 2.2)

1.1.2 Hvordan rette opp syntakstr?r som har blitt h?yreassosiative etter fjerning av venstrerekursjon?

1. Bruk EBNF. Antlr genererer kode omtrent som beskrevet i 4.2 av Louden.
2. Bruk en parameter for ? sende venstresida til en syntakstrenode med i en h?yrerekursiv BNF-regel.

      exp : exp "+" exp | NUMBER;
    

      exp : exp "+" NUMBER | NUMBER;
    

      exp : NUMBER exprr;
      exprr : "+" NUMBER exprr | // Empty ;
    

      exp : NUMBER ("+" NUMBER)* ;
    

    exp returns[Exp e]  
    : lhs:NUMBER {e = new Exp(Integer.valueOf(lhs.getText())); } 
      (("+" rhs:NUMBER) 
        { e=new Exp(e, new Exp(Integer.valueOf(rhs.getText()))); }
      )*
    ;
    

    exp returns[Exp e]  
    : lhs:NUMBER e = exprr[lhs] ;

    exprr[Exp lhs] returns [Exp e]
    {
        Exp rhs;
	e = lhs;
    }
    : "+" n:NUMBER {rhs = new Exp(Integer.valueOf(n.getText())); } 
       e=exprr[ new Exp(lhs, rhs)]
    | // Empty  {e = lhs; }
    

1.2 Utskrift

1.2.1 Hvordan skrive ut noder som ikke er vist i Canonical.ast?

Den generelle syntaksen for utskrift av en node er som f?lger:

      node       : "(" NODE_NAME (attributes)* (node)* ")"
      attributes : "ref"
    

hvor NODE_NAME er venstresiden til produksjonen noden er utledet fra i den opprinnelige Diss-grammatikken. N?r det gjelder uttrykk, bruker eksempelet en litt innviklet syntaks:

(ARITH_OP + ... )

Dette kan godt forenkles til bare:

(+ ... )

Konkrete sp?rsm?l:

(BOOL_LITERAL "true")

b =  false && true;

(ASSIGN_STMT (NAME b) (LOG_OP && (BOOL_LITERAL "false") (BOOL_LITERAL "true")))
    

b =  true || b;

(ASSIGN_STMT (NAME b) (LOG_OP || (BOOL_LITERAL "true") (NAME b)))
    

Utskrift av WHILE_STMT: input:

while (condition) { }

b?r bli:

      (WHILE_STMT (NAME condition)
          ()
      )
    

1.3 Hva betyr "!"? Er det en logisk NOT-operator?

Ja. Det er logisk negasjon, som i C* og Java. Dette er den eneste un?re operatoren i spr?ket. Man trenger ikke bry seg om betydningen av denne i oblig 1, annet enn evt. til klassifisering av syntakstretyper, men i oblig 2 skal dens operand typesjekkes som bool.

2. Antlr

2.1 Generelt

2.1.1 Store og sm? bokstaver

Symptom:

    program : (Decl)* EOF ; 

    program : (decl)* EOF ; 

Pass p? bruken av store og sm? bokstaver i Antlr-identifikatorer. Hovedreglen er at terminaler starter med stor forbokstav (og b?r ellers bare inneholde store bokstaver, for ? f?lge konvensjon fra eksemplene), og non-terminaler starter med liten forbokstav.

Er det noen gode eksempler i Antlr-distribusjonen?

Ja, men eksemplene er ofte enten for enkle og banale, eller for vanskelige og omfattende. De jeg hadde mest bruk for var TinyC- og Pascal- og Java-eksemplene, listet opp noenlunde p? stigende brukbarhet og vanskelighetsgrad.

Pascal- og Java-eksemplene (1273 LOC!) er store og omfattende, men demonstrerer sv?rt mange av Antlrs avanserte egenskaper, fiklete skanning, syntaktisk lookahead, og AST-bygging med imagin?re tokens.

2.2 Vokabularer

2.2.1 Mystiske parserfeil p? terminaler

Symptom:

line 19:13: expecting '.', found '.'

Dette, og flere andre ganske merkelige feil p? terminaler, kan skyldes at parseren og skanneren har forskjellig oppfatning av kodeverdier for den samme terminalen i konstant-tabellen. L?sningen er ? s?rge for at parsere og skannere bruker det samme vokabularet med opsjonene importVocab og exportVocab. Sjekk kapitlet om "Token Vocabularies" i referansemanualen.

Antlr byr p? ganske mange m?ter (rekkef?lge mellom skanner og parser i samme fil, byggerekkef?lge, bruk av import og eksport) ? rote med terminaldefinisjonene, s? for ? spare dere for un?dvendig bry skal jeg her gjengi mitt oppsett av grammatikkfiler og vokabular- innstillinger. Mitt l?sningsforslag best?r av tre filer:

• Diss1.g: Konsis, men flertydig grammatikk.
• Diss2.g: Venstrefaktorisert LL(1)-grammatikk
• DissLexer.g: Skanner som brukes av begge parserne

      class Diss2Parser extends Parser;

      options {
          exportVocab = Diss;
      }
    

      /** Scanner. */
      class DissLexer extends Lexer;
      options {
          importVocab=Diss;
	  ...
      }
    

2.3 Skanning

2.3.1 Hvordan begrense lengden til terminaler?

Kort svar: Dessverre st?tter ikke Antlr lengdebegrensninger, som de fleste andre regexp-baserte skannerverkt?y, av typen (eksempel fra en skanner i GNU flex):

      identifier		{letter}{digit_letter_or_underscore}{0,15} 
    

p? en grei m?te. Brute-force-l?sningen med ? repetere en stadig lengre tegnsekvens 1, 2 ... N ganger, er b?de inelegant og produserer advarsler om non-determinisme (kan dog l?ses opsjonen greedy).

Dette er ikke noen viktig del av obligen, s? l?sninger som ikke tilfredsstiller kravet om h?yst 16 tegns lengde p? identifikatorer, er akseptable.

Lengre svar: De som er interessert, kan pr?ve ett s?kalt semantisk validerende predikat p? regelen som kjenner igjen navn i skanneren. Noe ? la:

	NAME : LETTER (DIGIT | LETTER | '_')* { text.length() <= 16 }? ;
      

Variabelen text er en instans av java.lang.StringBuffer i den genererte skannerklassen. Predikatet over kaster ett unntak hvis lengden til identifikatoren overstiger 16 tegn. Imidlertid skaper dette nye problemer med at unntaket ikke fanges opp av Antlrs defaulte feilh?ndtering.

2.4 Lookahead

2.4.1 Syntaktisk lookahead er rekkef?lgesensitivt!

	exp : (NAME | simpleExp DOT) => var
	    | simpleExp
            ; 
      

        exp : simpleExp
            | (NAME | simpleExp DOT) => var
            ; 
      

Det er viktig ? plassere regler med syntaktiske predikater f?r regler de st?r i konflikt med. For detaljer om LL(k)-predikater og rekkef?lge, se avsnittet om "Predicated-LL(k) Lexing" i ref.manualen.