INF5110 - Vår 2006

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
    3. Hva betyr "!"? Er det en logisk NOT-operator?
  2. Antlr
    1. Generelt
    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?

Det f�lgende gjelder uttrykksgrammatikken, f.o.m. produksjonen exp:
  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)
Det viktigste her er skillet mellom det f�rste steget og de tre andre. De siste kan man i st�rre grad blande sammen. Merk at disse omskrivingene m� gj�res i begge grammatikkene, derfor kan det l�nne seg � starte med den konsise, flertydige grammatikken, og bruke den som input (med LL(k)-opsjoner og -predikater fjernet) til venstrefaktorisering i den andre LL(1)-grammatikken.

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

Generelt, s� er det to l�sninger:
  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.
For � gj�re en lang historie kort: Det f�rste alternativet er � foretrekke, det er kortere og klarere, og unng�r komplikasjonene i aksjonskoden som det andre tilf�rer. Eks. flertydig, venstreassosiativ grammatikk: 
      exp : exp "+" exp | NUMBER;
til venstreassosiativ form: 
      exp : exp "+" NUMBER | NUMBER;
etter fjerning av venstrerekursjon: 
      exp : NUMBER exprr;
      exprr : "+" NUMBER exprr | // Empty ;
L�sning 1: � skrive om til EBNF 
      exp : NUMBER ("+" NUMBER)* ;
Med skisse av aksjonskode (se AmbigiousExp.g for ett mer fullstendig eksempel): 
    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()))); }
      )*
    ;
L�sning 2: 
    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: 

(+ ... )
siden n�r man leser terminalen +, s� vet man at den er operator for ett aritmetisk uttrykk, som er ett uttrykk.
Konkrete sp�rsm�l:
Utskrift av true: 
(BOOL_LITERAL "true")
Utskrift av LOG_OP, input 
b =  false && true;
gir: 
(ASSIGN_STMT (NAME b) (LOG_OP && (BOOL_LITERAL "false") (BOOL_LITERAL "true")))
Input 
b =  true || b;
gir: 
(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 ;
i stedet for 
    program : (decl)* EOF ;
genererer og kompilerer, men gir parsefeil run-time.

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:

I parsergrammatikkene Diss(1|2).g, eksporteres terminaldefinisjonene til to filer med prefikset Diss: 
      class Diss2Parser extends Parser;

      options {
          exportVocab = Diss;
      }
I skannergrammatikken DissLexer.g, importeres definisjone eksportert over: 
      /** Scanner. */
      class DissLexer extends Lexer;
      options {
          importVocab=Diss;
	  ...
      }
Man kan droppe eksport-opsjonene p� parserne, og i stedet importere ett av de defaulte parser-vokabularene ("Diss(1|2)Parser").

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!

Eks: 
	exp : (NAME | simpleExp DOT) => var
	    | simpleExp
            ;
parser forskjellig fra 
        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.

2006-03-16 14:50
Sven-J�rgen Karlsen