Bottom-up-Parser

Bottom-up-Parser oder Aufwärtsparser sind Analyse-Werkzeuge für formale Sprachen.

Im Regelfall wird ein Parser als Teil eines Übersetzungsprogramms von einer Sprache in eine andere eingesetzt. Bei Programmiersprachen ist ein solches Übersetzungsprogramm Teil eines Compilers. Ein Parser prüft auch die Konformität bzw. das Einhalten des Regelwerks einer Sprache: Er gibt Warnungen und Fehlermeldungen aus, wenn der Eingangstext nicht regelkonform ist.

Ein Bottom-up-Parser arbeitet ausgehend von der kleinsten vorgefundenen Einheit („Bottom“) in Richtung des größeren Zusammenhangs („up“).

Der Bottom-up-Parser implementiert die Strategie des Bottom-up-Parsings (datengeleitetes Parsing). Bei dieser wird von den Token (Wörtern) des Eingabesatzes ausgehend versucht, nach und nach größere syntaktische Strukturen aufzubauen, bis man schließlich beim Startsymbol der Grammatik angelangt ist.

Wichtige Unterklassen sind

Beispiel

Gegeben sei eine kontextfreie Grammatik mit folgenden Produktionsregeln:

  1. S → NP VP
  2. VP → V NP
  3. NP → Donald
  4. NP → Daisy
  5. V → liebt

Das Startsymbol sei S.

Der Satz, der durch den Bottom-up-Parser analysiert werden soll, sei „Daisy liebt Donald“. Der Stapel des Parsers ist anfänglich leer. Die Schritte eines Shift-Reduce-Parsers sehen so aus:

Eingabe Stapel Aktion Angewandte Regeln
Daisy liebt Donald Start
liebt Donald Daisy Lege Wort „Daisy“ auf den Stapel
liebt Donald NP Reduziere „Daisy“ zu NP mit Regel 4. 4
Donald NP liebt Lege Wort „liebt“ auf den Stapel 4
Donald NP V Reduziere „liebt“ zu V mit Regel 5. 4 5
NP V Donald Lege Wort „Donald“ auf den Stapel 4 5
NP V NP Reduziere „Donald“ zu NP mit Regel 3. 4 5 3
NP VP Reduziere die Folge V NP auf dem Stapel zu VP mit Regel 2. 4 5 3 2
S Reduziere die Folge NP VP auf dem Stapel zu S mit Regel 1. 4 5 3 2 1

Es gibt keine weiteren Wörter mehr im Eingabesatz, auf dem Stapel liegt das Startsymbol, der Satz wurde daher durch den Parser unter Ausgabe der Regelfolge 4 5 3 2 1 akzeptiert.

Read other articles:

East Dulwich railway station

National Rail station in London, England East Dulwich East DulwichLocation of East Dulwich in Greater LondonLocationEast DulwichLocal authorityLondon Borough of SouthwarkManaged bySouthernStation codeEDWDfT categoryENumber of platforms2Fare zone2National Rail annual entry and exit2018–19 1.712 million[1]2019–20 1.820 million[1]2020–21 0.456 million[1]2021–22 0.916 million[1]2022–23 1.041 million[1]Key dates1 October 1868Opened as Champion Hill...

 

Angkatan Bersenjata Republik Indonesia

Angkatan Bersenjata Republik IndonesiaLambang ABRIBendera ABRIDidirikan5 Oktober 1959(sebelumnya bernama Angkatan Perang Republik Indonesia)Dibubarkan18 Agustus 2000(dipisahkan menjadi Tentara Nasional Indonesia dan Kepolisian Negara Republik Indonesia)Angkatan Angkatan Darat Angkatan Laut Angkatan Udara Angkatan KepolisianMarkas besarJakartaIndustriPemasok lokalPindadPemasok asing Uni Soviet Amerika Serikat Jerman Barat Israel Britania Raya Jerman Timur Aus...

 

Soho

Artikel ini tentang kawasan di London. Untuk kawasan di New York City, lihat SoHo. Untuk kegunaan lain, lihat Soho (disambiguasi) Koordinat: 51°30′47″N 0°07′52″W / 51.513°N 0.131°W / 51.513; -0.131 Soho Palace Theatre, London, salah satu dari beberapa tempat hiburan di Soho. Soho Letak Soho di London Raya Ref. grid OS TQ295815 Borough London Westminster County seremonial Greater London Wilayah London Negara konstituen Inggris Negara...

Les Eyzies-de-Tayac-Sireuil

Part of Les Eyzies in Nouvelle-Aquitaine, FranceLes Eyzies-de-Tayac-SireuilPart of Les Eyzies Location of Les Eyzies-de-Tayac-Sireuil Les Eyzies-de-Tayac-SireuilShow map of FranceLes Eyzies-de-Tayac-SireuilShow map of Nouvelle-AquitaineCoordinates: 44°56′10″N 1°01′05″E / 44.936°N 1.018°E / 44.936; 1.018CountryFranceRegionNouvelle-AquitaineDepartmentDordogneArrondissementSarlat-la-CanédaCantonVallée de l'HommeCommuneLes Eyzies Area137.44 km2 (14.46...

 

Associazione Calcio Perugia 1989-1990

Voce principale: Associazione Calcistica Perugia Calcio. AC PerugiaStagione 1989-1990 Sport calcio Squadra Perugia Allenatore Ferruccio Mazzola, poi Marcello Neri Presidente Giancarlo Tinarelli Serie C19º nel girone B Coppa Italia Serie CFase a gironi Maggiori presenzeCampionato: Artistico, Mirisola, Vinti (33) Miglior marcatoreCampionato: Fermanelli (16) StadioRenato Curi 1988-1989 1990-1991 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti l'...

 

Лазерный принтер

Лазерный принтер 1993 Apple LaserWriter Pro 630 В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения б...

Angrivari

AngrivariIl popolo degli Angrivari, secondo Tacito, si trovava a nord dei Bructeri, a sud dei Frisi, ad est dei Camavi, ad nord-ovest dei Dulgubini e ad est dei Casuari[1] Sottogruppifaceva parte della popolazione dei Germani occidentali (Ingaevones) Luogo d'originead oriente del Reno nell'attuale Vestfalia), approssimativamente tra i fiumi Lupia (odierno Lippe) e Vesurgis (odierno Weser); confinavano con i Bructeri, prima e i Tencteripoi a sud[2] LinguaLingue germaniche ...

 

Edmonton Huskies

Edmonton Huskies Established1954 (1954)Based inEdmonton, AlbertaHome stadiumClarke StadiumHead coachJeff TobertGeneral managerJason LorrimerLeagueCanadian Junior Football LeagueDivisionPrairie Football ConferenceColoursBlack, Gold, WhiteLeague titles5 (1962, 1963, 1964, 2004, 2005)WebsiteOfficial website The Edmonton Huskies are a Canadian Junior Football team based in Edmonton, Alberta. The Huskies play in the six-team Prairie Football Conference, which itself is part of the Canadian Ju...

 

Lesbian/Woman

1972 book by Del Martin and Phyllis Lyon Lesbian/Woman Cover of the first editionAuthorsDel Martin and Phyllis LyonCountryUnited StatesLanguageEnglishSubjectLesbian feminismPublisherGlide PublicationsPublication date1972Media typePrint (Hardcover and Paperback)Pages283ISBN978-0553235975OCLC506556 Lesbian/Woman (1972; second edition 1991) is a work by the feminist and gay rights activists Del Martin and Phyllis Lyon, in which the authors discuss what it means to be a lesbian. The book was...

Nikolai Kamov (engineer)

Soviet aerospace engineerThis article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Nikolai Kamov engineer – news · newspapers · books · scholar · JSTOR (October 2009) (Learn how and when to remove this message) You can help expand this article with text translated from the corresponding article in Russian. (...

 

博里萨夫·约维奇

博里萨夫·约维奇攝於2009年 南斯拉夫社會主義聯邦共和國第12任總統任期1990年5月15日—1991年5月15日总理安特·马尔科维奇前任亚内兹·德尔诺夫舍克继任塞吉多·巴伊拉莫维奇（英语：Sejdo Bajramović） （代任）第12任不结盟运动秘书长任期1990年5月15日—1991年5月15日前任亚内兹·德尔诺夫舍克继任斯捷潘·梅西奇第3任塞尔维亚常驻南斯拉夫社会主义联邦共和国主席团代表任�...

 

Alma Bennett

Alma BennettBennett ditahun 1924LahirAlma Long(1904-04-09)9 April 1904Seattle, Washington, A.S.Meninggal16 September 1958(1958-09-16) (umur 54)Los Angeles, California, A.S.PekerjaanAktrisTahun aktif1919–1931Suami/istriFrederick Clayton Bennett ​ ​(m. 1924; c. 1928)​ Harry Spingler ​ ​(m. 1929; his death 1953)​ Blackie Whiteford ​(m. 1954)​ Alma Bennett (nee...

Beeban Kidron

British film director and politician (born 1961) The Right HonourableThe Baroness KidronOBEOfficial portrait, 2024Member of the House of LordsLord TemporalIncumbentAssumed office 26 June 2012Life peerage Personal detailsBornBeeban Tania Kidron (1961-05-02) 2 May 1961 (age 63)North London, EnglandSpouse Lee Hall ​(m. 2003)​Children2ParentMichael Kidron (father)Alma materNational Film SchoolOccupationFilm director, producer, campaigner Beeban Tania Kidron, ...

 

Asia Museum of Modern Art

Museum in Wufeng, Taichung, Taiwan Asia Museum of Modern Art亞洲現代美術館Established24 October 2013; 10 years ago (2013-10-24)LocationWufeng, Taichung, TaiwanCoordinates24°02′49.5″N 120°41′17.5″E / 24.047083°N 120.688194°E / 24.047083; 120.688194Typeart museumArchitectTadao AndoWebsiteOfficial website The Asia Museum of Modern Art (traditional Chinese: 亞洲現代美術館; simplified Chinese: 亚洲现代美术馆; pinyin...

 

Erling Knudtzon

Norwegian footballer (born 1988) Erling Knudtzon Personal informationDate of birth (1988-12-15) 15 December 1988 (age 35)Place of birth Oslo, NorwayHeight 1.78 m (5 ft 10 in)Position(s) MidfielderTeam informationCurrent team LillestrømNumber 15Youth career0000–2003 UllernSenior career*Years Team Apps (Gls)2004–2006 Ullern 2007–2010 Lyn 66 (4)2010–2018 Lillestrøm 231 (42)2019–2023 Molde 113 (8)2024– Lillestrøm 5 (1)International career‡2007 Norway U19 3 (1)...

Caesarism

Political philosophy inspired by Caesar This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) You can help expand this article with text translated from the corresponding article in French. (June 2022) Click [show] for important translation instructions. View a machine-translated version of the French article. Machine translation, like DeepL or Google Translate, is a useful starting point ...

 

房地产

此條目論述以部分區域為主，未必有普世通用的觀點。 (2009年7月3日)請協助補充內容以避免偏頗，或討論本文的問題。 此條目需要补充更多来源。 (2009年7月3日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：房地产 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该�...

 

National Register of Historic Places listings in Allegany County, New York

Location of Allegany County in New York Map all coordinates using OpenStreetMap Download coordinates as: KML GPX (all coordinates) GPX (primary coordinates) GPX (secondary coordinates) This is intended to be a complete list of properties and districts listed on the National Register of Historic Places in Allegany County, New York. The locations of National Register properties and districts for which the latitude and longitude coordinates are included below, may be seen in a map.[1] &...

Northwestern University Dental School

Clinic at Northwestern University Dental School. (1903) The Northwestern University Dental School closed in 2001, 110 years after opening in 1891.[1][2] Its first dean was Edgar Swain. According to the trustees, the mentioned financial stresses and reputation as reasons for the closure of the program. History The school was initially located on South State Street and then eventually moved into the new Medical School buildings on South Dearborn and East 24th in 1893. In 1895, N...

 

Portello

Disambiguazione – Se stai cercando la stazione della metropolitana, vedi Portello (metropolitana di Milano). PortelloIl Portello Stato Italia Regione Lombardia Provincia Milano Città Milano CircoscrizioneMunicipio 8 PortelloPortello (Milano) Il Portello (El Portell in dialetto milanese, AFI: [purˈtɛl]) è un quartiere residenziale di Milano, appartenente al Municipio 8. Indice 1 Geografia 2 Storia 2.1 Progetto di riqualificazione 3 Sport 3.1 Sede Calcio Milan 4 Infrastrut...