5

C の論理式と整数演算式のサブセットを生成する次の文法を用意しました。

Expression:
    LogicalOrExpression
    LogicalOrExpression ? Expression : LogicalOrExpression

LogicalOrExpression:
    LogicalAndExpression
    LogicalOrExpression || LogicalAndExpression

LogicalAndExpression:
    EqualityExpression
    LogicalAndExpression && RelationalExpression

EqualityExpression:
    RelationalExpression
    EqualityExpression EqualityOperator RelationalExpression

EqualityOperator:
    ==
    !=

RelationalExpression:
    AdditiveExpression
    RelationalExpression RelationalOperator AdditiveExpression

RelationalOperator:
    <
    >
    <=
    >=

AdditiveExpression:
    MultiplicativeExpression
    AdditiveExpression AdditiveOperator MultiplicativeExpression

AdditiveOperator:
    +
    -

MultiplicativeExpression:
    UnaryExpression
    MultiplicativeExpression MultiplicativeOperator UnaryExpression

MultiplicativeOperator:
    *
    /
    %

UnaryExpression:
    PrimaryExpression
    UnaryOperator UnaryExpression

UnaryOperator:
    +
    -
    !

PrimaryExpression:
    BoolLiteral    // TERMINAL
    IntegerLiteral // TERMINAL
    Identifier     // TERMINAL
    ( Expression )

shift/reduce 構文解析を試してみたいので、この文法が LR(k) である最小の k (もしあれば) を知りたいですか? (より一般的には、可能であれば任意の文法から k を決定する方法は?)

4

2 に答える 2

2

サンプル文法は、（ほぼ）演算子優先順位文法またはフロイド文法（FG）です。FGにするには、右側が単一の終端記号のみで構成される非終端記号をマクロ展開する必要があります。これは、演算子優先順位文法は演算子文法である必要があり、演算子文法には権利がないという機能があるためです。手側には2つの連続した非終端記号があります。

すべての演算子優先文法はLR(1)です。演算子文法にprecedenceプロパティがあるかどうかを示すことも簡単です。特に、文法のように、すべての端末が正確に1つの右側に表示される場合は簡単です。すべての端末が正確に1つの右側に表示される演算子文法は、常に演算子優先文法[1]であり、その結果、常にLR(1)です。

FGは文法の大きなクラスであり、それらのいくつかは有用でさえあり（たとえば、Algol 60はFGによって記述されています）LR(k)、k答えは常に「はい、K == 1"。正確を期すために、ここにプロパティがあります。G文法が4タプル（N、Σ、P、S）である通常の規則を使用します。ここで、は非終端記号Nのセットです。Σは端末のPセットであり、プロダクションのセットでありS、開始記号です。Vのために書きN ⋃ Σます。どの文法でも、次のようになります。

N ⋂ Σ = ∅
S ∈ N
P ⊂ V+ × V*

「文脈自由」要件は制限Pがあるため、すべての左側が単一の非終端記号になります。

P ⊂ Σ × V*

演算子文法でPは、さらに制限されます。右側が空になることはなく、右側に2つの連続する非終端記号がないこともあります。

P ⊂ Σ × (V+ − V*ΣΣV*)

演算子の優先順位文法では、⋖、⋗、≐の3つの優先順位関係を定義します。Leadsこれらは、関係と[2]の観点から定義されていTrailsます。ここで、 `

T Leads V iff T is the first terminal in some string derived from V
T Trails V iff T is the last terminal in some string derived from V

それで：

t1 ⋖ t2 iff ∃v ϶ t2 Leads v ∧ N→V*t1vV* ∈ P
t1 ⋗ t2 iff ∃v ϶ t1 Trails v ∧ N→V*vt2V* ∈ P
t1 ≐ t2 iff N→V*t1t2V* ∈ P ∨ N→V*t1V't2V* ∈ P

これらの関係についての直感的な考え方は次のとおりです。通常、導出を行うときは、LHSの代わりにRHSを使用しますが、⋖ RHS ⋗代わりに使用するとします。次に、非終端記号を削除し、連続する⋖と⋗の文字列を単一の記号に折りたたんで、最後に、間に演算子がない任意の2つの連続する終端記号の間に≐を追加することにより、派生を変更できます。それから、関係を読み上げます。

これで、任意の演算子文法でその計算を実行できますが、上記の関係を排他的にすることを強制するものはありません。演算子文法は、これら3つの関係が相互に排他的である場合、正確にはフロイド文法です。

演算子文法が相互に排他的な優先順位関係を持っていることを確認するのは簡単です。Leadsそして、とTrailsを推移閉包する必要があります。これは大まかに（実際には非終端記号の数と生成の数の積です）。そこから、優先順位の関係は、文法内のすべてのプロダクションに対する1回の線形スキャンで計算できます。FirstLastO(|G|2)O(|G|)

于 2012-12-21T01:59:38.103 に答える
1

Donald Knuths On the Translation of Languages from Left to Right から、要約すると、

ある k に対して文法が LR( k ) であるかどうかの問題が決定不能であることを示し、

言い換えると、

文法 G が与えられたとき、「∃k.G ∊ LR(k)」は決定不能です。

したがって、一般的にできる最善の方法は、LR(0)、次に LR(1)、LR(2) などのパーサーを構築することです。ある時点で成功するか、ある時点でkのときにあきらめる可能性があります。が大きくなります。

この特定の文法

この特定のケースでは、あなたが与える文法が LALR(1) であることをたまたま知っています。つまり、それは LR(1) でなければなりません。私は似たような言語の LALR パーサーを書いたので、これを知っています。明らかな理由で LR(0) にすることはできません (文法 {A -> x, A -> A + x} は LR(0) ではありません)。

于 2012-12-20T19:59:16.417 に答える