dechicom

generative grammar and langage generation

Feb 16th, 2020
112
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.         self.d = dict()
  22.         self.L = list()
  23.         self.S = S
  24.         self.shringking_rules()
  25.         self.max_len=max_len
  26.     def shringking_rules(self):
  27.         for lr,rr in self.R:
  28.             l  = self.count_terminals(lr)
  29.             r  = self.count_terminals(rr)
  30.             if l > r:
  31.                 WA.warn("word length prediction not accurate due to shrinking rules")
  32.                 break
  33.        
  34.     def count_non_terminals(self,string):
  35.         n=0
  36.         for s in string:
  37.             if s in self.Vn:
  38.                 n+=1
  39.         return n
  40.     def count_terminals(self,string):
  41.         n=0
  42.         for s in string:
  43.             if s in self.Vt:
  44.                 n+=1
  45.         return n
  46.            
  47.     def non_terminal_pos(self,Q,start=0):
  48.         post=0
  49.         nbr_Vn=0
  50.         P=Q[0]
  51.         for i in xrange(start,len(P)):
  52.             if P[i] in self.Vn:
  53.                 return i
  54.         return -1
  55.     def extend_R (self):
  56.         '''
  57.        copy the rules list and append information:
  58.        pos is the pos of the first non-terminal character
  59.        in lr (left part of the rule) or rr (right part of rule)
  60.        '''
  61.         self.ext_R=list()
  62.         for r in self.R:
  63.             lr,rr=r
  64.             lr_pos=self.non_terminal_pos([lr])
  65.             rr_pos=self.non_terminal_pos([rr])
  66.             lr_len=len(lr)
  67.             rr_len=len(rr)
  68.             self.ext_R.append((lr,lr_pos,rr,rr_pos,lr_len,rr_len))
  69.  
  70.     def order_R(self):
  71.         '''
  72.        '''
  73.         self.lr_poskey=dict()
  74.         for ext_r in self.ext_R:
  75.             try:
  76.                 lr_pos=ext_r[1]
  77.                 ext_r_list=self.lr_poskey[lr_pos]
  78.             except (KeyError):
  79.                 self.lr_poskey[lr_pos]=[ext_r]
  80.                 continue
  81.             ext_r_list.append(ext_r)
  82.         for key, value in self.lr_poskey.iteritems():
  83.             value=sorted(value,key=itemgetter(4))
  84.             self.lr_poskey[key]=value
  85.  
  86.  
  87.     def order_R2(self):
  88.         '''
  89.        we want to produce 3 imbricated dictionaries
  90.        self.lr_pos_dic={lr_pos:{lr_len:{lr:[[rr1,rrpos1],[rr2,rrpos2]]}},.....}
  91.        '''
  92.         self.lr_pos_dic=dict()
  93.         for ext_r in self.ext_R:
  94.             lr,lr_pos,rr,rr_pos,lr_len,rr_len=ext_r
  95.             if lr_pos in self.lr_pos_dic:
  96.                 lr_len_dic=self.lr_pos_dic[lr_pos]
  97.             else:
  98.                 self.lr_pos_dic[lr_pos]=lr_len_dic=dict()
  99.             if lr_len in lr_len_dic:
  100.                 lr_dic=lr_len_dic[lr_len]
  101.             else:
  102.                 lr_len_dic[lr_len]=lr_dic=dict()
  103.             if lr in lr_dic:
  104.                 lr_dic[lr].append([rr,rr_pos])
  105.             else:
  106.                 lr_dic[lr]=[[rr,rr_pos],]
  107.  
  108.         for key, value in self.lr_pos_dic.iteritems():
  109.             value=list(value.iteritems())
  110.             value=sorted(value,key=itemgetter(0))
  111.             self.lr_pos_dic[key]=value
  112.                
  113.  
  114.     def gen (self):
  115.         '''
  116.        '''
  117.         self. extend_R()
  118.         self.order_R()
  119.         self.order_R2()
  120.         self.gen2D(self.S,0)
  121.         self.L=list(set(self.L))
  122.        
  123.        
  124.     def gen2D(self,P,nt_pos):
  125.         '''
  126.        this is a more optimized algorithm that should work better
  127.        when there are a lot of rules. need further tests  
  128.        '''
  129.         print P
  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_list in self.lr_pos_dic.iteritems():
  140.             start = max(0,nt_pos- lr_pos)
  141.             for lr_len,lr_dic  in lr_len_list:
  142.                
  143.                 for start2 in xrange(start,len(P)):
  144.                     end=start2+lr_len
  145.                     if end > len(P):
  146.                         break
  147.                     try:
  148.                         rr_list=lr_dic[P[start2:end]]
  149.                     except:
  150.                         continue
  151.                     for rr,rr_pos in rr_list:
  152.                         derivation=True
  153.                         newP = P[:start2] + rr + P[end:]
  154.                         new_nt_pos = self.non_terminal_pos([newP],start)
  155.                         self.gen2D(newP,new_nt_pos)
  156.                        
  157.         if  derivation==False:
  158.             raise Exception("Derivation impossible:%s" %(P))
  159.             #return
  160.        
  161. if __name__ =="__main__":
  162.     '''
  163.    exemple with rules generating langage with Na(P)=Nb(P)
  164.    same number of a and b in each word of L
  165.    '''    
  166.     S="S"
  167.     Vn=["S","A","B"] # non terminal
  168.     Vt=["a","b"]     # terminal
  169.     R=[("S","aB"),  ("A","a"),("A","aS"),("A","bAA"),
  170.        ("S","bA"),("B","b"),("B","bS"),("B","aBB")]
  171.     Lg=Gramgen(Vn,Vt,R,S,8)
  172.     Lg.gen()
  173.     print Lg.L
RAW Paste Data