yacc.py

M5,一个功能强大的多处理器系统模拟器.很多针对处理器架构,性能的研究都使用它作为模拟平台

# For example, starting with a production "N : . A B C", we run it forward
# to obtain "N : A B C ."   We then build a relationship between this final
# state and the starting state.   These relationships are stored in a dictionary
# lookdict.
#
# INCLUDES:
#
# Computes the INCLUDE() relation (p,A) INCLUDES (p',B).
#
# This relation is used to determine non-terminal transitions that occur
# inside of other non-terminal transition states.   (p,A) INCLUDES (p', B)
# if the following holds:
#
#       B -> LAT, where T -> epsilon and p' -L-> p
#
# L is essentially a prefix (which may be empty), T is a suffix that must be
# able to derive an empty string.  State p' must lead to state p with the string L.
#
# -----------------------------------------------------------------------------

def compute_lookback_includes(C,trans,nullable):

    lookdict = {}          # Dictionary of lookback relations
    includedict = {}       # Dictionary of include relations

    # Make a dictionary of non-terminal transitions
    dtrans = {}
    for t in trans:
        dtrans[t] = 1

    # Loop over all transitions and compute lookbacks and includes
    for state,N in trans:
        lookb = []
        includes = []
        for p in C[state]:
            if p.name != N: continue

            # Okay, we have a name match.  We now follow the production all the way
            # through the state machine until we get the . on the right hand side

            lr_index = p.lr_index
            j = state
            while lr_index < p.len - 1:
                 lr_index = lr_index + 1
                 t = p.prod[lr_index]

                 # Check to see if this symbol and state are a non-terminal transition
                 if dtrans.has_key((j,t)):
                       # Yes.  Okay, there is some chance that this is an includes relation
                       # the only way to know for certain is whether the rest of the
                       # production derives empty

                       li = lr_index + 1
                       while li < p.len:
                            if Terminals.has_key(p.prod[li]): break      # No forget it
                            if not nullable.has_key(p.prod[li]): break
                            li = li + 1
                       else:
                            # Appears to be a relation between (j,t) and (state,N)
                            includes.append((j,t))

                 g = lr0_goto(C[j],t)               # Go to next set
                 j = _lr0_cidhash.get(id(g),-1)     # Go to next state

            # When we get here, j is the final state, now we have to locate the production
            for r in C[j]:
                 if r.name != p.name: continue
                 if r.len != p.len:   continue
                 i = 0
                 # This look is comparing a production ". A B C" with "A B C ."
                 while i < r.lr_index:
                      if r.prod[i] != p.prod[i+1]: break
                      i = i + 1
                 else:
                      lookb.append((j,r))
        for i in includes:
             if not includedict.has_key(i): includedict[i] = []
             includedict[i].append((state,N))
        lookdict[(state,N)] = lookb

    return lookdict,includedict

# -----------------------------------------------------------------------------
# digraph()
# traverse()
#
# The following two functions are used to compute set valued functions
# of the form:
#
#     F(x) = F'(x) U U{F(y) | x R y}
#
# This is used to compute the values of Read() sets as well as FOLLOW sets
# in LALR(1) generation.
#
# Inputs:  X    - An input set
#          R    - A relation
#          FP   - Set-valued function
# ------------------------------------------------------------------------------

def digraph(X,R,FP):
    N = { }
    for x in X:
       N[x] = 0
    stack = []
    F = { }
    for x in X:
        if N[x] == 0: traverse(x,N,stack,F,X,R,FP)
    return F

def traverse(x,N,stack,F,X,R,FP):
    stack.append(x)
    d = len(stack)
    N[x] = d
    F[x] = FP(x)             # F(X) <- F'(x)

    rel = R(x)               # Get y's related to x
    for y in rel:
        if N[y] == 0:
             traverse(y,N,stack,F,X,R,FP)
        N[x] = min(N[x],N[y])
        for a in F.get(y,[]):
            if a not in F[x]: F[x].append(a)
    if N[x] == d:
       N[stack[-1]] = sys.maxint
       F[stack[-1]] = F[x]
       element = stack.pop()
       while element != x:
           N[stack[-1]] = sys.maxint
           F[stack[-1]] = F[x]
           element = stack.pop()

# -----------------------------------------------------------------------------
# compute_read_sets()
#
# Given a set of LR(0) items, this function computes the read sets.
#
# Inputs:  C        =  Set of LR(0) items
#          ntrans   = Set of nonterminal transitions
#          nullable = Set of empty transitions
#
# Returns a set containing the read sets
# -----------------------------------------------------------------------------

def compute_read_sets(C, ntrans, nullable):
    FP = lambda x: dr_relation(C,x,nullable)
    R =  lambda x: reads_relation(C,x,nullable)
    F = digraph(ntrans,R,FP)
    return F

# -----------------------------------------------------------------------------
# compute_follow_sets()
#
# Given a set of LR(0) items, a set of non-terminal transitions, a readset,
# and an include set, this function computes the follow sets
#
# Follow(p,A) = Read(p,A) U U {Follow(p',B) | (p,A) INCLUDES (p',B)}
#
# Inputs:
#            ntrans     = Set of nonterminal transitions
#            readsets   = Readset (previously computed)
#            inclsets   = Include sets (previously computed)
#
# Returns a set containing the follow sets
# -----------------------------------------------------------------------------

def compute_follow_sets(ntrans,readsets,inclsets):
     FP = lambda x: readsets[x]
     R  = lambda x: inclsets.get(x,[])
     F = digraph(ntrans,R,FP)
     return F

# -----------------------------------------------------------------------------
# add_lookaheads()
#
# Attaches the lookahead symbols to grammar rules.
#
# Inputs:    lookbacks         -  Set of lookback relations
#            followset         -  Computed follow set
#
# This function directly attaches the lookaheads to productions contained
# in the lookbacks set
# -----------------------------------------------------------------------------

def add_lookaheads(lookbacks,followset):
    for trans,lb in lookbacks.items():
        # Loop over productions in lookback
        for state,p in lb:
             if not p.lookaheads.has_key(state):
                  p.lookaheads[state] = []
             f = followset.get(trans,[])
             for a in f:
                  if a not in p.lookaheads[state]: p.lookaheads[state].append(a)

# -----------------------------------------------------------------------------
# add_lalr_lookaheads()
#
# This function does all of the work of adding lookahead information for use
# with LALR parsing
# -----------------------------------------------------------------------------

def add_lalr_lookaheads(C):
    # Determine all of the nullable nonterminals
    nullable = compute_nullable_nonterminals()

    # Find all non-terminal transitions
    trans = find_nonterminal_transitions(C)

    # Compute read sets
    readsets = compute_read_sets(C,trans,nullable)

    # Compute lookback/includes relations
    lookd, included = compute_lookback_includes(C,trans,nullable)

    # Compute LALR FOLLOW sets
    followsets = compute_follow_sets(trans,readsets,included)

    # Add all of the lookaheads
    add_lookaheads(lookd,followsets)

# -----------------------------------------------------------------------------
# lr_parse_table()
#
# This function constructs the parse tables for SLR or LALR
# -----------------------------------------------------------------------------
def lr_parse_table(method):
    global _lr_method
    goto = _lr_goto           # Goto array
    action = _lr_action       # Action array
    actionp = { }             # Action production array (temporary)

    _lr_method = method

    n_srconflict = 0
    n_rrconflict = 0

    if yaccdebug:
        sys.stderr.write("yacc: Generating %s parsing table...\n" % method)
        _vf.write("\n\nParsing method: %s\n\n" % method)

    # Step 1: Construct C = { I0, I1, ... IN}, collection of LR(0) items
    # This determines the number of states

    C = lr0_items()

    if method == 'LALR':
        add_lalr_lookaheads(C)


    # Build the parser table, state by state
    st = 0
    for I in C:
        # Loop over each production in I
        actlist = [ ]              # List of actions
        st_action  = { }
        st_actionp = { }
        st_goto    = { }
        if yaccdebug:
            _vf.write("\nstate %d\n\n" % st)
            for p in I:
                _vf.write("    (%d) %s\n" % (p.number, str(p)))
            _vf.write("\n")

        for p in I:
            try:
                if p.len == p.lr_index + 1:
                    if p.name == "S'":
                        # Start symbol. Accept!
                        st_action["$end"] = 0
                        st_actionp["$end"] = p
                    else:
                        # We are at the end of a production.  Reduce!
                        if method == 'LALR':
                            laheads = p.lookaheads[st]
                        else:
                            laheads = Follow[p.name]
                        for a in laheads:
                            actlist.append((a,p,"reduce using rule %d (%s)" % (p.number,p)))
                            r = st_action.get(a,None)
                            if r is not None:
                                # Whoa. Have a shift/reduce or reduce/reduce conflict
                                if r > 0:
                                    # Need to decide on shift or reduce here
                                    # By default we favor shifting. Need to add
                                    # some precedence rules here.
                                    sprec,slevel = Productions[st_actionp[a].number].prec
                                    rprec,rlevel = Precedence.get(a,('right',0))
                                    if (slevel < rlevel) or ((slevel == rlevel) and (rprec == 'left')):
                                        # We really need to reduce here.
                                        st_action[a] = -p.number
                                        st_actionp[a] = p
                                        if not slevel and not rlevel:
                                            _vfc.write("shift/reduce conflict in state %d resolved as reduce.\n" % st)
                                            _vf.write("  ! shift/reduce conflict for %s resolved as reduce.\n" % a)
                                            n_srconflict += 1
                                    elif (slevel == rlevel) and (rprec == 'nonassoc'):
                                        st_action[a] = None
                                    else:
                                        # Hmmm. Guess we'll keep the shift
                                        if not rlevel:
                                            _vfc.write("shift/reduce conflict in state %d resolved as shift.\n" % st)
                                            _vf.write("  ! shift/reduce conflict for %s resolved as shift.\n" % a)
                                            n_srconflict +=1
                                elif r < 0:
                                    # Reduce/reduce conflict.   In this case, we favor the rule
                                    # that was defined first in the grammar file
                                    oldp = Productions[-r]
                                    pp = Productions[p.number]
                                    if oldp.line > pp.line:
                                        st_action[a] = -p.number
                                        st_actionp[a] = p
                                    # sys.stderr.write("Reduce/reduce conflict in state %d\n" % st)
                                    n_rrconflict += 1
                                    _vfc.write("reduce/reduce conflict in state %d resolved using rule %d (%s).\n" % (st, st_actionp[a].number, st_actionp[a]))
                                    _vf.write("  ! reduce/reduce conflict for %s resolved using rule %d (%s).\n" % (a,st_actionp[a].number, st_actionp[a]))
                                else:
                                    sys.stderr.write("Unknown conflict in state %d\n" % st)
                            else:
                                st_action[a] = -p.number
                                st_actionp[a] = p
                else:
                    i = p.lr_index
                    a = p.prod[i+1]       # Get symbol right after the "."
                    if Terminals.has_key(a):
                        g = lr0_goto(I,a)
                        j = _lr0_cidhash.get(id(g),-1)
                        if j >= 0:
                            # We are in a shift state
                            actlist.append((a,p,"shift and go to state %d" % j))
                            r = st_action.get(a,None)
                            if r is not None:
                                # Whoa have a shift/reduce or shift/shift conflict
                                if r > 0:
                                    if r != j:
                                        sys.stderr.write("Shift/shift conflict in state %d\n" % st)
                                elif r < 0:
                                    # Do a precedence check.
                                    #   -  if precedence of reduce rule is higher, we reduce.
                                    #   -  if precedence of reduce is same and left assoc, we reduce.
                                    #   -  otherwise we shift
                                    rprec,rlevel = Productions[st_actionp[a].number].prec
                                    sprec,slevel = Precedence.get(a,('right',0))
                                    if (slevel > rlevel) or ((slevel == rlevel) and (rprec != 'left')):
                                        # We decide to shift here... highest precedence to shift
                                        st_action[a] = j
                                        st_actionp[a] = p
                                        if not rlevel:
                                            n_srconflict += 1