next up previous contents index
: プログラム minicomp.rr : 構文解析 : 構文解析   目次   索引

再帰降下法

12章 の 12.2 節において, 後置記法(逆ポーランド記法)で書いた数式を計算するプログラムを 解説した. このプログラムはスタックの利用により後置記法の式の計算を実現している. この節では, 中置記法の数式を後置記法へ変換する プログラムを開発する. 中置記法は演算子を真中におく, おなじみの式の記述方法である. たとえば

\begin{displaymath}2+3*(45+2) \end{displaymath}

は中置記法の式であり, これを後置記法に変換すると, たとえば 2 3 45 2 + * + となる.

変換するプログラムを書く前にどのような ``文法'' の 中置記法の式を入力として認めるのか きちんと定義する必要がある. 計算機の世界で意味する文法というのは, 英文法の意味する文法とは違い, 曖昧さが入る余地はゆるしていないし, 人間が人工的に定義する.

文法は BNF (Bakus-Nauer) 形式や構文図を用いて定義する. われわれの, ``式'' の構文を構文図で定義してみよう.

number は次の構文図で定義する.

number :

\begin{picture}(50,80)
\put(0,60){\vector(1,0){20}}
\put(25,60){\oval(10,10)}
\p...
...35){$\cdot$} %14
\put(25,30){$\cdot$} %15
\put(25,25){$\cdot$} %16
\end{picture}
    
左端からスタートして右端への矢印へたどりつければ number である. たとえば, 123 は number であるが, 1.23 は number でない. なぜなら 1 は構文図がうけつけてくれるが, 次にくる . は構文図がうけつけてくれない.

variable は, A から Z, a から z のうちの一文字である. 構文図は省略する.

sentense は, 次の構文図で定義する.
sentense :

\begin{picture}(110,30)
\put(0,20){\vector(1,0){10}} %1
\put(10,15){\framebox (2...
...{\oval(10,10)} %8
\put(45,20){;}
\put(50,20){\vector(1,0){10}} %9
\end{picture}

expression は, 次の構文図で定義する.
expression :

\begin{picture}(110,40)
\put(0,20){\vector(1,0){10}} %1
\put(10,15){\framebox (2...
...,-1){20}}
\put(32,0){\line(1,0){55}}
\put(87,0){\vector(0,1){20}}
\end{picture}

term は, 次の構文図で定義する.
term :

\begin{picture}(110,40)
\put(0,20){\vector(1,0){10}} %1
\put(10,15){\framebox (2...
...,-1){20}}
\put(32,0){\line(1,0){55}}
\put(87,0){\vector(0,1){20}}
\end{picture}

factor は次の構文図で定義する.

\begin{picture}(100,40)
\put(0,30){\vector(1,0){20}}
\put(25,30){\oval(10,10)}
\...
...riable}}
\put(70,10){\line(1,0){20}}
\put(90,10){\vector(0,1){20}}
\end{picture}

構文図にでてくる      でかこまれた記号を 非終端記号 とよぶ. これらは, 別の構文図で定義されている. ○で囲まれた記号を終端記号という.



Nobuki Takayama 平成15年9月12日