# 青山学院大学

 授業 科目 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ ガナ 評点 氏名 担当者 DÜRST, Martin J.

## 正規表現と有限オートマトンの作成Creation of regular expressions and finite automata (21 点)

For each of the languages with the following conditions, write the corresponding regular expression and the transition diagram of the finite automaton that accepts this language (the alphabet in each case is limited to the letters appearing in the description, the transition diagram should be as simple as possible)

 q が基奇数個 / an odd number of qs f で始まり、g で終わり、その間二つ以下の xstart with f, end with g, with two or less x in between ``` q(qq)* ``` ```fx?x?g ``` p の数が四で割った場合のあまりが三 / the reminder of the number of ps when divided by four is three s の数が最低二つ、t の数が最低一つat least two ses, at least one t ```ppp(pppp)* ``` ```(t+s+t*s|st+s|ss+t)(s|t)* ```

## 文法から決定性オートマトンへ From Grammar to Deterministic Automaton (合計 26 点)

ヒント： 受理専用の新状態 F を導入する / Hint: Introduce a new state F for acceptance only.

```S → xA | yB
A → zS | z | εB
B → xC | zC
C → yA | yB | zC | x```

 x y z →{S} {A, B} {B} {A, B} {C} {S, C, F} {B} {C} {C} {C} {F} {A, B} {C} *{S, C, F} {A, B, F} {A, B} {C} *{F} *{A, B, F} {C} {S, C, F}

Explain the purpose of the conversion to a deterministic automaton (3 点)

The grammar at the top of the page contains an ε, but right linear grammars do not allow that. Devise and explain a method to remove ε from such grammars, and give the resulting grammar (7 点)

# 青山学院大学

 授業 科目 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ ガナ 評点 氏名 担当者 DÜRST, Martin J.

## 構文解析の仕組み / How Parsing Works (24 点)

The figure below shows 10 stages of parsing some input.

```  Exp  → Term | Exp + Term;
Term → num | Term * num
```

Expand the grammar above to deal with '-' and '/', as well as '(' and ')', in their usual meaning (6 点)

```  Exp  → Term | Exp + Term | Exp - Term
Term → Fac | Term * Fac | Term / Fac
Fac → num | ( Exp )
```

Give the name of the general parsing method used above and the name of a tool used for this method (2 点)

そのツールの場合、図の 3→4、4→5、6→7、7→8 のそれぞれの移行に使われている操作の名前と説明を書きなさい / Give the name of, and explain, the operation in the transitions 3→4, 4→5, 6→7, and 7→8 above (3 点)

shift; 入力の終端記号を関連する状態とともにスタックに積み

Same as above for transitions such as 2→3 and 8→9 (3 点)

reduce; 複数の (非) 終端記号を、文法の書換規則と逆に、一つの非終端記号にまとめる

「導出」で図の段階の順番を説明しなさい / Explain the order of the stages above using "derivation" (3 点)

## コード生成と最適化 (合計 24 点)

Very simple assembly language uses the following instructions (caution: differences to version used in lecture):

`LOAD` `R1, a` メモリの変数 `a` の値をレジスタ `R1` に代入 / load value from variable `a` into register `R1`
`STORE` `a, R1` レジスタ `R1` の値をメモリの変数 `a` に代入 / store the value in `R1` to variable `a`
`CONST` `R1, 5` レジスタ `R1` に定数 `5` を代入 / `R1`, `5` / set register `R1` to `5`
`JUMP` `label` 無条件に `label` へジャンプ / Unconditional jump to instruction at label `target`
`JUMP<` `R1, label` レジスタ `R1` の値が `0` より小さい時 `label` へジャンプ (`JUMP>=``JUMP!=` なども使用可能) / Jump to `target` if `R1` is <0. Otherwise, continue to next instruction (`JUMP>=`, `JUMP!=`, ... also available)
`ADD` `R1, R2, R3` `R2``R3` を足して `R1` に代入。同じレジスタを何回使ってもよい。 同様に `SUB``SHL` (<<)、`SHR` (>>)、`AND` (&) もある。 / Add `R2` and `R3` and put the result into `R1`. The same register can be used two or three times. `SUB`, `SHL` (<<), `SHR` (>>), and `AND` (&) are also available.

メモリのアドレスは変数名 (小文字) で表す。レジスタは `R1`, `R2`,... で表し、数は無制限。被演算子の順番は結果を一番左側に書く。 / Memory addresses are expressed as variable names (lower case). Registers are expressed as `R1`, `R2`,... The number of registers is not limited.

この機械には掛け算の命令がないので、下記の左側の普通の C 言語のプログラム断片は `m``n` の積を `t` に残す。これを制限された C 言語 (制御文は `if``goto` のみ、`if` 文の条件は 0 との比較のみ、`if` 文後は `goto` のみ)、最適化されてないアセンブリ、最適化されたアセンブリに変換しなさい。
Because this machine does not have a multiplication instruction, the plain C code below leaves the product of `m` and `n` in `t`. Convert this code to restricted C (control statements limited to `if` and `goto`, conditions in `if` restricted to comparison with 0, `if` statement takes only `goto`), non-optimized assembly, and optimized assembly.

Generated code (no optimization)

Generated code (continued)
```t = 0;
while (m > 0) {
if (m & 1)
t += n;
m >>= 1;
n <<= 1;
}
```
```    CONST R1, 0
STORE  t, R1
JUMP<= R1, e1
CONST  R2, 1
JUMP== R1, f1
STORE  t, R1
CONST  R2, 1
SHR    R1, R1, R2
STORE  m, R1
CONST  R2, 1
SHL    R1, R1, R2
STORE  n, R1

```
```    JUMP   n1
e1:```

Optimized code (8 点)

Restricted C (6 点)
```    CONST  R1, 1
CONST  R2, 0; t
n1: JUMP<= R3, e1
AND    R5, R3, R1
JUMP== R5, f1
f1: SHR    R3, R3, R1
SHL    R4, R4, R1
JUMP   n1
e1: STORE  t, R2
STORE  m, R3
STORE  n, R4
```
```    t = 0;
n1: if (m <= 0)
goto e1;
if (m&1 == 0)
goto f1;
t += n;
f1: m >>= 1;
n <<= 1;
goto n1;
e1:
```

# 青山学院大学

 授業 科目 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ ガナ 評点 氏名 担当者 DÜRST, Martin J.

## 形式言語の分類 (合計 24 点)

オートマトンを使って、ある語がある言語に属するかどうか (受理できるかどうか) を判断できる。

Using a concrete example, explain why the last two rows of the table differ. (3 点)

Using a concrete example, explain where and how the things lumped into a single row in the table can be split further. (3 点)

プッシュダウンオートマトンで決定性なものより非決定性なものの受理能力が高いことによって、二行に小分けできるはず。

## 授業へのコメント / Comment on Course (6 点)

この授業で一番分かりにくかったことを書きなさい (決まった正解はありません)
What was most difficult to understand in this course (there is no single answer)

@@@@

この授業で一番勉強になったことを書きなさい (決まった正解はありません)
What was most informative/interesting in this course (there is no single answer)

@@@@

```
```

## 字句解析と構文解析の比較 / Lexical Analysis and Parsing (合計 12 点)

字句解析 / Lexical Analysis 構文解析 / Parsing 定数、識別子、予約語、演算子など 式、文、関数など 速さ 能力

# 青山学院大学

 授業 科目 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ ガナ 評点 氏名 担当者 DÜRST, Martin J.

## 形式言語の演算 / Operations on Formal Languages (10 点)

Explain the five operations on formal languages that were discussed in the course. For binary operations, give the result of using X and Y as operands. For unary operations, give the result of using Z as operand. If the result is of infinite size, list the five firsteight smallest words.
X={ab, bc}, Y={bc, cd}, Z={a, b, ac}

クリーン閉包; {ε, a, b, aa, ab, ac, ba, bb}

## 英語の用語 / English Terms (24 点)

Provide Japanese translations (avoiding Katakana where possible) and explanations of the following English terms

Attribute grammar: 属性文法; 文法の書換規則とともに(非)終端記号の属性も書替える仕組み

Virtual machine: 仮想計算機; 移植性向上などのための仮想的な計算機

Start symbol: 初期記号; 文法の導出を開始する非終端記号

Type inference: 型推論; 変数などの型をプログラムの分析などによって導き出す

Panic Mode: エラー処理の一つで、文法に合うトークンを見つけるまでにトークンを捨てる

Control Flow Analysis: 制御フロー解析; プログラムを基本ブロックに分けてその流れの解析

Parser generator: 構文解析器生成系; bison みたいに構文解析器を自動生成するツール

Relocatable program: 再配置可能プログラム; .obj ファイル等、再配置が可能な機械語のもの

Ambiguous grammar: 曖昧な文法; ある入力に対して複数の解析木を許す文法

Universal Turing machine: 万能チューリング機械; 可能な計算を何でもできるチューリング機械

Recursive descent parsing: 再帰的下向き構文解析; 各非終端記号に関数を用意する解析方法

Constant Folding: 静式評価; プログラム内の定数だけからなる式のコンパイル時の評価