前期試験 ・ 2016 年 7 月 29日 2 時限実施 ・ ページ
| 授業 科目 |
言語理論とコンパイラ | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
| 氏名 | ||||||||||||||||
| 担当者 | DÜRST, Martin J. | |||||||||||||||
次の英語の用語の (カタカナはできるだけ少ない) 日本語訳と説明を書きなさい。
Syntactic sugar: 糖衣構文; 本質てきな機能ではなく利便性のための構文
Concrete syntax tree: 解析木; 構文解析の途中経過など構文解析方法の研究・調査に使う木
Symbol table: 名前表; 関数・変数名などの名前、型、スコープなどを管理する表
Context-sensitive grammar: 文脈依存文法; 文脈依存言語を定義する文法
Portability: 移植性; ソフトウェアを他の機械に移植できる安易度
Chomsky hierarchy: チョムスキー階層; 形式言語理論での言語族の包囲階層
Relocatable program: 再配置可能プログラム; .obj ファイル等、再配置が可能な機械語のもの
Constant propagation: 定数伝播; 最適化で、(変数に代入された) 定数を追って、入れ換える
Mark and sweep: 印掃式; ゴミ集めの一つの方法で、印をつけて回収不可能なメモリを識別
Phrase structure language: 句構造言語; 一番自由度が多く、複雑な言語 (族) の種類
Data Flow Analysis: データフロー解析; 変数の代入から変数の使用への影響の分析
Lexical analyzer generator:
字句解析器生成系; flex 等、字句解析の作成を自動化する処理系
次の形式言語を受理する正規表現を作りなさい。使える記号は |, *,
(, ) と ? である。説明に書いた以外の記号は含まれない。
| 説明 | 正規表現 | |
|---|---|---|
| 例 | a 3個の語の集合 | aaa |
| b が奇数個の語の集合 | b(bb)* | |
| c が 4個以上で偶数個の語の集合 | cccc(cc)* | |
| x の数が5で割れる語の集合 | (xxxxx)* | |
| d が奇数個で e がゼロ個、又は e が偶数個で d がゼロ個の語の集合 | d(dd)*|(ee)* | |
| q の数が4で割って2か3になる語の集合 | (qqqq)*(qq|qqq) | |
| y が1個以上3個以下の語の集合 | yy?y? | |
| g が3個以上の後に h が偶数個の語の集合 | gggg*(hh)* | |
| s が偶数で u が一個だけの語の集合 | (ss)*(u|sus)(ss)* | |
| 初めは fh で、終わりが hf で、その間任意の数の f と h の語の集合 | fh(f|h)*hf | |
| p が偶数で q が任意の数の語の集合 | q*(pq*pq*)* | |
| r と t が任意の数で、t が二つ以上続かない語の集合 | (r|tr)*t? |
前期試験 ・ 2016 年 7 月 29日 2 時限実施 ・ ページ
下記左右の、整数の引き算に限定されたプログラムの一部に対し、 それぞれ対応する文法 (各 2 点) と文法・実装の問題点の説明 (各 3 点) を書きなさい。 右側の Number() は共通の関数である。字句解析や main 関数、グローバル変数の定義、エラー処理は省略されている。
int Number(void)
{
int result = next_token.value;
next_token = getNexToken();
return result;
}
| プログラムの一部 |
int Expression(void)
{
int result = Number();
if (next_token.type == MINUS) {
next_token = getNextToken();
result -= Expression();
}
return result;
}
|
int Expression(void)
{
int result = Expression();
if (next_token.type == MINUS) {
next_token = getNextToken();
result -= Number();
}
return result;
}
|
|---|---|---|
| 対応 する 文法 | Expression → Number MINUS Expression | Expression → Expression MINUS Number |
| 問題点の説明 | この Expression (式) 用の関数・文法は引き算を右結合の演算ととらえますが、実際は左結合であるべき。 例えば "9-5-3" の入力の場合、結果は 1 になる筈ですが、実際には 7 になってしまう。 | 文法では左側の右結合の問題が解決されていますが、実装の関数は最初のところすぐ再帰をして、 いわゆる「左再帰」で Stack Overflow などになり、失敗する。 これは下向き構文解析の典型的な問題。 |
|
上記の問題を解決し、さらに足し算 (使用記号 PLUS) も可能とする文法を書きなさい。(3 点) Expression → Number [(PLUS|MINUS) Number] 上記の文法で使った記述方法とその記号を説明しなさい。(3 点) [] は繰り返しを表していっる。() はグループを表している。| は選択肢を表している。記述方法は EBNF (Extended Backus-Naur Form) の一種。
再帰的下向き構文解析の不変条件として、必ず次のトークンが next_token にあるはず。その為、トークンを消化した後すぐ次のトークンをセットする必要がある。 |
上記の問題を解決し、さらに足し算も可能とするプログラムを書きなさい (記述方法が分からない部分は疑似コードでもよい)。(8 点)
int Expression(void)
{
int result = Number();
int type;
while ((type=next_token.type)==PLUS
|| type==MINUS) {
next_token = getNextToken();
if (type==PLUS)
result += Number();
else
result -= Number();
}
return result;
}
|
前期試験 ・ 2016 年 7 月 29日 2 時限実施 ・ ページ
| 授業 科目 |
言語理論とコンパイラ | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
| 氏名 | ||||||||||||||||
| 担当者 | DÜRST, Martin J. | |||||||||||||||
bison の処理内容 (20 点)次に bison -v で作成された .output
ファイルの一部 (一つの状態についての情報) を示す。
State 19
4 exp: exp PLUS term .
7 term: term . ASTERISK factor
8 | term . SLASH factor
ASTERISK shift, and go to state 16
SLASH shift, and go to state 17
$default reduce using rule 4 (exp)
上記の . (三ヶ所) の意味を説明しなさい。 (2 点)
. は解析の現在位置を表します。
上記の情報を題材にして、bison による優先度の処理を詳しく説明しなさい。(4 点)
現在の状態は、足し算 (PLUS) を見かけたところで、次に掛け算 (ASTERISK) や割り算 (SLASH) が来たら、それの優先度が高いために先に shift で処理して、それ以外のものが来たら、reduce で足し算を処理することとなっています。
引き算 (MINUS) も含め、exp と term の書換規則を完成しなさい。(4 点)
exp : exp PLUS term
| exp MINUS term
| term;
term : term ASTERISK factor
| term SLASH factor
| factor;
bison と対応する言語理論のオートマトンの相違点と共通点について考察し、説明しなさい。 (6 点)
対応するオートマトンはプッシュダウンオートマトン。プッシュダウンオートマトンではスタック記号だけをスタックに載せますが、
bison の場合、状態と (非) 終端記号です。しかし、bison の状態と (非) 終端記号の組に対応するスタック記号を導入すれば、
これはプッシュダウンオートマトンと同様だ。
更に、bison の shift はプッシュダウンオートマトンのプッシュに直接対応しますが、reduce は複数のスタック記号を一つに置き換えます。
しかし、reduce を、スタックから記号を取る複数の ε 遷移と新記号をスタックに乗せる一つの ε 遷移に置き換えると、ここもプッシュダウンスタックと同様である。
bison の入力に曖昧な文法を書くと、bison はどのように対応するか説明しなさい。(4 点)
曖昧な文法は bison で shift/reduce conflict 又は reduce/reduce conflict として報告される。 shift/reduce conflict の場合は shift が使用され、reduce/reduce conflict の場合は書き換え規則の順番による。
前期試験 ・ 2016 年 7 月 29日 2 時限実施 ・ ページ
超単純アセンブリ言語は次のような命令を持つ:
| 命令 | 被演算子 | 説明 (コメント) |
LOAD |
R1, a |
メモリの変数 a の値をレジスタ
R1 に代入 |
STORE |
a, R1 |
レジスタ R1 の値をメモリの変数
a に代入 |
CONST |
R1, 5 |
レジスタ R1 に定数 5 を代入 |
JUMP |
label |
無条件に label へジャンプ |
JUMP< |
R1, label |
レジスタ R1 の値が 0 より小さい時
label へジャンプ (同様に JUMP<=, JUMP==,
JUMP!=, JUMP>= と JUMP>
がある。) |
ADD |
R1, R2, R3 |
R2 と R3 を足して R1
に代入。同じレジスタを何回使ってもよい。
同様に SUB、MUL、DIV
がある。演算は全て整数のものです。それ以外の演算は使えない。 |
メモリのアドレスは変数名 (小文字) で表す。レジスタは
R1, R2,...
で表し、数は無制限。被演算子の順番は結果を一番左側に書く。
下記の左側の普通の C 言語のプログラム断片を制限された C 言語
(制御文は if と goto のみ、if
文の条件は 0 との比較のみ、if 文後は goto のみ)、最適化されてないアセンブリ、最適化されたアセンブリに変換しなさい。
| 普通の C 言語 | 生成されたコード (最適化無し、8 点) |
最適化されたコード (8 点) |
|---|---|---|
while (a<20 && b>=500)
b -= a++;
|
next: LOAD R1, a CONST R2, 20 SUB R1, R1, R2 JUMP>= R1, end LOAD R1, b CONST R2, 500 SUB R1, R1, R2 JUMP< R1, end LOAD R1, a LOAD R2, b SUB R2, R2, R1 STORE b, R2 CONST R1, 1 ADD R2, R2, R1 STORE a, R2 JUMP next end: |
LOAD R1, a LOAD R2, b CONST R3, 20 CONST R4, 500 CONST R5, 1 SUB R2, R2, R4 next: SUB R6, R1, R3 JUMP>= R6, end JUMP< R2, end SUB R2, R2, R1 ADD R1, R1, R5 JUMP next end: STORE a, R1 ADD R2, R2, R4 STORE b, R2 |
| 制限された C 言語 (6 点) | ||
next: if (a-20 >= 0)
goto end;
if (b-500 < 0)
goto end;
b -= a++;
goto next;
end:
|
この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)
@@@@
この授業で一番勉強になったことを書きなさい。 (決まった正解はありません。)
@@@@
前期試験 ・ 2016 年 7 月 29日 2 時限実施 ・ ページ
| 授業 科目 |
言語理論とコンパイラ | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
| 氏名 | ||||||||||||||||
| 担当者 | DÜRST, Martin J. | |||||||||||||||
エラー処理の難しさの原因を説明しなさい。(5 点)
要点は主に三つです： 1) 構文解析などに言語理論が使えるが、エラー処理について理論が少ない。 2) 正しいプログラムよろ、エラーを含むプログラムが、何でもありなので多い。 3) 機械に解析しやすいプログラム言語と人間に書きやすい言語、機械に分析しやすいエラーと人間にやりやすいエラーは違う。
bison でのエラー処理の機能について具体例を使って説明しなさい。(5 点)
文法の書換規則の右側に error という特別なトークンが使えます。
例えば statement : error SEMICOLON は、エラーが起きたら、次のセミコロンまで読んで、エラーメッセージを出力して、
読んだ部分を statement として扱います。それにより、この statement 内の二次エラーが防げるとともに、
次の文のエラーも検知できる。
次の有限オートマトンを線形文法に変更しなさい (ヒント: εは線形文法では使えません)。
S → eB | e | fC | fA
A → eD | e | gD | g
B → gA
C → eA
D → fD | f | hD | h | gC
| gA | hC | hA
上記の NFA を DFA に変更し、その状態遷移表を書きなさい (状態の書き替えは不要)。
| e | f | g | h | |
|---|---|---|---|---|
| →{S} | {B} | {A, C} | {} | {} |
| {B}* | {} | { } | {A} | {} |
| {A, C} | {A, D} | {} | {D} | {} |
| {A} | {D} | {} | {D} | {} |
| {A, D}* | {D} | {D} | {A, C, D} | {A, C, D} |
| {D} | {} | {D} | {A, C} | {A, C, D} |
| {A, C, D}* | {A, D} | {D} | {A, C, D} | {A, C, D} |
前期試験 ・ 2016 年 7 月 29日 2 時限実施 ・ ページ
左のチューリング機械の遷移表に相当する遷移図を右側に書きなさい。(6 点)
| 現状態 | 現記号 | 新記号 | 移動方向 | 新状態 |
|---|---|---|---|---|
| → 1 | a | b | L | 1 |
| → 1 | b | a | L | 1 |
| → 1 | ␣ | b | R | 2 |
| 2 | b | a | R | 2 |
| 2 | a | ␣ | R | 1 |
| 2 | ␣ | a | L | 1 |
[図省略]
上記の機械の ...␣aba␣... に対する動作を 8遷移分示しなさい。(6 点)
- _ _ _ a b a _ _ _ ↑1
- _ _ _ a b b _ _ _ ↑1
- _ _ _ a a b _ _ _ ↑1
- _ _ _ b a b _ _ _ ↑1
- _ _ b b a b _ _ _ ↑2
- _ _ b a a b _ _ _ ↑2
- _ _ b a _ b _ _ _ ↑1
- _ _ b a _ a _ _ _ ↑1
- _ _ b a b a _ _ _ ↑2
上記のチューリング機器は Wolfram の 2,3 チューリング機器と言われ、2007年に万能であると証明された。 万能チューリング機器の条件を説明しなさい。(5 点)
万能チューリング機器は、全てのチューリング機器をシムレートできるようなチューリング機器である。 シム―レートしたい機器の情報とシムレーションに必要な他の情報を全部適切な符号化でテープに記録して、操作する。
上記の機器を例に、万能性の意義と限界について述べなさい。(5 点)
万能性は「計算できることはなんでも計算できる」という意味でとらえられます。上記の例を見ると、 非常に単純な装置でも万能性が生まれるので、「なんでも計算できる」ということは決して珍しいものではない。 しかし、万能と言っても、上記の機器は現在のコンピュータに比べて、スピードが全く違うというところに限界がある。
前期試験 ・ 2016 年 7 月 29日 2 時限実施 ・ ページ
| 授業 科目 |
言語理論とコンパイラ | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
| 氏名 | ||||||||||||||||
| 担当者 | DÜRST, Martin J. | |||||||||||||||
論理的な正規表現と実用的な正規表現は色々な面で違う。実用的な正規表現にあるが、論理的な正規表現に無い機能を、論理的な正規表現でどの様に代用できるかを含め、三つ説明しなさい。 できるだけ異なる機能を選びなさい。(各 3 点)
. (ドット)： 任意の文字ひとつ。論理的な正規表現での書き方: (a|b|c|d|e|....)
文字クラス: [ABF-H] で多くの文字をコンパクトに表現。論理的： (A|B|F|G|H)
+: 一つ以上という意味。R+ は論理的に RR* と書けます。
論理的な正規表現にあるが、実用的な正規表現に無い唯一の機能とその理由と代用を説明しなさい (3 点)
ε (空語) である。ε は欧米のキーボードで書きにくいし、理解しにくい。? (有か無か) で代表する。
論理的な正規表現と実用的な正規表現の全体的な違いの理由について説明しなさい。(5 点)
理論の場合には証明などが大切で、証明をするためにできるだけ機能の数を少なくしたい。実際の文字も少なめで十分なので、メタ文字のエスケープも使いません。 実用的な正規表現は文字の数は (特に漢字などの場合) 非常に多く、沢山の文字を簡潔に指定できないと不便。繰返しの回数なども細かく指定できないと、コピペに手を出すことになってしまう。
実用的な正規表現には次の機能がある。最初の丸括弧で囲まれた正規表現の部分にマッチするものを正規表現の後半にもう一回マッチしてほしいところを \1 で示す。 例として、正規表現 (ab*c)de\1 は acdeac と abcdeabc と abbcdeabbc にはマッチするが、acdeabc とか abbcdeac などにはマッチしない。 この機能を論理的な正規表現で表現できる場合はその表現方法、できない場合はその理由を書きなさい。 (5 点)
この機能は論理的な正規表現で表現不可能です。なぜかというと、丸括弧の中の文字列 (今回は b の数だけでも) 記憶しないと、\1 で本当にあっているかどうかは判断できません。 しかし、論理的な正規表現を受理する有限オートマトンにはそのような機能や力は一切ありません。