Syntax-directed translation using recursive-descent.

main.py

import io
import os

class SyntaxError(Exception): pass

class Parser:
  """
  Translates infix expressions into postfix through a 
  syntax-directed, predictive "translator" (parser).
  
  A predictive parser is a special case of recursive-descentparser, 
  where no backtracking is required.
 
  Grammar: (FIXME: this is the left-recursive variant + it does not reflect the translation)

    expr   -> expr + term   | expr - term   | term
    term   -> temr * factor | term / factor | factor
    factor -> digit
    digit  -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

  The algorithm here is an extended port of the algorithm outlined in
  chapter 2 of "Compilers: Principles, Techniques, & Tools" 2ed,
  by Alfred Aho, Jeffrey Ullman, Ravi Sethi & Monica Lam.
  """

  # PUBLIC

  def translate(self, src):
    self.istream = io.StringIO(src + "\0")
    self.ostream = io.StringIO()
    self.column  = 1
    self.read()

    try:
      self.expr() # GO!
      
      self.istream.seek(0, os.SEEK_SET)
      self.ostream.seek(0, os.SEEK_SET)
      print(f"{self.istream.read()} -> {self.ostream.read()}")

    except SyntaxError as e:
      print(f"{e}")
 
  # PRIVATE 

  def read(self):
    self.lookahead = self.istream.read(1)
    self.column   += 1

  def match(self, token):
    if self.lookahead == token:
      self.read()
    else:
      self.error(f"expected {token}")

  def output(self, token):
    self.ostream.write(token)
    self.ostream.write(" ")

  def error(self, msg):
    self.istream.seek(0, os.SEEK_SET)
    src = self.istream.read()
    ptr = ' ' * (self.column - 2) + "^"

    msg = (
      f"Syntax error: {msg}\n"
      f"  {src}\n  {ptr}"
    )

    raise SyntaxError(msg)

  def expr(self):
    self.term()
    while True:
      match self.lookahead:
        case "+":
          self.match("+")
          self.term()
          self.output("+")
        case "-":
          self.match("-")
          self.term()
          self.output("-")
        case "\0":
          return
        case _:
          self.error(f"Expected operator but got {repr(self.lookahead)}.")

  def term(self):
    self.factor()
    while True:
      match self.lookahead:
        case "*":
          self.match("*")
          self.factor()
          self.output("*")
        case "/":
          self.match("/")
          self.factor()
          self.output("/")
        case _:
          return

  def factor(self):
    if self.lookahead.isdigit():
      self.output(self.lookahead)
      self.match(self.lookahead)
    else:
      self.error(f"Expected digit but got {repr(self.lookahead)}.")

      
if __name__ == "__main__":
  parser = Parser()
  parser.translate("1+2")          # 1 2 +
  parser.translate("1+2/2*2-5+1")  # 1 2 2 / 2 * + 5 - 1 + 
  parser.translate("0*2 2")        # Syntax error: Expected operator but got ' '.
  parser.translate("1++2/2*2")     # Syntax error: Expected digit got '+'.