構文解析文法を変更して、代入文と非代入文を許可する方法はありますか？

Question

質問は以下の文法についてです。私は楽しいためにミニインタープリタ言語に取り組んでいます（私たちはクラスでいくつかのコンパイラデザインについて学んだので、次のレベルに持ち帰り、自分で何かを試してみたいと思います）。私は非終端記号Exprを作ろうとしています。

Statement ::= Expr SC 
Expr ::=   /* I need help here */ 
Assign ::= Name EQUAL Expr 
AddSub ::= MulDiv {(+|-) AddSub} 
MulDiv ::= Primary {(*|/) MulDiv} 
Primary ::= INT | FLOAT | STR | LP Expr RP | Name 
Name ::= ID {. Name} 

ExprStatementは、2つのケースについて可能にしなければならないように行わなければならない。

1. x = 789;（セミコロンに続く標準割当、）
2. x+2;（NO割り当て、単に計算、廃棄。続いてセミコロン）

2番目のケースの目的は、m将来の鉱石の変化。私は、単項インクリメントとデクリメント演算子、そして関数呼び出しについて考えていました。どちらも意味のある代入を必要としません。

私は他の文法（C＃）を見てきましたが、理解するにはあまりにも複雑で時間がかかりました。もちろん、私は解決策を探しているわけではなく、文法をどのように変更できるかについてのガイダンスのためにのみです。

すべてのご協力をいただきありがとうございます。

EDIT：最初の考えはExpr ::= Assign | AddSubだったと思いますが、どちらも非終端記号Nameで始まる可能性があるため、あいまいさが生じるため動作しません。 Tokenizerは、トークンを先読みすることができるようにしましたが、避けることができる問題を修正しようとしているので、非終端記号についてはこれを作っていません（あいまいさ）。文法では、端末はすべて大文字です。

Answer 1

最も簡単な解決策は、Cの設計者が実際にとった解決策であり、さまざまなCの派生品である：割り当てを単に別の演算子として扱い、ステートメントの最上位レベルに制限することはありません。したがって、Cには、次のように問題がない：

while ((ch = getchar()) != EOF) { ... } 

誰もがその良いスタイルを検討しますが、それは特に、構文多かれ少なかれその割り当てを必要とfor文の句で（確かに一般的ではありません表現である）。

達成するのが比較的容易である二つの小さな合併症、があります。

1. 論理的には、ほとんどの事業者とは違って、右に割り当て仲間a = b = 0がされるであろう（a = (b = 0)なく(a = b) = 0として解析されるように、非常に予期しない）。それはまた、少なくとも右には非常に弱く結合する。

   意見は、左側にどれくらい緊密に結合するかによって異なります。 Cでは、ほとんどの場合、厳密な優先順位モデルに従い、a = 2 + b = 3は、a = ((2 + b) = 3)として解析されるため、拒否されます。 a = 2 + b = 3はひどいスタイルのように見えるかもしれませんが、またa < b ? (x = a) : (y = a)と考えてください。 C++では、三項演算子の結果が参照となる場合は、(a < b ? x : y) = aと書くことができます。ここでは、三項演算子よりも優先順位が低いと考えられていてもかっこが必要です。

   しかし、これらのオプションはどれも文法で実装するのが難しくありません。

2. 多くの言語では、割り当ての左側には構文が制限されています。参照値を持つC++では、制限は意味論的と見なすことができ、通常は意味チェックで実装されると信じていますが、多くのC派生語ではlvalueを構文的に定義できます。そのような定義は明確ではありませんが、トップダウンの文法で解析することはできないことが多く、ボトムアップの文法でも複雑になります。ポスト・パース・チェックを行うことは、常に簡単な解決策です。

あなたが本当に式文からの代入文を区別したい場合には、このような再帰下降としてトップダウンの解析技術を使用している場合、あなたは確かに予測失敗（ない曖昧）の問題に遭遇。文法はあいまいではないので、簡単な解決策は、bison/yaccのようなLALR（1）パーサジェネレータを使用することです。このジェネレータは、どのような種類の文が存在するかについて早期に判断する必要がないため、解析される。全体として、LALR（1）やGLRパーサジェネレータを使用すると、文法を構文解析に対応した形式で簡単に読みやすくすることができ、パーサの実装が簡単になります。 LL（1）文法は右結合パースだけを生成することができ、したがって構文木の何らかの再構成を必要とするのに対し、LALR（1）パーザは自然に左結合演算子を処理できます。

A再帰的降下構文解析器は文法ではなくコンピュータプログラムであり、その表現力はLL（1）文法の形式的制約によって制限されない。それは強さと弱さの両方です：強さはLL（1）文法の限界によって制限されない解を見つけることができることです。弱点は、言語の正確な構文についての明確な声明を抽出することは、はるかに複雑（時には、不可能）であることです。例えば、この力は、上記の制限にもかかわらず、再帰的な降下文法が、より自然なやり方で左連想を処理することを可能にする。

この道を下りたい場合は、解決策が十分に簡単です。

/* This function parses and returns a single expression */ 
Node expr() { 
    Node left = value(); 
    while (true) { 
    switch (lookahead) { 
     /* handle each possible operator token. I left out 
     * the detail of handling operator precedence since it's 
     * not relevant here 
     */ 
     case OP_PLUS: { 
     accept(lookahead); 
     left = MakeNode(OP_PLUS, left, value()); 
     break; 
     } 
     /* If no operator found, return the current expression */ 
     default: 
     return left; 
    } 
    } 
} 

これは、式と文の両方を簡単に解析できるように簡単に変更できます。まず関数をリファクタリングして、最初の演算子があれば式の「残りの部分」を解析します。 （。唯一の変更は、新しいプロトタイプと体の最初の行の削除である）代わりにそれと

/* This function parses and returns a single expression 
* after the first value has been parsed. The value must be 
* passed as an argument. 
*/ 
Node expr_rest(Node left) { 
    while (true) { 
    switch (lookahead) { 
     /* handle each possible operator token. I left out 
     * the detail of handling operator precedence since it's 
     * not relevant here 
     */ 
     case OP_PLUS: { 
     accept(lookahead); 
     left = MakeNode(OP_PLUS, left, value()); 
     break; 
     } 
     /* If no operator found, return the current expression */ 
     default: 
     return left; 
    } 
    } 
} 

、exprとstmtの両方を実装するために簡単です。

Node expr() { 
    return expr_rest(value()); 
} 

Node stmt() { 
    /* Check lookahead for statements which start with 
    * a keyword. Omitted for simplicity. 
    */ 

    /* either first value in an expr or target of assignment */ 
    Node left = value(); 

    switch (lookahead) { 
    case OP_ASSIGN: 
     accept(lookahead); 
     return MakeAssignment(left, expr()) 
    } 
    /* Handle += and other mutating assignments if desired */ 
    default: { 
     /* Not an assignment, just an expression */ 
     return MakeExpressionStatement(expr_rest(left)); 
    } 
    } 
}