1998年度「プログラミング言語論」期末試験 1999年 1月 27日実施

  1. 次の言葉の中からひとつ選んで簡単に説明せよ。
  2. 以下の、2進数字`0'と`1'を並べた2進数で 3の倍数になるものを生成するCFG を用いて、10101(2)( = 21(10)) を導出せよ。
    Σ = {0,1};
    VN = V - Σ
    = {M, M0, M1, M2 };
    P = {M → 0,
    M → M0, M1 → 1,
    M0 → M11, M0 → M00,
    M1 → M01, M1 → M20,
    M2 → M10, M2 → M21 };
    S = M
  3. コンパイラー(編訳系)の処理相を列挙し、それぞれの役割を 簡単に説明せよ。
  4. 次の空欄に適当な語句を入れよ。 構文解析には、大きく分けて、構文木を根から葉に向かって構成していく (1)____________ と葉から根に向かう (2)____________ とがある。 (1)は構文規則に従って 導出 によって入力された素語列に至ろうとするもので、一般には 再帰的手法が必要とされる。この再帰的解析は、関数の (3)_____________ ができる言語を用いてプログラミングすることで実現することもできるが、 (4)_____________ の状態遷移を表で与えることでも可能である。 また、(2)では素語を読み込みながら構文規則に従って (5)____________ をおこなう。 この場合にも、スタックと状態遷移表を用いた (4) での解析方法が一般的である。

解答例

  1. 省略
  2. M => M0 => M11 => M201 => M2101 => M10101 => 10101
  3. 語句解析
    プログラムの文字列がキーワード、変数・関数名などに適合するかチェックし、素語(token)列として次の処理相へ渡す。
    構文解析
    素語列が構文規則に合っているかをチェックする。
    意味解析
    変数・関数の型や範囲など文法の意味論的チェックをおこなう。
    コード生成
    機械語など目的言語によるオブジェクトコードを作る。最適化処理も含まれる。