yacc.py

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

    # We are computing First(x1,x2,x3,...,xn)
    result = [ ]
    for x in beta:
        x_produces_empty = 0

        # Add all the non-<empty> symbols of First[x] to the result.
        for f in First[x]:
            if f == '<empty>':
                x_produces_empty = 1
            else:
                if f not in result: result.append(f)

        if x_produces_empty:
            # We have to consider the next x in beta,
            # i.e. stay in the loop.
            pass
        else:
            # We don't have to consider any further symbols in beta.
            break
    else:
        # There was no 'break' from the loop,
        # so x_produces_empty was true for all x in beta,
        # so beta produces empty as well.
        result.append('<empty>')

    return result


# FOLLOW(x)
# Given a non-terminal.  This function computes the set of all symbols
# that might follow it.  Dragon book, p. 189.

def compute_follow(start=None):
    # Add '$end' to the follow list of the start symbol
    for k in Nonterminals.keys():
        Follow[k] = [ ]

    if not start:
        start = Productions[1].name

    Follow[start] = [ '$end' ]

    while 1:
        didadd = 0
        for p in Productions[1:]:
            # Here is the production set
            for i in range(len(p.prod)):
                B = p.prod[i]
                if Nonterminals.has_key(B):
                    # Okay. We got a non-terminal in a production
                    fst = first(p.prod[i+1:])
                    hasempty = 0
                    for f in fst:
                        if f != '<empty>' and f not in Follow[B]:
                            Follow[B].append(f)
                            didadd = 1
                        if f == '<empty>':
                            hasempty = 1
                    if hasempty or i == (len(p.prod)-1):
                        # Add elements of follow(a) to follow(b)
                        for f in Follow[p.name]:
                            if f not in Follow[B]:
                                Follow[B].append(f)
                                didadd = 1
        if not didadd: break

    if 0 and yaccdebug:
        _vf.write('\nFollow:\n')
        for k in Nonterminals.keys():
            _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Follow[k]])))

# -------------------------------------------------------------------------
# compute_first1()
#
# Compute the value of FIRST1(X) for all symbols
# -------------------------------------------------------------------------
def compute_first1():

    # Terminals:
    for t in Terminals.keys():
        First[t] = [t]

    First['$end'] = ['$end']
    First['#'] = ['#'] # what's this for?

    # Nonterminals:

    # Initialize to the empty set:
    for n in Nonterminals.keys():
        First[n] = []

    # Then propagate symbols until no change:
    while 1:
        some_change = 0
        for n in Nonterminals.keys():
            for p in Prodnames[n]:
                for f in first(p.prod):
                    if f not in First[n]:
                        First[n].append( f )
                        some_change = 1
        if not some_change:
            break

    if 0 and yaccdebug:
        _vf.write('\nFirst:\n')
        for k in Nonterminals.keys():
            _vf.write("%-20s : %s\n" %
                (k, " ".join([str(s) for s in First[k]])))

# -----------------------------------------------------------------------------
#                           === SLR Generation ===
#
# The following functions are used to construct SLR (Simple LR) parsing tables
# as described on p.221-229 of the dragon book.
# -----------------------------------------------------------------------------

# Global variables for the LR parsing engine
def lr_init_vars():
    global _lr_action, _lr_goto, _lr_method
    global _lr_goto_cache, _lr0_cidhash

    _lr_action       = { }        # Action table
    _lr_goto         = { }        # Goto table
    _lr_method       = "Unknown"  # LR method used
    _lr_goto_cache   = { }
    _lr0_cidhash     = { }


# Compute the LR(0) closure operation on I, where I is a set of LR(0) items.
# prodlist is a list of productions.

_add_count = 0       # Counter used to detect cycles

def lr0_closure(I):
    global _add_count

    _add_count += 1
    prodlist = Productions

    # Add everything in I to J
    J = I[:]
    didadd = 1
    while didadd:
        didadd = 0
        for j in J:
            for x in j.lrafter:
                if x.lr0_added == _add_count: continue
                # Add B --> .G to J
                J.append(x.lr_next)
                x.lr0_added = _add_count
                didadd = 1

    return J

# Compute the LR(0) goto function goto(I,X) where I is a set
# of LR(0) items and X is a grammar symbol.   This function is written
# in a way that guarantees uniqueness of the generated goto sets
# (i.e. the same goto set will never be returned as two different Python
# objects).  With uniqueness, we can later do fast set comparisons using
# id(obj) instead of element-wise comparison.

def lr0_goto(I,x):
    # First we look for a previously cached entry
    g = _lr_goto_cache.get((id(I),x),None)
    if g: return g

    # Now we generate the goto set in a way that guarantees uniqueness
    # of the result

    s = _lr_goto_cache.get(x,None)
    if not s:
        s = { }
        _lr_goto_cache[x] = s

    gs = [ ]
    for p in I:
        n = p.lr_next
        if n and n.lrbefore == x:
            s1 = s.get(id(n),None)
            if not s1:
                s1 = { }
                s[id(n)] = s1
            gs.append(n)
            s = s1
    g = s.get('$end',None)
    if not g:
        if gs:
            g = lr0_closure(gs)
            s['$end'] = g
        else:
            s['$end'] = gs
    _lr_goto_cache[(id(I),x)] = g
    return g

_lr0_cidhash = { }

# Compute the LR(0) sets of item function
def lr0_items():

    C = [ lr0_closure([Productions[0].lr_next]) ]
    i = 0
    for I in C:
        _lr0_cidhash[id(I)] = i
        i += 1

    # Loop over the items in C and each grammar symbols
    i = 0
    while i < len(C):
        I = C[i]
        i += 1

        # Collect all of the symbols that could possibly be in the goto(I,X) sets
        asyms = { }
        for ii in I:
            for s in ii.usyms:
                asyms[s] = None

        for x in asyms.keys():
            g = lr0_goto(I,x)
            if not g:  continue
            if _lr0_cidhash.has_key(id(g)): continue
            _lr0_cidhash[id(g)] = len(C)
            C.append(g)

    return C

# -----------------------------------------------------------------------------
#                       ==== LALR(1) Parsing ====
#
# LALR(1) parsing is almost exactly the same as SLR except that instead of
# relying upon Follow() sets when performing reductions, a more selective
# lookahead set that incorporates the state of the LR(0) machine is utilized.
# Thus, we mainly just have to focus on calculating the lookahead sets.
#
# The method used here is due to DeRemer and Pennelo (1982).
#
# DeRemer, F. L., and T. J. Pennelo: "Efficient Computation of LALR(1)
#     Lookahead Sets", ACM Transactions on Programming Languages and Systems,
#     Vol. 4, No. 4, Oct. 1982, pp. 615-649
#
# Further details can also be found in:
#
#  J. Tremblay and P. Sorenson, "The Theory and Practice of Compiler Writing",
#      McGraw-Hill Book Company, (1985).
#
# Note:  This implementation is a complete replacement of the LALR(1)
#        implementation in PLY-1.x releases.   That version was based on
#        a less efficient algorithm and it had bugs in its implementation.
# -----------------------------------------------------------------------------

# -----------------------------------------------------------------------------
# compute_nullable_nonterminals()
#
# Creates a dictionary containing all of the non-terminals that might produce
# an empty production.
# -----------------------------------------------------------------------------

def compute_nullable_nonterminals():
    nullable = {}
    num_nullable = 0
    while 1:
       for p in Productions[1:]:
           if p.len == 0:
                nullable[p.name] = 1
                continue
           for t in p.prod:
                if not nullable.has_key(t): break
           else:
                nullable[p.name] = 1
       if len(nullable) == num_nullable: break
       num_nullable = len(nullable)
    return nullable

# -----------------------------------------------------------------------------
# find_nonterminal_trans(C)
#
# Given a set of LR(0) items, this functions finds all of the non-terminal
# transitions.    These are transitions in which a dot appears immediately before
# a non-terminal.   Returns a list of tuples of the form (state,N) where state
# is the state number and N is the nonterminal symbol.
#
# The input C is the set of LR(0) items.
# -----------------------------------------------------------------------------

def find_nonterminal_transitions(C):
     trans = []
     for state in range(len(C)):
         for p in C[state]:
             if p.lr_index < p.len - 1:
                  t = (state,p.prod[p.lr_index+1])
                  if Nonterminals.has_key(t[1]):
                        if t not in trans: trans.append(t)
         state = state + 1
     return trans

# -----------------------------------------------------------------------------
# dr_relation()
#
# Computes the DR(p,A) relationships for non-terminal transitions.  The input
# is a tuple (state,N) where state is a number and N is a nonterminal symbol.
#
# Returns a list of terminals.
# -----------------------------------------------------------------------------

def dr_relation(C,trans,nullable):
    dr_set = { }
    state,N = trans
    terms = []

    g = lr0_goto(C[state],N)
    for p in g:
       if p.lr_index < p.len - 1:
           a = p.prod[p.lr_index+1]
           if Terminals.has_key(a):
               if a not in terms: terms.append(a)

    # This extra bit is to handle the start state
    if state == 0 and N == Productions[0].prod[0]:
       terms.append('$end')

    return terms

# -----------------------------------------------------------------------------
# reads_relation()
#
# Computes the READS() relation (p,A) READS (t,C).
# -----------------------------------------------------------------------------

def reads_relation(C, trans, empty):
    # Look for empty transitions
    rel = []
    state, N = trans

    g = lr0_goto(C[state],N)
    j = _lr0_cidhash.get(id(g),-1)
    for p in g:
        if p.lr_index < p.len - 1:
             a = p.prod[p.lr_index + 1]
             if empty.has_key(a):
                  rel.append((j,a))

    return rel

# -----------------------------------------------------------------------------
# compute_lookback_includes()
#
# Determines the lookback and includes relations
#
# LOOKBACK:
#
# This relation is determined by running the LR(0) state machine forward.