Praktikum Softwareanalyse und -transformation · Syntax-baum semantische Analyse annotierter abstrakter Syntax-baum Front-End Lexer Token-strom Programm-text Pr aprozessor Programm-text

Praktikum Softwareanalyse und -transformation

Thilo Mende

Universitat BremenFachbereich 3 – Mathematik und Informatik

Arbeitsgruppe Softwaretechnikhttp://www.informatik.uni-bremen/st

Sommersemester 2009

http://www.informatik.uni-bremen/st

Syntaktische Analyse und Generierung des ASTs


1 Einfuhrung

2 Analyse I

3 Refactoring I

4 Analyse II

5 Refactoring II

T.Mende (Uni Bremen) Softwareanalyse und -transformation SS09 3 / 23



2 Analyse ISyntaktische Analyse und Uberfuhrung in AST

ANTLREin Beispiel: Addition+MultiplikationUnsere Programmiersprache

NamensbindungUnparse



Einordnung

WissensbasisCodeUnparse Back-End

Transformationen

Analysenannotierte

Zwischen-

darstellung

Middle-

End

Zwischen-

sprachen-

generator

Zwischen-

darstellung

Parserabstrakter

Syntax-

baum

semantische

Analyse

annotierter

abstrakter

Syntax-

baum

Front-End

Lexer Token-

strom

Programm-

textPraprozessor

Programm-

text mit

Makros



Einordnung

WissensbasisCodeUnparse Back-End

Transformationen

Analysenannotierte

Zwischen-

darstellung

Middle-

End

Zwischen-

sprachen-

generator

Zwischen-

darstellung

Parserabstrakter

Syntax-

baum

semantische

Analyse

annotierter

abstrakter

Syntax-

baum

Front-End

Lexer Token-

strom

Programm-

textPraprozessor

Programm-

text mit

Makros



ANTLR

Im Allgemeinen:

ANother Tool for Language Recognition aka Parser Generator

Top-Down-Parser LL(*):

L Von Links lesenL Das “linkeste“ nicht-Terminal wird zuerst ersetzt* Beliebiger Lookahead

Unterstutzt Java, C, Python . . .

ANTLRWorks als Grammatik-IDE

Und wie wir es nutzen:

Lexer und Parser in einer Grammatik

Java/Ant

Beispiel-Projekt unter http://www.informatik.uni-bremen.de/

~tmende/sat/SATParser-v.0.1.tar.gz


http://www.informatik.uni-bremen.de/~tmende/sat/SATParser-v.0.1.tar.gz



ANTLR

Im Allgemeinen:

ANother Tool for Language Recognition aka Parser Generator

Top-Down-Parser LL(*):

L Von Links lesenL Das “linkeste“ nicht-Terminal wird zuerst ersetzt* Beliebiger Lookahead

Unterstutzt Java, C, Python . . .

ANTLRWorks als Grammatik-IDE

Und wie wir es nutzen:

Lexer und Parser in einer Grammatik

Java/Ant

Beispiel-Projekt unter http://www.informatik.uni-bremen.de/

~tmende/sat/SATParser-v.0.1.tar.gz





Eingabe: Addition+Multiplikation

Eingabe:

2+3∗4

(1+2)∗5

Aufgabe:Transformation in einen Abstrakten Syntaxbaum



Eingabe: Addition+Multiplikation

Eingabe:

2+3∗4

(1+2)∗5

Aufgabe:Transformation in einen Abstrakten Syntaxbaum



Gerust

grammar SAT; // Name g l e i c h Dateiname

op t i o n s {l anguage = Java ; // Ausgabespracheoutput = AST; // Ausgabe : TreeASTLabelType=CommonTree ; // K l a s s e d e r Knotenback t r a ck = t r u e ; // A u t o m a t i s c h e s B a c k t r a c k i n g an

// macht i f / e l s e s p a t e r e i n f a c h e r}

t okens { // D e f i n i t i o n d e r Token , kann man auch i n l i n e machenPLUS = ’+’ ;TIMES = ’ ∗ ’ ;PAR L = ’ ( ’ ;PAR R = ’ ) ’ ;

}

@header { package ag s t . s a t ; } // Wird i n d i e g e n e r i e r t e n@ l e x e r : : heade r { package ag s t . s a t ;} // K l a s s e n g e s c h r i e b e n



Lexer

prog : ; // Dummy, e r s t m a l i g n o r i e r e n

// Fragment : w i r d n i c h t a l s Token b e n u t z tf ragment SPACE : ’ ’ | ’ \ t ’ ;f ragment DIGIT : ’ 0 ’ . . ’ 9 ’ ;

// Token werden groß g e s c h r i e b e nNEWLINE : ( ’ \ r ’ ? ’ \n ’)+ { $channe l = HIDDEN; } ;// HIDDEN : P a r s e r s i e h t d i e n i c h tWHITESPACE: SPACE+ { $channe l = HIDDEN; } ;

INTEGER : DIGIT+; // Zahlen : E in od e r mehr d i g i t s



Test des Lexers

. . .Reader r e a d e r = new F i l eR e ad e r ( a r g s [ 0 ] ) ;SATLexer l e x e r = new SATLexer ( new ANTLRReaderStream ( r e a d e r ) ) ;r e a d e r . c l o s e ( ) ;CommonTokenStream tokenStream = new CommonTokenStream ( l e x e r ) ;

f o r ( Object ob j : tokenStream . getTokens ( ) ) {CommonToken token = (CommonToken) ob j ;i f ( token . ge tChanne l ( ) != CommonToken .HIDDEN CHANNEL){

System . out . p r i n t f ( ”%s :%s \n” , token . getText ( ) ,SATParser . tokenNames [ token . getType ( ) ] ) ;

}. . .}



Test des Lexers (2)

cd Project-Dir && ant

java -cp build/sat.jar agst.sat.LexerTest example.math

2 : INTEGER+:PLUS3 : INTEGER∗ :TIMES4 : INTEGER( : PAR L1 : INTEGER+:PLUS2 : INTEGER) : PAR R∗ :TIMES5 : INTEGER

2+3∗4

(1+2)∗5



Test des Lexers (2)

cd Project-Dir && antjava -cp build/sat.jar agst.sat.LexerTest example.math


2+3∗4

(1+2)∗5



Test des Lexers (2)

cd Project-Dir && antjava -cp build/sat.jar agst.sat.LexerTest example.math


2+3∗4

(1+2)∗5



Parser

// Ein Programm : n u l l o de r mehr e x p rprog : ( exp r )∗ ;

e xp r :// M i t t e l s Mexpr w i r d d i e Operator−R e i h e n f o l g e g e s t e u e r t

mexpr ( PLUS mexpr )∗ ;

// PR o d e r V e r k e t t u n g von ∗mexpr :

pr (TIMES pr )∗;

p r : INTEGER |PAR L exp r PAR R ;

. . .



Parse-Tree mit ANTLRWorks



Transformation in AST

. . .// ˆ : n e u e r Knoten im ASTexp r :

mexpr ( PLUSˆ mexpr )∗;

mexpr :/∗ Das h i e r i s t d e r k o m p l i z i e r t e Weg O p e ra t o r e n mit

Rewr i te−R u l e s zu b e s c h r e i b e n . D e u t l i c h k u r z e r geht e s mitpr (TIMESˆ pr ) ∗ ;Daf u r s i e h t man auch nochmal w i r man l a b e l s b e n u t z t umTokens g l e i c h e n Typs u n t e r s c h i e d l i c h zu b e h a n d e l n :i d e n t i f i e r =r e g e l und dann mit $ i d e n t i f i e r r e f e r e n z i e r e n . ∗/

( pr −> pr ) (TIMES r=pr −> ˆ(TIMES $mexpr $r ) ) ∗ ;

// ! : N i c h t f u r den AST best immtpr : INTEGER |

PAR L ! exp r PAR R ! ;



AST mit ANTLRWorks



Test des Parsers

. . .SATParser p a r s e r = new SATParser ( tokenStream ) ;

SATParser . p r o g r e t u r n r = p a r s e r . prog ( ) ;CommonTree c t = (CommonTree ) r . ge tTree ( ) ;System . out . p r i n t l n ( c t . t oS t r i n gT r e e ( ) ) ;. . .

antjava -cp build/sat.jar agst.sat.Processor example.mathAusgabe: (+ 2 (* 3 4)) (* (+ 1 2) 5)



Test des Parsers



antjava -cp build/sat.jar agst.sat.Processor example.math

Ausgabe: (+ 2 (* 3 4)) (* (+ 1 2) 5)



Test des Parsers



antjava -cp build/sat.jar agst.sat.Processor example.mathAusgabe: (+ 2 (* 3 4)) (* (+ 1 2) 5)



Programmiersprache

Allgemeine Anforderungen:

so einfach wie moglich

so ausdrucksstark wie notig fur die Refactorings

Teilmenge von C++

→ Erleichtert Uberprufung von Transformationen

Konkrete Teilmenge:

Klassen mit Methoden und Attributen

einfachste Anweisungen, z.B. +

einfache weitere Datentypen, z.B. int

einfachste Kontrollstrukturen, z.B. if und while

einfache Ausgabeanweisungen (fur den Test)

Parametermodi: Wert und Referenz

kein Overloading, einfache Namensbindung



Programmiersprache

Allgemeine Anforderungen:

so einfach wie moglich

so ausdrucksstark wie notig fur die Refactorings

Teilmenge von C++

→ Erleichtert Uberprufung von Transformationen

Konkrete Teilmenge:

Klassen mit Methoden und Attributen

einfachste Anweisungen, z.B. +

einfache weitere Datentypen, z.B. int

einfachste Kontrollstrukturen, z.B. if und while

einfache Ausgabeanweisungen (fur den Test)

Parametermodi: Wert und Referenz

kein Overloading, einfache Namensbindung



BNF-Syntax

: := t r e n n t l i n k e und r e c h t e R e g e l s e i t e

. beendet Rege l

| t r e n n t A l t e r n a t i v e n

{X} b e s c h r e i b t b e l i e b i g v i e l e Wiederho lung von X ( auch 0)

[X] b e s c h r e i b t o p t i o n a l e s X

’ t s t e h t f u r Token t ( ’ { i s t a l s o e i n Token de r Sprache )

A l l e Symbole , d i e n i c h t au f de r l i n k e n S e i t e a u f t r e t e n ,s i n d Termina l e

<e p s i l o n > i s t d i e l e e r e r e c h t e S e i t e



Unsere Grammatik (1)

P : := { C | D } . // Prog . b e s t e h t aus K l a s s e n+D e k l a r a t i o n e n

C : := c l a s s i d [ : i d ] ’ { p u b l i c : {D} ’ } ; // Klassen−D e k l a r a t i o n// ( p u b l i c nur wg . K o m p a t i b i l t a t )

D : := T i d ; | M . // D e k l a r a t i o n ( V a r i a b l e o d er Methode )

T : := vo i d | i n t | i d . // Typen : B u i l t−i n und s e l b e r d e f i n i e r t e

M ::= T i d ( PL ) B . // Methoden−D e f i n i t i o n

PL : := <e p s i l o n > | Pa { , Pa } . // Parameter−L i s t e

Pa : := T [&] i d . // Parameter−Argument

B : := ’ { { D } { S } ’ } . // Block

N : := i d | i d ’ . i d . // Name



Unsere Grammatik (2)

E : := E < Te // E x p r e s s i o n| E = Te| Te .

Te : := Te + Pr // Terminal−E x p r e s s i o n (wg . Operator−Pr azedenz )| Te − Pr| Pr .

Pr : := N | number | ( E ) | t h i s −> i d | N (AL) . // P r i m i t i v e

AL : := <e p s i l o n > | E { , E } . // Argument−L i s t e

S : := N = E ; // Statement| N ( AL ) ;| r e t u r n E ;| i f ( E ) S [ e l s e S ]| B| p r i n t f ( ”%d\n” , E ) ;| wh i l e ( E ) S .



Beispiel-Programm

i n t g l o b a l ;

c l a s s C {p u b l i c :

i n t a ;i n t b ;

vo i d foo ( i n t& x ) {a = x ;x = (1 + 2 ) ;

}} ;

. . .

c l a s s B : C {p u b l i c :

i n t c ;C d ;

i n t bar ( i n t x , i n t y ) {wh i l e ( x<y ) {

x = x + 2 ;i f ( y > 5) {

i n t x ;x = y + 5 ;foo ( x ) ;r e t u r n x ;

}}c = x ;r e t u r n 0 ;

}} ;



Und so geht es weiter

Zum nachsten Termin:

Grammatik in ANTLR umsetzen

Beim nachsten Termin:

Zwischenergebnis besprechen

Die Woche danach: Semantische Analyse

Fragen?









Fragen?









Fragen?




Documents

Praktikum Softwareanalyse und -transformation · Syntax-baum semantische Analyse annotierter abstrakter Syntax-baum Front-End Lexer Token-strom Programm-text Pr aprozessor Programm-text