| dbo:abstract
|
- Analýza rekurzivním sestupem (anglicky recursive descent parser) je metoda syntaktické analýzy shora dolů, implementovaná sadou procedur (nebo jejich nerekurzivních ekvivalentů), kde každá taková procedura obvykle implementuje jedno z pravidel gramatiky. Výsledná struktura programu zrcadlí strukturu gramatiky, kterou má rozpoznávat. Prediktivní syntaktický analyzátor je analyzátor s rekurzivním sestupem, který nepoužívá backtracking. Prediktivní syntaktická analýza je možná pouze pro třídu LL(k) gramatik, což jsou bezkontextové gramatiky, pro které existuje nějaké kladné celé číslo k, které umožňuje, aby analyzátor s rekurzivním sestupem rozhodoval, jaké přepisovací pravidlo se má použít, na základě prohlédnutí dalších k symbolů na vstupu. LL(k) gramatiky proto neobsahují žádné nejednoznačné gramatiky, ani gramatiky, které obsahují levou rekurzi. Jakákoli bezkontextová gramatika může být převedena na ekvivalentní gramatiku bez levé rekurze, ale odstranění levé rekurze nedává vždy LL(k) gramatiku. Prediktivní syntaktický analyzátor pracuje v . Rekurzivní sestup s backtracking je technika, která určuje, jaké přepisovací pravidlo se použije, zkoušením každého přepisovacího pravidla. Rekurzivní sestup s backtrackingem není omezený na LL(k) gramatiky, ale není zaručené, že skončí, pokud gramatika není LL(k). I když analýza skončí, analyzátor, který používá rekurzivní sestup s backtrackingem, může vyžadovat . Ačkoli prediktivní syntaktické analyzátory jsou často používány a jsou velmi oblíbené při ruční konstrukci analyzátorů, programátoři často dávají přednost používání analyzátorů vytvořených buď pro LL(k) jazyk nebo pomocí alternativního parseru, jako například anebo LR založeného na tabulkové syntaktické analýze. To je obzvláště případ, jestliže gramatika není ve tvaru LL(k), protože transformační gramatika na LL upraví gramatiku na vhodnou pro prediktivní syntaktickou analýzu. Prediktivní syntaktické analyzátory mohou být také automaticky generované pomocí nástroje jako je ANTLR. Prediktivní syntaktické analyzátory lze znázornit pomocí přechodových diagramů pro každý neterminální symbol, kde hrany mezi počátečním a koncovým stavem jsou označeny symboly (terminály a neterminály) z pravé strany přepisovacího pravidla. (cs)
- الترميز التكراري النموذجي ترميز من أعلى لأسفل، تمت صياغته من مجموعة من الخطوات ثنائية-التكرار (أو ما يعادلها من الخطوات غير المتكررة). حيث عادة ما يقوم كل إجراء من هذه الإجراءات بتطبيق إحدى القواعد الإنتاجية للقواعد النحوية. وعلى هذا يكون شكل البرنامج الناتج قريب الشبه جدا من القواعد النحوية التي يتعرف عليها.الترميز الخطي عبارة عن ترميز تكراري نموذجي لا يتطلب تراجع. والترميز الخطي ممكن فقط للترميز من أعلى لأسفل للنصوص التي تخلو من القواعد النحوية بمعنى أنها نصوص لا تتضمن قواعد نحوية والتي لابد لها من بعض الأرقام الموجبة k والتي تسمح للترميز التكراري النموذجي بتحديد الناتج الذي يستخدمه وذلك بفحص رموز الأرقام الموجبة k التالية للمدخلات. (وعلى هذا فإن النصوص الخالية من القواعد النحوية تستبعد كل القواعد النحوية المبهمة وكذلك كل القواعد النحوية التي تحتوي على ترميز أيسر. يمكن تحويل النصوص الخالية من القواعد النحوية إلى قواعد نحوية بديلة لا تحتوي على تكرار أيسر إلا أن إزالة التكرار الأيسر لا يؤدي دائما إلى نصوص تخلو من القواعد النحوية). بعمل الترميز الخطي في توقيت خطي.التكرار النموذجي بملفات احتياطية طريقة تحدد النواتج التي تستخدم بتجربة كل ناتج وراء الآخر. والتكرار النموذجي بملفات احتياطية ليس قاصرا على النصوص الخالية من القواعد النحوية ولكن ليس مضمونا أن ينتهي ما لم تكن القواعد النحوية غير مستخدمة. والترميز الذي يستخدم تكرار نموذجي بملفات احتياطية قد يتطلب زمن أُسي.ورغم استخدام الترميز الخطي على نطاق واسع يفضل المبرمجون إنشاء ترميز من اليسار لليمين أو ترميز مباشر من اليسار لليمين من خلال أدوات الترميز بدون تحويل القواعد النحوية إلى صيغة تخلو من القواعد (ar)
- Rekursiver Abstieg (englisch: recursive descent) ist eine Technik aus dem Compilerbau, die auf direkte Weise (d. h. ohne Tabelle) einen Top-Down-Parser implementiert. Sie zeichnet sich durch geringe Komplexität aus, das Verwenden eines Parsergenerators ist nicht nötig. Bei diesem Verfahren kommt jedem Nichtterminalsymbol eine Prozedur zu, welche die Produktionsregel zu diesem Symbol charakterisiert. Erlauben die Produktionsregeln eine Rekursion, dann rufen sich daher auch diese Prozeduren wechselseitig rekursiv auf. Ein rekursiver Abstieg kann Backtracking enthalten. Ein Verzicht darauf ist jedoch garantiert, wenn eine LL(k)-Grammatik für die zu parsende Sprache gegeben ist. Im Folgenden wird der häufige Fall angenommen. (de)
- In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes. A predictive parser is a recursive descent parser that does not require backtracking. Predictive parsing is possible only for the class of LL(k) grammars, which are the context-free grammars for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input. The LL(k) grammars therefore exclude all ambiguous grammars, as well as all grammars that contain left recursion. Any context-free grammar can be transformed into an equivalent grammar that has no left recursion, but removal of left recursion does not always yield an LL(k) grammar. A predictive parser runs in linear time. Recursive descent with backtracking is a technique that determines which production to use by trying each production in turn. Recursive descent with backtracking is not limited to LL(k) grammars, but is not guaranteed to terminate unless the grammar is LL(k). Even when they terminate, parsers that use recursive descent with backtracking may require exponential time. Although predictive parsers are widely used, and are frequently chosen if writing a parser by hand, programmers often prefer to use a table-based parser produced by a parser generator, either for an LL(k) language or using an alternative parser, such as LALR or LR. This is particularly the case if a grammar is not in LL(k) form, as transforming the grammar to LL to make it suitable for predictive parsing is involved. Predictive parsers can also be automatically generated, using tools like ANTLR. Predictive parsers can be depicted using transition diagrams for each non-terminal symbol where the edges between the initial and the final states are labelled by the symbols (terminals and non-terminals) of the right side of the production rule. (en)
- 재귀 하향 파서(recursive descent parser)는 절차(procedure)의 집합(또는 비재귀 적인 동등한 구문)으로 이루어진 하향식 구문 분석이다. 한 절차는 문법의 한 을 처리한다. 따라서 프로그램의 구조는 문법을 반영한 모양이 된다. (ko)
- 再帰下降構文解析（さいきかこうこうぶんかいせき、Recursive Descent Parsing）は、相互再帰型の手続き（あるいは再帰的でない同等の手続き）で構成されるLL法のトップダウン構文解析であり、各プロシージャが文法の各生成規則を実装することが多い。従って、生成されるプログラムの構造はほぼ正確にその文法を反映したものとなる。そのような実装の構文解析器を再帰下降パーサ（Recursive Descent Parser）と呼ぶ。 (ja)
- Метод рекурсивного спуска (англ. Recursive descent parser) — алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации. (ru)
- Рекурсивний спуск — алгоритм синтаксичного аналізу, будується на основі взаємно рекурсивних процедур (або не рекурсивних еквівалентів), кожна із яких реалізує одну із продукцій граматики. (uk)
- Um analisador sintático descendente recursivo é um analisador sintático descendente construído a partir de subrotinas mutualmente recursivas (ou qualquer equivalência não recursiva como uma pilha) em que cada subrotina geralmente implementa uma das regras de produção da gramática. Cada subrotina fica associada a um elemento não-terminal da gramática. Consequentemente, a estrutura do programa resultante se assemelha bastante à gramática que ele reconhece. Um analisador sintático preditivo (ou analisador sintático preditor) é um analisador sintático descendente recursivo que não requer backtracking. Ele só é possível para a classe de gramáticas LL(k), que são gramáticas livres de contexto para as quais existem algum inteiro positivo k que permite um analisador sintático descendente recursivo para decidir qual produção usar analisando somente os k tokens seguintes na entrada de dados. (Portanto, as gramáticas LL(k) excluem todas as gramáticas ambíguas, assim como todas as gramáticas que contêm . O algoritmo entraria em laço infinito. Qualquer gramática livre de contexto pode ser transformada numa gramática equivalente que não possui recursividade à esquerda, mas a remoção da recursividade a esquerda nem sempre resulta numa gramática LL(k).) Um analisador sintático preditivo possui complexidade linear. Um analisador sintático descendente com cópia determina qual produção usar por tentativa e erro (por exemplo, diferentes regras com mesmo lado esquerdo, A ::= aB | aC | cD). O algoritmo só retorna ao consumir toda a entrada (sucesso) ou ao esgotar todas as possibilidades de produção (falha). Ele não é limitado às gramáticas LL(k), mas o término não é garantido a menos que a gramática seja LL(k). Mesmo que termine, essa técnica pode levar a complexidade exponencial, e geralmente consome muita memória, o que a torna praticamente inutilizada atualmente. Apesar dos analisadores sintáticos preditivos serem bastante usados, os programadores geralmente preferem criar analisador LR ou LALR através de geradores de analisador sintáticos sem a transformação da gramática numa forma LL(k). Geradores de analisadores sintáticos descendentes recursivos incluem JavaCC (para Java), (C#, Java), (C, C++, Java, Python, C#, Objective-C), pyparsing (Python) e Spirit (C++, parte da biblioteca Boost). (pt)
- 在计算机科学中，递归下降解析器是一种，由一组相互递归的程序（或等价的非递归程序）构建而成，其中每个程序都实现了文法中的一个非终结符。因此，这些程序的结构密切反映了它所识别的文法结构。 预测性解析器是一种不需要回溯的递归下降解析器。预测性解析只适用于 LL(k) 文法。这是一种上下文无关文法。这种文法允许递归下降解析器仅通过检测之后 k 个标记决定当前标记（token）所使用的。LL(k) 文法由此排除了所有包含歧义和左递归的文法。虽然任何一种上下文无关文法都可以转化为没有左递归的等效文法，但是去除了左递归却不一定能够得到 LL(k) 文法。预测性解析器能够在线性时间内运行。 具有回溯的递归下降是一种通过依次尝试生成规则来生成结果的技术。具有回溯的递归下降不限于 LL(k) 文法，但只在文法是 LL(k) 文法的情况下才保证能够停机。具有回溯的递归下降对于其他文法即使能够停机，也可能需要指数时间运行。 尽管预测性解析器被广泛使用，也经常被选择用于手工编写解析器，但程序员通常更愿意使用由文法解析器生成器产生的基于表的解析器，无论是对于 LL(k) 语言还是使用替代解析器，比如 LALR 或 LR。如果一个文法不是 LL(k) 文法，情况尤其如此，因为要把文法转化为 LL 形式，使其适合预测性解析。预测性解析器也可以使用 ANTLR 之类的工具自动生成。 预测性解析器可以用每个非终结符号的过渡图来描述，其中初始状态和最终状态之间的界限由生成规则右侧的符号（终结符和非终结符）来界定。 (zh)
|
| rdfs:comment
|
- 재귀 하향 파서(recursive descent parser)는 절차(procedure)의 집합(또는 비재귀 적인 동등한 구문)으로 이루어진 하향식 구문 분석이다. 한 절차는 문법의 한 을 처리한다. 따라서 프로그램의 구조는 문법을 반영한 모양이 된다. (ko)
- 再帰下降構文解析（さいきかこうこうぶんかいせき、Recursive Descent Parsing）は、相互再帰型の手続き（あるいは再帰的でない同等の手続き）で構成されるLL法のトップダウン構文解析であり、各プロシージャが文法の各生成規則を実装することが多い。従って、生成されるプログラムの構造はほぼ正確にその文法を反映したものとなる。そのような実装の構文解析器を再帰下降パーサ（Recursive Descent Parser）と呼ぶ。 (ja)
- Метод рекурсивного спуска (англ. Recursive descent parser) — алгоритм нисходящего синтаксического анализа, реализуемый путём взаимного вызова процедур, где каждая процедура соответствует одному из правил контекстно-свободной грамматики или БНФ. Применения правил последовательно, слева-направо поглощают токены, полученные от лексического анализатора. Это один из самых простых алгоритмов синтаксического анализа, подходящий для полностью ручной реализации. (ru)
- Рекурсивний спуск — алгоритм синтаксичного аналізу, будується на основі взаємно рекурсивних процедур (або не рекурсивних еквівалентів), кожна із яких реалізує одну із продукцій граматики. (uk)
- الترميز التكراري النموذجي ترميز من أعلى لأسفل، تمت صياغته من مجموعة من الخطوات ثنائية-التكرار (أو ما يعادلها من الخطوات غير المتكررة). حيث عادة ما يقوم كل إجراء من هذه الإجراءات بتطبيق إحدى القواعد الإنتاجية للقواعد النحوية. وعلى هذا يكون شكل البرنامج الناتج قريب الشبه جدا من القواعد النحوية التي يتعرف عليها.الترميز الخطي عبارة عن ترميز تكراري نموذجي لا يتطلب تراجع. والترميز الخطي ممكن فقط للترميز من أعلى لأسفل للنصوص التي تخلو من القواعد النحوية بمعنى أنها نصوص لا تتضمن قواعد نحوية والتي لابد لها من بعض الأرقام الموجبة k والتي تسمح للترميز التكراري النموذجي بتحديد الناتج الذي يستخدمه وذلك بفحص رموز الأرقام الموجبة k التالية للمدخلات. (وعلى هذا فإن النصوص الخالية من القواعد النحوية تستبعد كل القواعد النحوية المبهمة وكذلك كل القواعد النحوية التي تحتوي على ترميز أيسر. يمكن تحويل النصوص الخال (ar)
- Analýza rekurzivním sestupem (anglicky recursive descent parser) je metoda syntaktické analýzy shora dolů, implementovaná sadou procedur (nebo jejich nerekurzivních ekvivalentů), kde každá taková procedura obvykle implementuje jedno z pravidel gramatiky. Výsledná struktura programu zrcadlí strukturu gramatiky, kterou má rozpoznávat. Prediktivní syntaktické analyzátory lze znázornit pomocí přechodových diagramů pro každý neterminální symbol, kde hrany mezi počátečním a koncovým stavem jsou označeny symboly (terminály a neterminály) z pravé strany přepisovacího pravidla. (cs)
- Rekursiver Abstieg (englisch: recursive descent) ist eine Technik aus dem Compilerbau, die auf direkte Weise (d. h. ohne Tabelle) einen Top-Down-Parser implementiert. Sie zeichnet sich durch geringe Komplexität aus, das Verwenden eines Parsergenerators ist nicht nötig. Bei diesem Verfahren kommt jedem Nichtterminalsymbol eine Prozedur zu, welche die Produktionsregel zu diesem Symbol charakterisiert. Erlauben die Produktionsregeln eine Rekursion, dann rufen sich daher auch diese Prozeduren wechselseitig rekursiv auf. (de)
- In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes. Predictive parsers can be depicted using transition diagrams for each non-terminal symbol where the edges between the initial and the final states are labelled by the symbols (terminals and non-terminals) of the right side of the production rule. (en)
- Um analisador sintático descendente recursivo é um analisador sintático descendente construído a partir de subrotinas mutualmente recursivas (ou qualquer equivalência não recursiva como uma pilha) em que cada subrotina geralmente implementa uma das regras de produção da gramática. Cada subrotina fica associada a um elemento não-terminal da gramática. Consequentemente, a estrutura do programa resultante se assemelha bastante à gramática que ele reconhece. (pt)
- 在计算机科学中，递归下降解析器是一种，由一组相互递归的程序（或等价的非递归程序）构建而成，其中每个程序都实现了文法中的一个非终结符。因此，这些程序的结构密切反映了它所识别的文法结构。 预测性解析器是一种不需要回溯的递归下降解析器。预测性解析只适用于 LL(k) 文法。这是一种上下文无关文法。这种文法允许递归下降解析器仅通过检测之后 k 个标记决定当前标记（token）所使用的。LL(k) 文法由此排除了所有包含歧义和左递归的文法。虽然任何一种上下文无关文法都可以转化为没有左递归的等效文法，但是去除了左递归却不一定能够得到 LL(k) 文法。预测性解析器能够在线性时间内运行。 具有回溯的递归下降是一种通过依次尝试生成规则来生成结果的技术。具有回溯的递归下降不限于 LL(k) 文法，但只在文法是 LL(k) 文法的情况下才保证能够停机。具有回溯的递归下降对于其他文法即使能够停机，也可能需要指数时间运行。 尽管预测性解析器被广泛使用，也经常被选择用于手工编写解析器，但程序员通常更愿意使用由文法解析器生成器产生的基于表的解析器，无论是对于 LL(k) 语言还是使用替代解析器，比如 LALR 或 LR。如果一个文法不是 LL(k) 文法，情况尤其如此，因为要把文法转化为 LL 形式，使其适合预测性解析。预测性解析器也可以使用 ANTLR 之类的工具自动生成。 (zh)
|
