SHARE
TWEET

generative grammar and langage generation

dechicom Feb 16th, 2020 (edited) 49 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
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