6

我在这个语法中的左递归有一个小问题。我正在尝试在 Prolog 中编写它，但我不知道如何删除左递归。

<expression> -> <simple_expression>
<simple_expression> -> <simple_expression> <binary_operator> <simple_expression>
<simple_expression> -> <function>
<function> -> <function> <atom>
<function> -> <atom>
<atom> -> <number> | <variable>

<binary_operator> -> + | - | * | /

expression(Expr) --> simple_expression(SExpr), { Expr = SExpr }.
simple_expression(SExpr) --> simple_expression(SExpr1), binary_operator(Op), simple_expression(SExpr2), { SExpr =.. [Op, SExpr1, SExpr2] }.
simple_expression(SExpr) --> function(Func), { SExpr = Func }.
function(Func) --> function(Func2), atom(At), { Func = [Func2, atom(At)] }.
function(Func) --> atom(At), { Func = At }.

我写过类似的东西，但它根本不起作用。如何更改它以使该程序正常工作？

4

4 回答 4

1

只有在您使用反向链接时才会出现问题。在前向链接中，可以直接处理左递归语法规则。提供形式的语法规则：

NT ==> NT'

不要形成一个循环。您也可以使用辅助计算，即{}/1，如果您将它们放在主体的非终结符之后，并且头部中的非终结符没有专门用于辅助计算的参数。即自下而上的条件。

这是一个左递归语法示例，它在前向链接中完美地工作：

:- use_module(library(minimal/chart)).
:- use_module(library(experiment/ref)).

:- static 'D'/3.

expr(C) ==> expr(A), [+], term(B), {C is A+B}.
expr(C) ==> expr(A), [-], term(B), {C is A-B}.
expr(A) ==> term(A).

term(C) ==> term(A), [*], factor(B), {C is A*B}.
term(C) ==> term(A), [/], factor(B), {C is A/B}.
term(A) ==> factor(A).

factor(A) ==> [A], {integer(A)}.

这是图表解析器源代码的链接。从此链接还可以找到前向链接器的源代码。下面显示了一个示例会话：

?- use_module(library(minimal/hypo)).

?- chart([1,+,2,*,3], N) => chart(expr(X), N).
X = 7

在解析过程中，图表解析器将以自下而上的方式填充图表。对于上述产生式中的每个非终结 p/n，将有事实 p/n+2。以下是上述示例的图表结果：

:- thread_local factor/3.
factor(3, 4, 5).
factor(2, 2, 3).
factor(1, 0, 1).

:- thread_local term/3.
term(3, 4, 5).
term(2, 2, 3).
term(6, 2, 5).
term(1, 0, 1).

:- thread_local expr/3.
expr(3, 4, 5).
expr(2, 2, 3).
expr(6, 2, 5).
expr(1, 0, 1).
expr(3, 0, 3).
expr(7, 0, 5).
于 2012-05-19T16:27:26.197 回答
1

您的程序的问题确实是左递归；它应该被删除，否则你会陷入无限循环

要删除立即左递归，请替换表单的每个规则

A->A a1|A a2|....|b1|b2|....

和：

A -> b1 A'|b2 A'|....
A' -> ε | a1 A'| a2 A'|....

所以功能是

function -> atom, functionR.
funtionR -> [].

维基页面

于 2012-05-19T08:40:02.427 回答
0

@thanosQR 的答案相当不错，但适用于比 DCG 更一般的上下文，并且需要更改解析树。实际上，解析的“结果”已被删除，这不好。

如果您只对解析表达式感兴趣，我在这里发布了一些有用的东西。

于 2012-05-19T09:27:57.743 回答
0

Answer set programming (ASP) provides another route to implement grammars. ASP can be implemented with non-deterministic forward chaining and this is what our library(minimal/asp) provides. The result of ASP are then different models

of the given rules. We use here ASP models to represent a Cocke-Younger-Kasami chart. We begin our chart with the given words we want to parse which are represented by word/3 facts. Compared to DCG we do not pass around anymore

lists but instead word positions. The Prolog text calc2.p shows such an implementation of an ASP based parser. All rules are now (<=)/2 rules, means they are forward chaining rules. And all heads are now choose/1 heads, means they make a ASP

model choice. We explain how expr is realized, the term is realized similary. Since we do not have an automatic translation, we did the translation manually. We will provide the words from right to left and only trigger at the beginning

of each attributed grammar rule:

choose([expr(C, I, O)]) <= posted(expr(A, I, H)), word('+', H, J), term(B, J, O),  C is A+B.
choose([expr(C, I, O)]) <= posted(expr(A, I, H)), word('-', H, J), term(B, J, O),  C is A-B.
choose([expr(B, I, O)]) <= posted(word('-', I, H)), term(A, H, O), B is -A.
choose([expr(A, I, O)]) <= posted(term(A, I, O)).

As can be seen no extra predicate expr_rest was needed and the translation from grammar to rules was 1-1. The same happens for term. The execution of such a grammar requires that first the words are posted from right to left, and the result can

then be read off from the corresponding non-terminal:

?- post(word(78,7,8)), post(word('+',6,7)), post(word(56,5,6)), post(word('*',4,5)),
    post(word(34,3,4)), post(word('+',2,3)), post(word(12,1,2)), post(word('-',0,1)),
    expr(X,0,8).
X = 1970

We have also made a Prolog text show.p which allows visualizing the ASP model as a parsing chart. We simply use the common triangular matrix representation. The parsing chart for the above arithmetic expression has looks as follows:

enter image description here

Peter Schüller (2018) - Answer Set Programming in Linguistics
https://peterschueller.com//pub/2018/2018-schueller-asp-linguistics.pdf

User Manual - Module "asp"
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/15_min/10_docu/02_reference/07_theory/01_minimal/06_asp.html

于 2020-01-09T14:34:45.390 回答