yacc.py

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

            Terminals[t].append(p.number)
            # Is a terminal.  We'll assign a precedence to p based on this
            if not hasattr(p,"prec"):
                p.prec = Precedence.get(t,('right',0))
        else:
            if not Nonterminals.has_key(t):
                Nonterminals[t] = [ ]
            Nonterminals[t].append(p.number)
        i += 1

    if not hasattr(p,"prec"):
        p.prec = ('right',0)

    # Set final length of productions
    p.len  = len(p.prod)
    p.prod = tuple(p.prod)

    # Calculate unique syms in the production
    p.usyms = [ ]
    for s in p.prod:
        if s not in p.usyms:
            p.usyms.append(s)

    # Add to the global productions list
    try:
        Prodnames[p.name].append(p)
    except KeyError:
        Prodnames[p.name] = [ p ]
    return 0

# Given a raw rule function, this function rips out its doc string
# and adds rules to the grammar

def add_function(f):
    line = f.func_code.co_firstlineno
    file = f.func_code.co_filename
    error = 0

    if isinstance(f,types.MethodType):
        reqdargs = 2
    else:
        reqdargs = 1

    if f.func_code.co_argcount > reqdargs:
        sys.stderr.write("%s:%d: Rule '%s' has too many arguments.\n" % (file,line,f.__name__))
        return -1

    if f.func_code.co_argcount < reqdargs:
        sys.stderr.write("%s:%d: Rule '%s' requires an argument.\n" % (file,line,f.__name__))
        return -1

    if f.__doc__:
        # Split the doc string into lines
        pstrings = f.__doc__.splitlines()
        lastp = None
        dline = line
        for ps in pstrings:
            dline += 1
            p = ps.split()
            if not p: continue
            try:
                if p[0] == '|':
                    # This is a continuation of a previous rule
                    if not lastp:
                        sys.stderr.write("%s:%d: Misplaced '|'.\n" % (file,dline))
                        return -1
                    prodname = lastp
                    if len(p) > 1:
                        syms = p[1:]
                    else:
                        syms = [ ]
                else:
                    prodname = p[0]
                    lastp = prodname
                    assign = p[1]
                    if len(p) > 2:
                        syms = p[2:]
                    else:
                        syms = [ ]
                    if assign != ':' and assign != '::=':
                        sys.stderr.write("%s:%d: Syntax error. Expected ':'\n" % (file,dline))
                        return -1


                e = add_production(f,file,dline,prodname,syms)
                error += e


            except StandardError:
                sys.stderr.write("%s:%d: Syntax error in rule '%s'\n" % (file,dline,ps))
                error -= 1
    else:
        sys.stderr.write("%s:%d: No documentation string specified in function '%s'\n" % (file,line,f.__name__))
    return error


# Cycle checking code (Michael Dyck)

def compute_reachable():
    '''
    Find each symbol that can be reached from the start symbol.
    Print a warning for any nonterminals that can't be reached.
    (Unused terminals have already had their warning.)
    '''
    Reachable = { }
    for s in Terminals.keys() + Nonterminals.keys():
        Reachable[s] = 0

    mark_reachable_from( Productions[0].prod[0], Reachable )

    for s in Nonterminals.keys():
        if not Reachable[s]:
            sys.stderr.write("yacc: Symbol '%s' is unreachable.\n" % s)

def mark_reachable_from(s, Reachable):
    '''
    Mark all symbols that are reachable from symbol s.
    '''
    if Reachable[s]:
        # We've already reached symbol s.
        return
    Reachable[s] = 1
    for p in Prodnames.get(s,[]):
        for r in p.prod:
            mark_reachable_from(r, Reachable)

# -----------------------------------------------------------------------------
# compute_terminates()
#
# This function looks at the various parsing rules and tries to detect
# infinite recursion cycles (grammar rules where there is no possible way
# to derive a string of only terminals).
# -----------------------------------------------------------------------------
def compute_terminates():
    '''
    Raise an error for any symbols that don't terminate.
    '''
    Terminates = {}

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

    Terminates['$end'] = 1

    # Nonterminals:

    # Initialize to false:
    for n in Nonterminals.keys():
        Terminates[n] = 0

    # Then propagate termination until no change:
    while 1:
        some_change = 0
        for (n,pl) in Prodnames.items():
            # Nonterminal n terminates iff any of its productions terminates.
            for p in pl:
                # Production p terminates iff all of its rhs symbols terminate.
                for s in p.prod:
                    if not Terminates[s]:
                        # The symbol s does not terminate,
                        # so production p does not terminate.
                        p_terminates = 0
                        break
                else:
                    # didn't break from the loop,
                    # so every symbol s terminates
                    # so production p terminates.
                    p_terminates = 1

                if p_terminates:
                    # symbol n terminates!
                    if not Terminates[n]:
                        Terminates[n] = 1
                        some_change = 1
                    # Don't need to consider any more productions for this n.
                    break

        if not some_change:
            break

    some_error = 0
    for (s,terminates) in Terminates.items():
        if not terminates:
            if not Prodnames.has_key(s) and not Terminals.has_key(s) and s != 'error':
                # s is used-but-not-defined, and we've already warned of that,
                # so it would be overkill to say that it's also non-terminating.
                pass
            else:
                sys.stderr.write("yacc: Infinite recursion detected for symbol '%s'.\n" % s)
                some_error = 1

    return some_error

# -----------------------------------------------------------------------------
# verify_productions()
#
# This function examines all of the supplied rules to see if they seem valid.
# -----------------------------------------------------------------------------
def verify_productions(cycle_check=1):
    error = 0
    for p in Productions:
        if not p: continue

        for s in p.prod:
            if not Prodnames.has_key(s) and not Terminals.has_key(s) and s != 'error':
                sys.stderr.write("%s:%d: Symbol '%s' used, but not defined as a token or a rule.\n" % (p.file,p.line,s))
                error = 1
                continue

    unused_tok = 0
    # Now verify all of the tokens
    if yaccdebug:
        _vf.write("Unused terminals:\n\n")
    for s,v in Terminals.items():
        if s != 'error' and not v:
            sys.stderr.write("yacc: Warning. Token '%s' defined, but not used.\n" % s)
            if yaccdebug: _vf.write("   %s\n"% s)
            unused_tok += 1

    # Print out all of the productions
    if yaccdebug:
        _vf.write("\nGrammar\n\n")
        for i in range(1,len(Productions)):
            _vf.write("Rule %-5d %s\n" % (i, Productions[i]))

    unused_prod = 0
    # Verify the use of all productions
    for s,v in Nonterminals.items():
        if not v:
            p = Prodnames[s][0]
            sys.stderr.write("%s:%d: Warning. Rule '%s' defined, but not used.\n" % (p.file,p.line, s))
            unused_prod += 1


    if unused_tok == 1:
        sys.stderr.write("yacc: Warning. There is 1 unused token.\n")
    if unused_tok > 1:
        sys.stderr.write("yacc: Warning. There are %d unused tokens.\n" % unused_tok)

    if unused_prod == 1:
        sys.stderr.write("yacc: Warning. There is 1 unused rule.\n")
    if unused_prod > 1:
        sys.stderr.write("yacc: Warning. There are %d unused rules.\n" % unused_prod)

    if yaccdebug:
        _vf.write("\nTerminals, with rules where they appear\n\n")
        ks = Terminals.keys()
        ks.sort()
        for k in ks:
            _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Terminals[k]])))
        _vf.write("\nNonterminals, with rules where they appear\n\n")
        ks = Nonterminals.keys()
        ks.sort()
        for k in ks:
            _vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Nonterminals[k]])))

    if (cycle_check):
        compute_reachable()
        error += compute_terminates()
#        error += check_cycles()
    return error

# -----------------------------------------------------------------------------
# build_lritems()
#
# This function walks the list of productions and builds a complete set of the
# LR items.  The LR items are stored in two ways:  First, they are uniquely
# numbered and placed in the list _lritems.  Second, a linked list of LR items
# is built for each production.  For example:
#
#   E -> E PLUS E
#
# Creates the list
#
#  [E -> . E PLUS E, E -> E . PLUS E, E -> E PLUS . E, E -> E PLUS E . ]
# -----------------------------------------------------------------------------

def build_lritems():
    for p in Productions:
        lastlri = p
        lri = p.lr_item(0)
        i = 0
        while 1:
            lri = p.lr_item(i)
            lastlri.lr_next = lri
            if not lri: break
            lri.lr_num = len(LRitems)
            LRitems.append(lri)
            lastlri = lri
            i += 1

    # In order for the rest of the parser generator to work, we need to
    # guarantee that no more lritems are generated.  Therefore, we nuke
    # the p.lr_item method.  (Only used in debugging)
    # Production.lr_item = None

# -----------------------------------------------------------------------------
# add_precedence()
#
# Given a list of precedence rules, add to the precedence table.
# -----------------------------------------------------------------------------

def add_precedence(plist):
    plevel = 0
    error = 0
    for p in plist:
        plevel += 1
        try:
            prec = p[0]
            terms = p[1:]
            if prec != 'left' and prec != 'right' and prec != 'nonassoc':
                sys.stderr.write("yacc: Invalid precedence '%s'\n" % prec)
                return -1
            for t in terms:
                if Precedence.has_key(t):
                    sys.stderr.write("yacc: Precedence already specified for terminal '%s'\n" % t)
                    error += 1
                    continue
                Precedence[t] = (prec,plevel)
        except:
            sys.stderr.write("yacc: Invalid precedence table.\n")
            error += 1

    return error

# -----------------------------------------------------------------------------
# augment_grammar()
#
# Compute the augmented grammar.  This is just a rule S' -> start where start
# is the starting symbol.
# -----------------------------------------------------------------------------

def augment_grammar(start=None):
    if not start:
        start = Productions[1].name
    Productions[0] = Production(name="S'",prod=[start],number=0,len=1,prec=('right',0),func=None)
    Productions[0].usyms = [ start ]
    Nonterminals[start].append(0)


# -------------------------------------------------------------------------
# first()
#
# Compute the value of FIRST1(beta) where beta is a tuple of symbols.
#
# During execution of compute_first1, the result may be incomplete.
# Afterward (e.g., when called from compute_follow()), it will be complete.
# -------------------------------------------------------------------------
def first(beta):