6

私は言語プロローグを初めて使用し、プロローグでの解析に関する割り当てを与えられました。問題を解決するために助けが必要です。

assingment には、次の文法があります。

Expr ::= + Expr Expr | * Expr Expr | Num | Xer  
Xer  ::= x | ^ x Num  
Num  ::= 2 | 3 | .... a Integer (bigger than 1) ...

トークン^は数学と同じです。5^5に等しい25。

解析は、両方の方法で機能する必要があります。インスタンス化されたリストを使用して呼び出して Ast を生成する一方で、インスタンス化された Ast を使用して呼び出しを行うと、同様のプレフィックス リストが生成されます。

私の割り当ては、これを行うプレフィックス解析を行う必要があることを示しています:
例 (Ast の値を削除): 

?- parse([+, *, 2, x, ^, x, 5 ], Ast), parse(L, Ast).  
X = ...,  
L = [+, *, 2, x, ^, x, 5]

また、解析ツリーがどのようになるかを知りたいです。

4

1 に答える 1

9

Prolog には、文脈自由文法を直接処理するための特定の形式があります: DCG (確定節文法)。あなたの例は、ほとんどすぐに DCG に変換されます。

expr --> [+], expr, expr | [*], expr, expr | num | xer.

xer --> [x] | [^], [x], num.

num --> [2] | [3] | [4] | [5].

これで、すでに文をテストできます。

?- phrase(expr, [+, *, 2, x, ^, x, 5 ]).
true ;
false.

?- phrase(expr, [+, *, *, 2, x, ^, x, 5 ]).
false.

次のように、考えられるすべての文を生成することもできます。

?- length(L, N), phrase(expr, L).
L = [2],
N = 1 ;
L = [3],
N = 1 ;
...

最後に、抽象構文ツリーを定義に追加できます。

expr(plus(A,B)) --> [+], expr(A), expr(B).
expr(mul(A,B)) --> [*], expr(A), expr(B).
expr(Num) --> num(Num).
expr(Xer) --> xer(Xer).

xer(var(x)) --> [x].
xer(pow(var(x),N)) --> [^], [x], num(N).

num(num(2)) --> [2].
num(num(3)) --> [3].
num(num(4)) --> [4].
num(num(5)) --> [5].

これで、必要に応じて使用できます。

?- phrase(expr(AST), [+, *, 2, x, ^, x, 5 ]), phrase(expr(AST),L).
AST = plus(mul(num(2), var(x)), pow(var(x), num(5))),
L = [+, *, 2, x, ^, x, 5] ;
false.

ちょっとしたヒント: DCG へのインターフェイス述語は ではありphrase/2ませんparse/2。

于 2013-11-05T20:08:46.593 に答える