Ziel ist ein sehr einfacher Makroprozessor. Darunter ist ein Programm zu verstehen, welches Befehle in einem Text gegen Zeichenketten ersetzt, ähnlich der Interpolation von Zeichenketten. Zur Vereinfachung betrachten wir lediglich parameterlose Makros. Die Makros seien von geschweiften Klammern umschlossen, analog zu den Platzhaltern in den Schablonen zur Formatierung von Zeichenketten.
Definiert man beispielsweise Makros für die Verknüpfungssymbole der Aussagenlogik, dann wird die Zeichenkette
A {and} (A {imp} B) {imp} B
zu
A ∧ (A → B) → B
expandiert.
Bestandteil der Expansion muss ein kleiner Parser sein, der die Makros vom Rest der Eingabe trennt. Hier muss man sich überlegen, wie man genau vorgehen will, denn aufgrund der UTF-8-Kodierung tun sich mehrere Möglichkeiten auf.
Die erste Variante des Programms zeigt eine recht unkomplizierte Vorgehensweise.
static MACROS: &[(&str, fn() -> String)] = &[
("not", || String::from("¬")),
("and", || String::from("∧")),
("or", || String::from("∨")),
("imp", || String::from("→"))
];
fn expand_macro(name: &str) -> Result<String, String> {
for t in MACROS {
if t.0 == name {return Ok(t.1());}
}
Err(format!("Makro '{}' wurde nicht gefunden.", name))
}
fn expand(text: &str) -> Result<String, String> {
let a: Vec<char> = text.chars().collect();
let n = a.len();
let mut acc = String::new();
let mut i = 0;
while i < n {
if a[i] == '{' {
i += 1;
let mut name = String::new();
while i < n && a[i] != '}' {
name.push(a[i]);
i += 1;
}
acc.push_str(&expand_macro(&name)?);
i += 1;
} else {
acc.push(a[i]);
i += 1;
}
}
Ok(acc)
}
fn main() {
println!("{:?}", expand("A {and} (A {imp} B) {imp} B"));
}
Man kann das vorherige Programm als ein wenig ineffizient betrachten, weil es vermeidbare Speicherallokationen enthält. Dies wurde im folgenden Programm beseitigt, im Wesentlichen indem die aufwändige Umwandlung des Textes zu einem Zeichen-Array ausgetauscht wurde durch die Benutzung eines Iterators.
static MACROS: &[(&str, fn(&mut String))] = &[
("not", |acc| acc.push_str("¬")),
("and", |acc| acc.push_str("∧")),
("or", |acc| acc.push_str("∨")),
("imp", |acc| acc.push_str("→"))
];
fn expand_macro(acc: &mut String, name: &str) -> Result<(), String> {
for t in MACROS {
if t.0 == name {return Ok(t.1(acc));}
}
Err(format!("Makro '{}' wurde nicht gefunden.", name))
}
fn expand(text: &str) -> Result<String, String> {
let mut acc = String::with_capacity(text.len());
let mut name = String::with_capacity(16);
let mut it = text.chars();
while let Some(c) = it.next() {
if c == '{' {
name.clear();
while let Some(c) = it.next() {
if c == '}' {break;} else {name.push(c);}
}
expand_macro(&mut acc, &name)?;
} else {
acc.push(c);
}
}
Ok(acc)
}
fn main() {
println!("{:?}", expand("A {and} (A {imp} B) {imp} B"));
}
Würde lediglich die Grundfunktionalität der Iteration zur
Verfügung stehen, wären wir gezwungen, wie gezeigt einen Puffer
für die Makronamen zu Verwenden. Allerdings haben wir bei einem
Iterator über Zeichenketten zusätzlich as_str zur
Verfügung, damit erhält man den verbleibenden Rest der Zeichenkette.
Dieses Hilfsmittel ermöglicht die folgende Modifikation.
fn expand(text: &str) -> Result<String, String> {
let mut acc = String::with_capacity(text.len());
let mut it = text.chars();
while let Some(c) = it.next() {
if c == '{' {
let rest = it.as_str();
let mut len = 0;
while let Some(c) = it.next() {
if c == '}' {break;} else {len += c.len_utf8();}
}
expand_macro(&mut acc, &rest[..len])?;
} else {
acc.push(c);
}
}
Ok(acc)
}
Man muss bei der Programmierung solcher Algorithmen genau darauf achten, was man tut. Ersetzen wir
len += c.len_utf8();
gegen die naive Inkrementierung len += 1;,
ist Unicode in Makronamen nicht mehr gestattet.
Zudem führt die Ausschnitt-Bildung &rest[..len]
dann bei bestimmten Unicode enthaltenden Namen zum Programmabbruch.
Nämlich immer dann, wenn der Index len durch die
fehlerhafte Semantik inmitten einer UTF-8-Sequenz liegt. Das ist
beispielsweise bei
expand("{Café}")
der Fall.
Eine weitere Alternative besteht in der Betrachtung des Textes als Bytekette. Als kleines Manko nimmt man dabei in Kauf, dass das Hantieren mit Byteketten nun das gesamte Programm durchzieht.
Ferner wurde lineare Suche gegen eine binäre Suche ersetzt, wobei nun darauf zu achten ist, dass die Makrotabelle ab jetzt lexikographisch sortiert bleibt.
static MACROS: &[(&[u8], fn(&mut dyn FnMut(&[u8])))] = &[
(b"and", |cb| cb("∧".as_bytes())),
(b"imp", |cb| cb("→".as_bytes())),
(b"not", |cb| cb("¬".as_bytes())),
(b"or", |cb| cb("∨".as_bytes()))
];
fn expand_macro(acc: &mut Vec<u8>, name: &[u8]) -> Result<(), String> {
match MACROS.binary_search_by_key(&name, |t| t.0) {
Ok(i) => Ok(MACROS[i].1(&mut |data| acc.extend(data))),
_ => Err(format!("Makro '{}' wurde nicht gefunden.",
std::str::from_utf8(name).unwrap()))
}
}
fn expand(text: &str) -> Result<String, String> {
let a = text.as_bytes();
let n = a.len();
let mut acc: Vec<u8> = Vec::with_capacity(n);
let mut i = 0;
while i < n {
if a[i] == b'{' {
i += 1;
let j = i;
while i < n && a[i] != b'}' {i += 1;}
expand_macro(&mut acc, &a[j..i])?;
i += 1;
} else {
acc.push(a[i]);
i += 1;
}
}
Ok(String::from_utf8(acc).unwrap())
}
fn main() {
println!("{:?}", expand("A {and} (A {imp} B) {imp} B"));
}
Bei dieser Umsetzung drängt sich auf, die
Schnittstelle von expand so zu modifizieren, dass
das Programm ausschließlich mit Byteketten arbeitet, womit die
Voraussetzung der Korrektheit der UTF-8-Daten entfällt. Nämlich
darf die Prüfung der Korrektheit beim Einlesen der Eingabe aus einer
Datei dann ebenfalls entfallen, indem man die Datei stattdessen als
Binärdatei einlesen lässt. Das macht das Programm nochmals effizienter.