Conversation

Notices

Embed this notice
Masanori Ogino 𓀁 (omasanori@mstdn.maud.io)'s status on Monday, 05-Jun-2023 13:10:23 JST Masanori Ogino 𓀁

CFGとPEGのどちらかがもう片方の部分集合というわけではないのではないか（共通部分とそれぞれ片方でしか書けない文法があるのではないか）と言われてはいるけれど、それが証明されたという話はまだ聞いてない

In conversation Monday, 05-Jun-2023 13:10:23 JST from mstdn.maud.io permalink
- Embed this notice
  斎藤ただし (tadd@best-friends.chat)'s status on Monday, 05-Jun-2023 16:47:54 JST 斎藤ただし
  in reply to
  
  @omasanori 「片方でしか書けない文法」については15年くらい前に聞いたことがあります。この例の末尾にあるやつで
  、 "non-context-free language" と明記されてるので、PEGがCFGをはみ出てる例、ということになるのだと思います。
  https://en.m.wikipedia.org/wiki/Parsing_expression_grammar#Examples
  個人的には、この証明が長年議論になるほどに難しいとは思えないのですが、しかしたしかに、きちんと証明して論文になってる、みたいなのは自分もあんまり聞いたことはないです。実際は難しいのかもしれません。
  （何より自分、この辺はとても苦手です……）
  In conversation Monday, 05-Jun-2023 16:47:54 JST permalink
  Attachments
  1. Domain not in remote thumbnail source whitelist: login.wikimedia.org
    
    Parsing expression grammar
    
    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; a string has exactly one valid parse tree or none. 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. Definition Syntax...
- Embed this notice
  Masanori Ogino 𓀁 (omasanori@mstdn.maud.io)'s status on Monday, 05-Jun-2023 16:47:54 JST Masanori Ogino 𓀁
  in reply to
  - 斎藤ただし
  @tadd ありがとうございます
  
  In conversation Monday, 05-Jun-2023 16:47:54 JST permalink

Public

Conversation

Notices

Feeds