Ambiguous grammar (original) (raw)
Existieren bzgl. einer formalen Grammatik für ein Wort mehrere Rechtsableitungen oder Linksableitungen, bzw. gibt es zu einem Wort der Grammatik zwei verschiedene Rechts- oder zwei verschiedene Linksableitungsbäume, die nicht isomorph zueinander sind, dann heißt diese Grammatik mehrdeutig.
| Property | Value |
|---|---|
| dbo:abstract | في علم الكمبيوتر ، القواعد الغامضة عبارة عن قواعد خالية من السياق ، والتي توجد بها سلسلة (مجموعة من الكلمات) يمكن أن تحتوي على أكثر من أو ، في حين أن القواعد التي لا لبس فيها عبارة عن غرامر خالية من السياق يكون لكل سلسلة صحيحة اشتقاق فريد من أقصى اليسار أو شجرة تحليل فريدة. العديد من اللغات تعترف بكل من القواعد النحوية الغامضة و الخالية من الغموض، في حين أن بعض اللغات تعترف فقط بالقواعد النحوية الغامضة. أي لغة غير فارغة تعترف بقواعد غامضة من خلال أخذ قواعد خالية من الغموض وإدخال قاعدة مكررة أو مرادف (اللغة الوحيدة بدون قواعد غامضة هي اللغة الفارغة). تسمى اللغة التي تعترف فقط بالقواعد الغامضة ، وهناك لغات عديدة خالية من السياق غامضة بطبيعتها. دائمًا ما تكون غامضة، وهي فئة فرعية مهمة من القواعد الغامضة، على أية حال، هناك قواعد غير حتمية غير غامضة. بالنسبة للغات برمجة الكمبيوتر ، غالبًا ما تكون القواعد المرجعية غامضة، نظرًا لوجود مشكلات مثل مشكلة . إذا وجدت، يتم حل هذه الغموض بشكل عام عن طريق إضافة قواعد الأسبقية أو قواعد تحليل أخرى ، لذا فإن عبارة القواعد بشكل عام لا غموض فيها. تسمى مجموعة أشجار التحليل اللغوية لجملة غامضة غابة التحليل. (ar) Nejednoznačná gramatika (anglicky ambiguous grammar) v teorii formálních jazyků je taková bezkontextová gramatika, která generuje (aspoň jednu) nejednoznačnou větu. Nejednoznačná věta je taková věta, pro kterou existují nejméně dva různé derivační stromy. Pokud každá z vět generovaných gramatikou má jediný derivační strom, je gramatika jednoznačná. Nejednoznačný jazyk je jazyk, pro které neexistuje žádná jednoznačná gramatika. Aby se předešlo problémům s porovnáváním derivačních stromů používá se také definice, že nejednoznačná gramatika je bezkontextová gramatika, v níž existuje věta, který má více než jednu levou derivaci, zatímco jednoznačná gramatika (anglicky unambiguous grammar) je bezkontextová gramatika, jejíž každá větu má jednoznačnou levou derivaci. Problém zjišťování nejednoznačnosti gramatiky je pro obecné bezkontextové gramatiky algoritmicky nerozhodnutelný. (cs) In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation or parse tree. Many languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars. Any non-empty language admits an ambiguous grammar by taking an unambiguous grammar and introducing a duplicate rule or synonym (the only language without ambiguous grammars is the empty language). A language that only admits ambiguous grammars is called an , and there are inherently ambiguous context-free languages. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however. For computer programming languages, the reference grammar is often ambiguous, due to issues such as the problem. If present, these ambiguities are generally resolved by adding precedence rules or other context-sensitive parsing rules, so the overall phrase grammar is unambiguous. Some parsing algorithms (such as (Earley or GLR parsers) can generate sets of parse trees (or "parse forests") from strings that are syntactically ambiguous. (en) Existieren bzgl. einer formalen Grammatik für ein Wort mehrere Rechtsableitungen oder Linksableitungen, bzw. gibt es zu einem Wort der Grammatik zwei verschiedene Rechts- oder zwei verschiedene Linksableitungsbäume, die nicht isomorph zueinander sind, dann heißt diese Grammatik mehrdeutig. (de) En Ciencias de la Computación, una gramática ambigua es un Gramática libre del contexto para la que existe una cadena que puede tener más de una derivación a la izquierda, mientras una gramática no ambigua es una Gramática libre del contexto para la que cada cadena válida tiene una única derivación a la izquierda. Muchos lenguajes admiten tanto gramáticas ambiguas como no ambiguas, mientras otros lenguajes admiten solo gramáticas ambiguas. Cualquier lenguaje no vacío admite una gramática ambigua al tomar una gramática no ambigua e introducir una regla duplicada (el único lenguaje sin gramáticas ambiguas es el lenguaje vacío). Un lenguaje que solo admite gramáticas ambiguas se conoce como un Lenguaje Inherentemente Ambiguo, y existen lenguajes libres del contexto inherentemente ambiguos. Las gramáticas libres del contexto deterministas son siempre no-ambiguas, y son una subclase importante de GLCs no-ambiguas; existen GLCs no-deterministas y no-ambiguas simultáneamente. (es) En informatique théorique et en théorie des langages, une grammaire ambiguë ou ambigüe est une grammaire algébrique qui admet un mot avec deux dérivations gauches distinctes ou — de manière équivalente — deux arbres de dérivation distincts. L'ambiguïté ou l'inambiguïté est une propriété des grammaires, et non des langages. De nombreux langages admettent à la fois des grammaires ambiguës et inambigües, alors que d'autres ne possèdent que des grammaires ambiguës. Un langage pour lequel toutes les grammaires sont ambiguës est appelé inhéremment ambigu (ou intrinsèquement ambigu), les autres sont appelés langages inambigus. La grammaire de référence de langages de programmation est parfois ambigüe à cause de constructions qui conduisent à de problèmes comme le problème du dangling else. De telles ambiguïtés sont généralement levées en ajoutant des règles de précédence ou d'autres règles, contextuelles celles-là, qui rendent la grammaire finale inambigüe. (fr) In de informatica wordt een contextvrije grammatica een ambigue grammatica genoemd als een bepaalde string, in deze context ook woord of zin genoemd, op verschillende manieren kan worden gegenereerd. Dit houdt in dat er meer syntaxisbomen bestaan voor die string. Omdat een syntaxisboom vaak een-op-een samenhangt met de interpretatie van een zin, is het in de praktijk meestal ongewenst dat een grammatica ambigu is. Een contextvrije grammatica is eenduidig als ze niet ambigu is. Bij veel ambigue grammatica's bestaat er ook een equivalente eenduidige grammatica, dat wil zeggen een eenduidige grammatica die dezelfde taal genereert. Er bestaan echter ook contextvrije talen die alleen door ambigue grammatica's worden gegenereerd. Zulke talen worden inherent ambigu genoemd. Een voorbeeld van een inherent ambigue taal is . (nl) 曖昧な文法（あいまいなぶんぽう、英: ambiguous grammar〈直訳すると「多義的な文法」〉）とは、構文木が唯一にならないかもしれない文法のことである。ここでは、自然言語は文法自体が不確かであることが多いため、そうではない形式言語に議論を限定するが、自然言語にも同様なことを考えることは可能である。形式言語的な文法を持つ言語が「本質的に曖昧である」とは、その言語を生成できるような文法は曖昧な文法にならざるをえないということである。 以下では、議論を統語（syntax）の曖昧性（ambiguity）に限定し、さらに用語として「文法」ではなく「統語」を使うことができる文脈ではできるだけ「統語」を使う。 (ja) Em ciência da computação, uma gramática livre de contexto é dita ser uma gramática ambígua se existe uma que pode ser gerada pela gramática em mais de um caminho (ou seja, a cadeia admite mais de uma árvore sintática ou, equivalentemente, mais de uma ). Uma linguagem livre de contexto é inerentemente ambígua se todas as gramáticas livres de contexto geradoras desta linguagem são ambíguas. Algumas linguagens de programação têm gramáticas ambíguas; neste caso, a informação semântica é necessária para selecionar a árvore sintática pretendida de uma construção ambígua. Por exemplo, em o seguinte: x * y ; pode ser interpretado como: * A declaração de um identificador chamado y do tipo ponteiro para x, ou * Uma expressão na qual x é multiplicado por y e então o resultado é descartado. Para escolher corretamente entre as duas interpretações possíveis, um compilador deve consultar a sua tabela de símbolos para descobrir se x foi declarada como um nome de typedef que é visível neste momento. (pt) In informatica, una grammatica è detta ambigua se esistono stringhe da essa generate che possono essere prodotte con diverse (in inglese leftmost derivation), o, equivalentemente, che hanno più di un possibile albero sintattico. Un linguaggio è detto inerentemente ambiguo quando può essere generato solo da grammatiche ambigue. Per quanto riguarda i linguaggi di programmazione, le grammatiche ambigue possono rendere difficile l'analisi sintattica (parsificazione) del codice sorgente. In genere, i (parser generator o compiler compiler in inglese) che permettono la definizione di linguaggi attraverso grammatiche ambigue (ad esempio GNU Bison) dispongono di metodi di risoluzione dell'ambiguità. (it) В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом (то есть для строки есть более одного дерева разбора). Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками. Грамматики некоторых языков программирования неоднозначны. При разборе таких языков необходимо учитывать семантическую информацию для выбора правильного варианта. Например, на языке C следующая запись: x * y; может быть проинтерпретирована как либо: * объявление идентификатора y с типом указатель-на-x, или * выражение, в котором x умножается на y, а результат игнорируется. Чтобы выбрать между этими интерпретациями, компилятор должен обратиться к своей таблице символов, чтобы узнать, было ли объявление x в качестве имени typedef в данной области видимости. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Leftmostderivations_jaredwf.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.brics.dk/grammar https://web.archive.org/web/20110719055512/http:/www2.tcs.ifi.lmu.de/~mlange/cfganalyzer/index.html https://archive.org/details/introductiontoau00hopc https://archive.org/details/introductiontoau00john_537 https://archive.org/details/introductiontoau00john_537/page/n232 |
| dbo:wikiPageID | 647729 (xsd:integer) |
| dbo:wikiPageLength | 14089 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102857237 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Rohit_Jivanlal_Parikh dbr:Decision_problem dbr:Deterministic_context-free_grammar dbr:Conditional_(computer_programming) dbr:Context-free_grammar dbr:Parikh's_theorem dbr:GLR_parser dbr:Context-free_language dbr:Context-sensitive_grammar dbr:Dangling_else dbr:LR_parser dbr:Production_rule_(formal_languages) dbr:Computer_science dbr:Deterministic_pushdown_automata dbr:Post_correspondence_problem dbr:String_(computer_science) dbr:Earley_parser dbr:Chart_parser dbr:Regular_language dbc:Ambiguity dbc:Formal_languages dbr:Syntactically_ambiguous dbr:Parse_tree dbr:CYK_algorithm dbr:Context-free_grammars dbr:Pushdown_automata dbr:YACC dbr:Undecidable_problem dbr:Syntactic_ambiguity dbr:Programming_language dbr:Palindrome dbr:Right-associative dbr:Context_free_grammar dbr:Leftmost_derivation dbr:Generalized_LR_parser dbr:Semi-decidable dbr:File:Leftmostderivations_jaredwf.svg dbr:Nested_conditional |
| dbp:date | January 2017 (en) |
| dbp:reason | There is no such thing as an 'overall phrase grammar'. The 'nearest-if' rule can possibly be implemented by using a slightly modified, but still context-free grammar. (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Clarify dbt:Harvtxt dbt:Main dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Ambiguity dbc:Formal_languages |
| gold:hypernym | dbr:Grammar |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 dbo:Book yago:WikicatFormalLanguages |
| rdfs:comment | Existieren bzgl. einer formalen Grammatik für ein Wort mehrere Rechtsableitungen oder Linksableitungen, bzw. gibt es zu einem Wort der Grammatik zwei verschiedene Rechts- oder zwei verschiedene Linksableitungsbäume, die nicht isomorph zueinander sind, dann heißt diese Grammatik mehrdeutig. (de) 曖昧な文法（あいまいなぶんぽう、英: ambiguous grammar〈直訳すると「多義的な文法」〉）とは、構文木が唯一にならないかもしれない文法のことである。ここでは、自然言語は文法自体が不確かであることが多いため、そうではない形式言語に議論を限定するが、自然言語にも同様なことを考えることは可能である。形式言語的な文法を持つ言語が「本質的に曖昧である」とは、その言語を生成できるような文法は曖昧な文法にならざるをえないということである。 以下では、議論を統語（syntax）の曖昧性（ambiguity）に限定し、さらに用語として「文法」ではなく「統語」を使うことができる文脈ではできるだけ「統語」を使う。 (ja) في علم الكمبيوتر ، القواعد الغامضة عبارة عن قواعد خالية من السياق ، والتي توجد بها سلسلة (مجموعة من الكلمات) يمكن أن تحتوي على أكثر من أو ، في حين أن القواعد التي لا لبس فيها عبارة عن غرامر خالية من السياق يكون لكل سلسلة صحيحة اشتقاق فريد من أقصى اليسار أو شجرة تحليل فريدة. العديد من اللغات تعترف بكل من القواعد النحوية الغامضة و الخالية من الغموض، في حين أن بعض اللغات تعترف فقط بالقواعد النحوية الغامضة. أي لغة غير فارغة تعترف بقواعد غامضة من خلال أخذ قواعد خالية من الغموض وإدخال قاعدة مكررة أو مرادف (اللغة الوحيدة بدون قواعد غامضة هي اللغة الفارغة). تسمى اللغة التي تعترف فقط بالقواعد الغامضة ، وهناك لغات عديدة خالية من السياق غامضة بطبيعتها. دائمًا ما تكون غامضة، وهي فئة فرعية مهمة من القواعد الغامضة، على أية حال، هناك قواعد غير حتمية غير غامضة. (ar) Nejednoznačná gramatika (anglicky ambiguous grammar) v teorii formálních jazyků je taková bezkontextová gramatika, která generuje (aspoň jednu) nejednoznačnou větu. Nejednoznačná věta je taková věta, pro kterou existují nejméně dva různé derivační stromy. Pokud každá z vět generovaných gramatikou má jediný derivační strom, je gramatika jednoznačná. Nejednoznačný jazyk je jazyk, pro které neexistuje žádná jednoznačná gramatika. Problém zjišťování nejednoznačnosti gramatiky je pro obecné bezkontextové gramatiky algoritmicky nerozhodnutelný. (cs) In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation or parse tree. Many languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars. Any non-empty language admits an ambiguous grammar by taking an unambiguous grammar and introducing a duplicate rule or synonym (the only language without ambiguous grammars is the empty language). A language that only admits ambiguous grammars is called an , and there are inherently ambiguous context-free languages. Deterministic context-free grammars are always unambiguous, and are an i (en) En Ciencias de la Computación, una gramática ambigua es un Gramática libre del contexto para la que existe una cadena que puede tener más de una derivación a la izquierda, mientras una gramática no ambigua es una Gramática libre del contexto para la que cada cadena válida tiene una única derivación a la izquierda. Muchos lenguajes admiten tanto gramáticas ambiguas como no ambiguas, mientras otros lenguajes admiten solo gramáticas ambiguas. Cualquier lenguaje no vacío admite una gramática ambigua al tomar una gramática no ambigua e introducir una regla duplicada (el único lenguaje sin gramáticas ambiguas es el lenguaje vacío). Un lenguaje que solo admite gramáticas ambiguas se conoce como un Lenguaje Inherentemente Ambiguo, y existen lenguajes libres del contexto inherentemente ambiguos. La (es) In informatica, una grammatica è detta ambigua se esistono stringhe da essa generate che possono essere prodotte con diverse (in inglese leftmost derivation), o, equivalentemente, che hanno più di un possibile albero sintattico. Un linguaggio è detto inerentemente ambiguo quando può essere generato solo da grammatiche ambigue. (it) En informatique théorique et en théorie des langages, une grammaire ambiguë ou ambigüe est une grammaire algébrique qui admet un mot avec deux dérivations gauches distinctes ou — de manière équivalente — deux arbres de dérivation distincts. L'ambiguïté ou l'inambiguïté est une propriété des grammaires, et non des langages. De nombreux langages admettent à la fois des grammaires ambiguës et inambigües, alors que d'autres ne possèdent que des grammaires ambiguës. Un langage pour lequel toutes les grammaires sont ambiguës est appelé inhéremment ambigu (ou intrinsèquement ambigu), les autres sont appelés langages inambigus. (fr) Em ciência da computação, uma gramática livre de contexto é dita ser uma gramática ambígua se existe uma que pode ser gerada pela gramática em mais de um caminho (ou seja, a cadeia admite mais de uma árvore sintática ou, equivalentemente, mais de uma ). Uma linguagem livre de contexto é inerentemente ambígua se todas as gramáticas livres de contexto geradoras desta linguagem são ambíguas. x * y ; pode ser interpretado como: * A declaração de um identificador chamado y do tipo ponteiro para x, ou * Uma expressão na qual x é multiplicado por y e então o resultado é descartado. (pt) In de informatica wordt een contextvrije grammatica een ambigue grammatica genoemd als een bepaalde string, in deze context ook woord of zin genoemd, op verschillende manieren kan worden gegenereerd. Dit houdt in dat er meer syntaxisbomen bestaan voor die string. Omdat een syntaxisboom vaak een-op-een samenhangt met de interpretatie van een zin, is het in de praktijk meestal ongewenst dat een grammatica ambigu is. (nl) В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом (то есть для строки есть более одного дерева разбора). Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками. Грамматики некоторых языков программирования неоднозначны. При разборе таких языков необходимо учитывать семантическую информацию для выбора правильного варианта. Например, на языке C следующая запись: x * y; может быть проинтерпретирована как либо: (ru) |
| rdfs:label | القواعد الغامضة (ar) Nejednoznačná gramatika (cs) Mehrdeutige Grammatik (de) Ambiguous grammar (en) Gramática ambigua (es) Grammaire ambigüe (fr) Grammatica ambigua (it) 曖昧な文法 (ja) Ambigue grammatica (nl) Gramática ambígua (pt) Неоднозначная грамматика (ru) |
| owl:sameAs | freebase:Ambiguous grammar yago-res:Ambiguous grammar wikidata:Ambiguous grammar dbpedia-ar:Ambiguous grammar http://bs.dbpedia.org/resource/Nejednoznačna_gramatika dbpedia-cs:Ambiguous grammar dbpedia-de:Ambiguous grammar dbpedia-es:Ambiguous grammar dbpedia-fa:Ambiguous grammar dbpedia-fr:Ambiguous grammar dbpedia-hr:Ambiguous grammar dbpedia-it:Ambiguous grammar dbpedia-ja:Ambiguous grammar dbpedia-nl:Ambiguous grammar dbpedia-no:Ambiguous grammar dbpedia-pt:Ambiguous grammar dbpedia-ru:Ambiguous grammar https://global.dbpedia.org/id/qbya |
| prov:wasDerivedFrom | wikipedia-en:Ambiguous_grammar?oldid=1102857237&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Leftmostderivations_jaredwf.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Ambiguous_grammar |
| is dbo:wikiPageRedirects of | dbr:Ambiguous_context-free_grammar dbr:Inherently_ambiguous_language dbr:Unambiguous_context-free_grammar dbr:Ambiguous_grammars dbr:Unambiguous_grammar |
| is dbo:wikiPageWikiLink of | dbr:Parsing dbr:Berkeley_Yacc dbr:LALR_parser dbr:Context-free_grammar dbr:Ogden's_lemma dbr:Parikh's_theorem dbr:GLR_parser dbr:Dangling_else dbr:LR_parser dbr:SLR_grammar dbr:Chomsky–Schützenberger_enumeration_theorem dbr:Parsing_expression_grammar dbr:Spirit_Parser_Framework dbr:Syntax_(programming_languages) dbr:Tagged_Deterministic_Finite_Automaton dbr:Earley_parser dbr:Ambiguity dbr:Ambiguous_context-free_grammar dbr:PLY_(Python_Lex-Yacc) dbr:Chart_parser dbr:Formal_grammar dbr:Grammar dbr:Graph-structured_stack dbr:Left_recursion dbr:Probabilistic_context-free_grammar dbr:Production_(computer_science) dbr:Recursive_descent_parser dbr:Top-down_parsing dbr:CYK_algorithm dbr:Filtered-popping_recursive_transition_network dbr:Greibach's_theorem dbr:Most_vexing_parse dbr:Syntax_Definition_Formalism dbr:Syntactic_ambiguity dbr:Parser_combinator dbr:Polysemy dbr:Inherently_ambiguous_language dbr:Shift-reduce_parser dbr:Unambiguous_context-free_grammar dbr:Ambiguous_grammars dbr:Unambiguous_grammar |
| is foaf:primaryTopic of | wikipedia-en:Ambiguous_grammar |
