Earleyův algoritmus je algoritmus syntaktické analýzy, který vytvořil a v roce 1968 popsal Jay Earley ve své disertační práci vedené Robertem W. Floydem z Carnegie Mellon University.

PropertyValue
prop-cs:doi
  • 10.101600 (xsd:double)
  • 10.109300 (xsd:double)
prop-cs:jméno
  • Miloš
  • John
  • Masaru
  • Joop M. I. M.
  • R. Nigel
prop-cs:mr
  • 1112117 (xsd:integer)
prop-cs:místo
  • Plzeň
prop-cs:odkazNaAutora
  • Nigel Horspool
prop-cs:periodikum
prop-cs:příjmení
  • Leo
  • Tomita
  • Železný
  • Aycock
  • Horspool
prop-cs:rok
  • 1984 (xsd:integer)
  • 1991 (xsd:integer)
  • 2002 (xsd:integer)
prop-cs:sborník
  • 10 (xsd:integer)
prop-cs:strana
  • 35 (xsd:integer)
  • 165 (xsd:integer)
  • 354 (xsd:integer)
  • 620 (xsd:integer)
prop-cs:svazek
  • 45 (xsd:integer)
  • 82 (xsd:integer)
prop-cs:titul
  • A general context-free parsing algorithm running in linear time on every LR grammar without using lookahead
  • LR parsers for natural languages
  • Practical Earley Parsing
  • Strukturální metody rozpoznávání
prop-cs:url
prop-cs:vydavatel
  • Katedra kybernetiky ZČU
prop-cs:vydání
  • 1 (xsd:integer)
  • 6 (xsd:integer)
prop-cs:wikiPageUsesTemplate
prop-cs:zkratka
  • COLING
dbpedia-owl:abstract
  • Earleyův algoritmus je algoritmus syntaktické analýzy, který vytvořil a v roce 1968 popsal Jay Earley ve své disertační práci vedené Robertem W. Floydem z Carnegie Mellon University. Algoritmus byl v roce 1970 publikován ve zkrácené a čitelnější podobě v časopise Communications of the ACM v článku, zařazeném v roce 1983 mezi 21 nejvýznamnějších článků za čtvrtstoletí existence tohoto časopisu.Původní algoritmus pouze zjišťuje, zda zadaný textový řetězec patří do jazyka popsaného bezkontextovou gramatikou – jedná se tedy o rozpoznávač (anglicky recogniser). Lze jej však rozšířit, aby v průběhu analýzy vytvářel derivační strom, čímž vznikne kompletní syntaktický analyzátor (anglicky parser).Algoritmus je vhodný i pro nejednoznačné bezkontextové jazyky používané pro zpracování přirozeného jazyka, díky čemuž má v matematické lingvistice podobnou úlohu jako LR parsery a LL parsery používané v matematické informatice v překladačích programovacích jazyků.Asymptotická složitost Earleyova algoritmu pro obecný bezkontextový jazyk je O(n3), kde n je délka analyzovaného řetězce; pro jednoznačné gramatiky pracuje v kvadratickém čase O(n2), a pro téměř všechny LR(k) gramatiky v lineárním čase. Funguje obzvlášť dobře, když pravidla používají levou rekurzi. Některé varianty mohou trpět problémy s určitými vypouštějícími gramatikami.Earleyův analyzátor (anglicky Earley parser) je syntaktický analyzátor založený na Earleyově algoritmu. Často jej používají projektové frameworky podporující Rapid Application Development (RAD) využívané při konstrukci interpretů a kompilátorů především doménově specifických jazyků.
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 1063182 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 58288 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 104 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 13777832 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
dbpedia-owl:wikiPageWikiLinkText
  • Earleyův analyzátor
dcterms:subject
rdfs:comment
  • Earleyův algoritmus je algoritmus syntaktické analýzy, který vytvořil a v roce 1968 popsal Jay Earley ve své disertační práci vedené Robertem W. Floydem z Carnegie Mellon University.
rdfs:label
  • Earleyův analyzátor
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageRedirects of
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of