xmldtd.py

Python Development Environment (Python IDE plugin for Eclipse). Features editor, code completion, re

        elif self.type=="IDREFS" or self.type=="ENTITIES":
            for token in string.split(value):
                if not matches(reg_name,token):
                    parser.report_error(2021,(token,self.name))

    def get_name(self):
        "Returns the attribute name."
        return self.name
        
    def get_type(self):
        "Returns the type of the attribute. (ID, CDATA etc)"
        return self.type

    def get_decl(self):
        "Returns the declaration (#IMPLIED, #REQUIRED, #FIXED or #DEFAULT)."
        return self.decl

    def get_default(self):
        """Returns the default value of the attribute, or None if none has
        been declared."""
        return self.default    
                
# ==============================
# Entities
# ==============================

class InternalEntity:

    def __init__(self,name,value):
	self.name=name
	self.value=value

    def is_internal(self):
	return 1

    def get_value(self):
        "Returns the replacement text of the entity."
        return self.value
    
class ExternalEntity:

    def __init__(self,name,pubid,sysid,notation):
	self.name=name
	self.pubid=pubid
	self.sysid=sysid
	self.notation=notation

    def is_parsed(self):
        "True if this is a parsed entity."
	return self.notation==""
	
    def is_internal(self):
	return 0

    def get_pubid(self):
        "Returns the public identifier of the entity."
        return self.pubid

    def get_sysid(self):
        "Returns the system identifier of the entity."
        return self.sysid

    def get_notation(self):
        "Returns the notation of the entity, or None if there is none."
        return self.notation

# ==============================
# Internal classes
# ==============================

# Non-deterministic state model builder

class FNDABuilder:
    "Builds a finite non-deterministic automaton."

    def __init__(self):
        self.__current=0
        self.__transitions=[[]]
        self.__mem=[]

    def remember_state(self):
        "Makes the builder remember the current state."
        self.__mem.append(self.__current)

    def set_current_to_remembered(self):
        """Makes the current state the last remembered one. The last remembered
        one is not forgotten."""
        self.__current=self.__mem[-1]
        
    def forget_state(self):
        "Makes the builder forget the current remembered state."
        del self.__mem[-1]

    def new_state(self):
        "Creates a new last state and makes it the current one."
        self.__transitions.append([])
        self.__current=len(self.__transitions)-1

    def get_automaton(self):
        "Returns the automaton produced by the builder."
        return self.__transitions

    def get_current_state(self):
        "Returns the current state."
        return self.__current

    def new_transition(self,label,frm,to):
        "Creates a new transition from frm to to, over label."
        self.__transitions[frm].append((to,label))

    def new_transition_to_new(self,label):
        """Creates a new transition from the current state to a new state,
        which becomes the new current state."""
        self.remember_state()
        self.new_state()
        self.__transitions[self.__mem[-1]].append((self.__current,label))
        self.forget_state()

    def new_transition_cur2rem(self,label):
        """Adds a new transition from the current state to the last remembered
        state."""
        self.__transitions[self.__current].append((self.__mem[-1],label))

    def new_transition_rem2cur(self,label):
        """Creates a new transition from the current state to the last
        remembered one."""
        self.__transitions[self.__mem[-1]].append((self.__current,label))

    def new_transition_2cur(self,frm,label):
        "Creates a new transition from frm to current state, with label."
        self.__transitions[frm].append((self.__current,label))
        
# Content model class

class ContentModel:
    "Represents a singleton content model. (Internal.)"

    def __init__(self,contents,modifier):
	self.contents=contents
	self.modifier=modifier
        
    def add_states(self,builder):
        "Builds the part of the automaton corresponding to this model part."
        if self.modifier=="?":
            builder.remember_state()
            self.add_contents(builder)
            builder.new_transition_rem2cur("")
            builder.forget_state()
        elif self.modifier=="+":
            self.add_contents(builder)
            builder.remember_state()
            self.add_contents(builder,1)
            builder.set_current_to_remembered()
            builder.forget_state()
        elif self.modifier=="*":
            builder.remember_state()
            builder.new_transition_to_new("")
            self.add_contents(builder,1)
            builder.new_transition_rem2cur("")
            builder.forget_state()
        else:
            self.add_contents(builder)

    def add_contents(self,builder,loop=0):
        """Adds the states and transitions belonging to the self.contents
        parts. If loop is true the states will loop back to the first state."""
        if type(self.contents[0])==types.InstanceType:
            if loop:
                builder.remember_state()
                self.contents[0].add_states(builder)
                builder.new_transition_cur2rem("")
                builder.set_current_to_remembered()
                builder.forget_state()
            else:
                self.contents[0].add_states(builder)
        else:
            if loop:
                builder.new_transition(self.contents[0],
                                       builder.get_current_state(),
                                       builder.get_current_state())
            else:
                builder.new_transition_to_new(self.contents[0])
            
# Sequential content model
    
class SeqContentModel(ContentModel):
    "Represents a sequential content model. (Internal.)"

    def add_contents(self,builder,loop=0):
        if loop:
            builder.remember_state()
        
        for cp in self.contents:
            cp.add_states(builder)

        if loop:
            builder.new_transition_cur2rem("")
            builder.forget_state()
    
# Choice content model

class ChoiceContentModel(ContentModel):
    "Represents a choice content model. (Internal.)"

    def add_contents(self,builder,loop=0):
        builder.remember_state()
        end_states=[] # The states at the end of each alternative
        
        for cp in self.contents:
            builder.new_state()
            builder.new_transition_rem2cur("")
            cp.add_states(builder)
            end_states.append(builder.get_current_state())

        builder.new_state()
        for state in end_states:
            builder.new_transition_2cur(state,"")

        if loop:
            builder.new_transition_cur2rem("")

        builder.forget_state()
    
# ==============================
# Conversion of FDAs
# ==============================

def hash(included):
    "Creates a hash number from the included array."
    no=0
    exp=1L
    for state in included:
	if state:
	    no=no+exp
	exp=exp*2L

    return no

def fnda2fda(transitions,final_state,parser):
    """Converts a finite-state non-deterministic automaton into a deterministic
    one."""

    # transitions: old FNDA as [[(to,over),(to,over),...],
    #                           [(to,over),(to,over),...]] structure
    # new FDA as [{over:to,over:to,...},
    #             {over:to,over:to,...}] structure
    # err: error-handler

    #print_trans(transitions)
    transitions.append([])
    new_states={}

    # Compute the e-closure of the start state
    closure_hash={}
    start_state=[0]*len(transitions)
    compute_closure(0,start_state,transitions)
    state_key=hash(start_state)
    closure_hash[0]=state_key

    # Add transitions and the other states
    add_transitions(0,transitions,new_states,start_state,state_key,parser,
                    closure_hash)
    
    states=new_states.keys()
    states.sort()

    #print_states(new_states,2)
    
    for state in states:
	if state % 2==1:
	    new_states["start"]=state
	    break

    new_states["final"]=pow(2L,final_state)
    return new_states
    
def add_transitions(ix,transitions,new_states,cur_state_list,state_key,parser,
                    closure_hash):
    "Set up transitions and create new states."

    new_states[state_key]={} # OK, a new one, create it
    new_trans={} # Hash from label to a list of the possible destination states

    # Find all transitions from this set of states and group them by their
    # labels in the new_trans hash
    
    no=0
    for old_state in cur_state_list:
	if old_state:
	    for (to,what) in transitions[no]:
		if what!="":
                    if new_trans.has_key(what):
                        new_trans[what].append(to)
                    else:
                        new_trans[what]=[to]

	no=no+1

    # Go through the list of transitions, creating new transitions and
    # destination states in the model
        
    for (over,destlist) in new_trans.items():
        # creating new state                    

        # Reports ambiguity, but rather crudely. Will improve this later.
#         if len(destlist)>1:
#             parser.report_error(1008)

        if len(destlist)==1 and closure_hash.has_key(destlist[0]):
            # The closure of this state has been computed before, don't repeat
            new_state=closure_hash[destlist[0]]
        else:
            new_inc=[0]*len(transitions)
            for to in destlist:
                compute_closure(to,new_inc,transitions)

            new_state=hash(new_inc)
            if len(destlist)==1:
                closure_hash[destlist[0]]=new_state

        # add transition and destination state
        new_states[state_key][over]=new_state
        if not new_states.has_key(new_state):
            add_transitions(to,transitions,new_states,new_inc,\
                            new_state,parser,closure_hash)
        
def compute_closure(ix,included,transitions):
    "Computes the e-closure of this state."
    included[ix]=1
    for (to,what) in transitions[ix]:
        if what=="" and not included[to]:
            compute_closure(to,included,transitions)
        
def print_trans(model):
    ix=0
    for transitions in model:        
        print "STATE: %d" % ix
        for step in transitions:
            print "  TO %d OVER %s" % step
        ix=ix+1
        raw_input()
        
def print_states(states,stop=0):
    assert not (states.has_key("start") or states.has_key("final"))
    
    for trans_key in states.keys():
	trans=states[trans_key]
	print "State: "+`trans_key`
	for (to,what) in trans:
	    try:
		print "  To: "+`to`+" over: "+what
	    except TypeError,e:
		print "ERROR: "+`what`

        if stop>1:
            raw_input()

    if stop:
        raw_input()

def make_empty_model():
    "Constructs a state model for empty content models."
    return { 1:{}, "final":1, "start":1 }

def make_model(cmhash,content_model,err):
    "Creates an FDA from the content model."
    cm=`content_model`
    if cmhash.has_key(cm):
        return cmhash[cm]
    else:    
        content_model=make_objects(content_model)
        builder=FNDABuilder()
        content_model.add_states(builder)
        content_model=fnda2fda(builder.get_automaton(),
                               builder.get_current_state(),
                               err)
        cmhash[cm]=content_model
        return content_model

def make_objects(content_model):
    "Turns a tuple-ized content model into one based on objects."
    (sep,contents,mod)=content_model
    if contents[0][0]=="#PCDATA":
        mod="*" # it's implied that #PCDATA can occur more than once

    newconts=[]
    for tup in contents:
        if len(tup)==2:
            newconts.append(ContentModel([tup[0]],tup[1]))
        else:
            newconts.append(make_objects(tup))
    
    if sep==",":
        return SeqContentModel(newconts,mod)
    elif sep=="|":
        return ChoiceContentModel(newconts,mod)
    elif sep=="":
        return ContentModel(newconts,mod)

# --- Various utilities
    
def compile_content_model(cm):
    "Parses a content model string, returning a compiled content model."
    import dtdparser,utils

    p=dtdparser.DTDParser()
    p.set_error_handler(utils.ErrorPrinter(p))
    p.data=cm[1:]
    p.datasize=len(p.data)
    p.final=1
    return make_model({},p._parse_content_model(),p)

def parse_content_model(cm):
    "Parses a content model string, returning a compiled content model."
    import dtdparser,utils

    p=dtdparser.DTDParser()
    p.set_error_handler(utils.ErrorPrinter(p))
    p.data=cm[1:]
    p.datasize=len(p.data)
    p.final=1
    return p._parse_content_model()

def load_dtd(sysid):
    import dtdparser,utils
    
    dp=dtdparser.DTDParser()
    dp.set_error_handler(utils.ErrorPrinter(dp))
    dtd=CompleteDTD(dp)
    dp.set_dtd_consumer(dtd)
    dp.parse_resource(sysid)
    
    return dtd