Chart-Parser
Sign in to savetype of parser for ambiguous grammars
Article · Deutsch
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
Abstract from DBpedia / Wikipedia · CC BY-SA
Connections
CYK algorithm
Entity
computer science
Entity
natural language
Entity
computational linguistics
Entity
dynamic programming
Entity
parsing
Entity
context-free grammar
Entity
backtracking
Entity
parse tree
Entity
abstract syntax tree
Entity
brute-force search
Entity
compiler-compiler
Entity
Viterbi algorithm
Entity
memoization
Entity
LL parser
Entity
ambiguous grammar
Entity
LR parser
Entity
shunting-yard algorithm
Entity
top-down parsing
Entity
recursive-descent parser
Entity