Morphological Analysis and Generation › Code Implementation
Language AI HandbookAll chapters Morphological Analysis and Generation › Code ImplementationOne section · Sections in this chapter6 / 12 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
We will build three artifacts: a rule-based English plural analyzer and generator, a rule-based Turkish inflector, and a small neural sequence-to-sequence inflector trained on synthetic Turkish-style data that we then test on held-out stems. The Python rules illustrate finite-state behavior without compiling an FST library, including how reversing local rules can yield multiple candidate analyses.
A Hand-Rolled Transducer: English Plurals
First, the setup cell. It seeds all randomness and imports what we need for the entire chapter.
import random
import matplotlib.pyplot as plt
import numpy as np
import torch
import torch.nn as nn
from torch.utils.data import DataLoader, TensorDataset
torch.manual_seed(42)
random.seed(42)
np.random.seed(42)Now the generator side. This simplified rule-based function covers four cases: irregular stems bypass the general rules, sibilant-final stems take -es, consonant-final y becomes ies, and everything else takes plain -s. A compiled finite-state grammar could encode the same input-output relation, but this Python function is not itself a two-level grammar.
IRREGULAR_PLURALS = {
"child": "children",
"foot": "feet",
"goose": "geese",
"man": "men",
"mouse": "mice",
"tooth": "teeth",
}
VOWELS = "aeiou"
def is_vowel(ch):
return ch in VOWELS
def plural_noun(lemma):
"""Generate the English plural surface form from a lemma."""
if lemma in IRREGULAR_PLURALS:
return IRREGULAR_PLURALS[lemma]
if lemma.endswith(("s", "x", "z", "ch", "sh")):
return lemma + "es" # sibilant epenthesis
if lemma.endswith("y") and len(lemma) > 1 and not is_vowel(lemma[-2]):
return lemma[:-1] + "ies" # y -> i, then epenthetic e
return lemma + "s"The analyzer direction is where relation-like behavior shows itself. We reverse the applicable -ies or -es rule, then also test the independent final-s reversal, collecting all surviving analyses rather than committing to one.
IRREGULAR_SINGULARS = {p: l for l, p in IRREGULAR_PLURALS.items()}
def analyze_plural(form):
"""Propose all analyses consistent with the plural alternation rules."""
analyses = []
if form in IRREGULAR_SINGULARS:
analyses.append(IRREGULAR_SINGULARS[form] + " +N +PL")
if form.endswith("ies") and form not in IRREGULAR_SINGULARS:
analyses.append(form[:-3] + "y +N +PL")
elif form.endswith("es") and form not in IRREGULAR_SINGULARS:
analyses.append(form[:-2] + " +N +PL")
if form.endswith("s"):
analyses.append(form[:-1] + " +N +PL")
return analysescat -> cats watch -> watches kiss -> kisses party -> parties day -> days child -> children cats <- ['cat +N +PL'] watches <- ['watch +N +PL', 'watche +N +PL'] flies <- ['fly +N +PL', 'flie +N +PL'] parties <- ['party +N +PL', 'partie +N +PL'] children <- ['child +N +PL']
cat -> cats
watch -> watches
kiss -> kisses
party -> parties
day -> days
child -> children
cats <- ['cat +N +PL']
watches <- ['watch +N +PL', 'watche +N +PL']
flies <- ['fly +N +PL', 'flie +N +PL']
parties <- ['party +N +PL', 'partie +N +PL']
children <- ['child +N +PL']Look carefully at the analysis side. watches correctly yields watch, but it also yields the spurious watche. And flies yields fly +N +PL (correct, as in insects) alongside the non-word flie +N +PL. This is not a bug in our rules; it is the behavior expected when a transducer reverses local rules without a stem lexicon. Pruning requires knowledge of which stems occur in the lexicon. Real systems therefore compose the alternation rules with lexical constraints and may use weights to rank the survivors. The noun and verb readings of flies still require sentence context; sequence models from Part VI provide that layer.
To see this overgeneration at a glance, we count how many analyses the rules propose for each surface form.
probe_forms = [
"cats",
"watches",
"flies",
"parties",
"children",
"foxes",
"days",
]
analysis_counts = [len(analyze_plural(f)) for f in probe_forms]
The chart makes the pattern concrete: an applicable -ies or -es reversal can coexist with the separate final-s reversal, and neither path knows whether the recovered stem is a real word. Plain -s forms such as cats and days, and the irregular children, which bypasses the rules entirely, produce one analysis in this toy grammar.
The Turkish Harmony Generator
Now the rule-based Turkish inflector. We model vowel harmony as an explicit allomorphy table keyed by the stem's final vowel, plus buffer consonants (y after a vowel in the dative, n in the genitive). We deliberately omit Turkish consonant assimilation (real kitap → kitabın, with p becoming b); we will note what that omission costs.
FRONT = set("eiöü")
VOWELS = set("aeıioöuü")
def last_vowel(word):
for ch in reversed(word):
if ch in VOWELS:
return ch
return None
## Genitive allomorphy is four-way in real Turkish: -in/-ın/-ün/-un
GEN_ALLOMORPH = {
"e": "in",
"i": "in",
"ö": "ün",
"ü": "ün",
"a": "ın",
"ı": "ın",
"o": "un",
"u": "un",
}
def inflect(noun, tag): # Turkish noun inflection
"""Inflect a Turkish noun for a small set of cases, honoring vowel harmony."""
v = last_vowel(noun)
if v is None:
raise ValueError(f"no vowel in stem: {noun}")
front = v in FRONT
if tag == "PL":
return noun + ("ler" if front else "lar")
if tag == "LOC":
return noun + ("de" if front else "da")
if tag == "DAT":
link = (
"y" if noun[-1] in VOWELS else ""
) # buffer y after vowel-final stems
return noun + link + ("e" if front else "a")
if tag == "GEN":
link = (
"n" if noun[-1] in VOWELS else ""
) # buffer n after vowel-final stems
return noun + link + GEN_ALLOMORPH[v]
raise ValueError(f"unknown tag: {tag}")ev PL=evler, LOC=evde, DAT=eve, GEN=evin okul PL=okullar, LOC=okulda, DAT=okula, GEN=okulun araba PL=arabalar, LOC=arabada, DAT=arabaya, GEN=arabanın kitap PL=kitaplar, LOC=kitapda, DAT=kitapa, GEN=kitapın
ev PL=evler, LOC=evde, DAT=eve, GEN=evin
okul PL=okullar, LOC=okulda, DAT=okula, GEN=okulun
araba PL=arabalar, LOC=arabada, DAT=arabaya, GEN=arabanın
kitap PL=kitaplar, LOC=kitapda, DAT=kitapa, GEN=kitapınThe harmony table commits the suffix vowel according to the stem's last vowel, and vowel-final stems get their buffer consonants. The same functions handle ev, araba, and kitap without a per-stem suffix table because they reference phonological classes. The example also exposes what the toy grammar omits. Real Turkish voices final p before a vowel-initial suffix (kitaba, kitabın) and devoices the locative suffix after voiceless p (kitapta). Those consonant alternations are not implemented, so the code emits kitapa, kitapın, and kitapda.
We can also visualize the harmony mapping directly, as a grid over stem-final vowels and suffix vowels.
harmony_vowels = list(GEN_ALLOMORPH.keys())
suffix_vowels = ["a", "e", "ı", "i", "o", "ö", "u", "ü"]
harmony_matrix = np.zeros((len(harmony_vowels), len(suffix_vowels)))
for r, v in enumerate(harmony_vowels):
chosen = GEN_ALLOMORPH[v][0]
harmony_matrix[r, suffix_vowels.index(chosen)] = 1.0
Each row has exactly one marked cell, which is the visual signature of a deterministic rule: no stem-final vowel is left underspecified, and the rows partition into a front block and a back block. This is precisely the structure the archiphoneme rule pair encodes, and the same grid is what the neural model must induce implicitly from the training pairs.
Building the Synthetic Parallel Corpus
For the neural model, we need training pairs. We generate 400 Turkish-like stems from consonant-vowel syllables constrained to one harmony class, an intentionally simplified approximation to the dominant pattern in many native Turkish roots. Loans and several exceptional patterns are outside this generator. We hold out 80 stems entirely from training. Each stem pairs with four inflection tags, giving 1,280 training pairs and 320 held-out pairs. The input is the stem and tag joined by +, and the target is the surface form.
CONSONANTS = "bcdfgklmnprstz"
FRONT_V = "eiöü"
BACK_V = "aıou"
TAGS = ["PL", "LOC", "DAT", "GEN"]
def make_syllable(harmony):
vowel = random.choice(FRONT_V if harmony == "front" else BACK_V)
onset = random.choice(CONSONANTS)
coda = random.choice(CONSONANTS) if random.random() < 0.5 else ""
return onset + vowel + coda
def make_stem():
harmony = random.choice(["front", "back"])
return "".join(
make_syllable(harmony) for _ in range(random.choice([2, 2, 3]))
)
stems, seen = [], set()
while len(stems) < 400:
s = make_stem()
if s not in seen:
seen.add(s)
stems.append(s)
random.shuffle(stems)
train_stems, test_stems = stems[:320], stems[320:]
def make_pairs(stem_list):
return [(f"{s}+{t}", inflect(s, t)) for s in stem_list for t in TAGS]
train_pairs = make_pairs(train_stems)
test_pairs = make_pairs(test_stems)Stems: 400 total, 320 train, 80 held out Training pairs: 1280 Samples: gidsöri+PL -> gidsöriler gidsöri+LOC -> gidsöride gidsöri+DAT -> gidsöriye gidsöri+GEN -> gidsörinin lacpo+PL -> lacpolar lacpo+LOC -> lacpoda
Each held-out stem was never seen in training, so accuracy on the test pairs measures transfer to unseen stems rather than recall of exact training strings. The test stems still come from the same synthetic generator as the training stems, so this is an in-distribution stem split; it does not measure performance under a different language or stem distribution. Shared-task evaluations such as SIGMORPHON likewise use held-out lemma–feature–form triples, though their datasets and splits are substantially richer than this demonstration.
Encoding and the Seq2Seq Model
Next, the character vocabulary and tensor preparation. We pad everything to fixed lengths computed from the training data.
specials = ["<pad>", "<sos>", "<eos>"]
all_chars = sorted(
{c for inp, _ in train_pairs for c in inp}
| {c for _, t in train_pairs for c in t}
)
itos = list(dict.fromkeys(specials + sorted(all_chars)))
stoi = {c: i for i, c in enumerate(itos)}
PAD, SOS, EOS = 0, 1, 2
def encode(text):
return [stoi[c] for c in text]
def pad(ids, length):
return ids + [PAD] * (length - len(ids))Vocabulary size (chars + specials): 37 Inventory: <pad><sos><eos>+ACDEGLNOPTabcdefgiklmnoprstuyzöüı
The inventory is small: specials, the tag letters (P, L, O, C, D, A, T, G, E, N), +, consonants, and all eight Turkish vowels including dotless ı. That is the entire alphabet the model must reason over.
max_in = max(len(inp) for inp, _ in train_pairs)
max_out = max(len(tgt) for _, tgt in train_pairs) + 1 # +1 for <eos>
def build_tensors(pairs):
lin = max(max_in, max(len(inp) for inp, _ in pairs))
lout = max(max_out, max(len(t) for _, t in pairs) + 1)
src = torch.tensor([pad(encode(inp), lin) for inp, _ in pairs])
dec_in = torch.tensor([pad([SOS] + encode(t), lout) for _, t in pairs])
target = torch.tensor([pad(encode(t) + [EOS], lout) for _, t in pairs])
return src, dec_in, target
src, dec_in, target = build_tensors(train_pairs)src shape: (1280, 13), target shape: (1280, 13)
The shapes confirm that all 1,280 training pairs are padded to one common source length and one common target length, the fixed geometry the batched GRUs require. The decoder consumes <sos> followed by the gold target characters (teacher forcing) while predicting a one-step-shifted target. The model combines a GRU encoder with an attention-equipped GRU decoder and an output projection. Attention gives each output step direct access to every encoded input character rather than forcing the complete stem and tag through one fixed vector. That architecture supplies a route for copying, but this chapter does not include a no-attention ablation that would isolate its causal contribution.
class Seq2Seq(nn.Module):
def __init__(self, vocab_size, emb_dim=32, hid_dim=64, pad_idx=0):
super().__init__()
self.emb = nn.Embedding(vocab_size, emb_dim, padding_idx=pad_idx)
self.encoder = nn.GRU(emb_dim, hid_dim, batch_first=True)
self.decoder = nn.GRU(emb_dim + hid_dim, hid_dim, batch_first=True)
self.out = nn.Linear(2 * hid_dim, vocab_size)
def decode_step(self, token, hidden, encoded, source_mask):
scores = torch.bmm(encoded, hidden[-1].unsqueeze(2)).squeeze(2)
scores = scores.masked_fill(~source_mask, -1e9)
attention = torch.softmax(scores, dim=1)
context = torch.bmm(attention.unsqueeze(1), encoded).squeeze(1)
decoder_input = torch.cat([self.emb(token), context], dim=1)
output, hidden = self.decoder(decoder_input.unsqueeze(1), hidden)
logits = self.out(torch.cat([output.squeeze(1), context], dim=1))
return logits, hidden
def forward(self, src, dec_in, tf_ratio=0.7):
encoded, h = self.encoder(self.emb(src))
source_mask = src != PAD
B = src.size(0)
token = torch.full((B,), SOS, dtype=torch.long)
hidden = h
logits = []
for t in range(dec_in.size(1)):
inp = dec_in[:, t] if random.random() < tf_ratio else token
step_logits, hidden = self.decode_step(
inp, hidden, encoded, source_mask
)
logits.append(step_logits)
token = step_logits.argmax(-1)
return torch.stack(logits, dim=1)Model parameters: 55,877
The printed parameter count is modest by modern standards and sufficient for this synthetic harmony task. That result illustrates the compactness of the particular mapping we constructed; it does not imply that all of morphology is equally small or simple.
Now training. We re-seed before construction so the model's random initialization is reproducible regardless of how many random draws happened earlier. Mini-batch gradient descent gives the model enough parameter updates to learn the copying and harmony operations while keeping the example quick to execute; we record the mean loss per epoch for the first figure.
torch.manual_seed(42)
model = Seq2Seq(len(itos))
criterion = nn.CrossEntropyLoss(ignore_index=PAD)
optimizer = torch.optim.Adam(model.parameters(), lr=3e-3)
loader_generator = torch.Generator().manual_seed(42)
train_loader = DataLoader(
TensorDataset(src, dec_in, target),
batch_size=128,
shuffle=True,
generator=loader_generator,
)
losses = []
for epoch in range(60):
model.train()
epoch_loss = 0.0
for batch_src, batch_dec_in, batch_target in train_loader:
optimizer.zero_grad()
logits = model(batch_src, batch_dec_in, tf_ratio=1.0)
loss = criterion(
logits.reshape(-1, len(itos)), batch_target.reshape(-1)
)
loss.backward()
torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)
optimizer.step()
epoch_loss += loss.item() * batch_src.size(0)
losses.append(epoch_loss / len(train_loader.dataset))Initial loss: 3.298 Final loss: 0.002
The loss falls from its initial value to near zero, which is what we expect on a task with a tight, learnable regularity. This near-zero training loss is good news but not yet evidence of generalization, because the model could simply be memorizing the 1,280 training pairs. But the number that matters is exact-match accuracy on stems the model never saw, since a memorizer would ace training and fail there. Let's build the greedy decoder and evaluate.
@torch.no_grad()
def greedy_decode(model, src, max_len):
model.eval()
encoded, h = model.encoder(model.emb(src))
source_mask = src != PAD
B = src.size(0)
token = torch.full((B,), SOS, dtype=torch.long)
hidden = h
outputs = torch.full((B, max_len), PAD, dtype=torch.long)
finished = torch.zeros(B, dtype=torch.bool)
for t in range(max_len):
logits, hidden = model.decode_step(token, hidden, encoded, source_mask)
token = logits.argmax(-1)
outputs[:, t] = token
finished |= token == EOS
if finished.all():
break
return outputs
def ids_to_string(ids):
chars = []
for idx in ids.tolist():
if idx == EOS:
break
if idx != PAD:
chars.append(itos[idx])
return "".join(chars)
def evaluate(pairs):
src_t, _, _ = build_tensors(pairs)
max_len = max(max_out, max(len(t) for _, t in pairs) + 1)
outputs = greedy_decode(model, src_t, max_len)
correct = sum(
int(ids_to_string(outputs[i]) == gold)
for i, (_, gold) in enumerate(pairs)
)
return correct / len(pairs)
train_acc = evaluate(train_pairs)
test_acc = evaluate(test_pairs)Exact-match accuracy on training stems: 100.0% Exact-match accuracy on held-out stems: 64.7%
Exact-match accuracy on training stems: 100.0%
Exact-match accuracy on held-out stems: 64.7%These two numbers are the key empirical result of this chapter. Perfect training accuracy says the model fit the pairs, which is expected but uninformative on its own. The held-out number is the real test: those 80 stems and their 320 inflected forms never appeared in training. An exact-match score of 64.7% is far above what an exact-stem memorizer could achieve, so the model has learned reusable copying and harmony behavior. The 35.3-point gap from training accuracy is equally important: this small attention model has not induced a perfectly systematic rule, and exact copying remains brittle on unfamiliar strings.
Visualizing Training and Generalization
All computation is done, so we can render the training curve and the per-tag generalization comparison from precomputed values. First, the loss curve.
The curve drops steeply in the first epochs and then stays near zero, with a few small local fluctuations. Training loss alone does not reveal which linguistic behavior the model learned, so the held-out comparison matters more.
def accuracy_by_tag(pairs):
return {tag: evaluate([p for p in pairs if tag in p[0]]) for tag in TAGS}
seen_acc = accuracy_by_tag(train_pairs)
unseen_acc = accuracy_by_tag(test_pairs)
Read the suffix differences with care. All four seen-stem bars reach 100%, while held-out accuracy remains between roughly 63% and 68%. The aggregate scores are similar across suffixes, so no single tag stands out as uniquely difficult. They do not, by themselves, identify the main source of errors; the sample below supplies one concrete stem-copying failure. More representative data and a model designed for monotonic transduction would be sensible follow-up experiments, not conclusions supported by this run. The rule-based inflector handles every stem generated by this synthetic setup because its behavior is defined symbolically.
Finally, let's eyeball a few predictions on held-out stems.
sample = random.sample(test_pairs, 6)
src_t, _, _ = build_tensors(sample)
outs = greedy_decode(model, src_t, max(max_out, 14))
predictions = [ids_to_string(outs[i]) for i in range(len(sample))]rocon+GEN predicted=roconun gold=roconun correct riri+PL predicted=ririler gold=ririler correct nükdötöf+PL predicted=nükdötler gold=nükdötöfler WRONG zirzüc+PL predicted=zirzücler gold=zirzücler correct toptaco+DAT predicted=toptacoya gold=toptacoya correct pıla+GEN predicted=pılanın gold=pılanın correct
rocon+GEN predicted=roconun gold=roconun correct
riri+PL predicted=ririler gold=ririler correct
nükdötöf+PL predicted=nükdötler gold=nükdötöfler WRONG
zirzüc+PL predicted=zirzücler gold=zirzücler correct
toptaco+DAT predicted=toptacoya gold=toptacoya correct
pıla+GEN predicted=pılanın gold=pılanın correctFive of these six held-out predictions match exactly. The displayed error deletes part of the stem in nükdötöfler while retaining the correct plural suffix; it is a copying failure, not a harmony or buffer-consonant error. Six examples are useful for inspection but too few to characterize a general error profile.