fork download
copy 
  1. #Some helper functions
  2. def print_iter(Matched,Stack,Input,Action,verbose=True):
  3.     if verbose==True:
  4.         print(".".join(Matched).ljust(30)," | ",".".join(Stack).ljust(25)," | ",".".join(Input).ljust(30)," | ",Action)
  5. #The predictive parsing algorithm
  6. def predictive_parsing(sentence,parsingtable,terminals,start_state="S",verbose=True):      #Set verbose to false to not see the stages of the algorithm
  7.     status = None
  8.     match = []
  9.     stack = [start_state,"$"]
  10.     Inp = sentence.split(".")
  11.     if verbose==True:
  12.         print_iter(["Matched"],["Stack"],["Input"],"Action")
  13.     print_iter(match,stack,Inp,"Initial",verbose)
  14.     action=[]
  15.     while(len(sentence)>0 and status!=False):
  16.         top_of_input = Inp[0]
  17.         pos = top_of_input
  18.         if stack[0] =="$" and pos == "$" :
  19.             print_iter(match,stack,Inp,"Accepted",verbose)
  20.             return "Accepted"
  21.         if stack[0] == pos:
  22.             print_iter(match,stack,Inp,"Pop",verbose)
  23.             match.append(stack[0])
  24.             del(stack[0])
  25.             del(Inp[0])
  26.             continue
  27.         if stack[0]=="epsilon":
  28.             print_iter(match,stack,Inp,"Poping Epsilon",verbose)
  29.             del(stack[0])
  30.             continue
  31.         try:
  32.             production=parsingtable[stack[0]][pos]
  33.             print_iter(match,stack,Inp,stack[0]+" -> "+production,verbose)
  34.         except:
  35.             return "error for "+str(stack[0])+" on "+str(pos),"Not Accepted"
  36.  
  37.         new = production.split(".")   
  38.         stack=new+stack[1:]
  39.     return "Not Accepted"
  40.  
  41. if __name__=="__main__":
  42.     #Example for the working of the predictive parsing :-
  43.     #input for the grammar : E->TE1;E1->+TE1|epsilon;T->FT1 ...
  44.     parsingtable = {
  45.     "E" : {"id" : "T.E1", "(" : "T.E1"},
  46.     "E1" : {"+":"+.T.E1", ")":"epsilon", "$" : "epsilon"},
  47.     "T" : {"id" : "F.T1", "(" : "F.T1" },
  48.     "T1" : {"+" : "epsilon", "*" : "*.F.T1", ")" : "epsilon", "$" : "epsilon"},
  49.     "F":{"id":"id","(":"(.E.)"}
  50.     }
  51.     terminals = ["id","(",")","+","*"]
  52.     print(predictive_parsing(sentence="id.+.(.id.+.id.).$",parsingtable=parsingtable,terminals=terminals,start_state="E",verbose=True))
  53.     #Another Example done in class:-
  54.     print(predictive_parsing(sentence="c.c.c.c.d.d.$",parsingtable={"S" : {"c":"C.C","d":"C.C"},"C":{"c":"c.C","d":"d"}},terminals=["c,d"],start_state="S"))
Success #stdin #stdout #stderr 0.02s 6912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
ERROR: /home/xNAVg2/prog:54:155: Syntax error: Unexpected end of file
ERROR: '$runtoplevel'/0: Undefined procedure: program/0
   Exception: (3) program ? EOF: exit
https://ideone.com/IpTVmg
language:
Prolog (swi 7.6.4)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!