プログラミング言語論第４回式の構文、式の評価篠埜功（参考）Type 3 • 右線形文法 (Right-linear grammar) すべての生成規則が X  xY または X  x の形をしている。ただし、 X, Y  N xT* Type3は正規表現と同等（参考）Type 2 • 文脈自由文法 (Context free grammar) すべての生成規則が X  の形をしている。ただし、 XN   (T  N)* Type 2はBNF記法と同等（参考）Type 1 • 文脈依存文法 (Context sensitive grammar) すべての生成規則が  X     の形をしている。ただし、 ,   N* XN   (T  N)+ （参考）Type 0 • 文脈依存文法 (Context sensitive grammar) すべての生成規則が  X     の形をしている。ただし、 ,   N* XN   (T  N)* 先週の補足: BNF記法 • Backus Normal Form (Backus Naur Form) • 文脈自由文法を簡潔に表現する記法 – 左辺が同じ非終端記号の規則を、縦棒 | を使って、まとめて表す。（例）文脈自由文法 G = (T, N, S, P) N={S} T={(,)} P = { S  ( ), S  (S), S  SS } は、BNF記法では、 <paren> ::= ( ) | (<paren>) | <paren> <paren> と表せる。式について Little Quilt言語のプログラムは１つの式であった。（C言語には文があるが、Little Quilt言語には文はない。）式の記法 --- 二項演算子は中置記法、前置記法、後置記法がある。 --- 結合性、優先順位 --- 木表現式の評価 --- スタックによる実現式の記法二項演算子： + の場合中置記法 a + b 前置記法 + a b 後置記法 a b + 前置記法の例１: * + 20 30 60 = * 50 60 = 3000 前置記法の例２: * 20 + 30 60 = * 20 90 = 1800 （前置記法、後置記法で書かれた式にはあいまいさがなく、括弧が不要。もちろん括弧をつけても良いが。）前置記法(prefix notation) • 定数、変数の前置記法は、それ自身である。 • 式E1, E2が前置記法で書かれていたとする。このとき、演算子op の式E1, E2への適用は、前置記法でop E1 E2である。（例１） * + 20 30 60 = * 50 60 = 3000 赤字の部分は20+30の前置記法による表現であり、*の１つ目の引数である。（例２） * 20 + 30 60 = * 20 90 = 1800 赤字の部分は30+60の前置記法による表現であり、*の２つ目の引数である。演算子opの引数が3以上の場合も同様である。 • 定数、変数の前置記法は、それ自身である。 •式E1, E2, … Ekが前置記法で書かれていたとする。演算子op の式E1, E2, … Ekへの適用は、前置記法でop E1 E2 … Ekである。前置記法の補足演算子の引数を括弧で囲んでコンマで区切ることにすると、演算子の引数の個数を可変にすることが可能。（例） printf (“hello”) や printf (“%d%d”, x, y)など。演算子も含めて括弧で囲むやり方もある。（例） (+ 1 2) や (+ 2 3 4) など。(Lisp, Scheme) 後置記法(postfix notation) • 定数、変数の後置記法は、それ自身である。 •式E1, E2が後置記法で書かれていたとする。演算子opの式E1, E2への適用は、後置記法でE1 E2 opである。（例１） 20 30 + 60 * = 50 60 * = 3000 赤字の部分は20+30の後置記法による表現であり、*の１つ目の引数である。（例２） 20 30 60 + * = 20 90 * = 1800 赤字の部分は30+60の後置記法による表現であり、*の２つ目の引数である。後置記法の場合、スタック構造を用いて直接評価できる。中置記法(infix notation) • 定数、変数の中置記法は、それ自身である。 • 式E1, E2が中置記法で書かれていたとする。演算子opの式E1, E2への適用は、中置記法でE1 op E2 である。（例） 2 + 5 - 4 = 7 - 4 = 3 赤字の部分は中置記法による2と5の和であり、外側の引き算の一つ目の引数である。 (注意点) 中置記法においては、たとえば、a+b*cは、aとb*cの和であるのか、a+bとcの積なのか、２通りの解釈がある。 --- 優先順位、結合性を導入する（後述）。中置記法は人間にとって分かりやすい。式の木表現（例） b * b – 4 * a * cの木表現－＊ b 抽象構文木（abstract syntax tree）と呼ばれる。（前置、中置などの書き方に依らないので）＊ b 4 ＊ c 前置: -*bb**4ac 中置: b*b-4*a*c 後置: bb*4a*c*- a 演算子を根、引数をその子とする木によって表現抽象構文木の例： if式の場合四則演算以外の場合でも同様である。（例） if a>b then a else b の抽象構文木は、if-thenelseという演算子を作ることによって構成できる。 if-then-else > a a b b 中置記法における演算子の優先順位、結合性中置記法の式を <E> ::= <num> | <E> + <E> | <E> - <E> | <E> * <E> | <E> / <E> のように定義すると、この文法はあいまいである。たとえば、a+b*cは、aとb*cの和であるのか、a+bとcの積なのか、２通りの解釈がある。 --- 優先順位、結合性を考慮した文法に変更するか、あるいは文法は変えずに、優先順位、結合性を別途、曖昧さ除去規則として定めることによって曖昧性を排除する。（参考）構文解析器生成系のyaccでは、曖昧さ除去規則を記述できる。優先順位、結合性伝統的に、 *は+よりも先に引数を取る（*は+よりも優先順位が高いと言う）。たとえば、a + b * c は、a と b * c の和と解釈される。（多くの言語において、*は+ よりも優先順位が高く、*と/は優先順位が同じであり、+と-も優先順位が同じである。）同じ優先順位の演算子については、普通、左から右にグループ化される（左結合と言う）。たとえば、4 - 2 - 1は4 - 2と1 の差と解釈される。（これに当てはまらない例） Smalltalk-80ではすべての算術演算は同じ優先順位を持つ。たとえば、a+b*cはa+bとcの積である。結合性を考慮した文法の例たとえば、+, -, 数字からなる言語を考える。 <E> ::= <num> | <E> + <E> | <E> – <E> は曖昧だが、 <L> ::= <num> | <L> + <num> | <L> – <num> は曖昧ではなく、１つの文字列に１つの構文木が対応する。しかも+, - が左結合の場合の抽象構文木に近い具象構文木となっている。 L － 4-2-1の抽象構文木－ 4 4-2-1の具象構文木 1 2 L － num L － num num 4 2 1 優先順位も考慮した文法の例 +, -, *, /, 数字からなる言語を考える。 <E> ::= <num> | <E> + <E> | <E> – <E> | <E> * <E> | <E> / <E> は曖昧だが、 <E> ::= <E> + <T> | <E> – <T> | <T> <T> ::= <T> * <num> | <T> / <num> | <num> は曖昧ではなく、１つの文字列に１つの構文木が対応する。（参考）混ざった記法(mixfix notation) 複数個のキーワードを組み合わせた構文による演算は前置、中置、後置のどれにも当てはまらない。（例） if a > b then a else b という式ではキーワード if, then, elseが式の中に散らばっている。このようなものはmixfix notationと言われる。式の評価式 E1 op E2の評価は、部分式 E1 、E2を評価し、それらの結果の値に演算子opを適用することによって行われ、その結果の値が式E1 op E2の値である。（例） 7 * 7 – 4 * 2 * 3 の評価： 7*7–4*2*3 = 49 – 4 * 2 * 3 = 49 – 8 * 3 = 49 – 24 = 25 後置記法の式の評価（例） 7 * 7 – 4 * 2 * 3 の評価：まず、後置記法に直すと、7 7 * 4 2 * 3 * -となる。一番左の演算子について、その前の２つの数に対して演算を行う。 7 7 * 4 2 * 3 * = 49 4 2 * 3 * = 49 8 3 * = 49 24 = 25 この評価はスタックを用いたアルゴリズムで行うことができる。後置記法の式の評価アルゴリズム (1) 式を後置記法に変換 (2) 後置記法の式を左から右へ見ていく。 (2-a) 数の場合、スタックへプッシュ (2-b) 演算子opの場合、スタックから数を２個ポップし、それらに演算子opを適用し、結果をスタックへプッシュする。 (3) 式をすべて見終わったときにスタック上にある数が式の評価結果である。評価の具体例式 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 * * * * * * * * * 4 4 4 4 4 4 4 4 4 スタック 2* 2* 2* 2* 2* 2* 2* 2* 2* 3 3 3 3 3 3 3 3 3 * * * * * * * * * - 7 7 7 49 49 4 49 4 2 49 8 49 8 3 49 24 25 演習問題 2 + 3 * 4 – 5を後置記法に直し、スタックを用いて評価せよ。その際、さきほどのスライドのように、１ステップずつスタックの変化を記述し、また、各ステップで後置記法に直した式のどの部分を読んでいるかを示せ。