Home > Archive > Prolog > January 2008 > Parsing Context-sensitive languages with Prolog
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Parsing Context-sensitive languages with Prolog
|
|
| Alessandro 2008-01-21, 8:17 am |
| Hello,
I study the possibility of parsing context-free languages with Prolog.
Head -> Body
I found the DCG (definite clause grammar).
I think that is possible with Prolog to handle context-sensitive construct :
before Head after -> before Body after
but I s a *good* exemple in Prolog, perhaps with the langage { a^n
b^n c^n } that is known to be context-sensitive (and not context-free).
Thanks :-)
| |
| Markus Triska 2008-01-21, 7:26 pm |
| Alessandro <askmeformymail@thanks.com> writes:
> I s a *good* exemple in Prolog, perhaps with the langage { a^n b^n
> c^n } that is known to be context-sensitive
What about :
anbncn --> n_x(N, a), n_x(N, b), n_x(N, c).
n_x(0, _) --> [].
n_x(s(N), X) --> [X], n_x(N, X).
Yielding:
%?- anbncn(Ls, []).
%@ Ls = [] ;
%@ Ls = [a, b, c] ;
%@ Ls = [a, a, b, b, c, c] ;
%@ Ls = [a, a, a, b, b, b, c, c, c] a
%@ Yes
--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
| |
| Alessandro 2008-01-21, 7:26 pm |
| Thanks ;-)
| |
| Jan Burse 2008-01-21, 7:26 pm |
| Markus Triska schrieb:
> Alessandro <askmeformymail@thanks.com> writes:
>
>
> What about :
>
> anbncn --> n_x(N, a), n_x(N, b), n_x(N, c).
>
> n_x(0, _) --> [].
> n_x(s(N), X) --> [X], n_x(N, X).
>
> Yielding:
>
> %?- anbncn(Ls, []).
> %@ Ls = [] ;
> %@ Ls = [a, b, c] ;
> %@ Ls = [a, a, b, b, c, c] ;
> %@ Ls = [a, a, a, b, b, b, c, c, c] a
> %@ Yes
>
More attributive grammar, than context sensitive grammar
as intially defined by chomsky.
Context sensitive by chomsky, means production rules of
the form:
A1..An --> B1..Bm
i.e. the head is allowed to contain more than one literal.
Can't be translated directly to DCG, isn't it?
Bye
P.S.: Context sensitive grammar for a^n b^n c^n n>=1 would be:
s -->
s --> y a b c
y -->
y --> y a a x
a x a --> a a x
a x b --> a b b x
b x b --> b b x
b x c --> b c c
Best Regards
| |
| Jan Burse 2008-01-21, 7:26 pm |
| > P.S.: Context sensitive grammar for a^n b^n c^n n>=1 would be:
>
> s -->
> s --> y a b c
> y -->
> y --> y a a x
> a x a --> a a x
> a x b --> a b b x
> b x b --> b b x
> b x c --> b c c
>
> Best Regards
This is more confluent (independent of rule application order):
s -->
s --> y a b c
y -->
y --> y a x
a x a --> a a x
x x a --> x a x
a x b --> a b b x
b x b --> b b x
x x b --> x b x
b x c --> b c c
x x c --> x c c
| |
| Alessandro 2008-01-21, 7:26 pm |
| I know that DCG rules aren't context-sensitive rules. I don't know a
practical parser that allows you to specify a context-sensitive grammar.
But with predicates, parameters, etc. you can match some (or all ?)
context-sensitive languages :-)
Alessandro
Jan Burse a écrit :
>
> This is more confluent (independent of rule application order):
>
> s -->
> s --> y a b c
> y -->
> y --> y a x
> a x a --> a a x
> x x a --> x a x
> a x b --> a b b x
> b x b --> b b x
> x x b --> x b x
> b x c --> b c c
> x x c --> x c c
>
| |
| Jan Burse 2008-01-22, 7:25 pm |
| Alessandro schrieb:
> but I s a *good* exemple in Prolog, perhaps with the langage { a^n
> b^n c^n } that is known to be context-sensitive (and not context-free).
>
> Thanks :-)
This is a nice paper:
http://www.idi.ntnu.no/emner/tdt427...icalGrammar.pdf
See page 15ff for a treatment.
| |
| Peter Van Weert 2008-01-23, 4:28 am |
| Alessandro wrote:
> I know that DCG rules aren't context-sensitive rules. I don't know a
> practical parser that allows you to specify a context-sensitive grammar.
Maybe you should have a look at the CHR grammars formalism of Henning
Christiansen (available at http://akira.ruc.dk/~henning/chrg/). It is
implemented for SICStus 3, but shouldn't be to difficult to port to
other Prolog+CHR systems. From the abstract of the journal paper
(published version available at http://arxiv.org/abs/cs/0408027v1):
"The formalism extends previous logic programming based grammars with a
form of context-sensitive rules and the possibility to include
extra-grammatical hypotheses in both head and body of grammar rules."
Cheers,
Peter
| |
| bart demoen 2008-01-23, 7:18 pm |
| On Mon, 21 Jan 2008 21:27:04 +0100, Alessandro wrote:
> But with predicates, parameters, etc. you can match some (or all ?)
> context-sensitive languages :-)
Prolog is Turing-complete. Surely it can do all context-sensitive
languages. You don't even need the whole power of Prolog/Turing machines
to do them :-)
Cheers
Bart Demoen
|
|
|
|
|