Deterministic context-free grammar (original) (raw)
V lingvistice a informatice označuje pojem deterministická bezkontextová gramatika (DCFG) vlastní podmnožinu bezkontextových gramatik takových, které rozpoznává deterministický zásobníkový automat. Ke každé bezkontextové gramatice lze sestrojit zásobníkový automat, který reprezentuje syntaktický analyzátor pro věty generované danou gramatikou. Z hlediska aplikací teorie formálních jazyků v překladačích jsou důležité právě deterministické bezkontextové jazyky (jazyky popsané deterministickou bezkontextovou gramatikou), které lze analyzovat deterministickými syntaktickými analyzátory.
| Property | Value | |
|---|---|---|
| dbo:abstract | En la teoria dels llenguatges formals, la classe de gramàtiques lliures de context deterministes (DCFGs per les seves sigles en anglès) son un subconjunt propi de les gramàtiques lliures de context. Son el subconjunt de les gramàtiques lliures de context que es poden derivar d'un i generen els . Aquestes gramàtiques son sempre no-ambigües. DCFGs son d'un gran interès pràctic, ja que poden es poden analitzar sintàcticament (parser) en temps lineal i de fet, es pot generar automàticament un parser a partir de la gramàtica amb un generador. Per aquest motiu s'han fet servir a bastament en computació, ja que formes més restrictives de DCFGs es poden analitzar sintàcticament per parsers força simples. (ca) V lingvistice a informatice označuje pojem deterministická bezkontextová gramatika (DCFG) vlastní podmnožinu bezkontextových gramatik takových, které rozpoznává deterministický zásobníkový automat. Ke každé bezkontextové gramatice lze sestrojit zásobníkový automat, který reprezentuje syntaktický analyzátor pro věty generované danou gramatikou. Z hlediska aplikací teorie formálních jazyků v překladačích jsou důležité právě deterministické bezkontextové jazyky (jazyky popsané deterministickou bezkontextovou gramatikou), které lze analyzovat deterministickými syntaktickými analyzátory. (cs) In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the deterministic context-free languages. DCFGs are always unambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however. DCFGs are of great practical interest, as they can be parsed in linear time and in fact a parser can be automatically generated from the grammar by a parser generator. They are thus widely used throughout computer science. Various restricted forms of DCFGs can be parsed by simpler, less resource-intensive parsers, and thus are often used. These grammar classes are referred to by the type of parser that parses them, and important examples are LALR, SLR, and LL. (en) En informatique théorique, et particulièrement dans la théorie des grammaires formelles, les grammaires context-free déterministes ( DCFG ) ou grammaires non contextuelles déterministes sont un sous-ensemble des grammaires non contextuelles. Ce sont les grammaires non contextuelles qui peuvent être dérivées d'automates à pile déterministes, et ils engendrent les langages non contextuels déterministes. Les DCFG sont toujours inambigües et ils constituent une sous-classe importante des grammaires non contextuelles ; il existe cependant des CFG inambigües qui ne sont pas déterministes. Les DCFG sont d'un grand intérêt pratique, car ils peuvent être analysés en temps linéaire et en fait un analyseur peut être généré automatiquement à partir de la grammaire par un générateur d'analyseurs. Ils sont donc largement utilisés en informatique. Diverses formes restreintes des DCFG peuvent être analysées par des analyseurs plus simples et moins gourmands en ressources, et sont donc souvent utilisées. Ces classes de grammaires sont désignées par le type d'analyseur qui les analyse, et les exemples paradigmatiques sont LALR, SLR et LL. (fr) Na teoria da gramática formal, as gramáticas livres de contexto determinísticas (GLCD) são um subconjunto das gramáticas livres de contexto. Elas podem ser derivadas a partir de autômatos com pilha determinísticos, que geram as linguagens livres de contexto determinísticas. (pt) 在形式文法理论中，确定上下文无关文法(DCFG)是上下文无关文法的真子集。确定上下文无关文法是确定下推自动机可识别的文法。确定上下文无关语言是确定上下文无关文法所定义的形式语言。 它们在计算机科学领域中特别重要，因为这些文法可以有效的识别，而非确定上下文无关文法需要回溯或其他复杂的技术；非确定步骤的每次出现，栈都必须被复制并接着被传播(propagate)，消耗运行时间、内存或两者。在实践中，当你希望为非确定文法(比如用 YACC)建立一个解析器的时候，你必须通过增加约束如优先级来改变分析器为确定的。 确定上下文无关语言是拥有的语言的集合的真子集。例如，无歧义文法 S → 0S0 | 1S1 | ε，它定义了在字母 0 和 1 上的偶数长度的回文的语言，它能用确定下推自动机解析。 (zh) |
| dbo:wikiPageID | 10609024 (xsd:integer) | |
| dbo:wikiPageLength | 4496 (xsd:nonNegativeInteger) | |
| dbo:wikiPageRevisionID | 1102693152 (xsd:integer) | |
| dbo:wikiPageWikiLink | dbr:Proper_subset dbr:Regular_expressions dbr:Deterministic_context-free_language dbr:Deterministic_parsing dbr:Deterministic_pushdown_automaton dbr:Compilers dbr:LL_parser dbr:LR_parser dbr:Linear_time dbr:Deterministic_pushdown_automata dbr:Formal_grammar dbr:History_of_programming_languages dbc:Formal_languages dbr:Donald_Knuth dbr:Context-free_grammars dbr:Pushdown_automata dbr:LALR dbr:Parser_generator dbr:SLR_parser dbr:Finite_automata dbr:Unambiguous_grammar dbr:Frank_DeRemer | |
| dbp:wikiPageUsesTemplate | dbt:Formal_languages_and_grammars | |
| dcterms:subject | dbc:Formal_languages | |
| gold:hypernym | dbr:Subset | |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 dbo:ProgrammingLanguage yago:WikicatFormalLanguages | |
| rdfs:comment | V lingvistice a informatice označuje pojem deterministická bezkontextová gramatika (DCFG) vlastní podmnožinu bezkontextových gramatik takových, které rozpoznává deterministický zásobníkový automat. Ke každé bezkontextové gramatice lze sestrojit zásobníkový automat, který reprezentuje syntaktický analyzátor pro věty generované danou gramatikou. Z hlediska aplikací teorie formálních jazyků v překladačích jsou důležité právě deterministické bezkontextové jazyky (jazyky popsané deterministickou bezkontextovou gramatikou), které lze analyzovat deterministickými syntaktickými analyzátory. (cs) Na teoria da gramática formal, as gramáticas livres de contexto determinísticas (GLCD) são um subconjunto das gramáticas livres de contexto. Elas podem ser derivadas a partir de autômatos com pilha determinísticos, que geram as linguagens livres de contexto determinísticas. (pt) 在形式文法理论中，确定上下文无关文法(DCFG)是上下文无关文法的真子集。确定上下文无关文法是确定下推自动机可识别的文法。确定上下文无关语言是确定上下文无关文法所定义的形式语言。 它们在计算机科学领域中特别重要，因为这些文法可以有效的识别，而非确定上下文无关文法需要回溯或其他复杂的技术；非确定步骤的每次出现，栈都必须被复制并接着被传播(propagate)，消耗运行时间、内存或两者。在实践中，当你希望为非确定文法(比如用 YACC)建立一个解析器的时候，你必须通过增加约束如优先级来改变分析器为确定的。 确定上下文无关语言是拥有的语言的集合的真子集。例如，无歧义文法 S → 0S0 | 1S1 | ε，它定义了在字母 0 和 1 上的偶数长度的回文的语言，它能用确定下推自动机解析。 (zh) En la teoria dels llenguatges formals, la classe de gramàtiques lliures de context deterministes (DCFGs per les seves sigles en anglès) son un subconjunt propi de les gramàtiques lliures de context. Son el subconjunt de les gramàtiques lliures de context que es poden derivar d'un i generen els . Aquestes gramàtiques son sempre no-ambigües. (ca) In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the deterministic context-free languages. DCFGs are always unambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however. (en) En informatique théorique, et particulièrement dans la théorie des grammaires formelles, les grammaires context-free déterministes ( DCFG ) ou grammaires non contextuelles déterministes sont un sous-ensemble des grammaires non contextuelles. Ce sont les grammaires non contextuelles qui peuvent être dérivées d'automates à pile déterministes, et ils engendrent les langages non contextuels déterministes. Les DCFG sont toujours inambigües et ils constituent une sous-classe importante des grammaires non contextuelles ; il existe cependant des CFG inambigües qui ne sont pas déterministes. (fr) |
| rdfs:label | Gramàtica lliure de context determinista (ca) Deterministická bezkontextová gramatika (cs) Deterministic context-free grammar (en) Grammaire non contextuelle déterministe (fr) Gramática livre de contexto determinística (pt) 确定上下文无关文法 (zh) | |
| owl:sameAs | freebase:Deterministic context-free grammar yago-res:Deterministic context-free grammar wikidata:Deterministic context-free grammar dbpedia-ca:Deterministic context-free grammar dbpedia-cs:Deterministic context-free grammar dbpedia-fa:Deterministic context-free grammar dbpedia-fr:Deterministic context-free grammar dbpedia-hr:Deterministic context-free grammar dbpedia-pt:Deterministic context-free grammar dbpedia-sr:Deterministic context-free grammar dbpedia-zh:Deterministic context-free grammar https://global.dbpedia.org/id/3AeXu | |
| prov:wasDerivedFrom | wikipedia-en:Deterministic_context-free_grammar?oldid=1102693152&ns=0 | |
| foaf:isPrimaryTopicOf | wikipedia-en:Deterministic_context-free_grammar | |
| is dbo:wikiPageDisambiguates of | dbr:Context-free | |
| is dbo:wikiPageRedirects of | dbr:Deterministic_context_free_grammar dbr:DCFG | |
| is dbo:wikiPageWikiLink of | dbr:Parsing dbr:History_of_compiler_construction dbr:Deterministic_context-free_language dbr:Deterministic_parsing dbr:Index_of_philosophy_articles_(D–H) dbr:Context-free_grammar dbr:GLR_parser dbr:LL_grammar dbr:Deterministic_context_free_grammar dbr:Strict_determinism dbr:Earley_parser dbr:Ambiguous_grammar dbr:Context-free dbr:DCFG dbr:Self-replicating_machine | |
| is foaf:primaryTopic of | wikipedia-en:Deterministic_context-free_grammar |