In meinem Studium hatte ich vor kurzem in der Vorlesung über die methodisch-praktischen Grundlagen der Informatik (MPGI) das Thema „Parser“. Während ich mich zuvor gefragt hatte, wie man einen komplexen, aber dennoch übersichtlichen Parser schreibt, weiß ich es nun. Die Vorteile gegenüber meinen vorherigen Versuchen liegen auf der Hand: Durch die Übersichtlichkeit findet man viel besser Fehler.
Motiviert von meinem neuen Wissen habe ich es sogleich selbst ausprobiert, dazu aber im Gegensatz zur Lehrveranstaltung nicht Opal sondern Python verwendet.
Ich habe mich dazu entschlossen, einen Parser für einfache Rechnungen zu schreiben.
Beispiele für gültige Eingaben:

(1+2)
(1+(2-3))

Anschließend habe ich, wie ich es gelernt habe, eine Grammatik erstellt, mit der ich die Ausdrücke beschreibe. Als Notation habe ich eine modifizierte Backus-Naur-Form (BNF) gewählt, welche als Veränderung zur BNF die Terminalsymbole in Anführungszeichen einschließt und dafür die damit überflüssigen spitzen Klammern um Nichtterminalsymbole entfallen lässt.

Jede Eingabe soll ein Ausdruck sein, welcher entweder eine in Klammern eingefasste binäre Operation auf zwei Unterausdrücke oder eine Zahl ist. Der binäre Operator ist ein Infix-Operator.
In meiner modifizierten BNF sieht obige Beschreibung so aus:

expr ::= '(' expr bin_op expr ')' | number

::= bezeichnet die Ersetzung eines Nichtterminalsymbols (hier expr) durch Nichtterminal- oder Terminalsymbole (hier alles rechts von ::=). | bezeichnet eine Entscheidungsmöglichkeit der Grammatik, d.h. entweder wird das Nichtterminalsymbol durch die linke oder die rechte Seite von | ersetzt. Wenn zwischen Nichtterminalen oder Terminalen ein Leerzeichen steht, bezeichnet dieses die Verkettung beider.
Damit ist die Grammatik noch lange nicht vollständig: Die Nichtterminalsymbole bin_op und number müssen noch ersetzt werden.
Der Operator kann recht leicht definiert werden:

bin_op ::= '+' | '-' | '*' | '/'

Dagegen ist die Definition von number rekursiv:

number ::= digit number | digit

D.h. eine Zahl ist entweder eine Ziffer oder eine Ziffer verkettet mit einer weiteren Zahl.
digit ist einfach eine Ziffer von 0 bis 9:

digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Im Folgenden die komplette Grammatik, mit einer kleinen Anpassung, sodass ein Nichtterminal entweder nur durch Nichtterminale oder nur durch Terminale ersetzt wird:

expr          ::= left_bracket expr bin_op expr right_bracket | number
bin_op        ::= '+' | '-' | '*' | '/'
digit         ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
number        ::= digit number | digit
left_bracket  ::= '('
right_bracket ::= ')'

Das Ziel bei der Implementierung des Parsers war für mich, dessen Grammatik austauschbar zu machen. Einfache Funktionen sollten die Grammatik beschreiben und dabei auf einem Kern aufbauen.
In meinen folgenden Ausführungen lasse ich den Kern des Parsers weg. Interessierte können sich den Quellcode am Ende des Beitrags ansehen.

Jedes Nichtterminal, das nur durch Terminale ersetzt wird, schreibe ich als Funktion auf, ohne besondere Eigenschaften anzuwenden. Beispiel: die Funktionen parse_left_bracket und parse_digit (letztere könnte auch komplizierter gestaltet werden)

@Parser
def parse_digit(text):
	x, rest = text[0], text[1:]
	if x in '0123456789':
		return [x], rest
	raise ParseError()

@Parser
def parse_left_bracket(text):
	x, rest = text[0], text[1:]
	if x == '(':
		return x, rest
	raise ParseError()

Vor die Funktionen des Parsers schreibe ich immer einen Decorator (die Zeile, die mit @ beginnt), der die Funktion zu einer Instanz einer Klasse macht, die dazu noch bestimmte Funktionen hat (dazu gleich).

Jedes Nichtterminal, das durch andere Nichtterminale ersetzt wird, wird durch eine Verkettung von Parser-Funktionen beschrieben. Beispiel: parse_expr

@Parser
def parse_expr(text):
	syntax_tree = ParserAction(lambda a: SyntaxTree(a[2], a[1], a[3]))
	return ((parse_left_bracket & parse_expr & parse_bin_op & parse_expr & parse_right_bracket & syntax_tree)
		| (parse_number))(text)

Diese Verkettung von den Funktionen wird durch Decorator möglich gemacht, da die Zeichen & und | für Python Funktionen einer Klasse darstellen.

Zum Verständnis erkläre ich hier das Beispiel parse_number. Dort steht zunächst:

@Parser
def parse_number(text):
	return (parse_digit & parse_number | parse_digit)(text)

Das verursacht folgendes Vorgehen des Parsers:
Zuerst wird text an das erste parse_digit übergeben, welches entweder einen Fehler erzeugt, wenn das nächste Zeichen keine Ziffer ist, oder das geparste Zeichen und einen Rest zurückgibt. Dieser Rest wird an parse_number übergeben. Sollte bei einem der beiden Funktionsaufrufe ein Fehler auftreten, wird das zweite parse_digit versucht und die Ausgabe davon ggf. zurückgegeben. Sollte auch dabei ein Fehler auftreten, wird dieser von parse_number zurückgegeben.
Da die Rückgabe von parse_number noch eine Liste ist, müssen die Elemente dieser zu einer Zahl vereint werden. Daher wird der Code etwas ergänzt:

@Parser
def parse_number(text):
	joiner = ParserAction(''.join)
	return (parse_digit & parse_number & joiner | parse_digit)(text)

Ziemlich ähnlich verläuft das Vorgehen bei parse_expr. Zum Verständnis sollte man am besten ein bisschen darüber nachdenken.
Dabei wird im ersten Fall (wenn der Ausdruck keine Zahl ist) die Rückgabe in einen sogenannten Syntaxbaum umgewandelt. Mit diesem kann auch eine Berechnung durchgeführt werden, was aber nicht mehr zu den Aufgaben eines Parsers gehört.

Zur Verbesserung des Parsers: Im Grunde genommen kann man den Parser so verändern, dass er nicht mit Funktionen sondern einer Grammatik arbeitet.

Verweise:
https://de.wikipedia.org/wiki/Formale_Grammatik
https://de.wikipedia.org/wiki/Backus-Naur-Form

Anlagen:

#!/usr/bin/env python3
#coding:utf8

# expr          ::= left_bracket expr bin_op expr right_bracket | number
# bin_op        ::= '+' | '-' | '*' | '/'
# digit         ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
# number        ::= digit number | digit
# left_bracket  ::= '('
# right_bracket ::= ')'

import re

from parser import ParseError, Parser, ParserAction

class SyntaxTree(object):
	def __init__(self, op, expr1, expr2):
		self.op = op
		self.expr1 = expr1
		self.expr2 = expr2
	
	def __str__(self):
		return '({}{}{})'.format(self.expr1, self.op, self.expr2)
	
	def eval(self):
		if isinstance(self.expr1, SyntaxTree):
			ex1 = self.expr1.eval()
		else:
			ex1 = int(self.expr1)
		if isinstance(self.expr2, SyntaxTree):
			ex2 = self.expr2.eval()
		else:
			ex2 = int(self.expr2)
		return {
			'+': lambda a, b: a + b,
			'-': lambda a, b: a - b,
			'*': lambda a, b: a * b,
			'/': lambda a, b: a / b
		}[self.op](ex1, ex2)

@Parser
def parse_expr(text):
	syntax_tree = ParserAction(lambda a: SyntaxTree(a[2], a[1], a[3]))
	return ((parse_left_bracket & parse_expr & parse_bin_op & parse_expr & parse_right_bracket & syntax_tree)
		| (parse_number))(text)

@Parser
def parse_bin_op(text):
	x, rest = text[0], text[1:]
	if x in '+-*/':
		return x, rest
	raise ParseError()

@Parser
def parse_number(text):
	joiner = ParserAction(''.join)
	return (parse_digit & parse_number & joiner | parse_digit)(text)

@Parser
def parse_digit(text):
	x, rest = text[0], text[1:]
	if x in '0123456789':
		return [x], rest
	raise ParseError()

@Parser
def parse_left_bracket(text):
	x, rest = text[0], text[1:]
	if x == '(':
		return x, rest
	raise ParseError()

@Parser
def parse_right_bracket(text):
	x, rest = text[0], text[1:]
	if x == ')':
		return x, rest
	raise ParseError()

def parse(text):
	t, r = parse_expr(text)
	if r:
		raise ParseError()
	return t


if __name__ == '__main__':
	tree = parse('(1+2)')
	print(tree, '=', tree.eval())
	tree = parse('(1+(2-34))')
	print(tree, '=', tree.eval())

#!/usr/bin/env python3
#coding: utf8

class ParseError(Exception):
	pass

class Parser(object):
	def __init__(self, f):
		self.f = f
	
	def __call__(self, *args, **kwargs):
		return self.f(*args, **kwargs)
	
	def __and__(a, b):
		def f(s):
			if len(s) == 0:
				raise ParseError()
			t1, r1 = a(s)
			if len(r1) == 0:
				raise ParseError()
			t2, r2 = b(r1)
			if not isinstance(t1, list):
				t1 = [t1]
			if not isinstance(t2, list):
				t2 = [t2]
			return t1 + t2, r2
		def g(s):
			t1, r1 = a(s)
			return b(t1), r1
		if isinstance(b, ParserAction):
			return Parser(g)
		return Parser(f)
	
	def __or__(a, b):
		def f(s):
			try:
				return a(s)
			except ParseError:
				pass
			return b(s)
		return Parser(f)

class ParserAction(object):
	def __init__(self, f):
		self.f = f
	
	def __call__(self, *args, **kwargs):
		return self.f(*args, **kwargs)