firstfollow.py

#!/usr/bin/python3
from functools import reduce

token = ['tModule', 'tBegin', 'tEnd', 'tProcedure', 'tFunction', 'tWhile', 'tDo', 'tReturn', 'tIf',
'tThen', 'tElse', 'tVar', 'tNumber', 'tIdent', 'tBoolean', 'tTermOp', 'tFactOp', 'tRelOp', 'tAssign',
'tSemicolon', 'tColon', 'tDot', 'tComma', 'tBang', 'tChar', 'tString', 'tBaseType', 'tLBrak', 'tRBrak',
'tLSquareBrak', 'tRSquareBrak', 'tEOF', 'tIOError', 'tUndefined']

ebnf = {
    'module' : ['tModule', 'tIdent', 'tSemicolon', 'varDeclaration', (['subroutineDecl']), 'tBegin', 'statSequence', 'tEnd', 'tIdent', 'tDot'],
    'type': {0: ['tBaseType'], 1: ['type', 'tLSquareBrak', ['tNumber'], 'tRSquareBrak']},
    'qualident': ['tIdent', (['tLSquareBrak', 'expression', 'tRSquareBrak'])],
    'factor': {0: ['qualident'], 1: ['tNumber'], 2: ['tBoolean'], 3: ['tChar'], 4: ['tString'], 5: ['tLBrak', 'expression', 'tRBrak'], 6: ['subroutineCall'], 7: ['tBang', 'factor']},
    'term': ['factor', (['tFactOp', 'factor'])],
    'simpleexpr': ['tTermOp', 'term', (['tTermOp', 'term'])],
    'expression': ['simpleexpr', ['tRelOp', 'simpleexpr']],
    'assignment': ['qualident', 'tAssign', 'expression'],
    'subroutineCall': ['tIdent', 'tLBrak', ['expression', (['tComma', 'expression'])], 'tRBrak'],
    'ifStatement': ['tIf', 'tLBrak', 'expression', 'tRBrak', 'tThen', 'statSequence', ['tElse', 'statSequence'], 'tEnd'],
    'whileStatement': ['tWhile', 'tLBrak', 'expression', 'tRBrak', 'tDo', 'statSequence', 'tEnd'],
    'returnStatement': ['tReturn', ['expression']],
    'statement': {0: ['assignment'], 1: ['subroutineCall'], 2: ['ifStatement'], 3: ['whileStatement'], 4: ['returnStatement']},
    'statSequence': [['statement', (['tSemicolon', 'statement'])]],
    'varDeclaration': [['tVar', 'varDeclSequence', 'tSemicolon']],
    'varDeclSequence': ['varDecl', (['tSemicolon', 'varDecl'])],
    'varDecl': ['tIdent', (['tComma', 'tIdent']), 'tColon', 'type'],
    'subroutineDecl': [{0: ['procedureDecl'], 1: ['functionDecl']}, 'subroutineBody', 'tIdent', 'tSemicolon'],
    'procedureDecl': ['tProcedure', 'tIdent', ['formalParam'], 'tSemicolon'],
    'functionDecl': ['tFunction', 'tIdent', ['formalParam'], 'tColon', 'type', 'tSemicolon'],
    'formalParam': ['tLBrak', ['varDeclSequence'], 'tRBrak'],
    'subroutineBody': ['varDeclaration', 'tBegin', 'statSequence', 'tEnd'],
}

lrecursion = []

def first(symbol):
    if type(symbol) == dict:
        return reduce(lambda x, y: x | y, [first(s[0]) for s in symbol.values()])
    if type(symbol) == list:
        return set(['e']) | first(symbol[0])
    elif type(symbol) != str:
        print(str(symbol) + ' is not valid symbol')
        return None
    if symbol in token:
        return set([symbol])
    if symbol in lrecursion:
        return set([])
    lrecursion.append(symbol)
    if type(ebnf[symbol]) == dict:
        return reduce(lambda x, y: x | y, [first(s[0]) for s in ebnf[symbol].values()])
    elif type(ebnf[symbol]) == tuple:
        return set(['e']) | first(ebnf[symbol][0][0])
    elif type(ebnf[symbol]) == list:
        return first(ebnf[symbol][0])


for symbol in ebnf.keys():
    lrecursion = []
    print('FIRST( ' + symbol + ' ) = ' + str(first(symbol)))