Member Avatar for TrustyTony
TrustyTony 888 ex-Moderator

Here is an amazing article.

Peter Norvig does not let small detail, that the language was never implemented in it's time, disturb his debugging the code written without implementation, but single handedly implements it with Python parser.

Frustration warning, this is frustratingly amazing stuff: Prescient but Not Perfect: A Look Back at a 1966 Scientific American Article on Systems Analysis By Peter Norvig | August 23, 2011

  • 1 Contributor
  • 0 Replies
  • 433 Views

Dani AI

Generated

Shared by , Peter Norvig’s walk‑through is a neat case study in reconstructive implementation: turning a prose spec into a working parser and evaluator. The single, most valuable takeaway is to treat the spec as the source of tests — extract every example in the article, convert it to a failing test, then implement the smallest piece that makes the test pass.

A compact, practical workflow:

  • Extract concrete examples and expected behavior from the spec; codify them as tests.
  • Define the token types first (numbers, identifiers, operators, delimiters, comments, whitespace).
  • Choose a parsing approach: recursive‑descent for clarity and control, or a generator/PEG for larger grammars.
  • Build a simple AST that separates syntax from semantics.
  • Implement the evaluator/interpreter and iterate against the test-suite until all tests pass.
  • Document every interpretation choice made where the spec is ambiguous, and keep tests that assert those choices.

A minimal Python skeleton that demonstrates the token → parse → AST pattern (expression grammar with precedence):

import re

token_re = re.compile(r'\s*(?:(\d+(?:\.\d+)?)|(.))')

def tokenize(s):
    for num, other in token_re.findall(s):
        if num: yield ('NUM', float(num))
        else: yield (other, other)

tokens = []
i = 0
def peek(): return tokens[i] if i < len(tokens) else ('EOF','')
def consume(expected=None):
    global i
    t = peek()
    if expected and t[0] != expected: raise SyntaxError(expected)
    i += 1
    return t

def parse_factor():
    if peek()[0] == 'NUM': return consume('NUM')[1]
    if peek()[0] == '(': consume('('); v = parse_expr(); consume(')'); return v
    raise SyntaxError('factor')

def parse_term():
    node = parse_factor()
    while peek()[0] in ('*','/'):
        op = consume()[0]; rhs = parse_factor(); node = (op, node, rhs)
    return node

def parse_expr():
    node = parse_term()
    while peek()[0] in ('+','-'):
        op = consume()[0]; rhs = parse_term(); node = (op, node, rhs)
    return node

def parse(s):
    global tokens, i
    tokens = list(tokenize(s)); i = 0
    return parse_expr()

Troubleshooting notes: ambiguous specs require explicit test cases; top‑down parsers fail on left recursion and need grammar refactoring; add source‑position info to AST nodes for good error messages. Norvig’s example is useful not because it’s exotic, but because it shows the discipline of small tests, incremental implementation, and recording every interpretation made when the original description is vague.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.