LexとYacc

準備

Bisonと Flexのインストール, JFlexとjaccのインストール

コンパイラの概要

コンパイラは、いくつかのフェーズからなる

字句解析
構文解析
意味解析
中間コード生成
コード最適化（ターゲット非依存）
コード生成
コード最適化（ターゲット依存）

今回扱うのは、この中の字句解析（単語の切分け）と構文解析（木構造の構築）である。

正規表現

記号列（文字列）の集合を定義するための方法の一つである。字句解析に使用される。

正規表現の定義

A を想定する文字の集合とする

A の要素は、 A の上の正規表現である
空の記号列 ε は、 A の上の正規表現である
x, y が A の上の正規表現であるとき、
1. x y （x とy の連接）
2. x | y （x とy の選択）
3. x * （x の反復）
も A の上の正規表現である。

優先順位

反復、連接、選択の順に優先順位が高い。

つまり、ab*|cは (a(b*))|c と解釈される。これ以外の順に結合するには、(ab)*|cのように括弧を用いる。

省略記法

斜字体（例: x ）は、任意の正規表現、a～zは文字

x + ⇢ x x *（x の1回以上の反復）
x ? ⇢ x |ε（x の1回以下の出現）
[abc] ⇢ a|b|c
[a-z] ⇢ a|b|…|z

注意

正規表現は入れ子関係（例: 括弧の釣り合った文字列）は表現できない。（一方、BNFはできる。）

練習問題

C言語の変数として使える文字列を表す正規表現を書け。
C言語の整数リテラル・浮動小数点リテラルを表す正規表現を書け。
メールアドレスとなる可能性のある文字列・URLとなる可能性のある文字列を表す正規表現を書け。（完全でなくても良い。）
危険なパス（/から始まったり、..を含むパス）を表す正規表現を書け。

LexとJFlex

Flexの説明, JFlexの説明

BNF

Backus=Naur Form（バッカス=ナウア記法）のこと。やはり、記号列（文字列）の集合を定義するための方法の一つである。再帰的な定義が可能なため、正規表現より表現力が高い。構文解析に使用される。

BNFの説明

α β … α のあとに β を続ける記号列
α | β … α または β
A → α … 記号A は記号列 α というカタチからなる。（記号列 αは A を構成する。）

BNFの例

expr	→	expr `+` num
	`\|`	expr `-` num
	`\|`	num
num	→	`0\|1\|`…`\|9`

「1+2+3は expr である」ことを示すためには、

expr ⇒ expr + num ⇒ expr + 3 ⇒ expr + num + 3 ⇒ expr + 2 + 3 ⇒ num + 2 + 3 ⇒ 1 + 2 + 3

という列を示せば良い。

終端記号 … 実際にプログラム中に現れる記号（上の BNFでは、+, -, 0, …）
非終端記号 … →の左辺に現れる記号（上のBNFでは expr, num）、文法上の分類（式・文など）を表す
ε … 空の記号列を表す
生成規則 … 「非終端記号 → 記号（非終端・終端または ε）の列」の形のこと
開始記号 …BNFで最終的に表現したい非終端記号（特に断らない限り BNFの最初の非終端記号が開始記号）

解析木

導出列を木の形に表したものを解析木という。書換え規則の適用順の違いという本質的でない違いを無視することができる。

最右導出

最も右側に出現する非終端記号を選択して、書き換えていく導出列のこと。例えば、上の expr ⇒ … ⇒ 1 + 2 + 3 という導出列は最右導出である。一方、次の導出列は最右導出ではない。

expr ⇒ expr + num ⇒ expr + num + num ⇒ num + num + num ⇒ 1 + num + num ⇒ 1 + 2 + num ⇒ 1 + 2 + 3

この導出列は、最も左側に出現する非終端記号を選択して、書き換えているので、 最左導出という。

曖昧な文法

一つの記号列に対して 2つ以上の解析木が生成される可能性がある文法のこと。例えば次のような BNF で表現される文法は曖昧である。

expr	→	expr `+` expr
	`\|`	expr `-` expr
	`\|`	num
num	→	`0\|1\|`…`\|9`

例えば、1+3-2という記号列に対して、 2つの解析木を対応させることができる。

優先順位と結合性

曖昧な文法は、利用価値がないというわけではない。演算子の優先順位や結合性を指定して非曖昧にすることができる。

優先順位

例えば *,/は +,-より優先順位が高い、などという。このとき、1+2*3は 1+(2*3)と解釈される。

結合性

例えば +, -は左結合である、という風に使う。つまり、（同じ優先順位の演算子の中で）左側に現れた演算子が優先であり、 3-2-1 は 3-(2-1) ではなく、 (3-2)-1 と解釈される。

左結合の他に、右側に現れた演算子を優先する右結合、演算子が続けて現れると文法エラーと解釈する非結合がある。

上向き構文解析

解析木を下から上へ（枝から幹へ）という順で生成していく構文解析方法のことをいう。 Yacc, Bison, Jaccなどが採用しているのは上向き構文解析である。

BisonとJacc

シフト (shift) と還元 (reduce)

Bisonなどで生成した構文解析プログラムの動作の途中で、次の字句（単語）を読み込む動作をシフト、解析木の一部を生成する動作を還元という。

衝突 (conflict)

Bisonなどに与えた文法が曖昧だと、シフト／還元衝突 (shift/reduce conflict)、あるいは、還元／還元衝突 (reduce/reduce conflict) があると言って Bisonに怒られる。

適宜、演算子の優先順位や結合性を宣言して、曖昧さを解消する必要がある。

宣言してもシフト／還元衝突が解消しないときは、警告を出しつつ、 Bisonはシフトのほうを採用する。例えば、次のような BNF で起こり得る。

stmt	→	`if` `(` expr `)` stmt
	`\|`	`if` `(` expr `)` stmt `else` stmt
	`\|`	…

また、還元／還元衝突に関しては、Bisonは先に書かれている生成規則を優先する。例えば、次のような BNF で起こり得る。

E	→	E `^` E `_` E
	`\|`	E `^` E
	`\|`	E `_` E
	`\|`	id

練習問題

四則演算に次の演算子を追加した簡易電卓プログラムを作成せよ。
- 累乗を表す**演算子、または^演算子
  （右結合で *, / 演算子よりも優先度が高い。）
- ==, <, > などの比較演算子
  （非結合で +, - 演算子よりも優先度が低い。）
  注: jaccでは非結合の指定 (%nonassoc) にバグがあり、うまくいかない。ただ、jaccの生成する Javaのソースコードはわかりやすいので、生成された Javaのソースに手を入れて修正することは可能と思われる。（-vオプション、または -hオプションで得られるオートマトンの説明を参考にすると良い。）
プログラミング言語 PL/0の文法に対する構文解析プログラムを作成せよ。さらに C (または Java) へのトランスレーターを作成せよ

その他の構文解析法

手書きの構文解析プログラムに適した再帰下降（下向き）構文解析法（プログラム例）、四則演算の式くらいなら表を用いる単純な方法で構文解析できる演算子順位法（プログラム例）などがある。

Haskell や Scala などの関数型言語では、パーサーコンビネーター (parser combinator) という手法もよく用いられる。

Parsec (Haskell)
scala.util.parsing.combinator.Parsers (Scala)

リンク集

2011年度コンパイラ（香川大学工学部）
2011年度コンパイラ・データベース演習（香川大学工学部）

JFlex The Fast Scanner Generator for Java
lx A ECMAScript (JavaScript) based lex implementation
Ragel State Machine Compiler
re2c a tool for writing very fast and very flexible scanners
SilverCity a lexing package, based on Scintilla

jacc Java用のパーサジェネレータ LALR、文法が Yacc/Bisonに一番似ている。
JavaCC Java用のパーサジェネレータ（構文解析器生成系） LL(k)
JavaCUP Java用のパーサジェネレータ LALR
Lapg the combined lexical analyzer and parser generator (Java, Javascript, C, C++ and C#)
Gin JavaScriptで構文解析
Caper LALR(1)パーサジェネレータ (C++/JavaScript/C#/D)
BYACC/J a YACC for Java
SableCC parser generator which generates fully featured object-oriented frameworks for building compilers, interpreters and other text parsers LALR(1)
ANTLR LL(k) parser generator
GOLD LALR parser generator for ANSI C, Assembly - Intel x86, C#, C++, D, Delphi, F#, Java, Pascal, Python, Visual Basic, Visual Basic .NET,
JISON LALR(1) JavaScript Parser Generator
LPG LALR Parser Generator for Java, C++ or C.
notavaCC パーサ・ジェネレータ LALR
Coco/R LL(k) for C#, Java and C++
kmyacc Java, JavaScript,Perl対応 LALRパーサー生成系
Rats! extensible parser generator for Java (PEG)

Parsec a parser combinator library for Haskell
The Packrat Parsing an alternative to context free grammars for formally specifying syntax

C言語の構文解析 C言語の yacc/lexのソースなど
- YACC
- LEX

Koji Kagawa