1

javascript に似た言語用に、lemon を使用して単純なパーサーを作成しようとしています。競合エラーを解決できません。解決できない問題だと思います。

競合は、次の文法の間にあります。

{x = 10;}

と

{x:10};

1 つ目は代入ステートメントを含むステートメント ブロックで、2 つ目はオブジェクトを定義する式ステートメントです。

それらの両方を解析する文法は、競合を引き起こします。最小限のコードは次のとおりです。

rMod ::= rStmt.

rStmt ::= rStmtList RCURLY. {leaveScope();}
rStmtList ::= rStmtList rStmt.
rStmtList ::= LCURLY. {enterScope();}

rStmt ::= rExpr SEMI.

rExpr ::= rObj.
rObj ::= LCURLY rObjItemList RCURLY.
rObjItemList ::= rObjItemList COMMA rObjItem.
rObjItemList ::= rObjItem.
rObjItem ::= ID COLON rExpr.

rExpr ::= ID.
rExpr ::= NUM.

out ファイルには次のように表示されます。

State 4:
  (3) rStmtList ::= LCURLY *
      rObj ::= LCURLY * rObjItemList RCURLY
      rObjItemList ::= * rObjItemList COMMA rObjItem
      rObjItemList ::= * rObjItem
      rObjItem ::= * ID COLON rExpr

                        ID shift        8      
                        ID reduce       3       ** Parsing conflict **
              rObjItemList shift        6      
                  rObjItem shift-reduce 8      rObjItemList ::= rObjItem
                 {default} reduce       3      rStmtList ::= LCURLY

これを解決する方法についての提案は、ありがたく受け入れられます。ありがとう。

4

1 に答える 1

1

enterScope()問題の核心は、ステートメント ブロックを開始するブレースの後に実行することです。ただし、ブレースの後に 2 つのトークンVARとが続く場合:は、ブロックではなくオブジェクト リテラルを開始します。そのため、2 トークン先読みなしでアクションを実行するかどうかを知ることは不可能enterScopeであり、lemon は LR(2) 文法を生成しません。その点で、問題が解決できないというあなたの意見は正しいです。しかし、もちろん解決策はあります。

おそらく、あらゆる観点 (読みやすさ、複雑さ、検証可能性) から見て最悪の解決策は、通常の LR(2)→LR(1) 変換を使用して LR(1) 文法を作成することですenterScope();。スコープが入力されていることは明らかです。これは、削減を 1 トークン遅らせることを意味します。つまり、a で始まることができるexprものとできないものです。で開始できるものについては、本質的に aと残りの;を接着できるメカニズムも提供する必要があります。式の場合、これは特に厄介です (ただし、それでも可能です)。目標は、次のように書けるようになることです。exprVARexprVARVARexpr

block(A)       ::= blockPrefix(B) RCURLY .                 { closeScope(); A = B;} 
blockPrefix(A) ::= lcurlyOpen exprNotStartingVAR(E) .      { A = E; }
blockPrefix(A) ::= lcurlyVAR(V) restOfExprStartingVar(R) . { A = makeExpr(V, R); }
blockPrefix(A) ::= blockPrefix(B) SEMI expr(E) .           { A = appendExpr(B, E); }
lcurlyOpen     ::= LCURLY .                                { openScope(); }
lcurlyVAR(A)   ::= LCURLY VAR(V) .                         { openScope(); A = V; }

これも醜いが、この特定のケースではおそらくそれほど醜くない別の方法は、変数名とそれに続くコロンを単一の字句トークン ( VAR_COLON) として認識することです。これは字句解析器を複雑にしますが (特に、変数名とコロンの間に空白やコメントが現れる構造を認識する必要があるため)、文法ははるかに単純になります。その変更により、オブジェクト リテラルは a で始まる必要があるのに対し、expr は a (または他の無関係なトークン)VAR_COLONでのみ開始できるため、競合はありません。VAR

はるかに簡単な解決策は、スコープ 継承属性を作成しようとしないことです。合成的にスコープ解決を行うと、問題は多かれ少なかれ消えます。

stmt       ::= expr SEMI | block .
stmtList   ::= stmt .
stmtList   ::= stmtList stmt .
block(A)   ::= LCURLY stmtList(B) RCURLY . { A = applyScope(newScope(), B); }
objLiteral ::= LCURLY itemList RCURLY .
objLiteral ::= LCURLY RCURLY .
itemList   ::= item .
itemList   ::= itemList COMMA item .
item       ::= VAR COLON expr .
expr       ::= VAR .
expr       ::= objLiteral .
...

その文法には競合はありませんが、スコープの処理方法が根本的に変わる可能性があります。これは、解析が進むにつれてインラインで行うのではなく、ブロックが完了したら変数名をスコープする必要があるためです。

ただし、ほとんどの言語 (Javascript を含む) では、実際にはブロックの最後でスコーピングを行う方が便利であると主張したいと思います。Javascript は、C とは異なり、最初の言及の後にローカル変数を宣言できます。ローカル関数は宣言前でも使用できます。(これは、関数宣言が実行可能な割り当てである Python とは微妙に異なりますが、スコープ規則は似ています。)

別の例として、C++ では、メンバーが別のクラス メンバー関数内で既に言及されている場合でも、クラスの宣言内の任意の場所でクラス メンバーを宣言できます。

そして、他にも多くの例があります。これらのスコープ規則は、一般に、C では不可能なスタイル オプション (C++ ではクラス定義の最後にメンバー変数定義を配置するなど) を許可することで、プログラマーに利益をもたらします。

于 2016-08-01T18:25:58.517 に答える