lalr_parsing.lr_zero Namespace Reference

Classes
class	Automaton

Functions
	get_automaton (gr)
	closure (gr, item_set)
	goto (gr, item_set, inp)
	kernels (item_set)

Function Documentation

closure()

lalr_parsing.lr_zero.closure	(		gr,
			item_set )

def closure(gr, item_set):
    result = set(item_set)
    set_queue = item_set
 
    while len(set_queue) > 0:
        new_elements = []
 
        for itemProdId, dot in set_queue:
            pname, pbody = gr.productions[itemProdId]
            if dot == len(pbody) or pbody[dot] not in gr.nonterms:
                continue
 
            nt = pbody[dot]
            nt_offset = gr.nonterm_offset[nt]
            for idx in range(len(nt.productions)):
                new_item_set = (nt_offset + idx, 0)
                if new_item_set not in result:
                    new_elements += [new_item_set]
                    result.add(new_item_set)
 
        set_queue = new_elements
 
    return frozenset(result)
 
 

get_automaton()

lalr_parsing.lr_zero.get_automaton

(

gr

)

def get_automaton(gr):
    dfa = Automaton()
    dfa.states = [closure(gr, [(0, 0)])]
    next_id = 0
 
    dfa.id_from_state[dfa.states[-1]] = next_id
    next_id += 1
 
    seen = set(dfa.states)
    set_queue = dfa.states
    while len(set_queue) > 0:
        new_elements = []
        for item_set in set_queue:
            item_set_id = dfa.id_from_state[item_set]
 
            for symbol in gr.symbols:
                next_item_set = goto(gr, item_set, symbol)
                if len(next_item_set) == 0:
                    continue
 
                if next_item_set not in seen:
                    new_elements += [next_item_set]
                    seen.add(next_item_set)
 
                    dfa.states += [next_item_set]
                    dfa.id_from_state[dfa.states[-1]] = next_id
                    next_id += 1
 
                dfa.goto[(item_set_id, symbol)] = dfa.id_from_state[next_item_set]
 
        set_queue = new_elements
 
    return dfa
 
 

goto()

lalr_parsing.lr_zero.goto	(		gr,
			item_set,
			inp )

def goto(gr, item_set, inp):
    result_set = set()
 
    for prod_index, dot in item_set:
        pname, pbody = gr.productions[prod_index]
        if dot < len(pbody) and pbody[dot] == inp:
            result_set.add((prod_index, dot + 1))
 
    result_set = closure(gr, result_set)
    return result_set
 
 

kernels()

lalr_parsing.lr_zero.kernels

(

item_set

)

def kernels(item_set):
    return frozenset((x, y) for x, y in item_set if y > 0 or x == 0)