LL grammar (original) (raw)
LL(k)-граматики — це клас контекстно-вільних граматик з додатковими обмеженнями, а саме: КВ-граматика називається LL(k)-граматикою, для деякого фіксованого k, якщо дія двох лівосторонніх виводів: 1. * 2. * , для яких з Firstk(x) = Firstk(y) випливає що. Неформально, граматика G буде LL(k)-граматикою, якщо для ланцюжка k перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з існує не більше однієїальтернативи виведення ланцюжка, що починається з та продовжуєтьсянаступними k термінальними символами. Означення:
Property | Value |
---|---|
dbo:abstract | Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. Eine LL(k)-Grammatik (im Gegensatz zu LF(k)-Grammatik auch schwache LL(k)-Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LL(k)-Parsers bildet. Eine kontextfreie Grammatik heißt LL(k)-Grammatik für eine natürliche Zahl k, wenn jeder Ableitungsschritt eindeutig durch die nächsten k Symbole der Eingabe (Lookahead) bestimmt ist. Das bedeutet, die Frage, welches Nichtterminalsymbol mit welcher Regel als Nächstes expandiert werden soll, kann eindeutig mit Hilfe der nächsten k Symbole der Eingabe bestimmt werden. Generell gilt, je größer k gewählt wird, umso mächtiger wird die Sprachklasse, wobei die Ausdrucksstärke von kontextfreien Grammatiken nie erreicht wird. Damit gibt es kontextfreie Sprachen, die für kein k von einer LL(k)-Grammatik erzeugt werden. Dabei steht DPDA für die deterministischen Kellerautomaten. Diese können genau die deterministisch kontextfreien Sprachen erkennen. (de) In formal language theory, an LL grammar is a context-free grammar that can be parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser that constructs a rightmost derivation). A language that has an LL grammar is known as an LL language. These form subsets of deterministic context-free grammars (DCFGs) and deterministic context-free languages (DCFLs), respectively. One says that a given grammar or language "is an LL grammar/language" or simply "is LL" to indicate that it is in this class. LL parsers are table-based parsers, similar to LR parsers. LL grammars can alternatively be characterized as precisely those that can be parsed by a predictive parser – a recursive descent parser without backtracking – and these can be readily written by hand. This article is about the formal properties of LL grammars; for parsing, see LL parser or recursive descent parser. (en) Dans la théorie du langage formel , une grammaire LL est une grammaire hors-contexte qui peut être analysée par un analyseur LL , qui analyse l'entrée de L gauche à droite, et construit une dérivation gauche de la phrase (d' où LL, par rapport à l'analyseur LR qui construit une dérivation la plus à droite). Un langage qui a une grammaire LL est appelé un langage LL . Ceux-ci forment des sous-ensembles de grammaires déterministes sans contexte (DCFG) et de langages déterministes sans contexte (DCFL), respectivement. On dit qu'une grammaire ou une langue donnée "est une grammaire / langue LL" ou simplement "est LL" pour indiquer qu'elle se trouve dans cette classe. (fr) LL(k)-граматики — це клас контекстно-вільних граматик з додатковими обмеженнями, а саме: КВ-граматика називається LL(k)-граматикою, для деякого фіксованого k, якщо дія двох лівосторонніх виводів: 1. * 2. * , для яких з Firstk(x) = Firstk(y) випливає що. Неформально, граматика G буде LL(k)-граматикою, якщо для ланцюжка k перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з існує не більше однієїальтернативи виведення ланцюжка, що починається з та продовжуєтьсянаступними k термінальними символами. Означення: (uk) |
dbo:thumbnail | wiki-commons:Special:FilePath/Parsing_a_C_program_that_needs_2_token_lookahead.svg?width=300 |
dbo:wikiPageExternalLink | https://archive.org/details/cprogramminglang00bria https://archive.org/details/introductiontoau00hopc http://www.antlr.org/papers/LL-star-PLDI11.pdf https://cs.uwaterloo.ca/research/tr/1979/CS-79-36.pdf |
dbo:wikiPageID | 32095640 (xsd:integer) |
dbo:wikiPageLength | 13985 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1073763378 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Moore_machine dbr:Parsing dbr:Deterministic_context-free_grammar dbr:Deterministic_context-free_language dbr:Context-free_grammar dbr:Empty_string dbr:LL_parser dbr:LR_parser dbr:Comparison_of_parser_generators dbr:Computer_language dbr:Post_correspondence_problem dbr:Formal_language_theory dbr:Partition_of_a_set dbr:Left_recursion dbr:Recursive_descent_parser dbr:Backtracking dbc:Formal_languages dbr:Greibach_normal_form dbr:Predictive_parser dbr:Unambiguous_grammar dbr:File:Parsing_a_C_program_that_needs_2_token_lookahead.svg |
dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfn dbt:Short_description dbt:Clarify_span dbt:Formal_languages_and_grammars |
dct:subject | dbc:Formal_languages |
gold:hypernym | dbr:Grammar |
rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 dbo:Book yago:WikicatFormalLanguages |
rdfs:comment | LL(k)-граматики — це клас контекстно-вільних граматик з додатковими обмеженнями, а саме: КВ-граматика називається LL(k)-граматикою, для деякого фіксованого k, якщо дія двох лівосторонніх виводів: 1. * 2. * , для яких з Firstk(x) = Firstk(y) випливає що. Неформально, граматика G буде LL(k)-граматикою, якщо для ланцюжка k перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з існує не більше однієїальтернативи виведення ланцюжка, що починається з та продовжуєтьсянаступними k термінальними символами. Означення: (uk) Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. Eine LL(k)-Grammatik (im Gegensatz zu LF(k)-Grammatik auch schwache LL(k)-Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LL(k)-Parsers bildet. Generell gilt, je größer k gewählt wird, umso mächtiger wird die Sprachklasse, wobei die Ausdrucksstärke von kontextfreien Grammatiken nie erreicht wird. Damit gibt es kontextfreie Sprachen, die für kein k von einer LL(k)-Grammatik erzeugt werden. (de) In formal language theory, an LL grammar is a context-free grammar that can be parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser that constructs a rightmost derivation). A language that has an LL grammar is known as an LL language. These form subsets of deterministic context-free grammars (DCFGs) and deterministic context-free languages (DCFLs), respectively. One says that a given grammar or language "is an LL grammar/language" or simply "is LL" to indicate that it is in this class. (en) Dans la théorie du langage formel , une grammaire LL est une grammaire hors-contexte qui peut être analysée par un analyseur LL , qui analyse l'entrée de L gauche à droite, et construit une dérivation gauche de la phrase (d' où LL, par rapport à l'analyseur LR qui construit une dérivation la plus à droite). Un langage qui a une grammaire LL est appelé un langage LL . Ceux-ci forment des sous-ensembles de grammaires déterministes sans contexte (DCFG) et de langages déterministes sans contexte (DCFL), respectivement. (fr) |
rdfs:label | LL(k)-Grammatik (de) LL grammar (en) Grammaire LL (fr) LL(k)-граматика (uk) |
owl:sameAs | freebase:LL grammar yago-res:LL grammar wikidata:LL grammar dbpedia-de:LL grammar dbpedia-fa:LL grammar dbpedia-fr:LL grammar dbpedia-no:LL grammar dbpedia-uk:LL grammar https://global.dbpedia.org/id/c3Pa |
prov:wasDerivedFrom | wikipedia-en:LL_grammar?oldid=1073763378&ns=0 |
foaf:depiction | wiki-commons:Special:FilePath/Parsing_a_C_program_that_needs_2_token_lookahead.svg |
foaf:isPrimaryTopicOf | wikipedia-en:LL_grammar |
is dbo:wikiPageRedirects of | dbr:LL-regular_grammar dbr:LL-regular_language dbr:LL1_grammar dbr:Simple_deterministic_language |
is dbo:wikiPageWikiLink of | dbr:LALR_parser dbr:LL-regular_grammar dbr:LL-regular_language dbr:Context-free_grammar dbr:LL_parser dbr:SLR_grammar dbr:LL1_grammar dbr:Simple_deterministic_language |
is foaf:primaryTopic of | wikipedia-en:LL_grammar |