情報工学実験 コンパイラ 演算子順位構文解析 (2013年度)

情報工学実験
コンパイラ
演算子順位構文解析
(2013年度)
内容
• BNFによる言語定義
• 表駆動型オートマトンによる字句解析
• 演算子順位構文解析
• 再帰下降型構文解析
• オブジェクトコード生成
– 本実験では CPU 実験で作成する CPU 用の
アセンブリ言語をオブジェクトコードとする
http://www.edu.cs.okayama-u.ac.jp
スケジュール
4/9
全体説明・言語定義説明
4/15
字句解析解説・実装
4/22,23
字句解析実装
4/30, 5/7 演算子順位構文解析説明・実装
5/8,13
演算子順位構文解析実装
5/14,20
演算子順位構文解析実装
5/21
再帰下降型構文解析説明・実装
5/27
再帰下降型構文解析実装
6/3,10,17 コード生成説明・実装
6/24
中間面接（コード生成）
7/1, 8
コード生成
7/22, 23, 29, 30 面接
構文解析手続き
• 上向き構文解析法
– 終端記号を非終端記号に還元
– 解析木を下から上に生成
• 下向き構文解析法
– 生成規則を使って左辺から右辺に変換
– 解析木を上から下に作成
解析木（構文木）
算術式
<算術式>::=<算術式><加減演算子><項> | <項>
<項>::=<項><乗除演算子><因子> | <因子>
<因子>::=<識別子> | (<算術式>)
<加減演算子>::= + | 項
<乗除演算子> ::= * | /
項
因子
算術式
算術式
項
項
因子
因子
因子
識別子
識別子
+
(
b
識別子
c
)
a
*
主な構文解析手法
1. 演算子順位構文解析
• 演算子順位文法にのみ適用可能
2. 再帰下降型構文解析
• 生成規則の左辺を右辺に変換する方法
3. LR 構文解析
• 解析手続きの自動生成に使用
算術式の解析
• 特徴： 算術式は左から解釈していくだけ
ではダメ
– 乗除算は加減算より優先される
– 括弧で優先順位が変わる
• 演算子順位構文解析を使う
（再帰下降型構文解析では無駄が多い）
演算子順位構文解析
• 演算子順位文法でなければ適用できない
• 演算子の優先順位を正しく扱うことが可能
• 算術式に対してのみ使われる
演算子順位文法
• 隣接した非終端記号を持たない
A ::= … B C …
という生成規則はない
ただし，A,B,C は非終端記号
• 終端記号間には <, >, = のうちたかだか１
個の関係しか成り立たない
演算子間の関係
• a = b
a と b が隣り合っているか，または一つの
非終端記号を挟む場合
例：
<因子> ::= ( <算術式> )
なので ( = )
演算子の関係
• a < b
a の右隣に非終端記号Aが現れ，Aが，最
初の終端記号がbである文字列を導出で
きる
例： <算術式> ::= <算術式> + <項>
<項> ::= <因子> * <項>
この場合 + < *
演算子の関係
• a > b
b の左隣に非終端記号Aが現れ，Aが，最
後の終端記号が a である文字列を導出で
きる
例： <因子> ::= ( <算術式> )
<算術式> ::= <算術式> + <項>
このとき + > )
演算子の関係（まとめ）
• a = b
A → …ab… または A → …aBb…
• a < b
B → …aA…という生成規則が存在し，
A → b… または A → Cb…
• a > b
B → …Ab…という生成規則が存在し，
A → …a または A → …aC
ただし，小文字は終端記号，大文字は非終端記号
算術式の始めと終わり
• 算術式は $ と $ で囲まれていると考える
• <算術式’> ::= $ <算術式> $
– 最初の $ は初期設定で積む
– 最後の $ は算術式の終わりであることがわ
かったら読み取ったことにする
演算子順位行列
• $ の順位も必要
• 本来は「数字」「識別子」にも順位は存在
（後で述べるアルゴリズムでは不要）
演算子順位法による構文解析手順
識別子・数値用の stack[0]
演算子用の stack[1]
• 識別子と数値は stack[0]に積む
• 演算子は
– stack[0]が空またはstack[1]の最上部よりこの
演算子の順位が高ければstack[1]に積む
– それ以外は木構造を作成（再帰的に処理）
ただし ( は破棄
構文木の形
B*C+D/E
四つ組による表現
(*, B, C, T1)
(/, D, E, T2)
(+, T1, T2, T3)
逆ポーランド記法による表現
日本語の語順と同じ
A + B → A B +
B * C + D / E → B C * D E / +
BにCをかけたものとDをEで割ったものを
加えたもの
演算子順位構文解析アルゴリズム
• ウェブページ参照
演算子順位表
• (A+B/C)*(D-E) の処理過程をホワイトボー
ドで説明
本日の作業内容
• 作業目標
– 各自で演算子順位アルゴリズムの演習問題を行い、
グループで答え合わせをすること
– 演算子順位行列の作成
– 構文木のデータ構造の決定
– push, pop, top 関数の作成
• 分担できる作業は分担して行うこと
• 作業報告書とともに演算子順位表を提出のこと
（最終レポートに入れてもらうので各自持っておく
こと）
• 演習問題の答えも提出のこと（手書き可）
作業内容の説明（１）
• 演算子順位行列の作成
ウェブを参照
oparser.cに入れる
• 演算子順位行列のための型定義
defin.hに入れる
• typeToOpeType
oparser.cに入れる
• 構文木のデータ構造
ウェブを参照
defin.hに入れる
作業内容の説明（2）
• 関数 push, pop, top
スタックに関する関数
２つのスタックを操作することに注意
各グループでスタックの実現については相
談して決めること
• これらの関数はoparser.cというファイルに
入れる
実験をすすめる上での注意
• 時間があればスタックを扱う関数が正しく
動くかどうかを確認すること