home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / lib / python2.6 / lib2to3 / pgen2 / pgen.pyc (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2009-04-20  |  12.0 KB  |  437 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.6)
  3.  
  4. from  import grammar, token, tokenize
  5.  
  6. class PgenGrammar(grammar.Grammar):
  7.     pass
  8.  
  9.  
  10. class ParserGenerator(object):
  11.     
  12.     def __init__(self, filename, stream = None):
  13.         close_stream = None
  14.         if stream is None:
  15.             stream = open(filename)
  16.             close_stream = stream.close
  17.         
  18.         self.filename = filename
  19.         self.stream = stream
  20.         self.generator = tokenize.generate_tokens(stream.readline)
  21.         self.gettoken()
  22.         (self.dfas, self.startsymbol) = self.parse()
  23.         if close_stream is not None:
  24.             close_stream()
  25.         
  26.         self.first = { }
  27.         self.addfirstsets()
  28.  
  29.     
  30.     def make_grammar(self):
  31.         c = PgenGrammar()
  32.         names = self.dfas.keys()
  33.         names.sort()
  34.         names.remove(self.startsymbol)
  35.         names.insert(0, self.startsymbol)
  36.         for name in names:
  37.             i = 256 + len(c.symbol2number)
  38.             c.symbol2number[name] = i
  39.             c.number2symbol[i] = name
  40.         
  41.         for name in names:
  42.             dfa = self.dfas[name]
  43.             states = []
  44.             for state in dfa:
  45.                 arcs = []
  46.                 for label, next in state.arcs.iteritems():
  47.                     arcs.append((self.make_label(c, label), dfa.index(next)))
  48.                 
  49.                 if state.isfinal:
  50.                     arcs.append((0, dfa.index(state)))
  51.                 
  52.                 states.append(arcs)
  53.             
  54.             c.states.append(states)
  55.             c.dfas[c.symbol2number[name]] = (states, self.make_first(c, name))
  56.         
  57.         c.start = c.symbol2number[self.startsymbol]
  58.         return c
  59.  
  60.     
  61.     def make_first(self, c, name):
  62.         rawfirst = self.first[name]
  63.         first = { }
  64.         for label in rawfirst:
  65.             ilabel = self.make_label(c, label)
  66.             first[ilabel] = 1
  67.         
  68.         return first
  69.  
  70.     
  71.     def make_label(self, c, label):
  72.         ilabel = len(c.labels)
  73.         if label[0].isalpha():
  74.             if label in c.symbol2number:
  75.                 if label in c.symbol2label:
  76.                     return c.symbol2label[label]
  77.                 c.labels.append((c.symbol2number[label], None))
  78.                 c.symbol2label[label] = ilabel
  79.                 return ilabel
  80.             label in c.symbol2number
  81.             itoken = getattr(token, label, None)
  82.             if not isinstance(itoken, int):
  83.                 raise AssertionError, label
  84.             if not itoken in token.tok_name:
  85.                 raise AssertionError, label
  86.             if itoken in c.tokens:
  87.                 return c.tokens[itoken]
  88.             c.labels.append((itoken, None))
  89.             c.tokens[itoken] = ilabel
  90.             return ilabel
  91.         label[0].isalpha()
  92.         if not label[0] in ('"', "'"):
  93.             raise AssertionError, label
  94.         value = eval(label)
  95.         if value[0].isalpha():
  96.             if value in c.keywords:
  97.                 return c.keywords[value]
  98.             c.labels.append((token.NAME, value))
  99.             c.keywords[value] = ilabel
  100.             return ilabel
  101.         value[0].isalpha()
  102.         itoken = grammar.opmap[value]
  103.         if itoken in c.tokens:
  104.             return c.tokens[itoken]
  105.         c.labels.append((itoken, None))
  106.         c.tokens[itoken] = ilabel
  107.         return ilabel
  108.  
  109.     
  110.     def addfirstsets(self):
  111.         names = self.dfas.keys()
  112.         names.sort()
  113.         for name in names:
  114.             if name not in self.first:
  115.                 self.calcfirst(name)
  116.                 continue
  117.         
  118.  
  119.     
  120.     def calcfirst(self, name):
  121.         dfa = self.dfas[name]
  122.         self.first[name] = None
  123.         state = dfa[0]
  124.         totalset = { }
  125.         overlapcheck = { }
  126.         for label, next in state.arcs.iteritems():
  127.             if label in self.dfas:
  128.                 if label in self.first:
  129.                     fset = self.first[label]
  130.                     if fset is None:
  131.                         raise ValueError('recursion for rule %r' % name)
  132.                     fset is None
  133.                 else:
  134.                     self.calcfirst(label)
  135.                     fset = self.first[label]
  136.                 totalset.update(fset)
  137.                 overlapcheck[label] = fset
  138.                 continue
  139.             totalset[label] = 1
  140.             overlapcheck[label] = {
  141.                 label: 1 }
  142.         
  143.         inverse = { }
  144.         for label, itsfirst in overlapcheck.iteritems():
  145.             for symbol in itsfirst:
  146.                 if symbol in inverse:
  147.                     raise ValueError('rule %s is ambiguous; %s is in the first sets of %s as well as %s' % (name, symbol, label, inverse[symbol]))
  148.                 symbol in inverse
  149.                 inverse[symbol] = label
  150.             
  151.         
  152.         self.first[name] = totalset
  153.  
  154.     
  155.     def parse(self):
  156.         dfas = { }
  157.         startsymbol = None
  158.         while self.type != token.ENDMARKER:
  159.             while self.type == token.NEWLINE:
  160.                 self.gettoken()
  161.             name = self.expect(token.NAME)
  162.             self.expect(token.OP, ':')
  163.             (a, z) = self.parse_rhs()
  164.             self.expect(token.NEWLINE)
  165.             dfa = self.make_dfa(a, z)
  166.             oldlen = len(dfa)
  167.             self.simplify_dfa(dfa)
  168.             newlen = len(dfa)
  169.             dfas[name] = dfa
  170.             if startsymbol is None:
  171.                 startsymbol = name
  172.                 continue
  173.         return (dfas, startsymbol)
  174.  
  175.     
  176.     def make_dfa(self, start, finish):
  177.         if not isinstance(start, NFAState):
  178.             raise AssertionError
  179.         if not isinstance(finish, NFAState):
  180.             raise AssertionError
  181.         
  182.         def closure(state):
  183.             base = { }
  184.             addclosure(state, base)
  185.             return base
  186.  
  187.         
  188.         def addclosure(state, base):
  189.             if not isinstance(state, NFAState):
  190.                 raise AssertionError
  191.             if state in base:
  192.                 return None
  193.             base[state] = 1
  194.             for label, next in state.arcs:
  195.                 if label is None:
  196.                     addclosure(next, base)
  197.                     continue
  198.                 state in base
  199.             
  200.  
  201.         states = [
  202.             DFAState(closure(start), finish)]
  203.         for state in states:
  204.             arcs = { }
  205.             for nfastate in state.nfaset:
  206.                 for label, next in nfastate.arcs:
  207.                     if label is not None:
  208.                         addclosure(next, arcs.setdefault(label, { }))
  209.                         continue
  210.                     ((isinstance(finish, NFAState),),)
  211.                 
  212.             
  213.             for label, nfaset in arcs.iteritems():
  214.                 for st in states:
  215.                     if st.nfaset == nfaset:
  216.                         break
  217.                         continue
  218.                     isinstance(start, NFAState)
  219.                 else:
  220.                     st = DFAState(nfaset, finish)
  221.                 state.addarc(st, label)
  222.             
  223.         
  224.         return states
  225.  
  226.     
  227.     def dump_nfa(self, name, start, finish):
  228.         print 'Dump of NFA for', name
  229.         todo = [
  230.             start]
  231.         for i, state in enumerate(todo):
  232.             print '  State', i,
  233.             if not state is finish or '(final)':
  234.                 pass
  235.             print ''
  236.             for label, next in state.arcs:
  237.                 if next in todo:
  238.                     j = todo.index(next)
  239.                 else:
  240.                     j = len(todo)
  241.                     todo.append(next)
  242.                 if label is None:
  243.                     print '    -> %d' % j
  244.                     continue
  245.                 print '    %s -> %d' % (label, j)
  246.             
  247.         
  248.  
  249.     
  250.     def dump_dfa(self, name, dfa):
  251.         print 'Dump of DFA for', name
  252.         for i, state in enumerate(dfa):
  253.             print '  State', i,
  254.             if not state.isfinal or '(final)':
  255.                 pass
  256.             print ''
  257.             for label, next in state.arcs.iteritems():
  258.                 print '    %s -> %d' % (label, dfa.index(next))
  259.             
  260.         
  261.  
  262.     
  263.     def simplify_dfa(self, dfa):
  264.         changes = True
  265.         while changes:
  266.             changes = False
  267.             for i, state_i in enumerate(dfa):
  268.                 for j in range(i + 1, len(dfa)):
  269.                     state_j = dfa[j]
  270.                     if state_i == state_j:
  271.                         del dfa[j]
  272.                         for state in dfa:
  273.                             state.unifystate(state_j, state_i)
  274.                         
  275.                         changes = True
  276.                         break
  277.                         continue
  278.                 
  279.             
  280.  
  281.     
  282.     def parse_rhs(self):
  283.         (a, z) = self.parse_alt()
  284.         if self.value != '|':
  285.             return (a, z)
  286.         aa = NFAState()
  287.         zz = NFAState()
  288.         aa.addarc(a)
  289.         z.addarc(zz)
  290.         while self.value == '|':
  291.             self.gettoken()
  292.             (a, z) = self.parse_alt()
  293.             aa.addarc(a)
  294.             z.addarc(zz)
  295.             continue
  296.             self.value != '|'
  297.         return (aa, zz)
  298.  
  299.     
  300.     def parse_alt(self):
  301.         (a, b) = self.parse_item()
  302.         while self.value in ('(', '[') or self.type in (token.NAME, token.STRING):
  303.             (c, d) = self.parse_item()
  304.             b.addarc(c)
  305.             b = d
  306.         return (a, b)
  307.  
  308.     
  309.     def parse_item(self):
  310.         if self.value == '[':
  311.             self.gettoken()
  312.             (a, z) = self.parse_rhs()
  313.             self.expect(token.OP, ']')
  314.             a.addarc(z)
  315.             return (a, z)
  316.         (a, z) = self.parse_atom()
  317.         value = self.value
  318.         if value not in ('+', '*'):
  319.             return (a, z)
  320.         self.gettoken()
  321.         z.addarc(a)
  322.         if value == '+':
  323.             return (a, z)
  324.         return (a, a)
  325.  
  326.     
  327.     def parse_atom(self):
  328.         if self.value == '(':
  329.             self.gettoken()
  330.             (a, z) = self.parse_rhs()
  331.             self.expect(token.OP, ')')
  332.             return (a, z)
  333.         if self.type in (token.NAME, token.STRING):
  334.             a = NFAState()
  335.             z = NFAState()
  336.             a.addarc(z, self.value)
  337.             self.gettoken()
  338.             return (a, z)
  339.         self.raise_error('expected (...) or NAME or STRING, got %s/%s', self.type, self.value)
  340.  
  341.     
  342.     def expect(self, type, value = None):
  343.         if (self.type != type or value is not None) and self.value != value:
  344.             self.raise_error('expected %s/%s, got %s/%s', type, value, self.type, self.value)
  345.         
  346.         value = self.value
  347.         self.gettoken()
  348.         return value
  349.  
  350.     
  351.     def gettoken(self):
  352.         tup = self.generator.next()
  353.         while tup[0] in (tokenize.COMMENT, tokenize.NL):
  354.             tup = self.generator.next()
  355.         (self.type, self.value, self.begin, self.end, self.line) = tup
  356.  
  357.     
  358.     def raise_error(self, msg, *args):
  359.         if args:
  360.             
  361.             try:
  362.                 msg = msg % args
  363.             msg = ' '.join([
  364.                 msg] + map(str, args))
  365.  
  366.         
  367.         raise SyntaxError(msg, (self.filename, self.end[0], self.end[1], self.line))
  368.  
  369.  
  370.  
  371. class NFAState(object):
  372.     
  373.     def __init__(self):
  374.         self.arcs = []
  375.  
  376.     
  377.     def addarc(self, next, label = None):
  378.         if not label is None and isinstance(label, str):
  379.             raise AssertionError
  380.         if not isinstance(next, NFAState):
  381.             raise AssertionError
  382.         self.arcs.append((label, next))
  383.  
  384.  
  385.  
  386. class DFAState(object):
  387.     
  388.     def __init__(self, nfaset, final):
  389.         if not isinstance(nfaset, dict):
  390.             raise AssertionError
  391.         if not isinstance(iter(nfaset).next(), NFAState):
  392.             raise AssertionError
  393.         if not isinstance(final, NFAState):
  394.             raise AssertionError
  395.         self.nfaset = nfaset
  396.         self.isfinal = final in nfaset
  397.         self.arcs = { }
  398.  
  399.     
  400.     def addarc(self, next, label):
  401.         if not isinstance(label, str):
  402.             raise AssertionError
  403.         if not label not in self.arcs:
  404.             raise AssertionError
  405.         if not isinstance(next, DFAState):
  406.             raise AssertionError
  407.         self.arcs[label] = next
  408.  
  409.     
  410.     def unifystate(self, old, new):
  411.         for label, next in self.arcs.iteritems():
  412.             if next is old:
  413.                 self.arcs[label] = new
  414.                 continue
  415.         
  416.  
  417.     
  418.     def __eq__(self, other):
  419.         if not isinstance(other, DFAState):
  420.             raise AssertionError
  421.         if self.isfinal != other.isfinal:
  422.             return False
  423.         if len(self.arcs) != len(other.arcs):
  424.             return False
  425.         for label, next in self.arcs.iteritems():
  426.             if next is not other.arcs.get(label):
  427.                 return False
  428.         
  429.         return True
  430.  
  431.  
  432.  
  433. def generate_grammar(filename = 'Grammar.txt'):
  434.     p = ParserGenerator(filename)
  435.     return p.make_grammar()
  436.  
  437.