Benutzer:Grey/pss

Milstone 1

• EBNF in BNF Grammatik umwandeln:

EBNF

Gegeben ist folgende EBNF Syntax von microOPAL:

Prog -> Def Def * #
Def  -> DEF Lhs == Expr
Lhs  -> MAIN : Type | id ( [id : Type (, id : Type)*]) : Type
Type -> nat | bool
Expr -> number | true | false | id [ ( [Expr (, Expr)*] ) ] | IF Expr THEN Expr [ELSE Expr] FI

BNF

Erste Umformung inklusive semantischer Aktionen:

 1)Prog  	->  Def <1> Def´ #

 2)Def  	->  DEF Lhs == Expr <2>

 3)Def'  	->  Def <3> Def´
 4) 	       	|   e

 5)Lhs   	->  MAIN <5> : Type <4>
 6)		|   id ( <5> Lhs´ ) : Type <4>

 7)Lhs´  	->  id : Type  <6> Lhs´´
 8)		|   e

 9)Lhs´´	->  , Lhs´
10)		|   e

11)Type  	->  nat <15>
12)       	|   bool <15> 

13)Expr    	->  number <7>
14)       	|   true <8>
15)       	|   false <8>
16)     	|   id Expr´
17)		|   IF Expr THEN Expr fi´ 

18)Expr´ 	->  ( <10> Expr´´ ) <9>
19)		|   e <12>

20)Expr´´	->  Expr <11> Expr´´´		
21)            |   e

22)Expr´´´ 	->  , Expr <11> Expr´´´
23)            |   e

24)fi´     	->  ELSE Expr FI <14>
      		|   FI <13> 

Semantische Aktionen:
<1> : makeDefList
<2> : makeDef
<3> : add2DefList
<4> : makeLhs
<5> : makeLhsParList
<6> : add2LhsParList
<7> : makeNatConst
<8> : makeBoolConst
<9> : makeFunCall
<10> : makeExprList
<11> : add2ExprList
<12> : makeParRef
<13> : makeCond
<14> : makeElse
<15> : makeType

Directormengen

Vorlage:Highlight1 |Produktion	Vorlage:Highlight1 |Directormenge	Vorlage:Highlight1 |disjunkt?
1)	uninteressant	ja
2)	uninteressant	ja
3) 3b)	{DEF} {#, DEF}	ja
4) 5)	{MAIN} {id}	ja
6) 7)	{id} {)}	ja
8) 9)	{,} {)}	ja
10) 11)	{nat} {bool}	ja
12) 13) 14) 15) 16)	{number} {true} {false} {id} {IF}	ja
17) 18)	{(} {THEN, ELSE, FI, ,, )}	ja
19) 20)	{number, true, false, id, IF} {,, )}	ja
21) 22)	{,} {)}	ja
23) 24)	{ELSE} {FI}	ja

Abstrakter Syntaxbaum

http://www.freitagsrunde.org/~grey/pss/absy.jpg

Implementation

Absy.impl

IMPLEMENTATION Absy
 
DATA absy == 	Prog( defseq:seq[absy])
		Def(id:denotation, seq[id:denotation, typ: type], typ:type) 
	 	Funcall(id: denotation, parref: seq[absy])
		ParRef(id:denotation)
		Cond(ifCond:absy, thenCond:absy)
		CondElse(ifElse:absy, thenElse:absy, elseElse: absy)
		NatConst(number:nat)
		BoolConst(boolean:bool)

DATA type == 	TNat(n:nat)
		TBool(b:bool)


-- Ausgabefunktion vom Absy
-- DEF `(Absy) ==  
DEF `(Prog(defseq)) == "Prog(" ++ (printSeqAbsy(defseq)) ++ ")"
DEF `(Def(id,seqIdTyp,typ)) == "Def " ++ id ++ "(" ++ (printSeqType(seqIdTyp)) ++ ") :" ++ (printType(typ))
DEF `(Funcall(id,parref)) == "Funcall:" ++ id ++ "(" ++ (printSeqAbsy(parref)) ++ ")"
DEF `(ParRef(id)) == "ParRef:" ++ id 
DEF `(Cond(ifCond,thenCond)) == "Cond(" ++ "IF " ++ (`(ifCond)) ++ " THEN " ++ (`(thenCond)) ++ ")"
DEF `(CondElse(ifCondE,thenCondE, elseCondE)) == "Cond(" ++ "IF " ++ (`(ifCondE)) ++ " THEN " ++ (`(thenCondE)) ++ " ELSE " ++ (`(elseCondE)) ++ ")"
DEF `(NatConst(natC)) == `(natC)
DEF `(BoolConst(boolC)) == `(boolC)

DEF printSeqAbsy(<>) == "<>"
DEF printSeqAbsy(a::R) == `(a) ++ ";" ++ printSeqAbsy(R) 

DEF printType(TNat) == "nat"
DEF printType(TBool) == "bool"	
	
DEF printSeqType(<>) == "<>"
DEF printSeqType((id,typ)::R) == id ++ ":" ++ printType(typ) ++ ", " ++ printSeqType(R)

Absy.sign

/* %
Die abstrakte Syntax. NOT YET IMPLEMENTED.
*/
 
SIGNATURE Absy
 
SORT absy 	

-- Augabefunktion 
FUN ` : absy -> denotation

-- Ausgabefunktionen für Typen inerhalb von Absy
FUN printSeqAbsy : seq[absy] -> denotation
FUN printType : type -> denotation
FUN printSeqType : seq[denotation, type] -> denotation