# Parse a given input program using the LR(0) parser
input = 'aab'

# Define the grammar
grammar = {
  'nonTerminals': ['S', 'A'],
  'terminals': ['a', 'b'],
  'productions': [
    {'left': 'S', 'right': ['A', 'a']},
    {'left': 'S', 'right': ['b']},
    {'left': 'A', 'right': ['a', 'A']},
    {'left': 'A', 'right': []}
  ]
}

# Construct the LR(0) parsing table
parsingTable = {
  0: {
    'S': {'action': 's', 'value': 1},
    'A': {'action': 's', 'value': 2},
    'a': {'action': '', 'value': ''},
    'b': {'action': '', 'value': ''}
  },
  1: {
    'S': {'action': '', 'value': ''},
    'A': {'action': '', 'value': ''},
    'a': {'action': '', 'value': ''},
    'b': {'action': 'r', 'value': 2}
  },
  2: {
    'S': {'action': '', 'value': ''},
    'A': {'action': '', 'value': ''},
    'a': {'action': 's', 'value': 3},
    'b': {'action': '', 'value': ''}
  },
  3: {
    'S': {'action': '', 'value': ''},
    'A': {'action': 'r', 'value': 1},
    'a': {'action': '', 'value': ''},
    'b': {'action': 'r', 'value': 1}
  }
}

# Implement the LR(0) parsing algorithm
def parseInput(input):
  stack = [0] # Stack to store the state transitions
  symbols = list(input) + ['$'] # Input symbols
  currentIndex = 0

  while True:
    currentState = stack[-1] # Get the current state from the top of the stack
    currentSymbol = symbols[currentIndex] # Get the current symbol from the input

    action = parsingTable[currentState][currentSymbol] # Look up the action in the parsing table

    if action['action'] == 's': # Shift action
      stack.append(action['value']) # Push the new state onto the stack
      symbols.append(currentSymbol) # Push the current symbol onto the symbols list
      currentIndex += 1 # Move to the next input symbol
    elif action['action'] == 'r': # Reduce action
      production = grammar['productions'][action['value']] # Get the production rule to apply

      # Reduce the symbols on the stack by popping the appropriate number of symbols
      for _ in range(len(production['right'])):
        stack.pop()

      nextState = stack[-1] # Get the new state from the top of the stack
      nonTerminal = production['left'] # Get the non-terminal symbol of the production rule

      stack.append(parsingTable[nextState][nonTerminal]['value']) # Push the new state onto the stack
      symbols.append(nonTerminal) # Push the non-terminal symbol onto the symbols list
    elif action == '': # Invalid action
      print('Error: Invalid input')
      return
    else: # Accept action
      print(f'Result: Syntax "{input}" valid and parsed successfully.')
      return

# Print the grammar table
print('\nGrammar Table:\n--------------')
print('\nNon-terminals:')
print(', '.join(grammar['nonTerminals']))
print('\nTerminals:')
print(', '.join(grammar['terminals']))
print('\nProductions:')
for index, production in enumerate(grammar['productions']):
  print(f'{index + 1}. {production["left"]} -> {"ε" if len(production["right"]) == 0 else " ".join(production["right"])}')
print('\n')

parseInput(input) # Call the parsing function with the input