Chart parser (original) (raw)
Tabulkový analyzátor (anglicky chart parser) je v matematické informatice druh syntaktických analyzátorů vhodných pro analýzu nejednoznačných bezkontextových jazyků (včetně gramatik přirozených jazyků). Používá přístupu dynamického programování – všechny probírané dílčí výsledky se ukládají do tabulky, která reprezentuje orientovaný multigraf, díky čemuž mohou být používány opakovaně. Tím se zabrání backtrackingu a kombinatorické explozi. Český název odráží skutečnost, že orientovaný multigraf bývá implementován tabulkou (maticí). Za autora tabulkové analýzy je považován .
| Property | Value |
|---|---|
| dbo:abstract | Tabulkový analyzátor (anglicky chart parser) je v matematické informatice druh syntaktických analyzátorů vhodných pro analýzu nejednoznačných bezkontextových jazyků (včetně gramatik přirozených jazyků). Používá přístupu dynamického programování – všechny probírané dílčí výsledky se ukládají do tabulky, která reprezentuje orientovaný multigraf, díky čemuž mohou být používány opakovaně. Tím se zabrání backtrackingu a kombinatorické explozi. Český název odráží skutečnost, že orientovaný multigraf bývá implementován tabulkou (maticí). Za autora tabulkové analýzy je považován . (cs) في علوم الكمبيوتر، يعد محلل المخطط نوعاً من المحللات اللغوية المناسب للقواعد الغامضة (بما في ذلك قواعد اللغات الطبيعية ) وهو يستخدم نهج البرمجة الديناميكية - حيث يتم تخزين النتائج الافتراضية المفترضة في بنية تسمى المخطط ويمكن إعادة استخدامها. هذا يلغي الحاجة لاستخدام خوارزمية الرجوع في الطريق. وينسب تحليل المخطط إلى مارتن كاي . (ar) Ein Chart-Parser, auch Chartparser geschrieben, ist als Computerprogramm ein Parser für kontextfreie Grammatiken, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die Effizienz erheblich und macht das Parsen von kontextfreien Sprachen zu einem in polynomieller Zeit lösbaren Problem. Chartparsing ist ein Überbegriff für alle Parsverfahren, die eine solche Tabelle benutzen. Nach dem verwendeten Parsalgorithmus unterscheidet man verschiedene Subtypen: * Top-Down-Chart-Parser (Earley-Parser) * Left-Corner-Chart-Parser * Insel-Chart-Parser (de) In computer science, a chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages). It uses the dynamic programming approach—partial hypothesized results are stored in a structure called a chart and can be re-used. This eliminates backtracking and prevents a combinatorial explosion. Chart parsing is generally credited to Martin Kay. (en) Un chart parser es un analizador sintáctico dedicado a las gramáticas libres de contexto, que utiliza un chart (una tabla) como ayuda para ir guardando las constituyentes sintácticas según va procesando la oración correspondiente. Este método de procesamiento aumenta la eficiencia y disminuye a su vez el tiempo de procesamiento el cual llega a ser polinomial en este caso a diferencia de otros procesadores sintácticos. (es) チャートパーサ（英: Chart parser）は、自然言語などの曖昧な文法に向いた構文解析器の一種である。動的計画法を用い、中間的かつ仮説的な結果をチャート（chart）と呼ばれるデータ構造に格納しておき、再利用する。これによりバックトラッキングを省き、同時に組合せ爆発を防ぐ。 チャートパーサは Martin Kay が開発した。 (ja) |
| dbo:wikiPageExternalLink | https://bishoy.github.io/ArcExtensionAlgorithm/ |
| dbo:wikiPageID | 106490 (xsd:integer) |
| dbo:wikiPageLength | 2414 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1069916316 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Parsing dbr:Combinatorial_explosion dbr:Bottom-up_parsing dbc:Parsing_algorithms dbr:Compiler-compiler dbr:Computational_linguistics dbr:Computer_science dbr:Viterbi_algorithm dbr:Dynamic_programming dbr:Earley_parser dbr:Ambiguous_grammar dbc:Natural_language_parsing dbr:Backtracking dbr:Top-down_parsing dbr:Martin_Kay dbr:Context-free_grammars dbr:Brute-force_search dbr:Natural_language dbr:Cocke-Younger-Kasami_algorithm |
| dbp:wikiPageUsesTemplate | dbt:More_citations_needed dbt:Reflist dbt:Short_description dbt:Parsers |
| dcterms:subject | dbc:Parsing_algorithms dbc:Natural_language_parsing |
| gold:hypernym | dbr:Parser |
| rdf:type | dbo:Software yago:WikicatParsingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Language106282651 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatFormalLanguages |
| rdfs:comment | Tabulkový analyzátor (anglicky chart parser) je v matematické informatice druh syntaktických analyzátorů vhodných pro analýzu nejednoznačných bezkontextových jazyků (včetně gramatik přirozených jazyků). Používá přístupu dynamického programování – všechny probírané dílčí výsledky se ukládají do tabulky, která reprezentuje orientovaný multigraf, díky čemuž mohou být používány opakovaně. Tím se zabrání backtrackingu a kombinatorické explozi. Český název odráží skutečnost, že orientovaný multigraf bývá implementován tabulkou (maticí). Za autora tabulkové analýzy je považován . (cs) في علوم الكمبيوتر، يعد محلل المخطط نوعاً من المحللات اللغوية المناسب للقواعد الغامضة (بما في ذلك قواعد اللغات الطبيعية ) وهو يستخدم نهج البرمجة الديناميكية - حيث يتم تخزين النتائج الافتراضية المفترضة في بنية تسمى المخطط ويمكن إعادة استخدامها. هذا يلغي الحاجة لاستخدام خوارزمية الرجوع في الطريق. وينسب تحليل المخطط إلى مارتن كاي . (ar) In computer science, a chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages). It uses the dynamic programming approach—partial hypothesized results are stored in a structure called a chart and can be re-used. This eliminates backtracking and prevents a combinatorial explosion. Chart parsing is generally credited to Martin Kay. (en) Un chart parser es un analizador sintáctico dedicado a las gramáticas libres de contexto, que utiliza un chart (una tabla) como ayuda para ir guardando las constituyentes sintácticas según va procesando la oración correspondiente. Este método de procesamiento aumenta la eficiencia y disminuye a su vez el tiempo de procesamiento el cual llega a ser polinomial en este caso a diferencia de otros procesadores sintácticos. (es) チャートパーサ（英: Chart parser）は、自然言語などの曖昧な文法に向いた構文解析器の一種である。動的計画法を用い、中間的かつ仮説的な結果をチャート（chart）と呼ばれるデータ構造に格納しておき、再利用する。これによりバックトラッキングを省き、同時に組合せ爆発を防ぐ。 チャートパーサは Martin Kay が開発した。 (ja) Ein Chart-Parser, auch Chartparser geschrieben, ist als Computerprogramm ein Parser für kontextfreie Grammatiken, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die Effizienz erheblich und macht das Parsen von kontextfreien Sprachen zu einem in polynomieller Zeit lösbaren Problem. Chartparsing ist ein Überbegriff für alle Parsverfahren, die eine solche Tabelle benutzen. Nach dem verwendeten Parsalgorithmus unterscheidet man verschiedene Subtypen: (de) |
| rdfs:label | محلل المخطط (ar) Tabulkový analyzátor (cs) Chart-Parser (de) Chart parser (es) Chart parser (en) チャートパーサ (ja) |
| owl:sameAs | freebase:Chart parser yago-res:Chart parser wikidata:Chart parser dbpedia-ar:Chart parser dbpedia-cs:Chart parser dbpedia-de:Chart parser dbpedia-es:Chart parser dbpedia-ja:Chart parser https://global.dbpedia.org/id/4QJAi |
| prov:wasDerivedFrom | wikipedia-en:Chart_parser?oldid=1069916316&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Chart_parser |
| is dbo:wikiPageDisambiguates of | dbr:Chart_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Chart_parsing |
| is dbo:wikiPageWikiLink of | dbr:Parsing dbr:Deterministic_parsing dbr:Dynamic_programming dbr:Earley_parser dbr:Ambiguous_grammar dbr:Left_corner_parser dbr:Chart_(disambiguation) dbr:Semantic_parsing dbr:Chart_parsing |
| is foaf:primaryTopic of | wikipedia-en:Chart_parser |