■四則演算式の文法と解析
2005年10月4日 21:19 更新
1. 文法の記述
「整数リテラル同士の加減乗除算（括弧あり）」の四則演算式を表す文法を記述する。
演算の評価の優先順位は、括弧 > '*','/' > '+','-' でなければならない。
ボトムアップ型構文解析のため、この逆の親子関係で生成規則を記述する。
A. 四則演算式の文法
終端記号 '+' '-' '*' '/' '(' ')' Num
非終端記号 Expr Term Factor
開始記号 Expr生成規則：
(1) Expr → Expr '+' Term
(2) Expr → Expr '-' Term
(3) Expr → Term
(4) Term → Term '*' Factor
(5) Term → Term '/' Factor
(6) Term → Factor
(7) Factor → '(' Expr ')'
(8) Factor → Num
B. 上記の文法が受理する入力列の例（ $ は入力終端を表す[EOF]と同じ）
Num '/' Num '-' Num $
'(' Num '+' Num ')' '/' Num $
Num '/' Num '-' Num '*' Num $ など
2. 構文解析
2.1 LR解析表
文法（1.A）四則演算式 のLR解析表を、表3.1に示す。
表3.1: 文法（1.A）四則演算式 のLR解析表
------------------------------------------------------------------
STATE action next state
Num + - * / ( ) $ Expr Term Factor
------------------------------------------------------------------
0 S5 S4 1 2 3
1 S6 S7 受理
2 R3 R3 S8 S9 R3 R3
3 R6 R6 R6 R6 R6 R6
4 S5 S4 10 2 3
5 R8 R8 R8 R8 R8 R8
6 S5 S4 11 3
7 S5 S4 12 3
8 S5 S4 13
9 S5 S4 14
10 S6 S7 S15
11 R1 R1 S8 S9 R1 R1
12 R2 R2 S8 S9 R2 R2
13 R4 R4 R4 R4 R4 R4
14 R5 R5 R5 R5 R5 R5
15 R7 R7 R7 R7 R7 R7
-------------------------------------------------------------------
|
2.2 LR表を用いた解析例
入力 ( Num + Num ) / Num $ に対する解析例を、表2.2に示す。
ここで、非終端記号は、E:Expr, T:Term, F:Factor のように１文字に簡略して表記した。
表3.2: 入力 ( Num + Num ) / Num $ に対する解析例
---------------------------------------------------------------------
STEP stack(--->head) <--- token input --SR-- output(node)
---------------------------------------------------------------------
(1) 0 ( Num + Num ) / Num $
(2) 0 ( 4 Num + Num ) / Num $ --S4--
(3) 0 ( 4 Num 5 + Num ) / Num $ --S5--
(4) 0 ( 4 F 3 + Num ) / Num $ --R8-- Num <- F
(5) 0 ( 4 T 2 + Num ) / Num $ --R6-- F <- T
(6) 0 ( 4 E 10 + Num ) / Num $ --R3-- T <- E
(7) 0 ( 4 E 10 + 6 Num ) / Num $ --S6--
(8) 0 ( 4 E 10 + 6 Num 5 ) / Num $ --S5--
(9) 0 ( 4 E 10 + 6 F 3 ) / Num $ --R8-- Num <- F
(10) 0 ( 4 E 10 + 6 T 11 ) / Num $ --R6-- F <- T
(11) 0 ( 4 E 10 ) / Num $ --R1-- E + T <- E
(12) 0 ( 4 E 10 ) 15 / Num $ --S15--
(13) 0 F 3 / Num $ --R7-- ( E ) <- F
(14) 0 T 2 / Num $ --R6-- F <- T
(15) 0 T 2 / 9 Num $ --S9--
(16) 0 T 2 / 9 Num 5 $ --S5--
(17) 0 T 2 / 9 F 14 $ --R8-- Num <- F
(18) 0 T 2 $ --R5-- T / F <- T
(19) 0 E 1 $ --R3-- T <- E
--------------------------------------------------------------------
|
動作は、2章 構文解析 3.3節に説明した通り、シフト／還元とスタックへの状態値と（非）終端識別子のプッシュによって、順次行われる。スタックには、初期状態として先頭に 0 がセットされている。
STEP(1) :
状態0 : token ( --> action = S4 (shift (, and state 4)：
スタックに ( をプッシュする。次に、遷移先の状態値 4 をスタックにプッシュする。
stack [0:(:4]↓
STEP(2) :
状態4 : token Num --> action = S5 (shift Num, and state 5)：
スタックに Num をプッシュする。次に、遷移先の状態値 5 をスタックにプッシュする。
stack [0:(:4:Num:5]↓
STEP(3)：
状態5 : token '+' --> action = R8 (reduce using rule#8)：
スタック先頭の 状態値5, Num をポップする。8番目の生成規則 Factor -> Num を逆向きに使って、Num を Factor で置き換える（Num <- F）。スタック先頭には、Numをプッシュする前の状態値（状態4）が入っているので、解析表の状態値4の行における、next state : Factor のカラムの値（状態3）から、次の状態が決まる。最後に、F(Factor) と 遷移先の状態値 3 をスタックにプッシュする。
stack [0:(:4:F:3] , output [Num <- F]↓
STEP(4)：
状態3 : token '+' --> action = R6 (reduce using rule#6)：
スタック先頭の 状態値3, F をポップする。6番目の生成規則 Term -> Factor を逆向きに使って、Factor を Term で置き換える（T <- F）。スタック先頭には、Fをプッシュする前の状態値（状態4）が入っているので、解析表の状態値4の行における、next state : Term のカラムの値（状態2）から、次の状態が決まる。最後に、T(Term) と 遷移先の状態値 2 をスタックにプッシュする。
stack [0:(:4:T:2] , output [T <- F]↓
＜途中省略＞
STEP(18)：
..............
stack [0:E:1] , output [E + T <- E]↓
STEP(19)：
状態1：token $ --> action = 受理 ：
スタック先頭の 状態値1, E をポップする。終端記号 $ 入力時の action は「受理」であるので、ここで解析は正常に終了した。
3. 導出木の例
上記 2.2節 の解析に基づいて生成された、導出木の例（構築後）を、図3.1, 3.2に示す。
図3.1: '(' Num '+' Num ')' '/' Num $ の導出木
図3.2: Num '/' Num '-' Num '*' Num $ の導出木
4. SableCCによる解析器の生成
4.1 文法ファイル
4.2 test2.grammarの説明
4.3 SableCCによる構文解析器の生成とテスト
4.1 文法ファイル
先の test1.grammar 文法ファイルに対して、更に、減算（'-'）と除算（'/'）の非終端記号を追加した、test2.grammar 文法ファイルを作成する。
（説明上、左端に行番号を付した。実際の文法ファイル中に行番号は付されていない）
演算の評価の優先順位は、(括弧) > '*','/' > '+','-' でなければならない。
ボトムアップ型構文解析のため、この逆の親子関係で生成規則を記述する。
＜文法ファイル：test2.grammar＞
1 Package test2;
2
3 Tokens
4 number = [ '0' .. '9' ]+;
5 plus = '+';
6 minus = '-';
7 mult = '*';
8 div = '/';
9 l_par = '(';
10 r_par = ')';
11 blank = ( ' ' | 13 | 10 )+;
12
13 Ignored Tokens
14 blank;
15
16 Productions
17 expr =
18 {term} term |
19 {plus} expr plus term |
20 {minus} expr minus term;
21
22 term =
23 {factor} factor |
24 {mult} term mult factor |
25 {div} term div factor;
26
27 factor =
28 {number} number |
29 {expr} l_par expr r_par;
|
この文法ファイルは、「整数リテラル同士の加減乗除算（括弧あり）」の四則演算式を表す文法に基づき記述したものである。具体的には、以下の例のような文字列を受理するようなものである。（[EOF]は入力シーケンスの終端を示す）
例：
12 / 4 - 3[EOF]
( 4 + 8 ) / 2[EOF]
12 / 4 - 3 * 1[EOF]
＜注記＞ この文法は、"12 / 0[EOF]" という文字列も「受理」することに注意せよ。演算式の構文規則については定めているが、各演算子のドメインの制限などは、文法中に繰り入れることはできない。演算時のエラーについては、別途、実行時に検出して処置する必要がある。
4.2 test2.grammarの説明
※SableCCの文法ファイル形式はここから参照されたい。
http://sablecc.org/grammars/sablecc-2x.sablecc.web.html
文法ファイル（test2.grammar）について、各ディレクティブについて説明する。
3-11行目（Tokensディレクティブ）：
字句規則を指定している。test1.grammarに対して、さらに以下の２種類のトークンを追加して定義している。各々の意味付けは以下の通り。
minus ：'-'が１つ並んだ列（"減算"を表す２項演算子）
div ：'/'が１つ並んだ列（"除算"を表す２項演算子）
16-29行目（Productionsディレクティブ）：
構文規則を指定している。
ここでは、expr, term に加えて factor というラベルが付された３つの規則を定義している。規則exprの内部でterm, 規則termの内部で factor が使われているため、３つの規則には親子関係があり、expr > term > factor である。トークン plus, minusは、expr内部で利用されている。トークン mult, div は、term内部で利用されている。トークン number, l_par, r_par は、factor 内部で利用されている。各々の規則の意味は以下の通り。
規則expr：
{ラベルterm} ：term が出現する
あるいは
{ラベルplus} ：expr '+' term （加算の演算式）が出現する
あるいは
{ラベルminus} ：expr '-' term （減算の演算式）が出現する（終わり）。
規則term：
{ラベルfactor} ：factor が出現する
あるいは
{ラベルmult} ：term '*' factor （乗算の演算式）が出現する
あるいは
{ラベルdiv} ：term '/' factor （除算の演算式）が出現する（終わり）。規則factor：
{ラベルnumber} ：number（整数リテラル）が出現する
あるいは
{ラベルexpr} ：'(' expr ')' （左右括弧の内部に演算式）が出現する（終わり）。
4.3 SableCCによる構文解析器の生成とテスト
付録A. SableCCのインストール、5. 実行試験 を参考にして、今回は、test2.grammar試験用プロジェクトファイルを新たにビルドして、構文解析器を生成してみよう。
test2プロジェクトファイルはここからダウンロード（test2-src.tar.gz）
実際に、演算式（"12 / 4 - 3[EOF]"など）を解析器（test2.jar）に入力した場合の実行結果を以下に示す。
実行結果は、test2.tool.PrintTreeクラスによって、導出木全体を深さ優先探索した結果で表示されている。
＜実行結果１："12 / 4 - 3[EOF]"＞
$ echo "12 / 4 - 3" | java -jar test2.jar
Start
AMinusExpr
ATermExpr
ADivTerm
AFactorTerm
ANumberFactor
TNumber: 12
TDiv: /
ANumberFactor
TNumber: 4
TMinus: -
AFactorTerm
ANumberFactor
TNumber: 3
EOF:
|
＜実行結果２："( 4 + 8 ) / 2[EOF]"＞
$ echo "( 4 + 8 ) / 2" | java -jar test2.jar
Start
ATermExpr
ADivTerm
AFactorTerm
AExprFactor
TLPar: (
APlusExpr
ATermExpr
AFactorTerm
ANumberFactor
TNumber: 4
TPlus: +
AFactorTerm
ANumberFactor
TNumber: 8
TRPar: )
TDiv: /
ANumberFactor
TNumber: 2
EOF:
|
＜実行結果３："12 / 4 - 3 * 1[EOF]"＞
$ echo "12 / 4 - 3 * 1" | java -jar test2.jar
Start
AMinusExpr
ATermExpr
ADivTerm
AFactorTerm
ANumberFactor
TNumber: 12
TDiv: /
ANumberFactor
TNumber: 4
TMinus: -
AMultTerm
AFactorTerm
ANumberFactor
TNumber: 3
TMult: *
ANumberFactor
TNumber: 1
EOF:
|
wasaki@cs.shinshu-u.ac.jp
Copyright(c) 2006 Katsumi Wasaki. All rights reserved.