Bottom-up parsing (original) (raw)
In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning. Bottom-up parsing recognizes the text's lowest-level small details first, before its mid-level structures, and leaving the highest-level overall structure to last.
| Property | Value |
|---|---|
| dbo:abstract | Syntaktická analýza zdola nahoru je v informatice postup syntaktické analýzy, při kterém se derivační strom sestavuje odspodu – tj. nejdříve se identifikují jednotlivé symboly, z nichž je složen vstupní text, a z nich se následně vytvářejí složitější struktury. V souladu s tím, jak se kreslí stromy v lingvistice a informatice, je kořen derivačního stromu nahoře, a je tvořen symbolem, který symbolizuje celou analyzovanou větu; jednotlivá slova, z nichž je věta složena, a ze kterých se postupně vytvářejí složitější struktury, jsou na konci větví (odtud název terminální symboly) zcela dole. Opačným postupem je syntaktická analýza shora dolů, při které se komplexní jednotky rozdělují na jednodušší části, až se dospěje k symbolům, z nichž je složen analyzovaný řetězec. Oba postupy lze použít jak pro věty přirozeného jazyka, tak pro texty programů v nějakém programovacím jazyce. (cs) Bottom-up-Parser oder Aufwärtsparser sind Analyse-Werkzeuge für natürliche und 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 * Shift-Reduce-Parsing wie LR(k)-Parsing * (de) In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning. Bottom-up parsing recognizes the text's lowest-level small details first, before its mid-level structures, and leaving the highest-level overall structure to last. (en) En informatique, l'analyse syntaxique révèle la structure grammaticale d'un texte. C'est la première étape dans l'étude de son sens. À l'inverse de l'analyse descendante, l'analyse ascendante reconnaît d'abord les plus petites unités du texte (les unités lexicales) analysé avant d'en reconnaître la structure grammaticale en le confrontant à des règles de syntaxe. (fr) ボトムアップ構文解析（ボトムアップこうぶんかいせき、英: Bottom-up parsing）は、構文解析において、構文木を、木の葉に相当する終端記号の列から始めて、それを順次左辺の非終端記号へ書き換え、最終的に最上位の非終端記号（たとえば「文」）を得る、というような手順によって導出する構文解析の戦略である。逆はトップダウン構文解析。 (ja) Analiza wstępująca (ang. bottom-up parsing) – ogólna metoda analizy składniowej, w której zaczyna się od słowa wejściowego i próbuje się zredukować je do symbolu startowego. Drzewo wyprowadzenia jest konstruowane od liści do korzenia (stąd nazwa). W każdym momencie w trakcie tego procesu mamy formę zdaniową, która zawiera segment, powstały w ostatnim kroku wyprowadzenia. Segment ten (nazywany uchwytem (ang. handle) jest prawą stroną produkcji i powinien zostać w tym kroku zredukowany do jej lewej strony, w wyniku czego powstanie poprzednia forma zdaniowa z wyprowadzenia. Główna trudność w analizie wstępującej polega właśnie na odpowiednim znajdywaniu uchwytów. Analiza wstępująca może przebiegać w określonym kierunku (np. od lewej do prawej), lub w sposób bezkierunkowy, wtedy analizowane jest całe słowo naraz.Jednym z bardziej znanych przedstawicieli metody bezkierunkowej jest algorytm CYK.Do metod kierunkowych zalicza się między innymi parsery shift-reduce, czyli LR, LALR, SLR, BC, pierwszeństwa. (pl) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Parse_Tree_Example.svg?width=300 |
| dbo:wikiPageID | 679521 (xsd:integer) |
| dbo:wikiPageLength | 3955 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123029464 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Parsing dbr:Deterministic dbr:LALR_parser dbr:GLR_parser dbc:Parsing_algorithms dbr:LR_parser dbr:Operator-precedence_parser dbr:Computer_science dbr:Left_corner dbr:Simple_precedence_parser dbr:Backtracking dbr:Parse_tree dbr:Top-down_parsing dbr:CYK_algorithm dbr:Canonical_LR_parser dbr:File:Parse_Tree_Example.svg dbr:File:Top-down_Parse_Tree_Order.svg dbr:Recursive_ascent_parser dbr:Simple_LR_parser dbr:Packrat_parser dbr:Shift-reduce_parser dbr:File:Bottom-up_Parse_Tree_Order.svg |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Parsers |
| dct:subject | dbc:Parsing_algorithms |
| rdf:type | yago:WikicatParsingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning. Bottom-up parsing recognizes the text's lowest-level small details first, before its mid-level structures, and leaving the highest-level overall structure to last. (en) En informatique, l'analyse syntaxique révèle la structure grammaticale d'un texte. C'est la première étape dans l'étude de son sens. À l'inverse de l'analyse descendante, l'analyse ascendante reconnaît d'abord les plus petites unités du texte (les unités lexicales) analysé avant d'en reconnaître la structure grammaticale en le confrontant à des règles de syntaxe. (fr) ボトムアップ構文解析（ボトムアップこうぶんかいせき、英: Bottom-up parsing）は、構文解析において、構文木を、木の葉に相当する終端記号の列から始めて、それを順次左辺の非終端記号へ書き換え、最終的に最上位の非終端記号（たとえば「文」）を得る、というような手順によって導出する構文解析の戦略である。逆はトップダウン構文解析。 (ja) Bottom-up-Parser oder Aufwärtsparser sind Analyse-Werkzeuge für natürliche und 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. Wichtige Unterklassen sind * Shift-Reduce-Parsing wie LR(k)-Parsing * (de) Syntaktická analýza zdola nahoru je v informatice postup syntaktické analýzy, při kterém se derivační strom sestavuje odspodu – tj. nejdříve se identifikují jednotlivé symboly, z nichž je složen vstupní text, a z nich se následně vytvářejí složitější struktury. V souladu s tím, jak se kreslí stromy v lingvistice a informatice, je kořen derivačního stromu nahoře, a je tvořen symbolem, který symbolizuje celou analyzovanou větu; jednotlivá slova, z nichž je věta složena, a ze kterých se postupně vytvářejí složitější struktury, jsou na konci větví (odtud název terminální symboly) zcela dole. (cs) Analiza wstępująca (ang. bottom-up parsing) – ogólna metoda analizy składniowej, w której zaczyna się od słowa wejściowego i próbuje się zredukować je do symbolu startowego. Drzewo wyprowadzenia jest konstruowane od liści do korzenia (stąd nazwa). W każdym momencie w trakcie tego procesu mamy formę zdaniową, która zawiera segment, powstały w ostatnim kroku wyprowadzenia. Segment ten (nazywany uchwytem (ang. handle) jest prawą stroną produkcji i powinien zostać w tym kroku zredukowany do jej lewej strony, w wyniku czego powstanie poprzednia forma zdaniowa z wyprowadzenia. Główna trudność w analizie wstępującej polega właśnie na odpowiednim znajdywaniu uchwytów. (pl) |
| rdfs:label | Syntaktická analýza zdola nahoru (cs) Bottom-up-Parser (de) Bottom-up parsing (en) Analyse syntaxique ascendante (fr) ボトムアップ構文解析 (ja) Analiza wstępująca (pl) |
| owl:sameAs | freebase:Bottom-up parsing yago-res:Bottom-up parsing wikidata:Bottom-up parsing dbpedia-cs:Bottom-up parsing dbpedia-de:Bottom-up parsing dbpedia-fa:Bottom-up parsing dbpedia-fr:Bottom-up parsing dbpedia-ja:Bottom-up parsing dbpedia-no:Bottom-up parsing dbpedia-pl:Bottom-up parsing dbpedia-ro:Bottom-up parsing dbpedia-sr:Bottom-up parsing https://global.dbpedia.org/id/52msJ |
| prov:wasDerivedFrom | wikipedia-en:Bottom-up_parsing?oldid=1123029464&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Bottom-up_Parse_Tree_Order.svg wiki-commons:Special:FilePath/Parse_Tree_Example.svg wiki-commons:Special:FilePath/Top-down_Parse_Tree_Order.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Bottom-up_parsing |
| is dbo:wikiPageDisambiguates of | dbr:Bottom-up |
| is dbo:wikiPageRedirects of | dbr:Bottom-up_parser dbr:Bounded-context_parser |
| is dbo:wikiPageWikiLink of | dbr:Memoization dbr:Parsing dbr:History_of_compiler_construction dbr:Inversion_of_control dbr:LALR_parser dbr:Compiler dbr:Operator-precedence_grammar dbr:LL_parser dbr:LR_parser dbr:Operator-precedence_parser dbr:Comparison_of_parser_generators dbr:Compilers:_Principles,_Techniques,_and_Tools dbr:C_shell dbr:Top-down_and_bottom-up_design dbr:S-attributed_grammar dbr:Chart_parser dbr:Left_recursion dbr:Attribute_grammar dbr:Bottom-up dbr:Chomsky_normal_form dbr:Top-down_parsing dbr:XPL dbr:CYK_algorithm dbr:Simple_LR_parser dbr:Shift-reduce_parser dbr:Bottom-up_parser dbr:Bounded-context_parser |
| is foaf:primaryTopic of | wikipedia-en:Bottom-up_parsing |
