prolog - 涉及大括号的语法

Question

我正在尝试解决序言中的 DCG 语法并在一定程度上取得了成功，但我一直在评估涉及此类大括号的表达式。 expr( T, ['(', 5, +, 4, ')', *, 7], []),

expr(Z) --> num(Z).
expr(Z) --> num(X), [+], expr(Y), {Z is X+Y}.
expr(Z) --> num(X), [-], expr(Y), {Z is X-Y}.
expr(Z) --> num(X), [*], expr(Y), {Z is X*Y}.
num(D) --> [D], {number(D)}.

eval(L, V, []) :- expr(V, L, []).

Answer 1

Prolog 的 DCG 语法实现的解析器是递归下降 LL(something)(预测)语法。它从左到右遍历输入并生成最左推导。它们很容易制作，但语法必须符合一些限制:

它们不能是左递归的。可能/将会导致无限递归。这意味着在遵循递归路径之前必须从输入流中删除至少一个符号( token )。重构语法以消除左递归是一项相当机械的练习，尽管很乏味。请参阅任何不错的编译器书籍来了解如何做到这一点。

运算符优先级通常内置于语法本身的结构中。以下 BNF 表示法显示了一种定义递归下降语法以解析/评估简单算术表达式的方法:

ArithmeticExpression     : AdditiveExpression
                         ;

AdditiveExpression       : MultiplicativeExpression
                         | MultiplicativeExpression '+' AdditiveExpression
                         | MultiplicativeExpression '-' AdditiveExpression
                         ;

MultiplicativeExpression : ExponentialExpression
                         | ExponentialExpression '*' MultiplicativeExpression
                         | ExponentialExpression '/' MultiplicativeExpression
                         | ExponentialExpression '%' MultiplicativeExpression
                         ;

ExponentialExpression    : UnaryExpression
                         | UnaryExpression '^' ExponentialExpression
                         ;

UnaryExpression          : '-' UnaryExpression
                         | AtomicExpression
                         ;

AtomicExpression         : '(' ArithmeticExpression ')'
                         | ['0'..'9']+
                         ;

每个运算符优先级级别的术语都是根据下一个更高优先级的表达式构建的。因此任意算术表达式只是一个单一的加法表达式。

每个加法表达式都是 1 个或多个乘法表达式，由加法和减法运算符连接。

每个乘法表达式都是 1 个或多个指数表达式，由乘法、除法和余数运算符连接。

每个指数表达式都是一个一元表达式，带有一个选项指数运算符，后跟另一个一元表达式。

每个一元表达式要么是一个原子表达式，要么是一个一元减号后跟另一个一元表达式。

每个原子表达式要么是括在括号中的任意算术表达式，要么是无符号整数标记。

将上述内容翻译成 Prolog 的 DCG 语法应该很简单。如何评价语法中每个子句所代表的术语应该是不言而喻的。