使用DCG删除左递归语法 [英] Removing left recursion grammar using DCG

问题描述

以下语法具有左递归

语法:

Expr ::= E1|E2|E3|E4|E5|E6|E7

E1 ::= "(" Expr ")"
E2 ::= "not""(" Expr ")"
E3 ::= Expr "=>" Expr
E4 ::= Expr "=/=" Expr
E5 ::= Expr "*" Expr
E6 ::= Func "=>" Func
Func ::= Ter  (Ters)+","
...

并且我正在尝试以这种方式删除LR；

and I'm trying to remove the LR in this manner ;

Expr ::= E1|...

E1 ::= Expr "*" Expr ==>   E1   ::= Expr Expr'
                           Expr'::= *Expr Expr'

但是问题仍然存在，如何解决它才能使该程序正常工作?

but the problem still exists, How to fix it to get this program working?

示例查询和测试

| ?- phrase(e(T),"not((2+3)=/=5))").
! Resource error: insufficient memory

期望的答案

 | ?- phrase(e(T),"not((2+3)=/=5))").
    error 13 ')'
 | ?- phrase(e(T),"(2+3)=>>5))").
    error 7 '>'

推荐答案

您可以尝试自底向上解析.

You could try to bottom parse bottom up.

这是处理器:

:- op(150, xfx, ---> ).

parse(Phrase) -->
    leaf(SubPhrase),
    lc(SubPhrase, Phrase).

leaf(Cat) --> [Word], {word(Word,Cat)}.
leaf(Phrase) --> {Phrase ---> []}.

lc(Phrase, Phrase) --> [].

lc(SubPhrase, SuperPhrase) -->
    {Phrase ---> [SubPhrase|Rest]},
    parse_rest(Rest),
    lc(Phrase, SuperPhrase).

parse_rest([]) --> [].
parse_rest([Phrase|Phrases]) -->
    parse(Phrase),
    parse_rest(Phrases).

一个语法规范的例子(但是func似乎不正确，并且没有优先级或关联性规范...)

An example of grammar specification (but func seems ill specified, and there is no precedence or associativity specification...)

expr(E) ---> [opp, expr(E), clp].
expr(not(E)) ---> [not, opp, expr(E), clp].
expr(impl(L,R)) ---> [expr(L), impl, expr(R)].
expr(ne(L,R)) ---> [expr(L), ne, expr(R)].
expr(mul(L,R)) ---> [expr(L), mul, expr(R)].
expr(add(L,R)) ---> [expr(L), add, expr(R)].
expr(func(L,R)) ---> [func(L), impl, func(R)].
expr(num(N)) ---> [num(N)].

func(f(F, As)) ---> [name(F), args(As)].

args([A|As]) ---> [arg(A), comma, args(As)].
args([A]) ---> [arg(A)].
arg(E) ---> [expr(E)].


word(N, name(N)) :- atom(N).
word(N, num(N)) :- integer(N).
word(=>, impl).
word('(', opp).
word(')', clp).
word(*, mul).
word(+, add).
word(not, not).
word(=/=, ne).
word(',', comma).

示例运行

?- phrase(parse(E), [not,'(',2,+,2,*,3,')']).
E = func(f(not, [mul(add(num(2), num(2)), num(3))])) ;
E = func(f(not, [add(num(2), mul(num(2), num(3)))])) ;
E = expr(not(mul(add(num(2), num(2)), num(3)))) ;
E = arg(not(mul(add(num(2), num(2)), num(3)))) ;
E = args([not(mul(add(num(2), num(2)), num(3)))]) ;
E = expr(not(add(num(2), mul(num(2), num(3))))) ;
E = arg(not(add(num(2), mul(num(2), num(3))))) ;
E = args([not(add(num(2), mul(num(2), num(3))))]) ;
false.

但是也许这对您的任务没有什么用...

but maybe this is no so useful for your task...

这篇关于使用DCG删除左递归语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！