| dbo: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 Univerzity Carnegie-Mellon. Algoritmus byl v roce 1970 publikován ve zkrácené a čitelnější podobě v časopise 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 . 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ů. (cs)
- Der Earley-Algorithmus oder Earley-Parser ist in der Informatik ein Algorithmus, der entscheidet, ob ein Wort von einer kontextfreien Grammatik erzeugt werden kann. Er wurde 1970 von entwickelt.Er ähnelt dem Cocke-Younger-Kasami-Algorithmus und löst wie dieser das Wortproblem der kontextfreien Sprachen. Er verwendet die Methode der dynamischen Programmierung. (de)
- In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language, though (depending on the variant) it may suffer problems with certain nullable grammars. The algorithm, named after its inventor, Jay Earley, is a chart parser that uses dynamic programming; it is mainly used for parsing in computational linguistics. It was first introduced in his dissertation in 1968 (and later appeared in an abbreviated, more legible, form in a journal). Earley parsers are appealing because they can parse all context-free languages, unlike LR parsers and LL parsers, which are more typically used in compilers but which can only handle restricted classes of languages. The Earley parser executes in cubic time in the general case , where n is the length of the parsed string, quadratic time for unambiguous grammars , and linear time for all deterministic context-free grammars. It performs particularly well when the rules are written left-recursively. (en)
- El algoritmo de Earley es un algoritmo no determinista de análisis sintáctico para las gramáticas libres de contexto descrito originalmente por el informático estadounidense en 1970. Se ordena, a los lados de los algoritmos CYK y GLR, entre los algoritmos que usan la noción de reparto (de cálculos y de estructuras) y que construyen todos los análisis posibles de una frase (y no sólo uno de estos análisis). Es uno de los algoritmos no deterministas que usan ideas de la programación dinámica. (es)
- En théorie des langages, l'algorithme d'Earley est un algorithme d'analyse syntaxique pour les grammaires non contextuelles décrit pour la première fois par Jay Earley. À l'instar des algorithmes CYK et GLR, l'algorithme d'Earley calcule toutes les analyses possibles d'une phrase (et pas seulement une de ces analyses). Il repose sur de la programmation dynamique. On peut construire un analyseur Earley pour toute grammaire non contextuelle. Il s'exécute en temps cubique (O (n3), où n est la longueur de la chaîne d'entrée). Pour une grammaire non ambiguë, l'analyse Earley s'effectue en temps quadratique (O (n2)). (fr)
- In informatica, una parsing expression grammar, o PEG, è una grammatica formale analitica, ossia descrive un linguaggio formale in termini di un insieme di regole per riconoscere le stringhe che appartengono al linguaggio. Il formalismo è stato proposto nel 2004 ed è intimamente legato alla famiglia dei linguaggi analizzabili top-down introdotti nei primi anni settanta. Sintatticamente, le PEG somigliano anche alle grammatiche libere da contesto (CFG), ma hanno una diversa interpretazione: in una PEG l'operatore di scelta seleziona la prima corrispondenza, mentre in una CFG resta non deterministico. Ciò si avvicina alla pratica del riconoscimento delle stringhe ad esempio mediante un parser a discesa ricorsiva.A differenza delle CFG, le PEG non possono essere ambigue; se una stringa può essere derivata essa ammette esattamente un solo albero di derivazione. Si pensa che esistano linguaggi liberi che non possano essere analizzati tramite PEG, ma ciò non è ancora stato dimostrato. Le PEG sono indicate per l'analisi di linguaggio di programmazione (e linguaggi artificiali come Lojban), ma non per linguaggi naturali per i quali le prestazioni sono paragonabili a quelle degli algoritmi generali per CFG, ad esempio, l'algoritmo di Earley. (it)
- アーリー法（英: Earley parser）は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。 アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。 (ja)
- Algorytm Earleya – algorytm służący do analizy składniowej na podstawie dowolnej gramatyki bezkontekstowej. Stosuje się go między innymi do przetwarzania języków naturalnych, gdyż inaczej niż większość algorytmów analizy składniowej działa również z gramatykami niejednoznacznymi. Korzysta się też z niego przy tworzeniu interpreterów i kompilatorów języków programowania, zwłaszcza języków specjalizowanych, ponieważ szkielety projektowe oparte na tym algorytmie ułatwiają szybkie tworzenie prototypów (RAD). Górne ograniczenie czasu analizy n symboli terminalnych przez parser oparty na tym algorytmie rośnie proporcjonalnie do n3 w ogólnym przypadku, do n2 dla gramatyk jednoznacznych i do n dla sporej klasy gramatyk bezkontekstowych, w tym większości gramatyk języków programowania. Algorytm ten opracował w 1968 roku Jay Earley z Carnegie Mellon University w swojej pracy doktorskiej promowanej przez Roberta W. Floyda. W 1970 roku Earley opublikował go w Communications of the ACM w artykule, który w 1983 roku zaliczono do 21 najbardziej znaczących publikacji w ćwierćwieczu istnienia tego czasopisma. (pl)
- O algoritmo de análise gramatical Earley é um tipo de programa que subdivide uma entrada (input) para que um outro possa atuar sobre ela mais comumente usado em linguística computacional, nomeado após seu inventor, . O algoritmo faz uso de programação dinâmica. Os analisadores gramaticais Earley são interessantes porque podem analisar todas as linguagens livre de contexto. O algoritmo Earley tem tempo de execução O(n³) (onde n é o comprimento da cadeia de caracteres analisada), no caso geral, tempo quadrático (O(n²)) para gramáticas não ambígua, e tempo linear para quase toda as gramáticas LR(k)?. Seu desempenho é relativamente bom quando as regras são escritas de forma recursiva. (pt)
- Алгоритм Ерлі — алгоритм синтаксичного аналізу, призначений для перевірки коректності вхідного рядка. (uk)
- Алгори́тм Э́рли (англ. Earley) — алгоритм синтаксического анализа предложения по контекстно-свободной грамматике, основанный на методе динамического программирования. В отличие от алгоритма Кока — Янгера — Касами, который требует приведения грамматики к нормальной форме Хомского, алгоритм Эрли привлекателен тем, что не накладывает ограничений на используемую для анализа контекстно-свободную грамматику. Кроме того, Алгоритм Кока — Янгера — Касами работает по принципу «снизу-вверх», то есть строит возможные деревья разбора предложения начиная с вершины. В отличие от него Алгоритм Эрли реализует стратегию вывода «слева-направо». (ru)
|
| rdfs:comment
|
- Der Earley-Algorithmus oder Earley-Parser ist in der Informatik ein Algorithmus, der entscheidet, ob ein Wort von einer kontextfreien Grammatik erzeugt werden kann. Er wurde 1970 von entwickelt.Er ähnelt dem Cocke-Younger-Kasami-Algorithmus und löst wie dieser das Wortproblem der kontextfreien Sprachen. Er verwendet die Methode der dynamischen Programmierung. (de)
- El algoritmo de Earley es un algoritmo no determinista de análisis sintáctico para las gramáticas libres de contexto descrito originalmente por el informático estadounidense en 1970. Se ordena, a los lados de los algoritmos CYK y GLR, entre los algoritmos que usan la noción de reparto (de cálculos y de estructuras) y que construyen todos los análisis posibles de una frase (y no sólo uno de estos análisis). Es uno de los algoritmos no deterministas que usan ideas de la programación dinámica. (es)
- アーリー法（英: Earley parser）は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。 アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。 (ja)
- Алгоритм Ерлі — алгоритм синтаксичного аналізу, призначений для перевірки коректності вхідного рядка. (uk)
- Алгори́тм Э́рли (англ. Earley) — алгоритм синтаксического анализа предложения по контекстно-свободной грамматике, основанный на методе динамического программирования. В отличие от алгоритма Кока — Янгера — Касами, который требует приведения грамматики к нормальной форме Хомского, алгоритм Эрли привлекателен тем, что не накладывает ограничений на используемую для анализа контекстно-свободную грамматику. Кроме того, Алгоритм Кока — Янгера — Касами работает по принципу «снизу-вверх», то есть строит возможные деревья разбора предложения начиная с вершины. В отличие от него Алгоритм Эрли реализует стратегию вывода «слева-направо». (ru)
- 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 Univerzity Carnegie-Mellon. Algoritmus byl v roce 1970 publikován ve zkrácené a čitelnější podobě v časopise v článku, zařazeném v roce 1983 mezi 21 nejvýznamnějších článků za čtvrtstoletí existence tohoto časopisu. (cs)
- In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language, though (depending on the variant) it may suffer problems with certain nullable grammars. The algorithm, named after its inventor, Jay Earley, is a chart parser that uses dynamic programming; it is mainly used for parsing in computational linguistics. It was first introduced in his dissertation in 1968 (and later appeared in an abbreviated, more legible, form in a journal). (en)
- En théorie des langages, l'algorithme d'Earley est un algorithme d'analyse syntaxique pour les grammaires non contextuelles décrit pour la première fois par Jay Earley. À l'instar des algorithmes CYK et GLR, l'algorithme d'Earley calcule toutes les analyses possibles d'une phrase (et pas seulement une de ces analyses). Il repose sur de la programmation dynamique. (fr)
- In informatica, una parsing expression grammar, o PEG, è una grammatica formale analitica, ossia descrive un linguaggio formale in termini di un insieme di regole per riconoscere le stringhe che appartengono al linguaggio. Il formalismo è stato proposto nel 2004 ed è intimamente legato alla famiglia dei linguaggi analizzabili top-down introdotti nei primi anni settanta. Sintatticamente, le PEG somigliano anche alle grammatiche libere da contesto (CFG), ma hanno una diversa interpretazione: in una PEG l'operatore di scelta seleziona la prima corrispondenza, mentre in una CFG resta non deterministico. Ciò si avvicina alla pratica del riconoscimento delle stringhe ad esempio mediante un parser a discesa ricorsiva.A differenza delle CFG, le PEG non possono essere ambigue; se una stringa può es (it)
- O algoritmo de análise gramatical Earley é um tipo de programa que subdivide uma entrada (input) para que um outro possa atuar sobre ela mais comumente usado em linguística computacional, nomeado após seu inventor, . O algoritmo faz uso de programação dinâmica. (pt)
- Algorytm Earleya – algorytm służący do analizy składniowej na podstawie dowolnej gramatyki bezkontekstowej. Stosuje się go między innymi do przetwarzania języków naturalnych, gdyż inaczej niż większość algorytmów analizy składniowej działa również z gramatykami niejednoznacznymi. Korzysta się też z niego przy tworzeniu interpreterów i kompilatorów języków programowania, zwłaszcza języków specjalizowanych, ponieważ szkielety projektowe oparte na tym algorytmie ułatwiają szybkie tworzenie prototypów (RAD). (pl)
|
