5

P => プログラム K => ブロック

S => シングルコマンド

C => コマンド

E =>式

B => ブール式式

私 => 識別子

N > 数値

P ::= K.

K ::= 開始 C 終了

C ::= C1; C2 | S

S ::= 私 := E | (B) の場合 S | (B) の場合 S1 でなければ S2 | while (B) do S | (B) まで C を繰り返す | ケイ | Eを印刷する

E ::= − E | E1 + E2 | E1 − E2 | 第1話第2話 | E1 div E2 | E1 mod E2 | (E) | 私 | 私 | N

B ::= E1 = E2 | E1 > E2 | E1 < E2 | E1 != E2 | Bじゃない | B1とB2 | B1またはB2 | (ロ)

プロローグで DCG パーサーを記述できるように、E と B のあいまいさを取り除くことになっています。

4

2 に答える 2

5

Prolog はトップダウンで評価し、次に LL文法テクニックを適用できます。DCG は LL(1) よりも強力ですが、左再帰を排除する必要があります。

B処理が簡単です。生産の左の要素です。

B ::= E Bx | not B | (B)
Bx ::= = E | > E | < E | != E | and B | or B

ミスmulトークンがさらにあいまいさをもたらすため、E はより困難です。とりあえず

E ::= − E | (E) | I | N | El
El ::= Ex E | epsilon
Ex ::= + El | − El | div El | mod El

DCG のイプシロン (空の生産) は、このように記述できます。

epsilon --> [].

(B と E の両方で) 優先順位と結合性を処理する必要がある場合は、さらに作業が必要になります。作業スキーマについては、この古い回答を参照できます。

于 2012-10-30T08:37:57.233 に答える
3

@chac はすでに非常に良い回答を提供しており、これを解決する通常の方法を示しています。

あなたの質問を別の方法で読んでみましょう。「Prolog で DCG パーサーを記述できるように、E と B のあいまいさを取り除く必要があります」。つまり、Prolog で DCG パーサーを記述できる範囲でのみあいまいさを取り除く必要があります。良いニュースがあります。DCG パーサーを作成するためにあいまいさをまったく取り除く必要はありません。方法は次のとおりです。

あいまいさの原因は、次のようなプロダクションです

C ::= C ; C

または他の演算子 + - 並置 div mod と

簡略化された文法に固執させてください。

E ::= E + E | 「1」

これを次のようにエンコードできます

e --> "1".
e --> e, "+", e.

残念ながら、Prolog は次のようなクエリでは終了しません。

?- L = "1+1+1", phrase(e,L).
L = "1+1+1" ;
ERROR: Out of local stack

実際には終了しますが、それは私のコンピューターのメモリが有限であるためです...

さえありません：

?- L = "1", phrase(e,L).
L = "1" ;
ERROR: Out of local stack

これはあいまいさの問題ですか？いいえ！これは、左再帰を直接処理できない Prolog の手続き上の問題です。Prologに処理させる方法は次のとおりです。

e([_|S],S) --> "1".
e([_|S0],S) --> e(S0,S1), "+", e(S1,S).

?- L = "1+1+1", フレーズ(e(L,[]),L).
L = "1+1+1" ;
L = "1+1+1" ;
間違い。

?- L = "1", 句(e(L,[]),L)。
L = "1" ;
間違い。

現時点では、文法のみを定義していますが、ほとんどの場合、対応する構文ツリーも確認する必要があります。

e(整数(1), [_|S],S) --> "1".
e( plus(L,R), [_|S0],S) --> e( L, S0,S1), "+", e( R, S1,S).

?- L = "1+1+1", フレーズ(e(ツリー, L,[]),L).
L = "1+1+1",
ツリー = プラス (整数 (1)、プラス (整数 (1)、整数 (1))) ;
L = "1+1+1",
ツリー = プラス (プラス (整数 (1)、整数 (1))、整数 (1)) ;
間違い。

plusここで、 !にはあいまいさがあることがわかります。元の文法では、(1+1)+1 と 1+(1+1) の両方が受け入れられましたが、対応するセマンティクスが結合性を保証している限り、それ自体は問題ありません。ほとんどの場合、これは左結合、つまり (1+1)+1 を意味するように明確化されますが、これはすべての中置演算子に当てはまるわけではありません。

于 2012-10-30T16:44:59.760 に答える