レモンパーサーの競合を取得する

Question

私はlemonを使って、javascriptのような言語のための簡単なパーサを書こうとしています。私は競合エラーを解決することができませんし、それは解決できない問題であると思われます。最初は、代入文を含む文ブロックであり、第二は、オブジェクトを定義する式ステートメントである

{x = 10;} 

と

{x:10}; 

：

競合がための文法の間です。

両方を解析する文法が矛盾します。次のように最小限のコードは次のとおりです。

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 

私はこれを解決する方法上の任意の提案を感謝して受け入れられる：

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. 

アウトファイルには、以下を示しています。ありがとう。

Answer 1

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

おそらく、任意の視点から最悪ソリューション（読みやすさ、複雑さ、verificabilityは）あなたがenterScope();アクションを呼び出すことができます通常のLR（2）→ LR（1）変換を使用して、LR（1）文法を作成することですスコープが入力されたことが明らかな時点でこれは、減少を1トークン遅延させることを意味します。これは、exprを2つの分離した非終端記号に分割することを意味します。exprは、VARで始まるものとできないものです。で始まるexprの場合は、VARと残りのexprを一緒に接着することができます。表現の場合は、特に醜いですが（それでも可能です）。

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）：目標は、書くことができるようにすることです。これはレクサーを複雑にしますが（特に、空白やコメントが変数名とコロンの間に現れる構造を認識する必要があるため）、文法がはるかに単純になります。この変更では、オブジェクトリテラルはVAR_COLONで始まる必要があり、exprはVAR（または他の無関係なトークン）で始まるだけなので、競合はありません。

より簡単な解決策は、スコープinherited attributeを作成しないようにすることです。文法は何の競合がないことを

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を含む）では、実際にはブロックの終わりでスコープを実行する方が便利で、AST上では解析後のパースとして扱う方が便利です。 Javascriptは、Cとは異なり、ローカル変数が最初の言及の後に宣言されることを可能にします。ローカル関数は宣言の前に使用することもできます。 （これはPythonとは微妙に異なりますが、関数宣言は実行可能な代入ですが、有効範囲の規則は似ています）。

もう1つの例として、C++では、クラスメンバーがクラスの宣言内のどこにでも宣言することができますメンバは別のクラスメンバ関数の中ですでに言及されています。

他にも多くの例があります。これらの有効範囲規則は一般的に、C言語では不可能なスタイル定義オプション（C++のクラス定義の最後にメンバー変数定義を入れるなど）を許可することでプログラマにとって有益です。