コンパイラ入門
https://gyazo.com/ba70365530d1da870b3b1b4eb4fcfb29
学生時代のコンパイラの授業のきょうかしょ。
コンパイラの全体構造
コンパイラの世界にもフロントエンドとバックエンドが存在する。これは去年のYJITの話のときに出てきたと思う。
フロントエンド(解析)
字句解析
ソースプログラムの語彙単語を抽出する
構文解析
抽出された字句から構文構造を解析する
意味解析
構文構造からプラグラムの意味を解析する
バックエンド(合成)
コード最適化
コード生成
下向き構文解析法
LL(1) grammar
LL is Left to right, Leftmost derivation
左から右への最左導出
(1) は先読みに用いる終端記号が1こということ
上向き構文解析法
LLよりも扱える文法が広くて文法変換を必要としない
LRオートマトンとスタックを使って構文解析を実施するよ
LRオートマトンのスタックの最上部が構文規則と一致したときにスタックから最上部を取り除いて規則の左辺の非終端記号を入力記号列の先頭に付加する。これを還元という。
これはしおいさんの話でも出てきたね
還元の際に複数の還元さきがある場合は動作が不定となってしまう。これはオートマトンに「衝突がある」と呼ばれる。
これもどこかで話してたわ。「4つのdo」が衝突を避けるための解決策だったみたいな。
LR is Left to fight, Rightmost derivation 最右導出
LR(0)構文解析
たいしたことなし
SLR構文解析
そんなやつもいる
LR(1)構文解析
先読み記号を設けました。
Rubyはこれ
lex
字句解析するくんをつくるくん
記述としては以下のような感じ。
code:plain
宣言部
%%
正則表現部
%%
プログラム
定数宣言はyaccを使うなら勝手にそっちでやってくれる
yacc
文脈自由文法からLALR(1)構文解析するくんをつくるくん
記述としては以下の用な感じ
code:plain
宣言部
%%
構文規則部
%%
プログラム部
宣言部
変数関数マクロの宣言
yaccで宣言してればlexで定数宣言しなくていいよ
構文規則部
構文規則と還元の起きるときの意味処理をかくよ
X : a | b | c みたいな
X : a {} | b {} | c {} みたいにカッコの中で意味処理をかける
プログラム部
構文解析で使う補助関数をかく
yyerrorという関数で構文解析時のエラー表示を宣言する
yacc parse.y とかやると y.tab.c が生成される。このy.tab.cをCコンパイラでコンパイルすると実行ファイルが生成される。