演算子順位法での関数の扱い

質問

演算子順位法での関数の扱い

今手書きでパーサを作ることに挑戦しているのですが
関数の扱いに困っています。

式の文法自体はCに似せようと思っています

関数を発見する事はできました。
しかしその後の引数に扱いに困っています。

1+3+foo(6+2,a+b,5)+(6/5)

ここでfoo等定義されていない物はID,(はLPARENという名前のトークンに分割されています。

ID LPARENという文脈だと(キャストがないので)関数と確定します。

ですがその後
()の中をどうやって扱えばいいのかが分かりません

再帰的に
6+2
a+b
5
に対して式木を作成してそれを追加するという方法も考えたのですが
一番最後に,がなくどうやって判別しようかと迷っていた所です。

どのように考えればいいのでしょうか
アドバイスいただけませんか?

回答No.2

Tacosan · ベストアンサー

く, 一通り書いて[確認する]ボタンを押したらトップページに戻されたうえ回答まで完全にロストさせられた... このような挙動をするシステムの作り方の講習があったらぜひにも参加するのだが....
....
ああ, すみません, 演算子順位法の話でしたね. えぇと, #1 で「優先順位を変えるかっこ」について聞いたのは, 実は「ほとんど同じ」だからです. もっというと, 「引数を持つ呼び出し」については実質的に「全く同じ」ということができます.
文法からはおかしな解釈になるのですが, 「引数を区切るコンマ」を「引数リストを作る演算子」と思ってください. すると「全く同じ」であることがなんとなくわかるのではないでしょうか.
もちろん「引数を持たない関数呼び出し」も考えなければならず, そのときにはちょっと違う扱いをしなければなりません (優先順位を変えるかっこでは「空の式」が認められないため). また, 「関数呼び出しのかっこ」は「呼び出される関数」と「(空かもしれない) 引数リスト」からなる「2引数演算子」ですから, 演算子スタックに積むシンボルとしては「優先順位を変えるかっこ」とは別のものにすべきです. まあ, これは「同じ記号で異なる演算子を表す」場合 (単項・2項の - など) には当然ですが.

お礼

ありがとうございました

ほぼその方法で実装できました
スタックには関数の時は関数名を積んで処理しました。

ありがとうございました

補足

#1に補足しようとしたらトップに戻されてイラッとしてました…

ありがとうございます。
成る程そういう解釈があったのですね。
関数は関数fooという名のn項演算子という解釈しかできませんでした。(nは引数のかず)
その方針で実装してみることにします。

回答No.3

Tacosan

まあ解釈はわりと勝手なのでどうでもいいところではありますが, 演算子順位法が LR の一種であることから「LR 的にどうなってくれるとうれしいか」を考えるといいかもしれません.
今の場合, 最初のコンマまでで「1つの引数」としまとまってほしいのですが, これは LR では「1つの式になるまで還元する」ことに対応します. すると, (かっこ以外の) 全ての演算子に対して還元してほしいわけです. これを, 今度は逆に演算子順位法で考えると, コンマを「(ほぼ) 全ての演算子より優先順位の低い演算子」とみれば実現できることになります.
ただ, 実際にはどうするかなぁ.... 「関数呼び出しのかっこ」がきたときに, ε動作で「空の引数リスト」を作るかもしれないなぁ.

お礼

成る程
そのような解釈もできるのですね。

ただ今回は#1,2の方の方法を採用させていただいたのでそちらをベストアンサーとさせてください。

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

回答No.1

Tacosan

演算子順位法でパーズするなら, 「再帰したら負け」のような気がする. 再帰するんだったら, 最初から再帰下降パーザの方が (作るのは) 簡単だと思う. というか, 「演算子順位パーザを手書き」というのがそもそも珍しいような気がする.
さておきちょっと気になるのですが, 現状で「優先順位を変える」かっこは実装できているのでしょうか? 実装できているとしたら, どのように実装しているのでしょうか?

補足

できています

a+(b+c)とあったら
スタックに
+(+
と左括弧をそのままスタックに積んで
)（右括弧）が来たら最初の(までをはき出すという手順でやっています