四則演算と比較演算を行う式を定義する生成規則

質問

一桁の数値と四則演算だけを記述できる簡単な文法
の生成規則

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> 0 | 1 | ... | 9 | (factor)

に、関係演算子 > と < を追加したとき、
どのような生成規則になりますか？

型という観点から考えると、bool型という概念が
新たに追加されることになり、２つの関係演算子は、
bool型同士の計算はできません。
ここの、bool型同士の計算ができない、という点が、
生成規則に反映されるのか、また、
bool型同士も計算できるような生成規則を作成し、
型検査は別に行うべきなのか、
そこのところが知りたいです。

よろしくお願いします。

回答No.5

syulen · ベストアンサー

一日たって読み返すと自分の書いたこと最悪ですね。

まず、
>ただし、もう一階層うえに
>rel-exp2: rel-exp |
>rel-exp < rel-exp |
>rel-exp > rel-exp
>のようなものが必要になる(そうしないと自由度が低い)かと思います。
は、自分でも何を言っているのかわかりません;;
第一、書いたことと矛盾していますね。

「<」と「>」は真理値との演算できないので、「rel-exp」と「rel-exp」の比較できないですもんね。
ま、or演算やand演算の事指していたと思ってください・・・。(逃げです;;)
混乱させて申し訳ありません。

適当に書いていると恥ずかしい思いしますねぇ^^;

回答に対する補足の説明は大筋liar_adanさんと同じ考えです。
liar_adanさん、すごいですねぇ。

ただ、大体おわかりのことかと思いますが、
言語は、扱えるデータ、およびその構造とそれを操るための文法により構成されており、
どのようなデータ構造を扱わせるか、
またそれらデータ構造に対しどのような操作を行うかは、
全てポリシーにより決定されるかと思います。
そこから、実現の仕方の違いは、単純なポリシーの違いと捕らえてよいのではないでしょうか。

C言語の場合、メモリを直接操作することが主となる
(「基本的にどれも「値」」と書かれている主な理由になるかと思います)のに対し、
Javaの場合、元となる言語がインタプリタ上での動作であり、
純粋にデータ構造を操作することが主となる
(実行効率のためにプリミティブな型がベースにありますが)、
という言語の目的の違いもあるかとは思います。
これもまぁ、ポリシーですけどね。

あと、蛇足ですが、
liar_adanさんも解って書いてらっしゃると思いますが、
生成規則では型チェックは出来ません。
あくまで、型チェックは
「字句解析->構文解析->意味解析」
の意味解析の段階で行われるものです。

たとえば、日本語の文法でも、
「人間は猫である」という文は文法上はおかしくないですよね。

ただし、在るひとつの文法に出現する方に縛りをかけることは可能であり、
それにより、一部の型チェックを省くことは出来るかと思います。
「生成規則に型チェックを任せる」
というのはそういうことを言いたいのだと思います。

今回のお題を例にとれば、日本語で真理値のTRUEと数字を比較する際、
「１はTRUEよりも大きい」とする事も文法上は可能ですが、
「数字は数字同士でなければ比較できない」という縛りをかけることで、
「１はTRUEより・・・」とした時、数字とほかのものを比較することになり、
先ほどの縛りのため、出来なくなります。

Harryさんのお書きになった、
rel_expr -> fund_expr < fund_expr |
　　　　　　　fund_expr > fund_expr
なども、その一例だと思います。

厳密には「数字」の意味がわからなければいけず、
かりにTRUEを数字のひとつとした場合は、可能になってしまいますが。

「型検査は別に行うべきなのか」から、ご理解されているとは思いますが、
念のためと、これを読むほかの方のためにも・・・って、読む人いるのか疑問が。

こんなことを書くのは、自分のおさらいのためだったりします^^

そうそう、一番初めの問いに対する回答って出てないんですね。
個人的な意見としては、きれいな実装を望まれるようであれば、
意味解析が必要になりますが、
「bool型同士も計算できるような生成規則を作成」を選ばれたらよいのでは、と思います。
ただ、扱う演算が現状四則演算のみであり、
そのような実装を求められているわけでもないかと思いますので、
現実解としては
「bool型同士の計算ができないという点が生成規則に反映される」形でよいのでは。

お礼

liar_adan さん、syulen さん、
貴重な意見と回答どうもありがとうございます。
ここでまとめてお礼させていただきます。

ポイントの発行、非常に悩みましたが、

> 個人的な意見としては、きれいな実装を望まれるようであれば、
> 意味解析が必要になりますが、
> 「bool型同士も計算できるような生成規則を作成」を選ばれたらよいのでは、
> と思います。

この部分が、質問に対する直接的な回答で、
最終的にこれを読んで私が設計方針について考え方を固めることができた、
という意味で syulen さんに20pt発行したいと思います。

質問と捕捉で私が挙げた例は、私がもっていた疑問を
最大限簡略化したもので、実際に作りたいものはもっと複雑です。
そして当然きれいな、より標準的な実装を望んでいますので、
「bool型同士も計算できるような生成規則を作成」
でいきたいと思います。

どうもありがとうございました。

回答No.4

liar_adan

#1です。問題を誤解していたようでした。

＞そして、後者の方が楽そうな気がしますが、
＞生成規則としてちょっと見慣れない気がするので、
＞何か見落としがあるのか、と気になっています。

これは問題ないと思います。
私が構文解析をやったのはしばらく前だったのですが、
こういうやり方も使ったような憶えがあります。(←だいぶ忘れてるけど)

ただこれだと、評価した式が
fund_exprとrel_exprの2種類あることになるので、
気持ち悪い気がしないでもありません。
気になるなら、その上に
abstract_expr -> rel_expr | fund_expr
の生成規則を付け加えてみるのはどうでしょう。
(自信がないですが…)

＞これは、C では真偽値が 0 または 0以外という
＞数値で表され、無意味であれ 1 < 2 < 3 のような式も
＞許される、という事情によるものですか？
＞それとも、単純な設計ポリシーの問題でしょうか？

CとJavaで実現が異なるといった根拠は、
Cの(JIS)規格についている構文表と、
『Java言語仕様』についている構文表が大きく違うことです。
実際のコンパイラがどうやっているかはわかりませんが、
たぶん構文表どおりにやっていると思います。

この違いの原因は、文法から来る面と、ポリシーの面の両方があると思います。
Cの場合基本的にどれも「値」ですが、
Javaでは、数値は数値、真偽値は真偽値とはっきり区別されています。
それによってプログラミングの安全性が増しています。

「型」と「生成規則」はいちおう別だけれど、Cの場合、
かなりの程度生成規則に型チェックをまかせているように感じます。
Javaは「型」に厳しいので、生成規則にまかせるのではなく、
意味規則をもとに型チェックをしているのではないでしょうか。

回答No.3

syulen

あ、やっちまった
という状態なので修正です。

1 < 2 < 3
の構文、非決定でもなんでもなく、それ自体の解析は出来るけど、「<」や「>」は2項演算で、
それぞれの計算後の出力が真理値だから、
「<」も「>」も計算対象に出来ず、
1 < 2
2 < 3
に分けてand演算繰り広げなきゃいけないから、
構文として受け付けない、が正しいですね。
すいません。

構文として受け付けてもいいけど、
どうせ中でand演算しなきゃいけないし、演算の意味を明示的に考えさせなきゃいけないから、
やらせないってことなのかな。
でもgccだと通ります。
ずっと1しか出力しないから、意図した結果が出力できないではいますが。

補足

回答ありがとうございます。
本当にすいません。
この手の質問は、質問文も非常に厳密にせねばならない、
ということが、わかってきました。

多分、Cを前提に考えてらっしゃるのではないかと思います。
今は、型として、互換性のない「数値型」「真偽値型」の２つだけをもち、
演算子 + - * / は２つの数値をオペランドにとり、式の値の型は数値、
演算子 > < は２つの数値をオペランドにとり、式の型は真偽値、
優先順位は優先度の高い順から、
* /
+ -
> <
で、すべて左結合、
という定義が全てである言語について話をしています。

その上で、 1 < 2 < 3 は左結合で ( 1 < 2) < 3 と
解釈され、(1<2) の値である真偽値は < のオペランド
になれないから駄目、という意味です。

それは、ちょっと本題からそれるので置くとして、

rel_expr2 -> rel_expr |
　　　　　　　rel_expr < rel_expr |
　　　　　　　rel_expr > rel_expr

のような規則を加える必要がある、とありましたが、
これが必要かどうかは、結局、言語仕様として、
どれくらいの自由度が求められるか次第、ということに
なるのでしょうか。
上記の誤解が原因だと思いますが、> < は真偽値を
オペランドに取れない(ことにしている)ので、
これらの生成規則は不要だと思いました。

また、C と Java とで実際のコンパイラとしての
実現の仕方が異なるとありました。
これは、C では真偽値が 0 または 0以外という
数値で表され、無意味であれ 1 < 2 < 3 のような式も
許される、という事情によるものですか？
それとも、単純な設計ポリシーの問題でしょうか？

回答No.2

syulen

んーと、生成規則とおっしゃっているので、yaccやbisonなどで構文解析機を生成するときのことを考えますね。

結果から申し上げると、やりたいことをやるためには、後者が適切です。
ただし、もう一階層うえに
rel-exp2: rel-exp |
rel-exp < rel-exp |
rel-exp > rel-exp
のようなものが必要になる(そうしないと自由度が低い)かと思います。

C言語などのBNF記法では前者が使われることが多いかと思います。
しかし、実際にプログラムすればわかることなのですが、前者の構文を使うものは、コンパイルは通るかと思いますが、通っても、演算結果として求めたいものが求められるわけではありません。
ただし、Java等の型の意味チェックを行うものであれば、意味チェックの段階ではじかれ、コンパイルが出来ません。

陥りやすい誤解が原因なのですが、まず、演算の前提として、「<」や「>」でもとめられるものは真理値であり、真理値は、四則演算等と同じ空間(というか、概念かな？)で使用することは出来ません。
そのため、真理値を求める構文の定義中では、同じく真理値を求める定義のみか、四則演算の定義のみしか出現させてはならないとなるかと思います。
C言語などでは、真理値のメタ定義が無いため、便宜上同じ空間上で計算することを許していますが、そのかわりに正しい結果が出ないわけです。
メタ定義が存在する言語である場合は、意味チェックの段階ではじかれると思います。

ここでメタ定義としているのは、その値の意味として、式で求められる値の意味と真理値の意味が違うことが区別される必要があるからで、「メタ定義」という必要は無いかもしれませんね。

あと、( 1 < 2 < 3 )は、プログラム言語上だと使えないとは思いますが、その「評価」は可能ではないですか？
ただ、構文として成立させるのは難しいですが。
実際には、これは構文解析において非決定性のものをコンピューターでは処理できないことから、構文として受け付けないようにしている。
というのが正しいかと思います。

そんなに自信は無いですが(笑)
面白そうな議題だったのでコメント入れてみます^^；

回答No.1

liar_adan

これはどっちでもよく、強いて言えば考え方の違いとなります。

C言語では、生成規則の適用によって大部分を処理しています。
だから「乗除式」「加減式」「シフト式」「関係式」など、
すごく沢山の階層を作っています。
そこで「乗除式」は「加減式」でもあり、
それがまた「関係式」にもなる、というような構造を取っています。

Javaでは(式については)あまり階層化せず、
3項演算子など以外は、
式　<演算子　式>
の形で受け取って、「型」の処理はそのあとでしているようです。

ちなみに、生成規則でつかう非終端記号(この場合はexpr, term, factor)の階層は、
プログラム言語の「型」とはちょっと意味が違うものなので、
混同に注意してください。

bool型同士の計算ができるようにするかできなくてもいいかは、設計上の判断になります。
単に、関係演算子を扱うため生成規則をひとつ付け加えるだけだったら、
当然bool型(←関係演算子を施した後の値)同士の演算はできませんね。
演算ができるようになるためには、
さらに2段ほど生成規則を追加する必要があります。

bool型同士の計算については、
*と+は使わず、&と|にしておくとやりやすいと思います。
なんだかわかりにくい文になってしまいましたが、
わからなければ補足ください。

補足

回答ありがとうございます。
私の質問が言葉足らずでした。

+ - * / < >

これらの演算子はすべて、
論理値同士の計算はできない仕様のつもりです。

疑問を生成規則で書くと、

rel_expr -> rel_expr < fund_expr |
　　　　　　　rel_expr > fund_expr |
　　　　　　　fund_expr
fund_expr -> fund_expr + term |
　　　　　　　fund_expr - term |
　　　　　　　term
term -> term * factor | term / factor | factor
factor -> 0 | 1 | ... | 9 | (rel_expr)

とし、"1 < 2 < 3" のような式を導出可能にした上で、
この式は評価不可能ですから、型検査でエラーとするか、
（これだと "1 + ( 2 < 3 )" なども導出できます）

rel_expr -> fund_expr < fund_expr |
　　　　　　　fund_expr > fund_expr
fund_expr -> fund_expr + term |
　　　　　　　fund_expr - term |
　　　　　　　term
term -> term * factor | term / factor | factor
factor -> 0 | 1 | ... | 9 | (fund_expr)

のようにして、bool型の式の値をもつ rel_expr
は、生成規則の右辺では使用しないようにするか、
といった感じになります。

そして、後者の方が楽そうな気がしますが、
生成規則としてちょっと見慣れない気がするので、
何か見落としがあるのか、と気になっています。