宿題：構文#

構文#宿題

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\ ) } \]

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

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

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

\[ \displaylines{ G=( & N &=& \{E, T\},\\ & \mathit{\Sigma} &=& \{0, 1\},\\ & P &=& \{\\ & & & \quad E \ra 0\ |\ 1\ |\ 0T0\ |\ 1T1, \\ & & & \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#

誤字#

• context free grammergrammar
• 自分自身を再帰的に呼び出す非終端記号\(E_1\)が～

thx

理解度の平均は3.2くらい#

こんなもんです．焦らなくて良いです．

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

じっくり資料を見返してください．

正規表現あたりがよくわからなかった#

それでOK．ほぼ解説していません．CF文法と拡張CF文法の違いが理解できればよいです．

• CF文法（とBNF）：正規表現の利用はNG
• 拡張CF文法（とEBNF）：正規表現の利用はOK

曖昧さの例としてif-else文を挙げたらよさそう#

確かに．来年はこういうクイズを出そうと思います．

if (0) if (1) printf("A"); else printf("B");

if (0)
    if (1) printf("A");
    else   printf("B");  // else文は直近のif文とくっつく

if (0)
    if (1) printf("A");
else       printf("B");  // else文は遠いif文とくっつく

ソースコードの読みやすさと行数の少なさどちらを優先するべきか？#

確実に読みやすさです．読みやすさが最優先です．他者が誤解しないような記述をすべきです．

横向きで描いている木を初めて見てびっくりした#

確かに．スペースの都合で横の木にしたが，文化的には縦が多い．混乱の元かも．来年考えます．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 20, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E];
  e1 --- e2[E];
  e1 --- times[#42;]:::tr;
  e1 --- e3[E];
  e2 --- lb["("]:::tr;
  e2 --- e4[E];
  e2 --- rb[")"]:::tr;
  e4 --- e5[E];
  e4 --- plus[#43;]:::tr;
  e4 --- e6[E];
  e5 --- num1[num]:::tr;
  e6 --- num2[num]:::tr;
  e3 --- num3[num]:::tr;

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 20, 'rankSpacing': 20, 'padding': 5}}}%%
graph TD
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E];
  e1 --- e2[E];
  e1 --- times[#42;]:::tr;
  e1 --- e3[E];
  e2 --- lb["("]:::tr;
  e2 --- e4[E];
  e2 --- rb[")"]:::tr;
  e4 --- e5[E];
  e4 --- plus[#43;]:::tr;
  e4 --- e6[E];
  e5 --- num1[num]:::tr;
  e6 --- num2[num]:::tr;
  e3 --- num3[num]:::tr;

解析木は文の生成手順を左から右に向かって表していると解釈した#

yes

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

良い質問．👍👍👍

構文の解析方法（コンパイル方法）を勉強するとCF文法の便利さがよくわかります．また曖昧さの問題点もより直感的に理解できます．実際に解析プログラムを作ると如実に困ります．

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

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

良い質問．👍👍👍

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

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

ウィンドウの最前面の固定方法は？#

"Always on top"という機能です．実はWindowsには相当の機能がありますが，UIが提供されていません．PowerToys等で利用できます．

院試を1ヶ月で勉強していることに驚いた#

参考程度に考えてください．彼らは優秀です．

情報科学研究科の再編による教員の利点・欠点はあるのか？#

（略）

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

良い質問．👍👍👍

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

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

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

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

具体的にどのような研究をしているのか？#

ソフトウェアを「うまく早く安く」作るための研究をしています．https://sdl.ist.osaka-u.ac.jp/

試験の実施方法を更新しました#

講義の概要#試験