PYTHON   133
Parse
Guest on 30th April 2022 11:59:15 PM


  1.  
  2. def scan(text) :
  3.     """scan splits apart the symbols in  text  into a list.
  4.  
  5.       pre:  text is a string holding a proposition
  6.       post: answer is a list of the words and symbols within  text
  7.             (spaces and newlines are removed)
  8.    """
  9.     OPERATORS = ("(", ")", "+", "-", ";", ":", "=")  # must be one-symbol operators
  10.     SPACES = (" ", "\n")
  11.     SEPARATORS = OPERATORS + SPACES
  12.  
  13.     nextword = ""  # the next symbol/word to be added to the answer list
  14.     answer = []
  15.  
  16.     for letter in text:
  17.         # invariant:  answer + nextword + letter  equals all the words/symbols
  18.         #     read so far from  text  with  SPACES  removed
  19.  
  20.         # see if  nextword  is complete and should be appended to answer:
  21.         if letter in SEPARATORS  and  nextword != "" :
  22.             answer.append(nextword)
  23.             nextword = ""
  24.  
  25.         if letter in OPERATORS :
  26.             answer.append(letter)
  27.         elif letter in SPACES :
  28.             pass  # discard space
  29.         else :    # build a word or numeral
  30.             nextword = nextword + letter
  31.  
  32.     if nextword != "" :  
  33.         answer.append(nextword)
  34.  
  35.     return answer
  36.  
  37.  
  38. EOF = "!"      # a word that marks the end of the input words
  39.  
  40. def getNextword() :
  41.     """moves the front word in  wordlist  to  nextword.
  42.       If wordlist is empty, sets  nextword = EOF
  43.    """
  44.     global nextword, wordlist
  45.     if wordlist == [] :
  46.         nextword = EOF
  47.     else :
  48.         nextword = wordlist[0]
  49.         wordlist = wordlist[1:]
  50.  
  51.  
  52.  
  53. def parseEXPR() :
  54.     """builds an EXPR operator tree from the words
  55.          in  nextword + wordlist,
  56.          where  EXPR ::=  NUMERAL  |  VAR  |  ( EXPR OP EXPR )
  57.                 OP is "+" or "-"
  58.      also, maintains the global invariant (on wordlist and nextword)
  59.    """
  60.     if  nextword.isdigit() :   # a NUMERAL ?
  61.         ans = nextword        
  62.         getNextword()
  63.     elif  isVar(nextword) :    # a VARIABLE ?
  64.         ans = nextword
  65.         getNextword()
  66.     elif nextword == "(" :     # ( EXPR op EXPR ) ?
  67.         getNextword()
  68.         tree1 = parseEXPR()
  69.         op = nextword
  70.         if op == "+"  or  op == "-" :
  71.             getNextword()
  72.             tree2 = parseEXPR()
  73.             if nextword == ")" :
  74.                 ans = [op, tree1, tree2]
  75.                 getNextword()
  76.             else :
  77.                 error("missing )")
  78.         else :
  79.             error("missing operator")
  80.     else :
  81.         error("illegal symbol to start an expression")
  82.  
  83.     return ans
  84.  
  85.  
  86. def isVar(word) :
  87.     """checks whether  word  is a legal variable name"""
  88.     KEYWORDS = ("print", "while", "end")
  89.     ans = ( word.isalpha()  and  not(word in KEYWORDS) )
  90.     return ans
  91.  
  92.  
  93. def error(message) :
  94.     """prints an error message and halts the parse"""
  95.     print "parse error: " + message
  96.     print nextword, wordlist
  97.     raise Exception
  98.  
  99.  
  100.  
  101. def parse() :
  102.     """reads the input mini-program and builds an operator tree for it,
  103.       where  PROGRAM ::= COMMANDLIST
  104.       Initializes the global invariant (for nextword and wordlist)
  105.    """
  106.     global wordlist
  107.     text = raw_input("Type the expression: ")
  108.     wordlist = scan(text)
  109.     getNextword()
  110.     # assert: invariant for nextword and wordlist holds true here
  111.     tree = parseEXPR()  
  112.     # assert: tree holds the entire operator tree for  text
  113.     #print tree
  114.     if nextword != EOF :
  115.        error("there are extra words")
  116.     return tree
Raw Paste

Login or Register to edit or fork this paste. It's free.