LF-Parser

LF-Parser

Ein LF-Parser (englisch strong LL-parser) ist ein Top-Down-Parser, der ausschließlich auf der Grundlage der k nächsten Eingabe-Token entscheidet, zu welcher Alternative ein Nichtterminalsymbol ersetzt wird. Von einem LL-Parser unterscheidet ihn, dass die Entscheidungsmengen, die beim Vorausschauen verwendet werden, für jedes Nichtterminalsymbol paarweise disjunkt sein müssen, das heißt, zu jedem Zeitpunkt muss jedes Tupel von Metasymbol und k-lookahead-Token eindeutig auf eine Alternative verweisen. Daher funktioniert dieses Verfahren nur für spezielle kontextfreie Grammatiken, die LF(k)-Grammatiken. LF-Parser werden auch als strong-LL-Parser bezeichnet.

Ein LF-Parser heißt LF(k)-Parser, wenn er während des Parsens k Token vorausschauen kann. Diese Token werden auch als lookahead-Token bezeichnet.

Die Klasse der LF(1)-Grammatiken ist gleich der Klasse der LL(1)-Grammatiken. Für k\ge 2 unterscheiden sich jedoch die Klassen, wie man an folgender Grammatik erkennt, die in LL(2), nicht jedoch in LF(2) liegt:

S → a A | b B
A → C a b
B → C b
C → a | ε

Diese Grammatik kann mit einem LF(2)-Parser nicht umgesetzt werden, denn sind die nächsten beiden Tokens ab, so könnte sowohl eine ε-Ableitung notwendig sein, wenn von A aus abgeleitet wurde als auch eine Ableitung nach a, wenn von B aus abgeleitet wurde. Es liegt eine LL-Grammatik, da zwischen zwei möglichen Ableitungen mit demselben Kontext stets mittels der Lookaheads unterschieden werden kann. Trivialerweise ist jede LF-Grammatik eine LL-Grammatik. Das Beispiel lässt sich auf beliebige k ausweiten, etwa:

S → a A | b B
A → C aᵏ⁻¹ b
B → C aᵏ⁻² b
C → a | ε

LF-Parser lassen sich wesentlich einfacher implementieren, etwa mittels rekursiven Abstiegs, der Begriff LL-Parser ist jedoch wesentlich häufiger verwendet, da LL(1)/LF(1)-Parser am verbreitetsten sind, und dort kein Unterschied besteht. Jede LL(1)-Grammatik ist auch eine LF(1)-Grammatik, denn wenn der Kontext zur Auswahl einer Ableitung entscheidend wäre, so wäre dies höchstens ein Token a im Lookahead, d.h. eine ε-Ableitung oder eine mit a beginnende Ableitung wären möglich, dies geschähe dann jedoch auch unter Berücksichtigung des Kontexts.

Literatur

  • Derick Wood: The theory of left factored languages: part 1. Comp. Journal12:4 (1969)
  • Derick Wood: The theory of left factored languages: part 2. Comp. Journal13:1 (1970)
  • Derick Wood: A further note on top-down deterministic languages. Comp. Journal14:4 (1971)

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Parser (magazine) — Parser: New Poetry Poetics is an annual journal of anarchist poetry and poetics from Vancouver, BC, edited by Roger Farr and Reg Johanson. The first issue was published in May 2007, featuring writing by Alice Becker Ho, Alfredo M. Bonanno, P.… …   Wikipedia

  • parser — (izg. pàrser) m DEFINICIJA inform. program koji obavlja sintaktičku analizu nekog jezika; sintaktički analizator ETIMOLOGIJA engl …   Hrvatski jezični portal

  • parser — pars er, n. One who parses. [1913 Webster] …   The Collaborative International Dictionary of English

  • Parser — Ein Parser [ˈpɑːʁzɐ] (engl. to parse, „analysieren“, bzw. lateinisch pars, „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Computertechnik für die Zerlegung und Umwandlung einer beliebigen Eingabe in ein für …   Deutsch Wikipedia

  • Parser combinator — In functional programming, a parser combinator is a higher order function which accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some… …   Wikipedia

  • Parser Combinator — In mathematics and functional programming, Higher Order functions (HOF) are defined as the functions that can take functions as their input and can also produce functions as their output. The use of a HOF as an infix operator in a function… …   Wikipedia

  • Parser — Это статья о языке программирования, об алгоритме синтаксического анализа см. Синтаксический анализ. Parser Семантика: мультипарадигменный Тип исполнения: Интерпретатор компилирующего типа Появился в …   Википедия

  • Parser-Generator — Ein Parsergenerator ist ein Computerprogramm, das unter Eingabe einer Spezifikation einen Parser erzeugt. Inhaltsverzeichnis 1 Grundlagen 2 Algorithmen 3 Siehe auch 4 Weblinks // …   Deutsch Wikipedia

  • Parser — Pạr|ser 〈m. 3; EDV〉 Bestandteil eines Compilers, Programm, das die syntaktische Analyse eines Quellprogramms durchführt, um es in eine Maschinensprache zu übertragen [zu engl. parse „(grammatisch) analysieren“] * * * Pạr|ser , der; s, [engl.… …   Universal-Lexikon

  • Parser (CGI language) — Infobox programming language name = Parser paradigm = multiparadigm macro, object oriented year = since 1997 designer = Konstantin Morshnev (Art. Lebedev Studio) developer = Alexander Petrosyan (Art. Lebedev Studio) latest release version = 3.2.2 …   Wikipedia

  • Parser Grammar Engine — The Parser Grammar Engine (originally Parrot Grammar Engine) or PGE is a compiler and runtime for a Perl 6 rules for the Parrot virtual machine. [cite web | url=http://search.cpan.org/ ltoetsch/parrot 0.2.2/compilers/pge/README | title=Parrot… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”