コンテンツにスキップ

宿題：構文#

構文#宿題

Homework 約30分 答え

2種類の文字0と1のみで構成される言語を生成するCF文法を答えよ．ただし先頭と末尾は同じ文字とする．

  • OK：0 1 00 11 101 01011110
  • NG： 01 10 11100 0001011001

以下の書式をコピーして回答せよ．\(\Sigma\)はZで代用している．\(\varepsilon\)遷移にはeという文字を使うと良い．

G = (
  N = {???},
  Z = {0,1},
  P = {???},
  S = ???
)

回答フォーム

Answer

\[ \displaylines{ G=( & N &=& \{E, T\},\\ & \mathit{\Sigma} &=& \{0, 1\},\\ & P &=& \{\\ & & & \quad E \ra 0\ |\ 1\ |\ 0T0\ |\ 1T1,\ & // \ \textsf{先頭と末尾の制御}\\ & & & \quad T \ra 0T\ |\ 1T\ |\ \varepsilon & // \ \textsf{0と1の任意の文字列}\\ & & & \},\\ & S &=& E\ ) } \]

生成規則を無機質な規則の集合と捉えずに，個々の規則に意味を見出すと良い．上記の場合は以下のように捉えると良い．

  • \(E\)：先頭と末尾の文字が同一な終端記号列を生成する規則
  • \(T\)：0と1の任意の終端記号列を生成する規則

拡張CF文法では以下のとおり．

\[ \displaylines{ G=( & N &=& \{E, T\},\\ & \mathit{\Sigma} &=& \{0, 1\},\\ & P &=& \{\\ & & & \quad E \ra 0 (T0)? \ |\ 1 (T1)?, \\ & & & \quad T \ra (0\ |\ 1)* & // \ \textsf{正規表現で書き換え}\\ & & & \},\\ & S &=& E\ ) } \]

構文図式ではこのように書ける．

別解：

\[ \displaylines{ P = &\{ \\ & E \ra 0\ |\ 1\ |\ 0T0\ |\ 1T1, & // \textsf{先頭と末尾の制御}\\ & T \ra 0\ |\ 1\ |\ TT\ |\ \varepsilon & // \textsf{0と1の任意の文字列}\\ \} } \]

ただし別解は曖昧な文法である．言語111に対する導出列（解析木）は2つ存在する．\(T\)の中の\(TT\)という規則が曖昧さの原因である．

Q&A#

誤字#

  • CF文法は G = {N, Σ, P, S} G = (N, Σ, P, S) の4つ組で定義される．
  • a(/a)*は y a a/a a/a/a/a/a
  • ちなみに ほ 実際のCPUでもレジスタは数個です．（宿題解説ページ）

thx

難しかった等#

焦らなくて良いです．試験までにじっくり資料を見返してください．絶対に理解できます．

可能な限り分かりやすい説明を試みるが，理論の講義であるため抽象的で捉えにくい部分もある．自発的な学習が必須である点を認識しておくこと．

なお形式的定義の部分はただの表現方法の定義です．ルールを決めているだけなので，その意義を深く考える必要はありません．形式言語（formal language）と呼ばれる分野で広く用いられる表現の定義です．

宿題のコメントに対するフィードバック#

宿題のコメントは全部読んでいます．授業への参加姿勢として加点しています．点が欲しい人は加点したくなるようなコメントを考えてみて下さい．

加点したくなるコメント

  • 拾いたくなる質問
  • 自身が理解できたことを示す深い考察
  • 経験との照らし合わせ
  • 具体性のある改善案

加点にしにくいコメント

  • 漠然とした感想（面白かった・わかりやすかった等）
  • 愚痴（プログラミングは嫌いです等）

CF文法をどうプログラムで解析しているのか？#

良い質問．👍👍👍

構文の解析方法（コンパイル方法）を勉強するとCF文法の便利さがよくわかります．CF文法の非終端記号一つ一つが関数に変換できます．再帰下降構文解析と呼びます．例えば次のような代入文の生成規則に対して；

\[ S \ra id = E_1 \]

次のような解析プログラムを書きます．

非終端記号Sの解析メソッド
def parse_S():   # 非終端記号Sは次のように定義・解析する
    expect('id')   # まずはidという文字のはず（さもなくば構文エラー）
    expect('=')    # 次は=という文字のはず（さもなくば構文エラー）
    parse_E1()     # 次はE1の定義・解析に飛ぶ

また曖昧さの問題点もより直感的に理解できます．曖昧さがあると実際に解析プログラムを作ると如実に困ります．

コンパイル方法はこの講義では扱いませんが，その理論と実践を3年後期の「言語処理工学」と「情報科学演習D」で扱います．

文法が無曖昧かどうかを判定する方法はあるか？#

良い質問．👍👍👍

判定方法はありません．これは計算理論の有名な問題「計算の停止性問題」と関係しています．停止性問題は（たぶん）3年前期の「計算理論」で扱います．

ただし無曖昧であることが確実な文法は存在します．ある文法がLL文法やLR文法であるなら，それは無曖昧です．ある文法がLL文法やLR文法に従っていないときに，それが無曖昧かはわかりません．LL文法は無曖昧の十分条件だが必要条件ではありません．

なぜ文脈「自由」と呼ぶのか？CF文法以外の文法は存在するのか？#

良い質問．👍👍👍

以下の言語を考えてみる．

\[ L(G) = \{ a^n b^n c^n|n \geq 0 \} \]

この言語を生成するCF文法は存在しない．CF文法の各非終端記号においては，その部分部分は独立である．例えば生成規則\(A \ra BC\)があったときに，非終端記号\(B\)から生成される記号列と，\(C\)から生成される記号列は一切の依存関係を持たない．この依存関係のなさが文脈「自由」と呼ばれる所以である．

より実践的なケースとしては，プログラム文中での変数名の重複宣言のチェックが挙げられる．CF文法は文脈「自由」であるため宣言された変数名を記憶しておくことはできない．つまりCF文法の構文規則の範疇では重複チェックは不可能である．

一般的に，変数名の重複確認はCF文法による解析とは独立にチェック処理が施される．

形式的表現の\(\{\}\)と\(()\)の違いは？#

\(\{\}\)は集合，\(()\)はタプルと呼ばれます（数学の文脈です）．集合は順序を区別せず，タプルは区別するという違いがあります．

\[ \begin{gathered} \{1, 2, 3\} = \{3, 2, 1\} \\ (1, 2, 3) \neq (3, 2, 1) \end{gathered} \]

EBNFの存在意義は？#

バッカスナウア方式（BNF）と拡張バッカスナウア方式（EBNF）がありましたが，BNFだけですべての構文が表せるように感じました．そうするとEBNFの存在意義って何なのでしょうか．

確かにBNFとEBNFの記述能力は完全に等価です．

EBNFの存在意義は簡単に書けて読みやすい，これに尽きます．正規表現を用いることで，繰り返しや省略可能性（\(\varepsilon\)遷移）をうまく記述できます．正規表現は開発者の中での一種の共通言語だと考えるとよいです．

ε遷移の厳密な定義が知りたい#

イプシロン遷移とは、非終端記号を全て空文字に導出する構文規則を指すのでしょうか、それとも定義に空文字が含まれている構文規則全てを指すのでしょうか。

次のような質問だと解釈しました．

  • これは\(\varepsilon\)遷移か？ \(A \ra \varepsilon\)
  • これも\(\varepsilon\)遷移か？ \(B \ra 0 \ |\ \varepsilon\)

CF文法の中では，\(A\)のような生成規則の右辺全体が空文字である規則を\(\varepsilon\)遷移と呼びます．\(B\)は該当しません．より正確には\(A\)は \(\varepsilon\)生成規則 （\(\varepsilon\)-production）と呼びます．

来年は資料を直そうかと思います．遷移という言葉を使うべきではありませんでした．

冪乗の↑はもしかしてクヌースの矢印表記ですか？#

Yes

if文と三項演算子は等価か？#

if文を無理やり式にしたものがC++にある三項演算子という認識でしょうか？

おおむね正しいですが，無理やりというわけではないです．次のようなif文はよくあります．

if (flag) a = 4;
else      a = 7;

三項演算子はこれを一つの式として記述できます．

a = flag ? 4 : 7;

Pythonでは条件式という文法規則があります．英語としても自然ですね．

a = 4 if flag else 7

i, j, kのような変数名は常に避けた方が良いですか#

ijkは許されます．今日の講義で軽く説明します．

非終端記号のラベルは自由か？#

繰り返しカウンタにおけるi,jのように、非終端記号はEやSを使うことが多いというだけで、文字自体はほかのものでもいいんでしょうか？

自由です．慣習として大文字を使うことが多いようです．

宿題のなりすまし対策#

解答を自身のメールアドレスに再送するか選択できるようにすれば（「回答のコピーを送信」），悪意のあるなりすましと，自身の解答確認ができるようになるかと思います．

Google Formにはそういう機能がたぶんありません．再送するかフォーム回答者が選ぶ方法がありません．理想はこうです．良いやり方があったら教えてください．

  • 学生の入力は少ないほどよい
  • Googleアカウントの強制入力は避けたい（個人情報の入力を必須にしたくない）
  • CLEはゆるさない