home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 December / simtel1292_SIMTEL_1292_Walnut_Creek.iso / msdos / turbopas / spoc88.arc / DCG.ARC / PARSTREE.PRO < prev   
Text File  |  1988-06-14  |  2KB  |  98 lines
  1. /* Parse Tree example 
  2.    Barbara Clinger, 1988
  3.  
  4. This program illustrates a parser for simple algebraic expressions,
  5. (no exponentation, parentheses, or functions). It returns the parse
  6. tree of the expression. The tree is built using the structure node,
  7. which is essentially an operator or number with left and right
  8. branches.
  9.  
  10. Sample input:  2 * 3 - 4 / 5 * 10 + 6
  11. The output is a tree which represents the number (in functor form)
  12.           +( -( *(2,3), *( /(4,5), 10) ), 6 )
  13. */
  14.  
  15. domains
  16.     item = op(string) ; leaf(real)
  17.     node = branch(item,node,node) ; empty
  18.     toklist = string*
  19. predicates
  20.     reader(string,toklist)
  21.     give_result(node,toklist,toklist)
  22.     append(toklist,toklist,toklist)
  23.     do
  24.    /* the grammar */
  25.     expr(node,toklist,toklist)
  26.     term(node,toklist,toklist)
  27.     number(node,toklist,toklist)
  28.  
  29. goal
  30.     do.
  31. clauses
  32. do :-
  33.     nl,write("Enter an expression --> "),
  34.     readln(String),nl,nl,
  35.     reader(String,List_in),
  36.     expr(Tree,List_in,Rest),
  37.     give_result(Tree,List_in,Rest).
  38.  
  39. give_result(N,_,T) :-
  40.     T = [],
  41.     write("The structure of the expression is:"),nl,nl,
  42.     write(N),nl.
  43. give_result(_,_,_) :-
  44.     write("Cannot evaluate the expression."),nl.
  45.     
  46. reader("",[]) :- !.
  47. reader(Str,[Tok|Rest]) :-
  48.     fronttoken(Str,Tok,Str1),
  49.     reader(Str1,Rest),!.
  50.  
  51. /* expansion of:
  52.     expr --> expr, [+], term
  53.     expr --> expr, [-], term
  54.     expr --> term
  55. */
  56. expr(branch(op("+"),L_node,R_node),L1,L2) :-
  57.     append(Left,["+"|Right],L1),
  58.     expr(L_node,Left,L2),
  59.     term(R_node,Right,L2).
  60. expr(branch(op("-"),L_node,R_node),L1,L2) :-
  61.     append(Left,["-"|Right],L1),
  62.     expr(L_node,Left,L2),
  63.     term(R_node,Right,L2).
  64. expr(X,L1,L2) :- term(X,L1,L2).
  65.  
  66. /* expansion of:
  67.     term --> term, [*], number
  68.     term --> term, [/], number
  69.     term --> number
  70. */
  71. term(branch(op("*"),L_node,R_node),L1,L2) :- 
  72.     append(Left,["*"|Right],L1),
  73.     term(L_node,Left,L2),
  74.     number(R_node,Right,L2).
  75. term(branch(op("/"),L_node,R_node),L1,L2) :-
  76.     append(Left,["/"|Right],L1),    
  77.     term(L_node,Left,L2),
  78.     number(R_node,Right,L2).
  79. term(X,L1,L2) :- number(X,L1,L2).
  80.  
  81. /* expansion of:
  82.     number --> [+], number
  83.     number --> [-], number
  84.     number --> [N]
  85. */    
  86. number(X,["+"|T],L2) :-
  87.     number(X,T,L2).
  88. number(X,["-"|T],L2) :-
  89.     number(branch(leaf(W),empty,empty),T,L2),
  90.     Z = -W,
  91.     X = branch(leaf(Z),empty,empty).
  92. number(branch(leaf(X),empty,empty),[H|T],T) :-
  93.     str_real(H,X).
  94.  
  95. append([],List,List).
  96. append([H|T],L,[H|T2]) :-
  97.     append(T,L,T2).
  98.