Springe zum Hauptinhalt
Fakultät für Informatik

164. Informatik-Kolloquium


Doz. Dr. Dušan Kolár

Department of Computer Science
VUT Brno, Czech Republic

"Parsing of Scattered Context Grammars"

Mittwoch, 24.11.2010
10:00 Uhr, 1/336

Alle interessierten Personen sind herzlich eingeladen!


Non-propagating scattered context grammars (SCGs) combine simplicity of definition known from context free-grammars with power of languages of type 0 of Chomsky hierarchy.
Moreover, it is possible to define similar properties for SCGs as for context free grammars, e.g. LL(1) grammars can be defined on the level of SCGs. Thus an idea of parsing arises.
Regulated pushdown automata (RPDA) introduced several years ago provide the same computational power as Turing machines.
A slight modification and definition of deterministic version of RPDA provides a way to practical exploitation of the RPDA.
It will be briefly introduced the idea of parsing based on scattered context grammars exploiting regulated pushdown automata.
Practical implementation aspects will be discussed as well.