yapps2.py

一个java写的proxy的例子

# Yapps 2.0 - yet another python parser system
# Amit J Patel, January 1999
# See http://theory.stanford.edu/~amitp/Yapps/ for documentation and updates

# notes - generates rules in correct order now
# no more tail rec elim
# should be re-entrant

from string import *
from yappsrt import *
import regex, re

INDENT = " "*4

class Generator:
    def __init__(self, name, options, tokens, rules):
        self.change_count = 0
        self.name = name
        self.options = options
        self.preparser = ''
        self.postparser = None
        
        self.tokens = {} # Map from tokens to regexps
        self.ignore = [] # List of token names to ignore in parsing
        self.terminals = [] # List of token names (to maintain ordering)
        for n,t in tokens:
            if n == '#ignore':
                n = t
                self.ignore.append(n)
            if n in self.tokens.keys() and self.tokens[n] != t:
                print 'Warning: token', n, 'multiply defined.'
            self.tokens[n] = t
            self.terminals.append(n)
            
        self.rules = {} # Map from rule names to parser nodes
        self.params = {} # Map from rule names to parameters
        self.goals = [] # List of rule names (to maintain ordering)
        for n,p,r in rules:
            self.params[n] = p
            self.rules[n] = r
            self.goals.append(n)
            
        import sys
        self.output = sys.stdout

    def __getitem__(self, name):
        # Get options
        return self.options.get(name, 0)
    
    def non_ignored_tokens(self):
        return filter(lambda x, i=self.ignore: x not in i, self.terminals)
    
    def changed(self):
        self.change_count = 1+self.change_count

    def subset(self, a, b):
        "See if all elements of a are inside b"
        for x in a:
            if x not in b: return 0
        return 1
    
    def equal_set(self, a, b):
        "See if a and b have the same elements"
        if len(a) != len(b): return 0
        if a == b: return 1
        return self.subset(a, b) and self.subset(b, a)
    
    def add_to(self, parent, additions):
        "Modify parent to include all elements in additions"
        for x in additions:
            if x not in parent:
                parent.append(x)
                self.changed()

    def equate(self, a, b):
        self.add_to(a, b)
        self.add_to(b, a)

    def write(self, *args):
        for a in args:
            self.output.write(a)

    def in_test(self, x, full, b):
        if not b: return '0'
        if len(b)==1: return '%s == %s' % (x, `b[0]`)
        if full and len(b) > len(full)/2:
            # Reverse the sense of the test.
            not_b = filter(lambda x, b=b: x not in b, full)
            return self.not_in_test(x, full, not_b)
        return '%s in %s' % (x, `b`)
    
    def not_in_test(self, x, full, b):
        if not b: return '1'
        if len(b)==1: return '%s != %s' % (x, `b[0]`)
        return '%s not in %s' % (x, `b`)

    def peek_call(self, a):
        a_set = (`a`[1:-1])
        if self.equal_set(a, self.non_ignored_tokens()): a_set = ''
        if self['context-insensitive-scanner']: a_set = ''
        return 'self._peek(%s)' % a_set
    
    def peek_test(self, a, b):
        if self.subset(a, b): return '1'
        if self['context-insensitive-scanner']: a = self.non_ignored_tokens()
        return self.in_test(self.peek_call(a), a, b)

    def not_peek_test(self, a, b):
        if self.subset(a, b): return '0'
        return self.not_in_test(self.peek_call(a), a, b)

    def calculate(self):
        while 1:
            for r in self.goals:
                self.rules[r].setup(self, r)
            if self.change_count == 0: break
            self.change_count = 0

        while 1:
            for r in self.goals:
                self.rules[r].update(self)                
            if self.change_count == 0: break
            self.change_count = 0

    def dump_information(self):
        self.calculate()
        for r in self.goals:
            print '    _____' + '_'*len(r)
            print ('___/Rule '+r+'\\' + '_'*80)[:79]
            queue = [self.rules[r]]
            while queue:
                top = queue[0]
                del queue[0]

                print `top`
                top.first.sort()
                top.follow.sort()
                eps = []
                if top.accepts_epsilon: eps = ['(null)']
                print '     FIRST:', join(top.first+eps, ', ')
                print '    FOLLOW:', join(top.follow, ', ')
                for x in top.get_children(): queue.append(x)
                
    def generate_output(self):
        self.calculate()
        self.write(self.preparser)
        self.write("from string import *\n")
        self.write("import re\n")
        self.write("from yappsrt import *\n")
	self.write("\n")
	self.write("class ", self.name, "Scanner(Scanner):\n")
	self.write("    def __init__(self, str):\n")
	self.write("        Scanner.__init__(self,[\n")
	for p in self.terminals:
	    self.write("            (", `p`, ", ", `self.tokens[p]`, "),\n")
	self.write("            ], "+`self.ignore`+", str)\n")
	self.write("\n")
        
        self.write("class ", self.name, "(Parser):\n")
        for r in self.goals:
            self.write(INDENT, "def ", r, "(self")
            if self.params[r]: self.write(", ", self.params[r])
            self.write("):\n")
            self.rules[r].output(self, INDENT+INDENT)
            self.write("\n")

        self.write("\n")
        self.write("def parse(rule, text):\n")
        self.write("    P = ", self.name, "(", self.name, "Scanner(text))\n")
        self.write("    return wrap_error_reporter(P, rule)\n")
        self.write("\n")
        if self.postparser is not None:
            self.write(self.postparser)
        else:
            self.write("if __name__=='__main__':\n")
            self.write(INDENT, "from sys import argv, stdin\n")
            self.write(INDENT, "if len(argv) >= 2:\n")
            self.write(INDENT*2, "if len(argv) >= 3:\n")
            self.write(INDENT*3, "f = open(argv[2],'r')\n")
            self.write(INDENT*2, "else:\n")
            self.write(INDENT*3, "f = stdin\n")
            self.write(INDENT*2, "print parse(argv[1], f.read())\n")
            self.write(INDENT, "else: print 'Args:  <rule> [<filename>]'\n")

######################################################################
class Node:
    def __init__(self):
        self.first = []
        self.follow = []
        self.accepts_epsilon = 0
        self.rule = '?'
        
    def setup(self, gen, rule):
        # Setup will change accepts_epsilon,
        # sometimes from 0 to 1 but never 1 to 0.
        # It will take a finite number of steps to set things up
        self.rule = rule

    def used(self, vars):
        "Return two lists: one of vars used, and the other of vars assigned"
        return vars, []

    def get_children(self):
        "Return a list of sub-nodes"
        return []
    
    def __repr__(self):
        return str(self)
    
    def update(self, gen):
        if self.accepts_epsilon:
            gen.add_to(self.first, self.follow)

    def output(self, gen, indent):
        "Write out code to _gen_ with _indent_:string indentation"
        gen.write(indent, "assert 0 # Invalid parser node\n")
    
class Terminal(Node):
    def __init__(self, token):
        Node.__init__(self)
        self.token = token
        self.accepts_epsilon = 0

    def __str__(self):
        return self.token

    def update(self, gen):
        Node.update(self, gen)
        if self.first != [self.token]:
            self.first = [self.token]
            gen.changed()

    def output(self, gen, indent):
        gen.write(indent)
        if re.match('[a-zA-Z_]+', self.token):
            gen.write(self.token, " = ")
        gen.write("self._scan(%s)\n" % `self.token`)
        
class Eval(Node):
    def __init__(self, expr):
        Node.__init__(self)
        self.expr = expr

    def setup(self, gen, rule):
        Node.setup(self, gen, rule)
        if not self.accepts_epsilon:
            self.accepts_epsilon = 1
            gen.changed()

    def __str__(self):
        return '{{ %s }}' % strip(self.expr)

    def output(self, gen, indent):
        gen.write(indent, strip(self.expr), '\n')
        
class NonTerminal(Node):
    def __init__(self, name, args):
        Node.__init__(self)
        self.name = name
        self.args = args

    def setup(self, gen, rule):
        Node.setup(self, gen, rule)
        try:
            self.target = gen.rules[self.name]
            if self.accepts_epsilon != self.target.accepts_epsilon:
                self.accepts_epsilon = self.target.accepts_epsilon
                gen.changed()
        except KeyError: # Oops, it's nonexistent
            print 'Error: no rule <%s>' % self.name
            self.target = self
            
    def __str__(self):
        return '<%s>' % self.name

    def update(self, gen):
        Node.update(self, gen)
        gen.equate(self.first, self.target.first)
        gen.equate(self.follow, self.target.follow)

    def output(self, gen, indent):
        gen.write(indent)
        gen.write(self.name, " = ")
        gen.write("self.", self.name, "(", self.args, ")\n")
        
class Sequence(Node):
    def __init__(self, *children):
        Node.__init__(self)
        self.children = children

    def setup(self, gen, rule):
        Node.setup(self, gen, rule)
        for c in self.children: c.setup(gen, rule)
        
        if not self.accepts_epsilon:
            # If it's not already accepting epsilon, it might now do so.
            for c in self.children:
                # any non-epsilon means all is non-epsilon
                if not c.accepts_epsilon: break 
            else:
                self.accepts_epsilon = 1
                gen.changed()

    def get_children(self):
        return self.children
    
    def __str__(self):
        return '( %s )' % join(map(lambda x: str(x), self.children))

    def update(self, gen):
        Node.update(self, gen)
        for g in self.children:
            g.update(gen)

        empty = 1
        for g_i in range(len(self.children)):
            g = self.children[g_i]
            
            if empty:  gen.add_to(self.first, g.first)
            if not g.accepts_epsilon: empty = 0
            
            if g_i == len(self.children)-1: 
                next = self.follow
            else:
                next = self.children[1+g_i].first
            gen.add_to(g.follow, next)

        if self.children:
            gen.add_to(self.follow, self.children[-1].follow)

    def output(self, gen, indent):
        if self.children:
            for c in self.children:
                c.output(gen, indent)
        else:
            # Placeholder for empty sequences, just in case
            gen.write(indent, 'pass\n')
            
class Choice(Node):
    def __init__(self, *children):
        Node.__init__(self)
        self.children = children

    def setup(self, gen, rule):
        Node.setup(self, gen, rule)
        for c in self.children: c.setup(gen, rule)
            
        if not self.accepts_epsilon:
            for c in self.children:
                if c.accepts_epsilon:
                    self.accepts_epsilon = 1
                    gen.changed()

    def get_children(self):
        return self.children
    
    def __str__(self):
        return '( %s )' % join(map(lambda x: str(x), self.children), ' | ')

    def update(self, gen):
        Node.update(self, gen)
        for g in self.children:
            g.update(gen)

        for g in self.children:
            gen.add_to(self.first, g.first)
            gen.add_to(self.follow, g.follow)
        for g in self.children:
            gen.add_to(g.follow, self.follow)
        if self.accepts_epsilon:
            gen.add_to(self.first, self.follow)

    def output(self, gen, indent):
        test = "if"
        gen.write(indent, "_token_ = ", gen.peek_call(self.first), "\n")
        tokens_seen = []
        tokens_unseen = self.first[:]
        if gen['context-insensitive-scanner']:
            # Context insensitive scanners can return ANY token,
            # not only the ones in first.
            tokens_unseen = gen.non_ignored_tokens()
        for c in self.children:
            testset = c.first[:]
            removed = []