2

Stackoverflow で「HTML を Regex で解析するにはどうすればよいですか」という質問を無数に読んだ後、私は再び文法に興味を持ち、大学のスクリプトを手に取り、数分後にはどうやって試験に合格したのか疑問に思いました。

単純な (まあ、「単純な」と思っていた) 演習として、有効な python タプルを生成する CFG を作成しようとしました (簡単にするために、識別子aとのみを使用bしますc)。しばらくして、私はこれを思いつきました：

G = ( {Tuple, TupleItem, Id}, {“a”, “b”, “c”, “,”, “(“, “)”}, P, Tuple)

Pであること：

Tuple → “(“ TupleItem “)”
Tuple → “(“ TupleItem Id “)”
Tuple → “(“ TupleItem Tuple “)”
TupleItem → TupleItem TupleItem
TupleItem → Id “,”
TupleItem → Tuple “,”
Id → “a”
Id → “b”
Id → “c”

この文法は、例えば(a,), (a,b), (a,b,),を生成するはずですが((a,),)、,などは生成しません。 orのような余分な括弧を生成したくありません。実際には、オプション (複数のアイテムの場合) と必須 (アイテムが 1 つだけの場合) の場合があり、末尾のコンマはほとんど私を殺しました。((a,b,),(a,),)(,a)(),(a,b c)((a),)((a,b))

  1. この文法はすべての有効な python タプルを生成しますか ( と のみを使用a) ?bc
  2. この文法は、有効な Python タプルではない文字列を生成しますか?
  3. この文法は正しいですか？（循環基準についてはよくわかりません）
  4. なぜ私の文法はこんなに長いのですか？生産ルールの数を減らすにはどうすればよいですか? (パイプのようなシンタックス シュガーを使用するのではなく、1 行に複数のルールを配置するだけです。)

コメントと回答をお寄せいただきありがとうございます。

4

1 に答える 1

2

実際に Python の文法を参照しなくても、あなたの文法は 1 つの ( ()、空のタプル) を除いてすべての有効な Python タプルを生成し、Python タプル以外のものは何も生成しないと確信しています。だから、その程度でいいんです。

ただし、解析にはあまり役に立ちません。

TupleItem → TupleItem TupleItem

指数関数的にあいまいです。(ちなみに、TupleItem は、この非終端記号を表す名前ではなく、実際にはリストです。) あいまいな文法は、文脈自由文法のすべての規則に従うという意味で「適切」ですが、明確な文法です。通常はより優れています。

修正は簡単です：

Tuple → “(“ “)”
Tuple → “(“ ItemList “,” “)”
Tuple → “(“ ItemList “,” Item “)”
ItemList → Item
ItemList → ItemList “,” Item
Item → Id
Item → Tuple

(私はIdプロダクションを省略しました。実用的な文法でIdは、ターミナルになりますが、ほとんど違いはありません。)

最後に、なぜこの文法は「とても長い」のでしょうか? （7つのプロダクションは本当に「そんなに長いですか？」? あなたの基準次第だと思います。）

簡単な答えは、CFG がそのようなものだということです。シンタックス シュガーを追加して、右辺を正規表現にすることができます (代替だけでなく、Kleene スターとそのコンパニオンも):

Tuple → “(“ [ ItemList “,” Item? ]? “)”
ItemList → Item // “,”
Item → Id | Tuple

ここでは、有用な補間演算子を使用しています//。これは、学術的な授業ではめったに教えられないため、驚くほど実装が少ないものです。

a // b =def a(ba)*

上記の方が読みやすいかどうかは、読者にお任せします。これは、文法の説明、特に RFC で一般的に使用される EBNF (Extended Backus-Naur Form) に似ています。(EBNF は、補間演算子を使用する数少ない形式の 1 つですが、私のものほど明示的には書かれていません。)

とにかく、それ以外は、あなたの文法を整えることができるとは思いません.

于 2013-09-14T15:44:45.373 に答える