Am Don, 2003-02-13 um 15.52 schrieb Michael Matz:
Hi,
On 13 Feb 2003, Ralf Corsepius wrote:
Irgendwie fehlt bei dir noch das input-file fuer bison (oder yacc), oder der handgeschriebene Parser. flex erkennt regulaere Sprachen, geklammerte Ausdruecke sind nicht Element irgendeiner regulaeren Sprache. Mithin kann man mit ausschliesslich flex keine allgemeinen geklammerten Ausdruecke erkennen. s/flex/lex/g
Mit lex allein geht's nicht. Mit flex unter Verwendung von "conditions" schon (Zustandsbehafteter lexer) würde es gehen.
Jein. Nur conditions reichen nicht aus, Ja. Sie sind aber notwendige Voraussetzung.
da sie die Maechtigkeit der Sprache nicht erhoehen. Versuch's wenn du es nicht glaubst. Der Automat muss zaehlen koennen, was ein Automat nicht kann (er kann endlich "zaehlen", aber fuer allgemeine Ausdruecke reicht das nicht). Ja.
Was man mindestens braucht, ist ein Stack von Zustaenden, Wenn die Sprache rekursiv ist, ja.
Wenn die Sprache nicht-rekursiv ist, nein (Die gesuchte "Klammerungserkennung" degeneriert dann zu einem Sonderfall der "C-Kommentarerkennung").
und in der Tat stellt flex einen bereit (zusammen mit yy_push_state, yy_pop_state und yy_top_state).
Nur braucht es den Flex-eigenen Stack dazu nicht unbedingt. Man kann stattdessen auch einen eigenen Stack verwenden, wenn man will. In Lex kann man zwar auch einen Stack implementieren, doch mittels lex zustandsbehaftete Scanner zu realisieren erscheint mir kaum möglich.
Das man dann geklammerte Ausdruecke erkennen kann ist nicht verwunderlich, da ein regulaerer Automat zusammen mit einem Stack gerade die kontextfreien Sprachen erkennen kann (wie z.B. auch yacc, bison usw. implementiert sind). Es gibt da noch Unterteilungen, wie LR(n), aber das ist hier nicht von Belang. Ja. Siehe Aho/Sethi/Ullman ;)
Ralf