Lexikalische Analyse
Lexikalische Analyse ist in der Informatik die Zerlegung einer Zeichenkette (z. B. Quelltext) in eine Folge von logisch zusammengehörigen Einheiten, sogenannte Token. Ein Computerprogramm, das eine lexikalische Analyse durchführt, wird Lexer, Tokenizer oder lexikalischer Scanner genannt. Ein Lexer ist meist Teil eines Compilers und wird als erster Schritt in der Analysephase ausgeführt. Das Ergebnis des Lexers wird im nächsten Schritt von einem Parser weiterverarbeitet.
Grundlagen
Bei der Zerlegung einer Eingabe in eine Folge von logisch zusammengehörigen Einheiten, in die so genannten Token, spricht man auch von lexikalischer Analyse. Typischerweise geschieht die Zerlegung nach den Regeln von regulären Grammatiken, und der Tokenizer ist durch eine Menge endlicher Automaten realisiert. Verfahren zur Überführung eines regulären Ausdrucks in einen nichtdeterministischen endlichen Automaten sind das Berry-Sethi-Verfahren sowie die Thompson-Konstruktion.<ref><templatestyles src="Webarchiv/styles.css" />{{#if:20160306215317
| {{#ifeq: 20160306215317 | *
| {{#if: Stanford Dragon Book Compilerbau - Lexical Analysis | {{#invoke:WLink|getEscapedTitle|Stanford Dragon Book Compilerbau - Lexical Analysis}} | {{#invoke:Webarchiv|getdomain|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20160306215317}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Stanford Dragon Book Compilerbau - Lexical Analysis | {{#invoke:WLink|getEscapedTitle|Stanford Dragon Book Compilerbau - Lexical Analysis}} | {{#invoke:Webarchiv|getdomain|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20160306215317}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Stanford Dragon Book Compilerbau - Lexical Analysis | {{#invoke:WLink|getEscapedTitle|Stanford Dragon Book Compilerbau - Lexical Analysis}} | {{#invoke:Webarchiv|getdomain|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: Stanford Dragon Book Compilerbau - Lexical Analysis | {{#invoke:WLink|getEscapedTitle|Stanford Dragon Book Compilerbau - Lexical Analysis}} | {{#invoke:Webarchiv|getdomain|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Stanford Dragon Book Compilerbau - Lexical Analysis | {{#invoke:WLink|getEscapedTitle|Stanford Dragon Book Compilerbau - Lexical Analysis}} | {{#invoke:Webarchiv|getdomain|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf}} }} ({{#if: {{#if: | | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Stanford Dragon Book Compilerbau - Lexical Analysis | {{#invoke:WLink|getEscapedTitle|Stanford Dragon Book Compilerbau - Lexical Analysis}} | {{#invoke:Webarchiv|getdomain|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20160306215317|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf}}
|| {{#if: || }}
}}{{#if: Stanford Dragon Book Compilerbau - Lexical Analysis
| {{#if: {{#invoke:WLink|isBracketedLink|Stanford Dragon Book Compilerbau - Lexical Analysis}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}} (englisch)</ref> Durch Anwendung der Potenzmengenkonstruktion lässt sich ein nichtdeterministischer in einen deterministischen endlichen Automaten überführen.
Ein Tokenizer kann Bestandteil eines Parsers sein und hat dort vorverarbeitende Funktion. Er erkennt innerhalb der Eingabe Schlüsselwörter, Bezeichner, Operatoren und Konstanten. Diese bestehen aus mehreren Zeichen, bilden aber jeweils logische Einheiten, sogenannte Token. Diese werden an den Parser zur weiteren Verarbeitung (d. h. syntaktischen Analyse) übergeben.
Programme zur Erzeugung
Wenn man eine formale Beschreibung der zu erkennenden Lexik angeben kann, lässt sich ein Tokenizer automatisch generieren. Das in Unix-Betriebssystemen enthaltene Programm Lex sowie das als freie Software entwickelte Flex erfüllen genau diese Funktion. Aus der formalen Beschreibung generieren diese Programme eine Funktion, die aus einem eingegebenen Text das jeweils nächste Token ermittelt und zurückgibt. Diese Funktion findet dann meist in einem Parser Verwendung.
{{#invoke:Vorlage:Siehe auch|f}}
Weblinks
- Flex – C++, C (englisch)
- re2c – C (englisch)
- Quex – C++, C (englisch)
- JFlex – Java (englisch)
- AnnoFlex – Java (englisch)
- Lexical – PHP (englisch)
Einzelnachweise
<references />