Endliche Automaten als Scanner

Id: scan.tex,v 1.2 2007-11-06 07:43:14 waldmann Exp

Während ein Automat nur akzeptiert (oder ablehnt), soll ein Scanner die Eingabe in Tokens zerteilen.

Gegeben ist zu jedem Tokentyp T_k ein Ausdruck X_k, der genau die Token-Werte zu T_k beschreibt.

Der Eingabestring w soll so in Wörter w_{k_i} zerlegt werden, daß

w = w_k₁w_k₁...w_{k_n}
für alle 1 $\le$ i $\le$ n: w_{k_i} ist longest match:
- w_{k_i} $\in$ L(X_{k_i})
- jedes Anfangsstück von w_{k_i}...w_{k_n}, das echt länger als w_{k_i} ist, gehört zu keinem der X_k.

Johannes Waldmann 2008-01-24