SHARE
TWEET

Untitled

a guest Jan 17th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. A -> e* | (eUe)
  2. e -> any combination of chars from the grammar
  3.    
  4. A -> e+ | '(' A 'U' A ')'
  5. e -> '0' | '1'
  6.    
  7. class MySyntaxError(Exception):
  8.   def __init__(self, text, index):
  9.     self.text = text
  10.     self.index = index
  11.   def __str__(self):
  12.     return "Syntax error at index " + repr(self.index) + ": " + self.text
  13.  
  14.  
  15. def parse(input):
  16.   global index
  17.   index = 0
  18.  
  19.   def eat_char(set):
  20.     global index
  21.     if index < len(input) and input[index] in set:
  22.       index += 1
  23.     else:
  24.       raise MySyntaxError("expected char in " + repr(set), index)
  25.  
  26.   def e():
  27.     eat_char(['0', '1'])
  28.  
  29.   def A():
  30.     global index
  31.     if index == len(input): # Successfully parsed
  32.       return
  33.     elif input[index] in ['0', '1']:
  34.       while (input[index] in ['0', '1']):
  35.         e()
  36.     elif input[index] is '(':
  37.       eat_char(['('])
  38.       A()
  39.       eat_char(['U'])
  40.       A()
  41.       eat_char([')'])
  42.     else:
  43.       raise MySyntaxError("expected char '0', '1' or '('", index)
  44.  
  45.   A()
  46.   if index != len(input): # Parsing didn't reach the end of the string
  47.     raise MySyntaxError("parsing ended before the end of the input", index)
  48.  
  49.  
  50. def test(string):
  51.   try:
  52.     parse(string)
  53.     print "The string " + string + " have been successfully parsed"
  54.   except MySyntaxError as e:
  55.     print "The string " + string + " can't be parsed:"
  56.     print e
  57.  
  58. test("(01U(1U0))")
  59. test("(01U(1U0)") # Missing parenthesis, syntax error
  60. test("(01U(1U0)))") # Too many parenthesis, syntax error
  61. test("01U(1U0)") # No parenthesis, syntax error
  62.    
  63. from state [1]
  64.   read a '0' or a '1' and loop into state [1]
  65.   read a '(', push the parenthesis and loop into state [1]
  66.   read a 'U', when there is an open parenthesis on the top of stack, push the 'U' and loop into state [1]
  67.   read a ')', when there is a 'U' on the top of the stack, pop the 'U', pop the opend parenthesis following, and loop into state[1]
  68.    
  69. def parse(input):
  70.   index = 0
  71.   stack = [];
  72.  
  73.   def top():
  74.     if len(stack) > 0:
  75.       return stack[len(stack)-1]
  76.     else:
  77.       return None
  78.  
  79.   while index < len(input):
  80.     if input[index] in ['0', '1']:
  81.       pass
  82.     elif input[index] is '(':
  83.       stack.append('(')
  84.     elif input[index] is 'U' and top() == '(':
  85.       stack.append('U')
  86.     elif input[index] is ')' and top() == 'U':
  87.       stack.pop()
  88.       stack.pop()
  89.     else:
  90.       raise MySyntaxError("Unexpected char '" + input[index] + "'", index)
  91.     index += 1
  92.  
  93.   if len(stack):
  94.     raise MySyntaxError("unterminated input", index)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top