ブール式で解析+と*

Question

私は例えば、ブール式の再帰下降パーサを書いています：

1が「本当」である

(1 * 0) 
(0 + ~1) 
(0 * (1 + c) 

、0は「偽」である、+ 'ですまたは '、* is' and '、〜は' not 'であり、' c 'は変数名です（アルファベットは一文字でも構いません）。何らかの操作順序を実装するのではなく、かっこを使用することを計画しています。

私の現在のパーサは表現

Expression ::= 1 
      | 0 
      | Character 
      | ~ Expression 

次の形式を認識することができますしかし、私はこの上に* +を実装してしまう方法としてわからないと思います。私はそれが左再帰的」であるとして

Expression ::= 1 
      | 0 
      | Character 
      | (Expression + Expression) 
      | (Expression * Expression) 

の明白な実装が無限ループを引き起こす読んだものから、かなり確信しています。私はこのような無限の再帰を取り除くためにこれをどのように変更するのか不明です。

Answer 1

括弧を使用すると、そこにあるものは再帰的に残ることはありません。左回帰は、間に消費されるトークンがなくても、プロダクションが（直接的または間接的に）到達できるときです。そのような文法は実際に再帰的な降下パーサで無限の再帰を引き起こしますが、それはあなたのものでは起こり得ません。

文法があいまいであるという問題があります。かっこの後、左辺の式が解析されるまで、+または*の形式が解析されているかどうかはわかりません。その問題を歩き回るの

一つの方法は、共有接頭辞/接尾辞の生産に共通する部分を引き上げている。

Expression ::= 1 
      | 0 
      | Character 
      | ParExpr 

ParExpr ::= (Expression ParOp Expression) 

ParOp ::= + 
     | * 

Answer 2

私はあなたのためにそれを検索してみましょう... https://en.wikipedia.org/wiki/Recursive_descent_parser

大手LPARENは、これを左回帰的にしないようにします。 式を一般化して演算子を優先する場合は、Wikipediaの記事のBNFの式の部分に従ってください。

ただし、選択した文法に構文のあいまいさがあります。同じ優先順位の演算子がある場合は、それらを非終端記号に結合します（例：

LogOp :: = + |拡張を可能にする*

ラベル同様のオペランド：

UnaryOp :: =〜

今、あなたは...気にしないことができますが、500 @私の最後のポイントをカバーして良い答えを投稿しました。