数式の構文解析：top-down parserの作り方

構文規則とは

前に、 簡単な数式の処理系を解説した。構文は、以 下のようなBNF(Backus nur form, Backus normal form),による構文規則で記述される。 

足し算の式　:= 式　＋の演算子　式
引き算の式　:= 式　−の演算子　式
式　:= 数字　| 足し算の式 ｜　引き算の式
ここで、構文の最終的な要素に現れるものを 終端記号(terminal symbol)、 それ以外のほかの構文規則によって定義される記号を 非終端記号(non-terminal symbol)と呼ぶ。 ここでは、非終端記号を<>で囲んで表すこと にする。
  1. 構文規則は, 非終端記号<T>に対して、<T> := e (eは構文規則)で、表現される。これは、非終端記号<T>は、構文規則eによって置き換えられることを意味する。
  2. eは空でもよい。
  3. eは、非終端記号、終端記号、もしくはe1 | e2、e1 e2、e1* のいずれか。 e1 | e2は、e1もしくはe2であることを意味し、e1 e2　はe1の次にe2が現れる ことを意味し、e1*は、e1の0個以上の繰り返しを意味する。
(...)は、構文規則のまとまりを示す。e1|e2|e3は、((e1|e2)|e3)を、e1 e2 e3　は　（(e1 e2) e3）と同じである。正規表現と似ていることを注意しよう。

ここでは、構文規則の左辺が、一つの終端記号<T>だけという文法を考える。 これはすなわち、どのような場合でも<T> := eの規則を使って、右辺に置き換 えることができることを意味し、このような文法を文脈自由文法とよぶ。この 制限を取り払って、例えば、 

e1 <T> e2 := ...
というような、e1 e2の間に構文要素<T>が現れたときだけ、置き換えるこ とができるというような文法が考えられるが、このような文法を文脈依存文法 と呼ぶ。

top-down parser の作り方

構文規則に対し、構文解析を作る方法を紹介しよう。例えば、 

<A> := a <B> c
という構文規則があったとすれば、<A>のための構文解析関数readAは以下 のように作ることができる。 
readA() {
   aを読み込む；
   readB();     /* Bを読み込むための関数を呼ぶ*/
   bを読み込む；
｝
これは、これから読み込むものの形を先に仮定してしまってから、それに合致 するかを調べていく構文解析法である。このような構文解析法を 再帰的下向き 構文解析(recursive decent parsing) あるいは top-down parser と呼ぶ。 以前、解説した数式の構文解析もこの方法によるものである。

さて、前回の数式を再度考え、括弧や乗算をいれて考えてみることにする。構 文規則を再度定義してみると、 

<expression> := <expression> <expr_op> <term>
<term> := <term> <term_op> <factor>
<factor> := number | '(' <expression> ')'
<expr_op> := '+' | '-' 
<term_op> := '*'
ここの定義で、加減算の優先順位を考慮して、生成される構文木を反映して構 文規則が作られていることに注目。しかし、これを上の方法で書くと 
readExpr() {
　　readExpr();
　　readExprOp();
　　readTerm();
}
となってしまって、readExprが再帰的に呼ばれて，うまく行かない。この問題 を、 top-down parserの　左再帰性の問題 と呼ばれている。 すなわち、最終的に 
 <T> := <T> e
となる、文法規則ではうまくいかないのである。

このために、前回のプログラムでは、 

readExpr() {
   readTerm();
   while(readExprOp() is OK)
　　　　readTerm();
}
とした。これは、 
<expresssion> := <term> <expression1>
<expression1> := <expr_op> <term> <expression1> | e
と書き換えたのと同等である。e は空を示す。

このほかに、 

 <T> := b ( c| e )
はうまく行かない。 (c|e)は、cを読むか、それともなにもしないかという意味であるが、この場合 は、<T>の次に何がくるかによって、cを読むかどうかが決まるので、 top-down parser では、処理ができないことになってしまう。