#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys

symbols = []
rules = []
data = []
isOriginal = 1


def s_validation():
    #9 represents new start, if S is used on the right side
    global rules, symbols, isOriginal

    for i in rules:
        if(i[3:].find("S") != -1):
            print("WARNING: Starting terminal used on the right side, fixing ...")
            rules.insert(0,"X->S")
            symbols.insert(0,"X")
            isOriginal = 0
            break;


def read_input():
    terminalCount = 0;
    nonTerminalCount = 0;
    ruleCount = 0;
    global symbols
    global rules

    if(len(sys.argv) < 2):
        print("ERROR: Too few arguments. Please, specify path to gramatika.txt")
        sys.exit()

    if sys.argv[1:]:
        grammarpath = sys.argv[1]


    try:
        inFile = open(grammarpath, 'r')
    except IOError:
        print("ERROR : Input file is missing or corrupted")
        sys.exit()
    else:
        terminalCount = int(inFile.readline())
        nonTerminalCount = int(inFile.readline())
        ruleCount = int(inFile.readline())
        for i in range(terminalCount + nonTerminalCount):
            symbols.append(inFile.readline().rstrip('\n\r'))
        for i in range(ruleCount):
            rules.append(inFile.readline().rstrip('\n\r0'))


def unfold(n): #unclod n-th state
    global data
    modified = 0
    stateUnfold = ""

    while True:
        modified = 0
        for i in data[n]: #for each rule recognized so far
            if(len(i) <4 ): #if the rule is already finished
                continue;
            if(str.istitle(i[3]) and stateUnfold.find(i[3])==-1 ): #rule starts with nonTerminal
                stateUnfold += i[3] #set array of nonTerminals unfolded already
                modified = 1; #flag deciding whether the state is unchanged, so we can stop
                for originRule in rules: #for origin rules
                    if(originRule[0] == i[3]): #add rule starting with recognized nonTerminal
                        data[n].append(originRule)


        if (modified == 0):
            return

def lr_0():
    global rules,data
    tempRule = []

    firstTerminal = "S" if isOriginal else "X"
    #------------------------------------initialize first state-----------------------------------------------
    for rule in rules:
        if(rule[0] == firstTerminal): #set first state with firstTerminal rule
            tempRule.append(rule)

    data.append(tempRule)

    #check whether the rule starts with nonTerminal, if so, unfold
    unfold(0)


    #---------------------------------------other states----------------------------------------------
    stateCnt = 0
    isTransfer = 0
    isReduction = 0
    testCnt = 0
    tempState = []

    while True:
        for checkRulesIfNoReduction in data[stateCnt]:
            if(len(checkRulesIfNoReduction) == 3):
                isReduction += 1     #TODO

        for symbol in symbols: #for every symbol
            for rule in data[stateCnt]: #find whether we can move forward on that symbol
                if(len(rule) < 4): #if the rule is already finished
                    continue;
                if(symbol == rule[3]): #we found symbol what we are going to unfold
                    isTransfer = 1        #TODO
                    tempState = [] #create new state
                    for subRule in data[stateCnt]: #iterate through current rules in our state
                        if (len(subRule) < 4):
                            continue;
                        if(subRule[3] == symbol): #if rule starting with letter is found, cut it
                            tempState.append(subRule[:3] + subRule[4:]) #cut the rule

                    data.append(tempState);  #add the state to global state
                    unfold(len(data) -1) #unfold the state

                    testCnt = len(data) #len of data
                    for t in range (testCnt-1): #delete last state if it is duplicate
                        if(data[t] == data[testCnt-1]):
                            data.pop(testCnt-1)
                            break;


        if(isTransfer == 1 and isReduction > 0):
            print "ERROR: KOLIZIA TRANSFER REDUKCIA"
            print "Daná gramatika nie je LR0 gramatikou"
            return
        elif(isReduction > 1):
            print "ERROR: KOLIZIA REDUKCIA REDUKCIA"
            print "Daná gramatika nie je LR0 gramatikou"
            return
        isTransfer = isReduction = 0;
        stateCnt+=1
        if(stateCnt >= len(data)):
            break

    print "Daná gramatika je LR0 gramatikou"


def main():
    read_input()
    s_validation()
    lr_0()


if __name__ == "__main__":
    main()