Parsing expression grammar (original) (raw)
Un parser packrat est un type d'analyseur syntaxique utilisé en informatique. Il se base sur la décomposition analytique, et donc découpe un flux continu de caractères puis construit un arbre d'analyse depuis le haut vers le bas. Grâce à cette mémoïsation, un parser packrat peut analyser un grand nombre de grammaires hors-contexte et toutes les (dont celles qui ne représentent pas des langages libres de contexte).
| Property | Value |
|---|---|
| dbo:abstract | In computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s.Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser. Unlike CFGs, PEGs cannot be ambiguous; if a string parses, it has exactly one valid parse tree. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven. PEGs are well-suited to parsing computer languages (and artificial human languages such as Lojban), but not natural languages where the performance of PEG algorithms is comparable to general CFG algorithms such as the Earley algorithm. (en) Un parser packrat est un type d'analyseur syntaxique utilisé en informatique. Il se base sur la décomposition analytique, et donc découpe un flux continu de caractères puis construit un arbre d'analyse depuis le haut vers le bas. Grâce à cette mémoïsation, un parser packrat peut analyser un grand nombre de grammaires hors-contexte et toutes les (dont celles qui ne représentent pas des langages libres de contexte). (fr) Parsing Expression Grammar (PEG) は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析に向いており、一方、自然言語の多義性を、そのまま複数の構文木が可能である、という形で形式化するのには向かない。 (ja) Грамматика, разбирающая выражение (РВ-грамматика) — тип аналитической формальной грамматики, описывающей формальный язык в терминах набора правил для распознавания строк языка. Грамматика, разбирающая выражение, в сущности, представляет собой синтаксический анализатор рекурсивного спуска в чисто схематической форме, которая выражает только синтаксис и не зависит от конкретной реализации или применения синтаксического анализатора. Грамматики, разбирающие выражение, похожи на регулярные выражения и на контекстно-свободные грамматики (КС-грамматики) в нотации Бэкуса-Наура, но имеют отличную от них интерпретацию. В отличие от КС-грамматик, РВ-грамматики не могут быть неоднозначными: если строка разбирается, то существует ровно одно дерево разбора. Это делает РВ-грамматики пригодными для компьютерных языков, но не для естественных. (ru) Na ciência da computação, uma gramática de análise sintática de expressão, ou GASE, é um tipo de gramática formal analítica, ou seja, ela descreve uma linguagem formal em termos de um conjunto de regras para o reconhecimento de cadeias na linguagem. O formalismo foi introduzido por em 2004 e está intimamente relacionado com a família de linguagens analíticas de cima para baixo (em inglês, top-down) introduzidas no início de 1970. Sintaticamente, GASEs também são semelhantes a gramáticas livres de contexto (GLCs), mas elas têm uma interpretação diferente: o operador escolha seleciona o primeiro jogo em GASE, enquanto é ambígua na GLC. Isto está mais próximo de como o reconhecimento de uma cadeia tende a ser feito na prática, por exemplo, por um analisador recursivo de descida. Ao contrário das GLCs, GASEs não podem ser ambíguas; Se uma cadeia é analisada sintaticamente, então ela tem exatamente um árvore de análise sintática válida. Conjectura-se que existem linguagens livres de contexto que não pode ser analisadas sintaticamente por uma GASE, mas isso ainda não está comprovado. GASEs são bem adaptadas para analisar linguagens de computador, mas não as linguagens naturais, onde seu desempenho é comparável ao de algoritmos gerais de GLC, como o algoritmo de Earley. (pt) 在计算机科学領域，解析表达文法，简称PEG（英語：Parsing Expression Grammar），是一种分析型形式文法。PEG在2004年由布莱恩·福特（Bryan Ford）推出，，它与20世纪70年代初引入的家族密切相关。 在语法上，PEG很接近上下文无关文法（CFG），但是他們採用了不同的解釋：例如PEG中的选择操作符總是会选中第一个匹配项，而在CFG中则是不明确的。这更接近于字符串识别在实际中的应用，例如使用递归下降解析器的情況。另外不像CFG，PEG不能有：在解析一个字符串的时候，只能有單一确定的語法分析树。据推测，存在上下文无关语言，不能用PEG处理，但尚未得到证实。 这个特性使得PEG更适合计算机语言的解析，对于一般的CFG算法（如）的性能可以与之比拟的自然语言就不是很合适。 (zh) |
| dbo:wikiPageExternalLink | http://bford.info/packrat/ http://www.digitalkingdom.org/~rlpowell/hobbies/lojban/grammar/ https://web.archive.org/web/20131103083443/http:/mathosproject.com/updates/convert-a-string-expression-into-a-lambda-expression/ https://www.gnu.org/software/guile/manual/html_node/PEG-Parsing.html |
| dbo:wikiPageID | 892899 (xsd:integer) |
| dbo:wikiPageLength | 25105 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122617388 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Python_(programming_language) dbr:Memoization dbr:Parsing dbr:Bellman–Ford_algorithm dbr:Regular_expression dbr:Regular_expressions dbr:Commutativity dbr:Compiler_Description_Language dbr:Context-free_grammar dbr:OMeta dbr:Function_(mathematics) dbr:GLR_parser dbr:Constructed_language dbr:Context-free_language dbr:Dangling_else dbr:LL_parser dbr:LR_parser dbr:Linear_time dbr:Lojban dbr:Comparison_of_parser_generators dbr:Computer_science dbr:String_(computer_science) dbr:Mutual_recursion dbr:Disjoint_sets dbr:Logic_programming dbr:Graph_algorithms dbr:Cut_(logic_programming) dbr:Ambiguous_grammar dbr:Nonterminal_symbol dbr:Floyd–Warshall_algorithm dbr:Formal_grammar dbr:Formal_language dbr:Left_recursion dbr:Recursion dbr:Recursive_descent_parser dbr:Syntactic_predicate dbr:Backtracking dbr:Terminal_symbol dbc:Formal_languages dbr:Parse_tree dbr:Top-down_parsing_language dbr:Boolean_grammar dbr:CYK_algorithm dbr:Circular_definition dbr:Context-free_grammars dbr:Greedy_algorithm dbr:Exponential_time dbr:Expression_(mathematics) dbr:Natural_language dbr:Parser_combinator dbr:LL(k) dbr:Earley_algorithm |
| dbp:wikiPageUsesTemplate | dbt:Code dbt:Reflist dbt:Short_description dbt:Tmath dbt:Parsers |
| dcterms:subject | dbc:Formal_languages |
| gold:hypernym | dbr:Grammar |
| rdf:type | yago:WikicatParsingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Language106282651 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Book yago:Rule105846932 yago:WikicatFormalLanguages |
| rdfs:comment | Un parser packrat est un type d'analyseur syntaxique utilisé en informatique. Il se base sur la décomposition analytique, et donc découpe un flux continu de caractères puis construit un arbre d'analyse depuis le haut vers le bas. Grâce à cette mémoïsation, un parser packrat peut analyser un grand nombre de grammaires hors-contexte et toutes les (dont celles qui ne représentent pas des langages libres de contexte). (fr) Parsing Expression Grammar (PEG) は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析に向いており、一方、自然言語の多義性を、そのまま複数の構文木が可能である、という形で形式化するのには向かない。 (ja) 在计算机科学領域，解析表达文法，简称PEG（英語：Parsing Expression Grammar），是一种分析型形式文法。PEG在2004年由布莱恩·福特（Bryan Ford）推出，，它与20世纪70年代初引入的家族密切相关。 在语法上，PEG很接近上下文无关文法（CFG），但是他們採用了不同的解釋：例如PEG中的选择操作符總是会选中第一个匹配项，而在CFG中则是不明确的。这更接近于字符串识别在实际中的应用，例如使用递归下降解析器的情況。另外不像CFG，PEG不能有：在解析一个字符串的时候，只能有單一确定的語法分析树。据推测，存在上下文无关语言，不能用PEG处理，但尚未得到证实。 这个特性使得PEG更适合计算机语言的解析，对于一般的CFG算法（如）的性能可以与之比拟的自然语言就不是很合适。 (zh) In computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s.Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser. (en) Na ciência da computação, uma gramática de análise sintática de expressão, ou GASE, é um tipo de gramática formal analítica, ou seja, ela descreve uma linguagem formal em termos de um conjunto de regras para o reconhecimento de cadeias na linguagem. O formalismo foi introduzido por em 2004 e está intimamente relacionado com a família de linguagens analíticas de cima para baixo (em inglês, top-down) introduzidas no início de 1970. Sintaticamente, GASEs também são semelhantes a gramáticas livres de contexto (GLCs), mas elas têm uma interpretação diferente: o operador escolha seleciona o primeiro jogo em GASE, enquanto é ambígua na GLC. Isto está mais próximo de como o reconhecimento de uma cadeia tende a ser feito na prática, por exemplo, por um analisador recursivo de descida. (pt) Грамматика, разбирающая выражение (РВ-грамматика) — тип аналитической формальной грамматики, описывающей формальный язык в терминах набора правил для распознавания строк языка. Грамматика, разбирающая выражение, в сущности, представляет собой синтаксический анализатор рекурсивного спуска в чисто схематической форме, которая выражает только синтаксис и не зависит от конкретной реализации или применения синтаксического анализатора. Грамматики, разбирающие выражение, похожи на регулярные выражения и на контекстно-свободные грамматики (КС-грамматики) в нотации Бэкуса-Наура, но имеют отличную от них интерпретацию. (ru) |
| rdfs:label | Parser packrat (fr) Parsing Expression Grammar (ja) Parsing expression grammar (en) Gramática de análise sintática de expressão (pt) Грамматика, разбирающая выражение (ru) 解析表达文法 (zh) |
| owl:sameAs | freebase:Parsing expression grammar yago-res:Parsing expression grammar wikidata:Parsing expression grammar dbpedia-fa:Parsing expression grammar dbpedia-fr:Parsing expression grammar dbpedia-ja:Parsing expression grammar dbpedia-pt:Parsing expression grammar dbpedia-ru:Parsing expression grammar dbpedia-zh:Parsing expression grammar https://global.dbpedia.org/id/2yk1o |
| prov:wasDerivedFrom | wikipedia-en:Parsing_expression_grammar?oldid=1122617388&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Parsing_expression_grammar |
| is dbo:wikiPageDisambiguates of | dbr:Peg |
| is dbo:wikiPageRedirects of | dbr:Parsing_Expression_Grammar dbr:PyPEG dbr:Packrat_parser dbr:PEG_parser dbr:Text_parsing dbr:Packrat_parsing dbr:Parsing_expression |
| is dbo:wikiPageWikiLink of | dbr:Roberto_Ierusalimschy dbr:List_of_algorithms dbr:List_of_filename_extensions_(M–R) dbr:List_of_formal_language_and_literal_string_topics dbr:Memoization dbr:Parsing dbr:Regular_expression dbr:List_of_programming_languages_by_type dbr:Compiler_Description_Language dbr:Context-free_grammar dbr:OMeta dbr:Timeline_of_algorithms dbr:Moose_(analysis) dbr:Myth:_The_Fallen_Lords dbr:Context-free_language dbr:Dangling_else dbr:LL_parser dbr:Lojban dbr:Comparison_of_parser_generators dbr:Compiler-compiler dbr:Pack_rat_(disambiguation) dbr:Parser_Grammar_Engine dbr:Peg dbr:Backus–Naur_form dbr:Lojban_grammar dbr:ANTLR dbr:Amber_Smalltalk dbr:Parboiled_(Java) dbr:Parsing_Expression_Grammar dbr:Formal_grammar dbr:Recursive_descent_parser dbr:Syntactic_predicate dbr:Sweble dbr:Top-down_parsing dbr:Top-down_parsing_language dbr:PyPEG dbr:Raku_(programming_language) dbr:Rebol dbr:Packrat_parser dbr:Raku_rules dbr:PEG_parser dbr:Text_parsing dbr:Packrat_parsing dbr:Parsing_expression |
| is foaf:primaryTopic of | wikipedia-en:Parsing_expression_grammar |