home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 01 / newton / parser.pro < prev    next >
Encoding:
Prolog Source  |  1987-06-10  |  15.6 KB  |  321 lines
  1. /****************************************************************************/
  2. /**                             PARSER                                     **/
  3. /**                                                                        **/
  4. /** PREDIKAT: parse(STRING,TokenListe,term)                                **/
  5. /** VORAUSSETZUNGEN: DOMAIN term                                           **/
  6. /** Uebersetzt einen Funktionsterm in einem String in eine Baumnotation    **/
  7. /** Tokenliste enthaelt die gewuenschten Variablen                         **/
  8. /****************************************************************************/
  9.  
  10. domains
  11.   TokenListe = STRING*
  12.  
  13. predicates
  14.   replace(Term,TokenListe,Term)                   /* Tauscht Pseudovariablen 
  15.                                                        gegen Konstanten aus */
  16.   zaehle_Token(TokenListe,STRING,INTEGER) /* Vorkommen eines Zeich. zaehlen */
  17.   member(STRING,TokenListe)                 /* Zeichen in Liste enthalten ? */
  18.   richtiger_Term(TokenListe) 
  19.   entferne_Leerzeichen(STRING,STRING)
  20.   string_tokenliste(STRING,TokenListe)   /* Wandelt String in Tokenliste um */
  21.   aeussere_Klammern(TokenListe,TokenListe,TokenListe)  /* Entfernt aeussere 
  22.                 Klammern und gibt Argument und Rest hinter Klammer zurueck. 
  23.                                                      Benutzt rechte_Klammer */ 
  24.   rechte_Klammer(TokenListe,INTEGER,TokenListe,TokenListe) 
  25.   ordne_vorne(TokenListe,TokenListe)  /* Fuehrende - und + beruecksichtigen */
  26.   tokenliste_term(TokenListe,term)         /* Wandelt Tokenliste in Term um */
  27.   verknuepf(term,STRING,term,term) /* Verkn. zwei Terme ueber einen Funktor */
  28.   append(TokenListe,TokenListe,TokenListe)              /* Verkettet Listen */
  29.   parse(STRING,TokenListe,term)        /* parsed einen String zu einen Term */
  30.   split_in_two(TokenListe,TokenListe,TokenListe) 
  31.                  /* Teilt eine Tokenliste an einem Komma in zwei Listen auf */
  32.   
  33. /* Die folgenden Pred. pruefen, ob ein Zeichen ein bestimmter Operator ist  */
  34.   ist_Strichop(STRING)
  35.   ist_Punktop(STRING)
  36.   ist_Op(STRING)
  37.   ist_Klammer(String)
  38.  
  39. /* Diese pruefen die Zugehoerigkeit von Funktoren zu bestimmten Gruppen     */ 
  40.   ist_Strichfunk(term)
  41.   ist_Punktfunk(term)
  42.   ist_dual_funk(term)                        /* Funktor mit zwei Argumenten */
  43.  
  44. /* Aufspaltung in Teile die nur mit Punkt- bzw. Strichliste */ 
  45.   split_in_P_Liste(TokenListe,term)
  46.   split_in_S_Liste(TokenListe,term)
  47.   ist_iso_term(TokenListe)                        /* Abgeschlossener Term ? */
  48.  
  49.   
  50. clauses
  51.   parse(S,VL,T) IF 
  52.       bound(S) AND entferne_leerzeichen(S,NS), string_tokenliste(NS,TL),
  53.       ordne_vorne(TL,NTL), tokenliste_term(NTL,TT) AND replace(TT,VL,T) AND !. 
  54.   parse(S,_,T) IF 
  55.       free(S) AND tokenliste_term(TL,T) AND string_tokenliste(S,TL) AND !. 
  56.  
  57.   replace(var(A),VarListe,var(A)) IF member(A,VarListe) AND !.
  58.   replace(var(A),_,const(A)) IF !.
  59.   replace(nconst(A),_,nconst(A)) IF !.  
  60.   replace(plus(A,B),VarListe,plus(AN,BN)) IF 
  61.       replace(A,VarListe,AN) AND replace(B,VarListe,BN) AND !.
  62.   replace(minus(A,B),VarListe,minus(AN,BN)) IF 
  63.       replace(A,VarListe,AN) AND replace(B,VarListe,BN) AND !.    
  64.   replace(mal(A,B),VarListe,mal(AN,BN)) IF 
  65.       replace(A,VarListe,AN) AND replace(B,VarListe,BN) AND !.         
  66.   replace(div(A,B),VarListe,div(AN,BN)) IF 
  67.       replace(A,VarListe,AN) AND replace(B,VarListe,BN) AND !.    
  68.   replace(funk(N,Arg),VarListe,funk(N,ArgN)) IF
  69.       replace(Arg,VarListe,ArgN) AND !.
  70.   replace(npot(A,B),VarListe,npot(AN,BN)) IF 
  71.       replace(A,VarListe,AN) AND replace(B,VarListe,BN) AND !.              
  72.  
  73.   /* anstaendiger Term ? */
  74.   tokenliste_term(TokenListe,_) :- 
  75.       BOUND(TokenListe) AND NOT(richtiger_Term(TokenListe)) AND ! AND FAIL. 
  76.  
  77.   /* atomare Terme parsen */
  78.   tokenliste_term([Token],nconst(X)) :- bound(Token), str_real(Token,X) AND !.
  79.   tokenliste_term([Token],nconst(X)) :- bound(X), str_real(Token,X) AND !.
  80.   tokenliste_term([Token],var(Token)) :- bound(Token), isname(Token) AND !.
  81.   tokenliste_term([Token],const(Token)) :- bound(Token), isname(Token) AND !.
  82.  
  83.   /* Vorne ein bisschen ordnen */
  84.   tokenliste_term(["-",Atom],Res) :- 
  85.       BOUND(Atom) AND concat("-",Atom,Arg), 
  86.       tokenliste_term([Arg],Res) AND !. 
  87.  
  88.   /* Klammerterme parsen: Endstaendig oder in Funktionen */
  89.   tokenliste_term(["("|T],Res) IF 
  90.       BOUND(T) AND aeussere_Klammern(["("|T],NArg,[]) AND 
  91.       tokenliste_term(NArg,Res) AND !.        
  92.   tokenliste_term(["("|T],Res) IF 
  93.       BOUND(T) AND aeussere_Klammern(["("|T],NArg,[Op|Rest]) AND
  94.       string_tokenliste(Str1,["("|NArg]) AND concat(Str1,")",Str2) AND
  95.       tokenliste_term([Str2,Op|Rest],Res) AND !.      
  96.  
  97.   /* Funktionen parsen: endstaendig oder in Term */            
  98.   tokenliste_term([Name,"("|Arg_u_Klamm],funk(Name,FunkArg)) IF 
  99.       BOUND(Name) AND BOUND(Arg_u_Klamm) AND 
  100.       member(Name,[sqr,sqrt,arctan,arcsin,arccos,tan,sin,cos,ln,exp]),
  101.       aeussere_Klammern(["("|Arg_u_Klamm],Arg,[]) AND 
  102.       tokenliste_term(Arg,FunkArg) AND !.
  103.   tokenliste_term([Name,"("|Arg_u_Klamm],Res) IF 
  104.       BOUND(Name) AND BOUND(Arg_u_Klamm) AND 
  105.       member(Name,[sqr,sqrt,arctan,arcsin,arccos,tan,sin,cos,ln,exp]),    
  106.       aeussere_Klammern(["("|Arg_u_Klamm],Arg,Rest) AND 
  107.       string_tokenliste(Str1,[Name,"("|Arg]) AND concat(Str1,")",Str2) AND
  108.       tokenliste_term([Str2|Rest],Res) AND !.      
  109.  
  110.   /* Potenzen analog Funktionen */    
  111.   tokenliste_term([pot,"("|Arg_u_Klamm],npot(FunkArg1,FunkArg2)) IF 
  112.       BOUND(Arg_u_Klamm),
  113.       aeussere_Klammern(["("|Arg_u_Klamm],Arg,[]), split_in_two(Arg,Arg1,Arg2),
  114.       tokenliste_term(Arg1,FunkArg1), tokenliste_term(Arg2,FunkArg2) AND !.
  115.   tokenliste_term([pot,"("|Arg_u_Klamm],Res) IF 
  116.       BOUND(Arg_u_Klamm),
  117.       aeussere_Klammern(["("|Arg_u_Klamm],Arg,Rest),        
  118.       string_tokenliste(Str1,[pot,"("|Arg]) AND concat(Str1,")",Str2) AND
  119.       tokenliste_term([Str2|Rest],Res) AND !.      
  120.  
  121.   /* Aufspaltung in Punktrechnungs- und Strichrechnungsterme */
  122.   tokenliste_term(L,Res) IF BOUND(L) AND split_in_P_Liste(L,Res) AND !.    
  123.   tokenliste_term(L,Res) IF BOUND(L) AND split_in_S_Liste(L,Res) AND !.
  124.       
  125.   /************************************************/
  126.   /* Und hier die Klauseln fuer rechts ---> links */
  127.   /************************************************/
  128.   
  129.   tokenliste_term(FunkTerm,funk(FName,FunkArg)) IF /*****/ 
  130.       BOUND(FunkArg) AND BOUND(FNAME) AND tokenliste_term(NFunkArg,FunkArg),
  131.       append([FName,"("],NFunkArg,Res1), append(Res1,[")"],FunkTerm) AND !.
  132.   tokenliste_term(FunkTerm,npot(Basis,Exp)) IF /*****/ 
  133.       BOUND(Basis) AND BOUND(Exp) AND tokenliste_term(Term1,Basis),
  134.       tokenliste_term(Term2,Exp), append([pot,"("],Term1,Res1), 
  135.       append(Res1,[","|Term2],Res2), append(Res2,[")"],FunkTerm) AND !.    
  136.   tokenliste_term(XL,minus(nconst(0),X)) IF tokenliste_term(XL,X) AND !.    
  137.  
  138.   /* Division durch nicht geschlossenen Term */      
  139.   tokenliste_term(StrL,div(A,B)) IF 
  140.       BOUND(A) AND BOUND(B) AND not(ist_Strichfunk(A)) AND ist_dual_Funk(B) 
  141.       AND tokenliste_term(AL,A) AND tokenliste_term(BL,B) AND 
  142.       append(AL,["/","("|BL],L1) AND append(L1,[")"],StrL) AND !.     
  143.  
  144.   /* Punktrechnung mit Strichrechnung verknuepft */
  145.   tokenliste_term(StrL,div(A,B)) IF 
  146.       BOUND(A) AND BOUND(B) AND ist_Strichfunk(A) AND ist_Strichfunk(B) AND
  147.       tokenliste_term(AL,A) AND tokenliste_term(BL,B) 
  148.       AND append(["("|AL],[")","/","("|BL],L1) 
  149.       AND append(L1,[")"],StrL) AND !.     
  150.   tokenliste_term(StrL,mal(A,B)) IF 
  151.       BOUND(A) AND BOUND(B) AND ist_Strichfunk(A) AND ist_Strichfunk(B) AND
  152.       tokenliste_term(AL,A) AND tokenliste_term(BL,B) AND 
  153.       append(["("|AL],[")","*","("|BL],L1) AND append(L1,[")"],StrL) AND !.
  154.  
  155.   /* Punktrechnung mit einem Strichrechnungsterm verknuepft */         
  156.   tokenliste_term(StrL,div(A,B)) IF 
  157.       BOUND(A) AND BOUND(B) AND ist_Strichfunk(A) AND tokenliste_term(AL,A) 
  158.       AND tokenliste_term(BL,B) AND append(["("|AL],[")","/"|BL],StrL) AND !.
  159.   tokenliste_term(StrL,mal(A,B)) IF 
  160.       BOUND(A) AND BOUND(B) AND ist_Strichfunk(A) 
  161.       AND tokenliste_term(AL,A) AND tokenliste_term(BL,B) 
  162.       AND append(["("|AL],[")","*"|BL],StrL) AND !.         
  163.   tokenliste_term(StrL,mal(A,B)) IF 
  164.       BOUND(A) AND BOUND(B) AND ist_Strichfunk(B)
  165.       AND tokenliste_term(AL,A) AND tokenliste_term(BL,B) 
  166.       AND append(AL,["*","("|BL],StrL1) AND 
  167.       append(StrL1,[")"],StrL) AND !.
  168.              
  169.   /* Division durch geschlossenen Term */
  170.   tokenliste_term(StrL,div(A,B)) IF 
  171.       BOUND(A) AND BOUND(B) AND tokenliste_term(AL,A)
  172.       AND tokenliste_term(BL,B) AND append(AL,["/"|BL],StrL) AND !.          
  173.  
  174.   /* Minus Strichrechnungsterm */
  175.   tokenliste_term(StrL,minus(A,B)) IF 
  176.       BOUND(A) AND BOUND(B) AND ist_Strichfunk(B) 
  177.       AND tokenliste_term(AL,A) AND tokenliste_term(BL,B) 
  178.       AND append(AL,[" - ","("|BL],L1) AND append(L1,[")"],StrL) AND !. 
  179.  
  180.   /* Minus anderen Term */
  181.   tokenliste_term(StrL,minus(A,B)) IF 
  182.       BOUND(A) AND BOUND(B) AND tokenliste_term(AL,A) AND 
  183.       tokenliste_term(BL,B) AND append(AL,[" - "|BL],StrL) AND !.           
  184.  
  185.   /* Allgemeine Faelle */
  186.   tokenliste_term(StrL,plus(A,B)) IF 
  187.       BOUND(A) AND BOUND(B) AND tokenliste_term(AL,A) 
  188.       AND tokenliste_term(BL,B) AND append(AL,[" + "|BL],StrL) AND !.
  189.   tokenliste_term(StrL,mal(A,B)) IF 
  190.       BOUND(A) AND BOUND(B) AND tokenliste_term(AL,A) 
  191.       AND tokenliste_term(BL,B) AND append(AL,["*"|BL],StrL) AND !.                 
  192.   tokenliste_term(StrL,div(A,B)) IF 
  193.       BOUND(A) AND BOUND(B) AND tokenliste_term(AL,A) 
  194.       AND tokenliste_term(BL,B) AND append(AL,["/"|BL],StrL) AND !.               
  195.       
  196.   verknuepf(Term1,"+",Term2,plus(Term1,Term2)) IF !. 
  197.   verknuepf(Term1,"-",Term2,minus(Term1,Term2)) IF !. 
  198.   verknuepf(Term1,"*",Term2,mal(Term1,Term2)) IF !. 
  199.   verknuepf(Term1,"/",Term2,div(Term1,Term2)) IF !. 
  200.                   
  201.   append([],List,List) IF !.
  202.   append([X|L1], List2, [X|L3]) IF append(L1,List2,L3).  
  203.   
  204.   split_in_two([","|T],[],T) IF !.
  205.   split_in_two([H|T],[H|N1],N2) IF split_in_two(T,N1,N2) AND !.
  206.   
  207.   ist_Strichop(" + "). ist_Strichop("-").
  208.   ist_Punktop("*").  ist_Punktop("/").
  209.   ist_Op(Op) IF ist_Strichop(Op) AND ! OR ist_Punktop(OP) AND !.
  210.   
  211.   ist_Strichfunk(plus(_,_)). ist_Strichfunk(minus(_,_)).
  212.  
  213.   ist_Punktfunk(mal(_,_)). ist_Punktfunk(div(_,_)).                
  214.   
  215.   ist_dual_funk(Funktor) IF
  216.       ist_Strichfunk(Funktor) AND ! OR ist_Punktfunk(Funktor) AND !.
  217.  
  218. /* Dokumentation der Termaufspaltung im Begleitartikel */
  219.   split_in_P_Liste([Front,Op,Last],Res) IF
  220.      ist_Punktop(Op) AND string_tokenliste(Front,FrontL) AND
  221.      tokenliste_term(FrontL,FrontT) AND tokenliste_term([Last],LastT) AND
  222.      verknuepf(FrontT,Op,LastT,Res) AND !.   
  223.   split_in_P_Liste([Front,Op|Tail],Res) IF
  224.      ist_Punktop(Op) AND ist_iso_term(Tail) AND string_tokenliste(Front,FrontL)
  225.       AND tokenliste_term(FrontL,FrontT) AND tokenliste_term(Tail,TailT) 
  226.       AND verknuepf(FrontT,Op,TailT,Res) AND !.
  227.   split_in_P_Liste([Front,"+",Third|Tail],Res) IF
  228.      string_tokenliste(Front,FrontL) AND tokenliste_term(FrontL,FrontT) AND
  229.      tokenliste_term([Third|Tail],TailT) AND  verknuepf(FrontT,"+",TailT,Res)
  230.      AND !.         
  231.   split_in_P_Liste([Front,"-",Third|Tail],Res) IF
  232.      string_tokenliste(Front,FrontL) AND tokenliste_term(FrontL,FrontT) AND 
  233.      tokenliste_term([Third|Tail],TailT) AND NOT(ist_Strichfunk(TailT)) AND 
  234.      verknuepf(FrontT,"-",TailT,Res) AND !.            
  235.   split_in_P_Liste([Front,Op,Third|Tail],Res) IF
  236.      ist_Op(Op) AND bound(Third) AND not(ist_Klammer(Third)) AND 
  237.      not(member(Third,[sqr,sqrt,arctan,arcsin,arccos,tan,sin,cos,ln,exp,pot]))
  238.      AND string_tokenliste(NFront,[Front,Op,Third]) AND 
  239.      tokenliste_term([NFront|Tail],Res) AND !.
  240.   split_in_P_Liste([Front,Op,Third|Tail],Res) IF
  241.      ist_Op(Op) AND bound(Third) AND 
  242.      member(Third,[sqr,sqrt,arctan,arcsin,arccos,tan,sin,cos,ln,exp,pot]) AND
  243.      aeussere_Klammern(Tail,Arg,Rest) AND 
  244.      string_Tokenliste(Front1,[Front,Op,Third,"("|Arg]) AND 
  245.      concat(Front1,")",NFront) AND tokenliste_term([NFront|Rest],Res) AND !. 
  246.   split_in_P_Liste([Front,Op,Third|Tail],Res) IF
  247.      ist_Op(Op) AND bound(Third) AND ist_Klammer(Third) AND
  248.      aeussere_Klammern([Third|Tail],Arg,Rest), 
  249.      string_tokenliste(Str1,[Front,Op,Third|Arg]), concat(Str1,")",NFront), 
  250.      tokenliste_term([NFront|Rest],Res) AND !.            
  251.   split_in_P_Liste([Front,Op,Tail],Res) IF
  252.      ist_Op(Op) AND string_tokenliste(Front,FrontL) AND 
  253.      tokenliste_term(FrontL,FrontT) AND tokenliste_term([Tail],TailT) AND
  254.      verknuepf(FrontT,Op,TailT,Res) AND !.
  255.   
  256.   split_in_S_Liste([Front,Op,Last],Res) IF
  257.      ist_Strichop(Op) AND string_tokenliste(Front,FrontL) AND
  258.      split_in_S_Liste(FrontL,FrontT) AND tokenliste_term([Last],LastT) AND
  259.      verknuepf(FrontT,Op,LastT,Res) AND !.         
  260.   split_in_S_Liste([Front,Op|Tail],Res) IF
  261.      ist_Strichop(Op) AND ist_iso_term(Tail) 
  262.      AND string_tokenliste(Front,FrontL) AND tokenliste_term(FrontL,FrontT) 
  263.      AND tokenliste_term(Tail,TailT) AND verknuepf(FrontT,Op,TailT,Res) AND !.
  264.   split_in_S_Liste([Front,Op,Third|Tail],Res) IF
  265.      ist_Op(Op) AND bound(Third) AND not(ist_Klammer(Third)) AND
  266.      string_tokenliste(NFront,[Front,Op,Third]) AND 
  267.      tokenliste_term([NFront|Tail],Res) AND !.            
  268.   
  269.   ist_iso_term(["("|T]) IF BOUND(T) AND aeussere_Klammern(["("|T],_,[]) AND !. 
  270.   ist_iso_term([Name,"("|Arg_u_Klamm]) IF 
  271.       BOUND(Name) AND BOUND(Arg_u_Klamm) AND 
  272.       member(Name,[sqr,sqrt,arctan,arcsin,arccos,tan,sin,cos,ln,exp]),
  273.       aeussere_Klammern(["("|Arg_u_Klamm],_,[]) AND !.
  274.   ist_iso_term([pot,"("|Arg_u_Klamm]) IF 
  275.       BOUND(Arg_u_Klamm), aeussere_Klammern(["("|Arg_u_Klamm],_,[]) AND !.    
  276.   ist_Klammer("("). ist_Klammer(")").
  277.   
  278.   entferne_Leerzeichen(E_String,A_String) :-
  279.       fronttoken(E_String,Token,Rest) AND /* Token vorhanden ?! */ 
  280.       entferne_Leerzeichen(Rest,A_Rest), concat(Token,A_Rest,A_String) AND !.
  281.   entferne_Leerzeichen(_,"") IF !.  
  282.   
  283.   richtiger_Term(TokenListe) :-               /* Anzahl oeffnender Klammern 
  284.                                                           = schliessender ? */
  285.       zaehle_Token(TokenListe,"(",Anzahl) AND 
  286.       zaehle_Token(TokenListe,")",Anzahl) AND !.        
  287.       
  288.   zaehle_Token([],_,0) IF !.        
  289.   zaehle_Token([Token|RestList],Token,Aus) IF  
  290.       zaehle_Token(RestList,Token,Aus1), Aus = Aus1 + 1 AND !.
  291.   zaehle_Token([_|Tail],Token,Aus) IF zaehle_Token(Tail,Token,Aus) AND !.
  292.   
  293.   String_TokenListe("",[]) :- !.  
  294.   String_TokenListe(Str,[H|T]) :- 
  295.       BOUND(Str) AND  fronttoken(Str,H,Rest) 
  296.       AND String_TokenListe(Rest,T) AND !.
  297.   String_TokenListe(Str,[H|T]) :-  
  298.       BOUND(H) AND BOUND(T) AND String_TokenListe(Rest,T) AND 
  299.       fronttoken(Str,H,Rest) AND !.     
  300.        
  301.   aeussere_Klammern(["("|T],NT,Rest) IF ! AND rechte_Klammer(T,1,NT,Rest).
  302.   aeussere_Klammern(A,A,[]). 
  303.   
  304.   rechte_Klammer(X,0,[],X) IF !.
  305.   rechte_Klammer(X,0,[],Y) IF ! AND X = Y. /* Faile falls X <> Y */  
  306.   rechte_Klammer([")"|T],1,[],T) :- BOUND(T) AND !.
  307.   rechte_Klammer(["("|T],Zaehler,["("|NT],Rest) IF ! AND  
  308.       Zaehler_1 = Zaehler + 1 AND rechte_Klammer(T,Zaehler_1,NT,Rest).
  309.   rechte_Klammer([")"|T],Zaehler,[")"|NT],Rest) IF ! AND
  310.       Zaehler_1 = Zaehler - 1 AND rechte_Klammer(T,Zaehler_1,NT,Rest).
  311.   rechte_Klammer([H|T],Zaehler,[H|NT],Rest) IF ! AND
  312.       bound(H) AND rechte_Klammer(T,Zaehler,NT,Rest).
  313.     
  314.   ordne_vorne(["+"|T],T) :- !.
  315.   ordne_vorne(["-"|T],["0","-"|T]) :- !.
  316.   ordne_vorne(A,A).
  317.   
  318.   member(X,[X|_]).
  319.   member(X,[_|L]) :- member(X,L).
  320.   
  321.