Concepts of Programming LanguagesParsing, Interpretation, Compilation, Type Systems, and Programming Paradigms

>>> import re

>>> re.match(r"^(a|b|c)$", "a")   # Succeeds.
<_sre.SRE_Match object; span=(0, 1), match='a'>

>>> re.match(r"^(a|b|c)$", "def") # Fails.
None

>>> re.match(r"^((red|green|blue)+)$", "redgreenblueredblue")
<_sre.SRE_Match object; span=(0, 19), match='redgreenblueredblue'>

>>> re.match(r"^([a-zA-Z0-9]+)$", "redgreenblueredblue")
<_sre.SRE_Match object; span=(0, 19), match='redgreenblueredblue'>

>>> re.match(r"^([a-zA-Z0-9]+)$", "!@#$")
None
        

and (or (and (true, false), not(false)), or (true, false))
        

{ "And": [
    { "Or": [
        { "And": ["True","False"]}, 
        { "Not": ["False"]}
      ]
    }, 
    { "Or": ["True","False"]}
  ]
}
        

import re
def tokenize(s):
    # Use a regular expression to split the string into
    # tokens or sequences of zero or more spaces.
    tokens = [t for t in re.split(r"(\s+|true|false|and|or|not|,|\(|\))", s)]

    # Throw out the spaces and return the result.
    return [t for t in tokens if not t.isspace() and not t == ""]
        

>>> tokenize("and (or (and (true, false), not(false)), or (true, false))")

['and', '(', 'or', '(', 'and', '(', 'true', ',', 'false', ')', ',', 'not', 
 '(', 'false', ')', ')', ',', 'or', '(', 'true', ',', 'false', ')', ')']
        

def parse(tokens):
    if tokens[0] == 'true':
        return ('True', tokens[1:])

    if tokens[0] == 'false':
        return ('False', tokens[1:])

    if tokens[0] == 'not' and tokens[1] == '(':
        (e1, tokens) = parse(tokens[2:])
        if tokens[0] == ')':
          return ({'Not':[e1]}, tokens[1:])

    if tokens[0] == 'or' and tokens[1] == '(':
        (e1, tokens) = parse(tokens[2:])
        if tokens[0] == ',':
            (e2, tokens) = parse(tokens[1:])
            if tokens[0] == ')':
                return ({'Or':[e1,e2]}, tokens[1:])

    if tokens[0] == 'and' and tokens[1] == '(':
        (e1, tokens) = parse(tokens[2:])
        if tokens[0] == ',':
            (e2, tokens) = parse(tokens[1:])
            if tokens[0] == ')':
                return ({'And':[e1,e2]}, tokens[1:])
        

>>> import json
>>> (tree, tokens) =\
      parse(tokenize(\
        "and (or (and (true, false), not(false)), or (true, false))"\
        )\
      )
>>> print(json.dumps(tree, sort_keys=True, indent=2))
{
  "And": [
    {
      "Or": [
        {
          "And": [
            "True", 
            "False"
          ]
        }, 
        {
          "Not": [
            "False"
          ]
        }
      ]
    }, 
    {
      "Or": [
        "True", 
        "False"
      ]
    }
  ]
}
>>> print(tokens)
[]
        

def parse(tmp, top = True):
    tokens = tmp[0:]
    if tokens[0] == 'true':
        tokens = tokens[1:]
        if not top or len(tokens) == 0:
            return ('True', tokens)

    tokens = tmp[0:]
    if tokens[0] == 'false':
        tokens = tokens[1:]
        if not top or len(tokens) == 0:
            return ('False', tokens)

    tokens = tmp[0:]
    if tokens[0] == 'not' and tokens[1] == '(':
        tokens = tokens[2:]
        r = parse(tokens, False)
        if not r is None:
            (e1, tokens) = r
            if tokens[0] == ')':
                tokens = tokens[1:]
                if not top or len(tokens) == 0:
                    return ({'Not':[e1]}, tokens)

    tokens = tmp[0:]
    if tokens[0] == '(':
        tokens = tokens[1:]
        r = parse(tokens, False)
        if not r is None:
            (e1, tokens) = r
            if tokens[0] == 'or':
                tokens = tokens[1:]
                r = parse(tokens, False)
                if not r is None:
                    (e2, tokens) = r
                    if tokens[0] == ')':
                        tokens = tokens[1:]
                        if not top or len(tokens) == 0:
                            return ({'Or':[e1,e2]}, tokens)

    tokens = tmp[0:]
    if tokens[0] == '(':
        tokens = tokens[1:]
        r = parse(tokens, False)
        if not r is None:
            (e1, tokens) = r
            if tokens[0] == 'and':
                tokens = tokens[1:]
                r = parse(tokens, False)
                if not r is None:
                    (e2, tokens) = r
                    if tokens[0] == ')':
                        tokens = tokens[1:]
                        if not top or len(tokens) == 0:
                            return ({'And':[e1,e2]}, tokens)
        

def parse(tmp, top = True):
    seqs = [\
        ('True', ['true']), \
        ('False', ['false']), \
        ('Not', ['not', '(', parse, ')']), \
        ('And', ['(', parse, 'and', parse, ')']), \
        ('Or', ['(', parse, 'or', parse, ')']) \
        ]

    # Try each choice sequence.
    for (label, seq) in seqs:
        tokens = tmp[0:]
        ss = [] # To store matched terminals.
        es = [] # To collect parse trees from recursive calls.
        
        # Walk through the sequence and either
        # match terminals to tokens or make
        # recursive calls depending on whether
        # the sequence entry is a terminal or
        # parsing function.
        for x in seq:
            if type(x) == type(""): # Terminal.

                if tokens[0] == x: # Does terminal match token?
                    tokens = tokens[1:]
                    ss = ss + [x]
                else:
                    break # Terminal did not match token.

            else: # Parsing function.

                # Call parsing function recursively
                r = x(tokens, False) 
                if not r is None:
                    (e, tokens) = r
                    es = es + [e]

        # Check that we got either a matched token
        # or a parse tree for each sequence entry.
        if len(ss) + len(es) == len(seq):
            if not top or len(tokens) == 0:
                return ({label:es} if len(es) > 0 else label, tokens)
        

 
def parse(tokens):
    if tokens[0] == 'true':
        return ('True', tokens[1:])

    if tokens[0] == 'false':
        return ('False', tokens[1:])

    # ...

    # Recursive call, but no tokens consumed.
    (e1, tokens) = parse(tokens) 
      if tokens[0] == 'and':
        (e2, tokens) = parse(tokens[1:])
        return ({'And':[e1,e2]}, tokens[1:])

    # ...
        

 
def formula(tmp):
    tokens = tmp[0:]
    (e1, tokens) = left(tokens)
      if tokens[0] == 'and':
        (e2, tokens) = formula(tokens[1:])
        return ({'And':[e1,e2]}, tokens[1:])

    # ...

def left(tokens):
    if tokens[0] == 'true':
        return ('True', tokens[1:])

    if tokens[0] == 'false':
        return ('False', tokens[1:])

    # ...
        

def vnot(v):
    if v == 'True':  return 'False'
    if v == 'False': return 'True'

def vand(v1, v2):
    if v1 == 'True'  and v2 == 'True':  return 'True'
    if v1 == 'True'  and v2 == 'False': return 'False'
    if v1 == 'False' and v2 == 'True':  return 'False'
    if v1 == 'False' and v2 == 'False': return 'False'

def vor(v1, v2):
    if v1 == 'True'  and v2 == 'True':  return 'True'
    if v1 == 'True'  and v2 == 'False': return 'True'
    if v1 == 'False' and v2 == 'True':  return 'True'
    if v1 == 'False' and v2 == 'False': return 'False'

Node = dict
Leaf = str

def evaluate(e):
    if type(e) == Node:
        for label in e:
            children = e[label]
            if label == 'Not':
                f = children[0]
                v = evaluate(f)
                return vnot(v)
            elif label == 'And':
                # Notice that we can make the recursive calls
                # below in any order we like; the order of the
                # calls is not specified by the operational
                # semantics.
                f1 = children[0]
                v1 = evaluate(f1)
                f2 = children[1]
                v2 = evaluate(f2)
                return vand(v1, v2)
            elif label == 'Or':
                f2 = children[1]
                v2 = evaluate(f2)
                f1 = children[0]
                v1 = evaluate(f1)
                return vor(v1, v2)
    elif type(e) == Leaf:
        if e == 'True':
            return 'True'
        if e == 'False':
            return 'False'
        

def evaluate(e):
    if type(e) == Node:
        for label in e:
            children = e[label]
            if label == 'Not':
                f = children[0]
                v = evaluate(f)
                return not v # Use the Python not operator.
            elif label == 'And':
                f1 = children[0]
                v1 = evaluate(f1)
                f2 = children[1]
                v2 = evaluate(f2)
                return v1 and v2 # Use the Python and operator.
            elif label == 'Or':
                f2 = children[1]
                v2 = evaluate(f2)
                f1 = children[0]
                v1 = evaluate(f1)
                return v1 or v2 # Use the Python or operator.
    elif type(e) == Leaf:
        if e == 'True':
            return True # Use the Python True constant.
        if e == 'False':
            return False # Use the Python False constant.
        

def execute(s):
    if type(s) == Leaf:
        if s == 'End':
            return []
    elif type(s) == Node:
        for label in s:
            if label == 'Print':
                children = s[label]
                f = children[0]
                p = children[1]
                v = evaluate(f) # Implemented elsewhere.
                o = execute(p)
                return [v] + o
        

def execute(s):
    if type(s) == Leaf:
        if s == 'End':
            return []
    elif type(s) == Node:
        for label in s:
            if label == 'Print':
                children = s[label]
                f = children[0]
                p = children[1]
                v = evaluate(f)
                print(v) # Must appear before recursive call.
                o = execute(p)
                return [v] + o
        

def evaluate(env, e):
    if type(e) == Node:
        for label in e:
            children = e[label]
            if label == 'Not':
                f = children[0]
                v = evaluate(env, f)
                return vnot(v)
            elif label == 'And':
                f1 = children[0]
                v1 = evaluate(env, f1)
                f2 = children[1]
                v2 = evaluate(env, f2)
                return vand(v1, v2)
            elif label == 'Or':
                f2 = children[1]
                v2 = evaluate(env, f2)
                f1 = children[0]
                v1 = evaluate(env, f1)
                return vor(v1, v2)
            elif label == 'Variable':
                x = children[0]
                if x in env:
                    return env[x]
                else:
                    print(x + " is unbound.")
                    exit()
    elif type(e) == Leaf:
        if e == 'True':
            return 'True'
        if e == 'False':
            return 'False'

def execute(env, s):
    if type(s) == Leaf:
        if s == 'End':
            return []
    elif type(s) == Node:
        for label in s:
            if label == 'Print':
                children = s[label]
                f = children[0]
                p = children[1]
                v = evaluate(env, f)
                o = execute(env, p)
                return [v] + o
            if label == 'Assign':
                children = s[label]
                x = children[0]['Variable'][0]
                f = children[1]
                p = children[2]
                v = evaluate(env, f)
                env[x] = v
                o = execute(env, p)
                return o
        

print true;
repeat twice {
  print false;
  end;
}
print true;
end;
        

def execute(env, s):
    if type(s) == Leaf:
        if s == 'End':
            return (env, [])
    elif type(s) == Node:
        for label in s:
            if label == 'Print':
                children = s[label]
                f = children[0]
                p = children[1]
                v = evaluate(env, f)
                (env, o) = execute(env, p)
                return (env, [v] + o)
            if label == 'Assign':
                children = s[label]
                x = children[0]['Variable'][0]
                f = children[1]
                p = children[2]
                v = evaluate(env, f)
                env[x] = v
                (env, o) = execute(env, p)
                return (env, o)
            if label == 'RepeatTwice':
                children = s[label]
                body = children[0]
                rest = children[1]
                env1 = env
                (env2, o1) = execute(env1, body)
                (env3, o2) = execute(env2, body)
                (env4, o3) = execute(env3, rest)
                return (env4, o1 + o2 + o3)
        

if label == 'While':
    [cond, body, rest] = s[label]
    env1 = env
    v = evaluate(env1, cond)
    if v == 'False':
        (env2, o1) = execute(env1, rest)
        return (env2, o1)
    if v == 'True':
        (env2, o1) = execute(env1, body)
        (env3, o2) = execute(env2, {'While':[cond, body, rest]})
        return (env3, o1 + o2)
        

# Simulate a machine running the program represented by the string s.
def simulate(s):
    instructions = [l.split(" ") for l in s.split("\n")]
    mem = {0: 0}
    control = 0
    while control < len(instructions):
        inst = instructions[control]
        if inst[0] == 'label':
            pass
        # For two arguments, test the memory address in the second
        # argument; given one argument, branch unconditionally.
        if inst[0] == 'branch':
            if len(inst) == 2 or mem[int(inst[2])] != 0:
                control = instructions.index(['label', inst[1]])
                continue
        if inst[0] == 'set':
            mem[int(inst[1])] = int(inst[2])
        if inst[0] == 'copy':
            mem[int(inst[2])] = mem[int(inst[1])]
        if inst[0] == 'add':
            mem[0] = mem[1] + mem[2]
        control = control + 1
    return mem[0]
        

>>> p = '''
  label start
  set 1 2
  set 2 3
  branch skip 1
  set 2 40
  label skip
  add
  '''
>>> simulate(p)
5
        

set 3 10
set 4 20
copy
        

def copy(frm, to):
   return [\
      'set 3 ' + str(frm),\
      'set 4 ' + str(to),\
      'copy'\
   ]
        

def setAllToInRegion(constant, startAddr, endAddr):
  # Memory location 8 contains the constant.
  # Memory location 9 contains the counter.  
  return [\
        'set 8 ' + str(constant),\
        'set 9 ' + str(startAddr),\
        'label loop'\
      ] \
      # Set second argument (destination) of copy.
      + copy(9,4)\
      + [\
        # Set first argument (source) for copy.
        'set 3 8',\
        'copy'\
      ]\
      # Increment the counter.
      + increment(9) \
      # If counter is endAddr, break out of loop;
      # otherwise, go back to the beginning of the loop.
      # We check by adding -endAddr to the counter.
      # First argument of add.
      + copy(9,1) \
      + [\
        # Second argument of add.
        'set 2 -' + str(endAddr),\
        'add',\
        'branch loop 0'\
      ]
        

>>> setAllToInRegion(3, 10, 100)
['set 8 3', 
 'set 9 10', 
 'label loop', 
 'set 3 9', 
 'set 4 4', 
 'copy', 
 'set 3 8', 
 'copy', 
 '# increment() done as homework.',
 'set 3 9', 
 'set 4 1', 
 'copy', 
 'set 2 -100', 
 'add', 
 'branch loop 0']
        

def compileFormula(f, heap = 3, fresh = 0):
    if type(f) == Leaf:
        if f == 'True':
            # Find a new memory address on the heap.
            heap = heap + 1
            # Generate instruction to store the integer representing 'True' on the heap.
            inst = 'set ' + str(heap) + ' 1'
            # Return the instruction list and "top" of the heap.
            return ([inst], heap, fresh)
        if f == 'False':
            # Find a new memory address on the heap.
            heap = heap + 1
            # Generate instruction to store the integer representing 'False' on the heap.
            inst = 'set ' + str(heap) + ' 0'
            # Return the instruction list and "top" of the heap.
            return ([inst], heap, fresh)
    if type(f) == Node:
        for label in f:
            children = f[label]
            if label == 'Not':
                # Compile the subtree f to obtain the list of
                # instructions that computes the value represented
                # by f.
                f = children[0]
                (insts, heap, fresh) = compileFormula(f, heap, fresh)
                # Generate more instructions to change the memory
                # location in accordance with the definition of the
                # 'Not' operation.
                instsNot = \
                   ["branch setZero" + str(fresh) + " " + str(heap),\
                    "set " + str(heap) + " 1",\
                    "branch finish" + str(fresh),\
                    "label setZero" + str(fresh),\
                    "set " + str(heap) + " 0",\
                    "label finish" + str(fresh)\
                   ]
                return (insts + instsNot, heap, fresh + 1)
            if label == 'Or':
                # Compile the two subtrees and get the instructions
                # lists as well as the addresses in which the results
                # of computing the two subtrees would be stored if someone
                # were to run those machine instructions.
                f1 = children[0]
                f2 = children[1]
                (insts1, heap2, fresh1) = compileFormula(f1, heap, fresh)
                (insts2, heap3, fresh2) = compileFormula(f2, heap2, fresh1)
                # Increment the heap counter so we store the
                # result of computing 'Or' in a new location.
                heap4 = heap3 + 1
                # Add instructions that compute the result of the
                # 'Or' operation.
                instsOr = \
                   ["copy " + str(heap2) + " 1",\
                    "copy " + str(heap3) + " 2",\
                    "add",\
                    "branch setOne" + str(fresh2) + " 0",\
                    "branch finish" + str(fresh2),\
                    "label setOne" + str(fresh2),\
                    "set 0 1",\
                    "label finish" + str(fresh2),\
                    "copy 0 " + str(heap4)\
                   ]
                return (insts1 + insts2 + instsOr, heap4, fresh2 + 1)
        

x := true; 
while x { 
  x := false; 
}
print false;
        

procedure printProc {
  print true;
  print false;
}
call printProc;
print false;
call printProc;
print true;
        

# The procedure.
goto printProcEnd   # Skip procedure body.
label printProc
set 5 1             # print true;
set 5 0             # print false;

# Return control to the last calling point.
< increment integer stored in address 7 by 2 >
jump 7
label printProcEnd

# The first call.
< copy integer from address 6 to address 7 >
goto printProc

set 5 0             # print false;

# The second call.
< copy integer from address 6 to address 7 >
goto printProc

set 5 1             # print true;
        

# Set stack pointer to top of stack at address 8.
set 7 8

# The procedure.
goto printProcEnd   # Skip procedure body.
label printProc
set 5 1             # print true;
set 5 0             # print false;

# Return control to the last calling point.
< copy integer from top of stack 
  (i.e., integer/address contained in address 7) to address 1 >

< set address 2 to some constant
  (to skip the calling machine instructions) >

< add contents of address 1 and address 2 >
jump 0
label printProcEnd

# The first call.
< increment integer in address 7 (the stack pointer) >
< copy integer from address 6 to top of stack
  (i.e., address/integer specified in address 7) >

goto printProc

set 5 0             # print false;

# The second call.
< increment integer in address 7 (the stack pointer) >
< copy integer from address 6 to top of stack
  (i.e., address/integer specified in address 7) >

goto printProc

set 5 1             # print true;
        

i = 0;
while (i < 1000000) {
  i++;
}
        

label whileLoop
< increment integer in address 123 >
< compare integer in address 123 to integer 1000000 and store result in address 200 >
branch whileLoop 200
        

i = 0;
while (i < 1000000) {
  i++;
  i++;
  i++;
  i++;
  i++;
  i++;
  i++;
  i++;
  i++;
  i++;
}
        

label whileLoop
< increment integer in address 123 >
< increment integer in address 123 >
< increment integer in address 123 >
< increment integer in address 123 >
< increment integer in address 123 >
< increment integer in address 123 >
< increment integer in address 123 >
< increment integer in address 123 >
< increment integer in address 123 >
< increment integer in address 123 >
< compare integer in address 123 to integer 1000000 and store result in address 200 >
branch whileLoop 200
        

{'Print': [
  {'Plus': [
    {'Mult':[{'Number':[3]}, {'Number':[4]}]},
    {'Variable':['x']}
  ]}
]}
        

{'Print': [
  {'Plus': [
    {'Number':[12]},
    {'Variable':['x']}
  ]}
]}
        

a := 2;
b := 5;
print a + b;
f := true and false;
print f;
a := 7;
g := true;
h := false;
b := 0;
print b;
print h;
print g;
print a;
        

a_0 := 2;
b_0 := 5;
print a_0 + b_0;
f_0 := true and false;
print f_0;
a_1 := 7;
g_0 := true;
h_0 := false;
b_1 := 0;
print b_1;
print h_0;
print g_0;
print a_1;
        

Node = dict
Leaf = str

def metric(f):
    if type(f) == Leaf:
        return 1
    if type(f) == Node:
        for label in f:
            return 1 + max([metric(child) for child in f[label]])
        

def formulas(n):
    if n <= 0:
        return []
    elif n == 1:
        return ['True', 'False']
    else:
        fs = formulas(n-1)
        fsN = []
        fsN += [{'Not':[f]} for f in fs]
        fsN += [{'And':[f1,f2]} for f1 in fs for f2 in fs]
        fsN += [{'Or':[f1,f2]} for f1 in fs for f2 in fs]
        return fs + fsN
        

def typeCheck(e):
    if type(e) == Leaf:
        if e == 'True' or e == 'False':
            return 'boolean'
    if type(e) == Node:
        for label in e:
            if label == 'Number':
                 return 'integer'
            if label == 'Not':
                  [e1] = e[label]
                  t1 = typeCheck(e1)
                  if t1 != 'boolean':
                     print("not must be applied to a boolean")
                     return None
                  return 'boolean'
            
            # ...
            
            if label == 'Plus':
                [e1,e2] = e[label]
                t1 = typeCheck(e1)
                t2 = typeCheck(e2)
                if t1 != 'integer' or t2 != 'integer':
                    print("+ requires integer arguments")
                    return None
                return 'integer'
        

def evaluate(env, e):
   if type(e) == Node:
        for label in e:
            children = e[label]
            if label == 'Number':
                n = children[0]
                return n
            elif label == 'Plus':
                [e1,e2] = children
                return evaluate(env, e1) + evaluate(env, e2)
            elif label == 'Variable':
                x = children[0]
                value = env[x]
                return value
            elif label == 'Apply':
                 [f, eArg] = children
                 f = f['Variable'][0] # Unpack.
                 x = env[f]['Function'][2]['Variable'][0]
                 eBody = env[f]['Function'][3] # Body.
                 vArg = evaluate(env, eArg)
                 envF = env.copy()
                 envF[x] = vArg
                 vResult = evaluate(envF, eBody)
                 return vResult
        
def execute(env, s):
    if type(s) == Leaf:
        if s == 'End':
            return (env, [])
    elif type(s) == Node:
        for label in s:
            if label == 'Assign':
                [var, e, p] = s[label]
                x = var['Variable'][0]
                env[x] = evaluate(env, e)
                (env, o) = execute(env, p)
                return (env, o)
            if label == 'Function':
                [f, ty, x, e, p] = s[label]
                f = f['Variable'][0] # Unpack.
                env[f] = s
                (env, o) = execute(env, p)
                return (env, o)
        

def tyExpr(env, e):
   if type(e) == Node:
        for label in e:
            children = e[label]
            if label == 'Number':
                return 'TyInt'
            elif label == 'Variable':
                x = children[0]
                return env[x]
            elif label == 'Apply':
                 [f, eArg] = children
                 f = f['Variable'][0] # Unpack.
                 tyArg = tyExpr(env, eArg)
                 tyFunArg = env[f]['TyArrow'][0]
                 if tyArg == tyFunArg:
                     return env[f]['TyArrow'][1]
        
def tyProg(env, s):
   if type(s) == Leaf:
        if s == 'End':
            return 'TyVoid'
   elif type(s) == Node:
        for label in s:
            if label == 'Assign':
                [x,e,p] = s[label]
                x = x['Variable'][0] # Unpack.
                tExpr = tyExpr(env, e)
                env[x] = tExpr
                tProg = tyProg(env, p)
                if tExpr == 'TyInt' and tProg == 'Void':
                    return 'TyVoid'
            if label == 'Function':
                [f, tyArg, x, e, p] = s[label]
                name = f['Variable'][0]
                x = x['Variable'][0]
                envF = env.copy()
                envF[x] = tyArg
                tBody = tyExpr(envF, e)
                if tBody == 'TyInt':
                    env[name] = {'TyArrow':[tyArg, tBody]}
                    tProg = tyProg(env, p)                  
                    return tProg