括弧の入れ子を規則で表す
文脈自由文法とは、「これは何でできているか」を書き換え規則で表す文法です。括弧の入れ子のように、中にまた同じものが入る形まで表せます。
前のレッスンで、正規表現は括弧の数を比べられないと分かりました。この問題を解くのが、この文法です。プログラミング言語の文法も、これで書かれています。
このレッスンのゴール
メモ
文法の規則を使って、ある文字列が正しい形かどうか決められる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| 文法 | 正しい文字列の作り方を決める規則の集まり | |
| 生成規則 | 左の記号を右の並びに書き換える規則 | S → ( S ) S |
| 終端記号 | 書き換えられず、最後の文字列に残る記号 | ( |
| 非終端記号 | 書き換えられる記号。最後には残らない | S |
| 開始記号 | 書き換えを始める記号 | |
| 導出 | 開始記号から規則で文字列を作る手順 |
学生が入力するセルは、このプレビューでは空白です。
2つの規則で入れ子を作る
正しい括弧の列は、2つの規則で作れます。開始記号 S は、書き換えられる非終端記号です。
規則1は、S を何もない状態に書き換えます。規則2は、S を ( S ) S に書き換えます。括弧の組を1つ作り、中と後ろに、また S を置く規則です。
括弧の文法
| 規則 | 書き換え | 意味 |
|---|---|---|
| 1 | S → 空 | 何もない文字列 |
| 2 | S → ( S ) S | 括弧の組と、その中と後ろ |
学生が入力するセルは、このプレビューでは空白です。
(())() の導出
| 手順 | 今の文字列 | 使った規則 |
|---|---|---|
| 0 | S | 開始記号 |
| 1 | (S)S | 規則2 |
| 2 | ((S)S)S | 規則2（最初の S） |
| 3 | (()S)S | 規則1（内側の S） |
| 4 | (())S | 規則1 |
| 5 | (())(S)S | 規則2（最後の S） |
| 6 | (())()S | 規則1 |
| 7 | (())() | 規則1。完成 |
学生が入力するセルは、このプレビューでは空白です。
個数が同じでは足りない
括弧の個数が同じなら正しい、と考えたくなります。しかし、)( は個数が同じでも、正しい入れ子ではありません。
開き括弧は、閉じ括弧より先に来る必要があります。次のコードで、個数だけを比べる検査が、)( をどう扱うかを確かめましょう。
個数だけの検査
# 開き括弧と閉じ括弧の個数だけを比べる検査。
for text in ["(())()", "(()", ")("]:
equal = text.count("(") == text.count(")")
print(text, "個数が同じ:", equal)
# ")(" は、正しい入れ子でしょうか。考えてから実行しましょう。
よくある間違い
注意
開き括弧と閉じ括弧の数が同じなら、正しい括弧の列だと思いがちです。数が同じでも、順番が違えば正しくありません。)( や ([)] がその例です。順番と入れ子まで調べるには、文法の規則が要ります。
規則を逆向きに使うと検査になる
導出は、規則で文字列を大きくする手順でした。逆に、隣り合った () を消していけば、文字列を小さくできます。
最後に何も残らなければ、その文字列は文法から作れます。残れば作れません。ラボの端末で、この消す手順を1回ずつ表示します。
消す手順のファイルを作る
printf 'import sys\ntext = sys.argv[1]\nwhile "()" in text or "[]" in text:\n text = text.replace("()", "").replace("[]", "")\n print(repr(text))\nprint(text == "")\n' > reduce.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
正しい列を調べる
python3 reduce.py '(())()'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
交差した列を調べる
python3 reduce.py '([)]'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
閉じ忘れを調べる
python3 reduce.py '(()'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
さらに挑戦: a と b の個数
「a が n 個、そのあとに b が n 個」という文字列は、正規表現では書けません。文法なら、2つの規則で書けます。
S → a S b と S → ab です。aaabbb の導出を、手順の表にして書きましょう。何回目で規則2の代わりに規則1を使いますか。