SHARE
TWEET

grammar generator in python

dechicom Feb 13th, 2020 (edited) 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/bin/python
  2. '''
  3. Egramgen.py
  4. grammar generator
  5. '''
  6.  
  7.  
  8. import string as ST
  9. from operator import itemgetter
  10. import warnings as WA
  11. class Gramgen(object):
  12.     '''
  13.    '''
  14.     def __init__(self,Vn,Vt,R,S,max_len):
  15.         self.Vn = Vn
  16.         self.Vt = Vt
  17.         self.R = R
  18.         self.Vn.sort()
  19.         self.Vt.sort()
  20.         self.R.sort()
  21.         print self.R
  22.         self.d = dict()
  23.         self.L = list()
  24.         self.S = S
  25.         self.shringking_rules()
  26.         self.max_len=max_len
  27.     def shringking_rules(self):
  28.         for lr,rr in self.R:
  29.             l  = self.count_terminals(lr)
  30.             r  = self.count_terminals(rr)
  31.             if l > r:
  32.                 WA.warn("word length prediction not accurate due to shrinking rules")
  33.                 break
  34.        
  35.     def count_non_terminals(self,string):
  36.         n=0
  37.         for s in string:
  38.             if s in self.Vn:
  39.                 n+=1
  40.         return n
  41.     def count_terminals(self,string):
  42.         n=0
  43.         for s in string:
  44.             if s in self.Vt:
  45.                 n+=1
  46.         return n
  47.            
  48.     def non_terminal_pos(self,Q,start=0):
  49.         post=0
  50.         nbr_Vn=0
  51.         P=Q[0]
  52.         for i in xrange(start,len(P)):
  53.             if P[i] in self.Vn:
  54.                 return i
  55.         return -1
  56.     def extend_R (self):
  57.         '''
  58.        copy the rules list and append information:
  59.        pos is the pos of the first non-terminal character
  60.        in lr (left part of the rule) or rr (right part of rule)
  61.        '''
  62.         self.ext_R=list()
  63.         for r in self.R:
  64.             lr,rr=r
  65.             lr_pos=self.non_terminal_pos([lr])
  66.             rr_pos=self.non_terminal_pos([rr])
  67.             lr_len=len(lr)
  68.             rr_len=len(rr)
  69.             self.ext_R.append((lr,lr_pos,rr,rr_pos,lr_len,rr_len))
  70.         #print self.ext_R
  71.     def order_R(self):
  72.         '''
  73.        '''
  74.         self.lr_poskey=dict()
  75.         for ext_r in self.ext_R:
  76.             try:
  77.                 lr_pos=ext_r[1]
  78.                 ext_r_list=self.lr_poskey[lr_pos]
  79.             except (KeyError):
  80.                 self.lr_poskey[lr_pos]=[ext_r]
  81.                 continue
  82.             ext_r_list.append(ext_r)
  83.         for key, value in self.lr_poskey.iteritems():
  84.             value=sorted(value,key=itemgetter(4))
  85.             self.lr_poskey[key]=value
  86.  
  87.         #print self.lr_poskey
  88.  
  89.     def order_R2(self):
  90.         '''
  91.        we want to produce 3 imbricated dictionaries
  92.        self.lr_pos_dic={lr_pos:{lr_len:{lr:[[rr1,rrpos1],[rr2,rrpos2]]}},.....}
  93.        '''
  94.         self.lr_pos_dic=dict()
  95.         for ext_r in self.ext_R:
  96.             lr,lr_pos,rr,rr_pos,lr_len,rr_len=ext_r
  97.             if lr_pos in self.lr_pos_dic:
  98.                 lr_len_dic=self.lr_pos_dic[lr_pos]
  99.             else:
  100.                 self.lr_pos_dic[lr_pos]=lr_len_dic=dict()
  101.             if lr_len in lr_len_dic:
  102.                 lr_dic=lr_len_dic[lr_len]
  103.             else:
  104.                 lr_len_dic[lr_len]=lr_dic=dict()
  105.             if lr in lr_dic:
  106.                 lr_dic[lr].append([rr,rr_pos])
  107.             else:
  108.                 lr_dic[lr]=[[rr,rr_pos],]
  109.  
  110.         for key, value in self.lr_pos_dic.iteritems():
  111.             value=list(value.iteritems())
  112.             value=sorted(value,key=itemgetter(0))
  113.             self.lr_pos_dic[key]=value
  114.                
  115.  
  116.     def gen (self):
  117.         '''
  118.        '''
  119.         self. extend_R()
  120.         self.order_R()
  121.         self.order_R2()
  122.         self.gen2D(self.S,0)
  123.        
  124.        
  125.     def gen2D(self,P,nt_pos):
  126.         '''
  127.        this is a more optimized algorithm that should work better
  128.        when there are a lot of rules. need further tests  
  129.        '''
  130.         if nt_pos <0:
  131.             if len(P) <= self.max_len:
  132.                 self.L.append(P)
  133.                 return
  134.             else:
  135.                 return
  136.         elif len(P) > self.max_len :
  137.             return
  138.         derivation=False
  139.         for lr_pos,lr_len_dic in self.lr_pos_dic.iteritems():
  140.             start = nt_pos- lr_pos
  141.             if start  < 0 :
  142.                 continue
  143.             else:
  144.                 for lr_len,lr_dic  in lr_len_dic:
  145.                    
  146.                     end=start+lr_len
  147.                     if end > len(P):
  148.                         print "P lr",P,P[start:end]
  149.                         break
  150.                     try:
  151.                         rr_list=lr_dic[P[start:end]]
  152.                     except:
  153.                         continue
  154.                     for rr,rr_pos in rr_list:
  155.                         derivation=True
  156.                         newP = P[:start] + rr + P[end:]
  157.                         if rr_pos < 0:
  158.                             new_nt_pos = self.non_terminal_pos([newP],start+len(rr))
  159.                         else:
  160.                             new_nt_pos = start + rr_pos
  161.                         self.gen2D(newP,new_nt_pos)
  162.         if  derivation==False:
  163.             raise Exception("Derivation impossible")
  164.        
  165. if __name__ =="__main__":
  166.     '''
  167.    exemple with rules generating langage with Na(P)=Nb(P)
  168.    same number of a and b in each word of L
  169.    '''    
  170.     S="S"
  171.     Vn=["S","A","B"] # non terminal
  172.     Vt=["a","b"]     # terminal
  173.     print Vn,Vt
  174.     R=[("S","aB"),  ("A","a"),("A","aS"),("A","bAA"),
  175.        ("S","bA"),("B","b"),("B","bS"),("B","aBB")]
  176.     Lg=Gramgen(Vn,Vt,R,S,8)
  177.     Lg.gen()
  178.     print Lg.L
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top