9
$\begingroup$

I have two lists:

grammarNonterminal = {{VP,{V,NP}},{NP,{D,N}},{S,{NP,VP}}} sentence = {{D,"the"},{N,"man"},{V,"hit"},{D,"the"},{N,"table"}}

I want to make a function which changes sentence into the followings when the function takes grammarNonterminal and sentence as arguments.

⇒ {{NP, {D, "the"}, {N,"man"}}, {V, "hit"}, {D, "the"}, {N, "table"}}} , {{{D, "the"}, {N, "man"}, {V, "hit"}, {NP, {{D, "the"}, {N, “table"}}}, ⇒ {{NP, {D, "the"}, {N, "man"}}, {V, "hit"}, {NP, {D, "the"}, {N, "table"}}}},{{D, "the"}, {N, "man"}, {VP, {{V, "hit"}, {NP, {D, "the"}, {N, "table"}}} ⇒ {{{NP, {D, "the"}, {N, "man"}}, {VP, {{V, "hit"}, {NP, {{D, "the"}, {N, "table"}}}}} ⇒ {{{S, {NP, {D, "the"}, {N, "man"}}, {VP, {{V, "hit"}, {NP, {{D, "the"}, {N, "table"}}}}}}

I know I have to use ReplaceList, Map and Union to achieve this.

Is there a simple way to do this?

What I wanted to do is something like below.

First, you make a function applyRule:

applyRule[sentence_, r_] := ReplaceList[sentence,{x___,c : Apply[PatternSequence, {#, _} & /@ r[[2]] ], y___} -> {x, ReplacePart[r, 2 -> {c}], y}]; r = {NP,{D,N}} applyRule[sentence,r] = {{{NP, {{D, "the"}, {N, "man"}}}, {V, "hit"}, {D, "the"}, {N, "table"}}, {{D,"the"}, {N, "man"}, {V, "hit"}, {NP, {{D, "the"}, {N, "table"}}}}}

And then make a function to change sentence into

{{{S, {NP, {D, "the"}, {N, "man"}}, {VP, {{V, "hit"}, {NP, {{D, "the"}, {N, "table"}}}}}}

by using applyRule, Map, and Union.

I tried

Union[Map[applyRule[sentence, #] &, grammarNonterminal]

but this doesn't give me the result that I want.

Improve this question
$\endgroup$
5
  • $\begingroup$ I really think this requires more explanation. We need at least a set of rules for the replacements. Why, for instance, does the second sequence of D, word, N, word get replaced first, then only later the other one? How do we specify the order in which terms get replaced? Must it happen from the end of the sentence backward? Probably not, because eventually, the D, word, N, word at the beginning of the sentence gets replaced, but that's only after nothing else can be replaced. Anyway, more info please! $\endgroup$ Commented Dec 13, 2015 at 7:02
  • $\begingroup$ Also: a comment about usage. Do not use capital letters for symbols, because all built-in Mathematica functions start with capital letters. You already have problems because both D and N have built-in Mathematica meanings. I recommend using vp, np, d, v, and n. $\endgroup$ Commented Dec 13, 2015 at 7:03
  • 1
    $\begingroup$ Wait wait! A couple of things! First, don't be so hasty to accept! This kind of question (if more information is included) can attract more answers, and better answers since there are a lot of Mathematica experts here who might actually have domain knowledge relevant to this problem, but people tend to avoid already accepted answers. Second, please answer the questions I had if you can! Third, it is considered bad form to accept without upvoting (I'm not sure by whom other than me, but anyway). $\endgroup$ Commented Dec 13, 2015 at 7:32
  • $\begingroup$ @march Thanks for pointing those out. I'm new to Mathematica and here and I mixed up "accept" with "upvoting". For the order, it does't necessarily have to be like that as long as you get {{{S, {NP, {D, "the"}, {N, "man"}}, {VP, {{V, "hit"}, {NP, {{D, "the"}, {N, "table"}}}}}} in the end. I just edited the question to add some explanations. $\endgroup$ Commented Dec 13, 2015 at 8:55
  • $\begingroup$ This might be overkill for the type of problem you want to tackle, but I have code here for a top-down (LL) parser, applied to sentences from a simple grammar. $\endgroup$ Commented Dec 13, 2015 at 21:27

1 Answer 1

Reset to default
9
$\begingroup$

Anyway, despite all of my comments, here's my best go at this problem. It's not general, and it doesn't exactly match your syntax, so perhaps someone else will come along and fix it, but this is at least a good start.

I've taken the liberty of changing your notation in a number of ways.

  • Lower-case letters for the parts-of-speech.

  • Instead of {d, "the"} I will use d["the"].

Let's define our parser as the following (neatened up per a comment from Simon Woods):

parseList[sentence_] := Delete[FixedPointList[ # /. { {a___, x : PatternSequence[_np, _vp], b___} :> {a, s[x], b}, {a___, x : PatternSequence[_v, _np], b___} :> {a, vp[x], b}, {a___, x : PatternSequence[_d, _n], b___} :> {a, np[x], b} } & , sentence ] , -1]

Due to the way that ReplaceAll works, once it replaces an entire expression, it doesn't replace sub-expressions of that expression. I'm taking advantage of that to replace one thing at a time so that we can get out a list of steps. I have also made the more global rules first; for instance, the rule that puts together the whole sentence comes first in the list. Finally, we use FixedPointList in order to replace phrases in this sentence until it doesn't change anymore.

If you don't care about the steps taken to get to the end, we can instead use ReplaceRepeated:

parse[sentence_] := sentence //. { {a___, x : PatternSequence[_np, _vp], b___} :> {a, s[x], b}, {a___, x : PatternSequence[_v, _np], b___} :> {a, vp[x], b}, {a___, x : PatternSequence[_d, _n], b___} :> {a, np[x], b} } // First

The sentence is

sentence = {d["the"], n["man"], v["hit"], d["the"], n["table"]};

Then,

parSen = parse[sentence] (* s[np[d["the"], n["man"]], vp[v["hit"], np[d["the"], n["table"]]]] *)

or

(list = parseList[sentence]) // MatrixForm

enter image description here

It doesn't exactly do things in exactly the order you requested, but it gets this simple job done.

The nice thing about this particular syntax (e.g. using d["the"] instead of {d, "the"}) is that we can display the final parsed sentence in a nice TreeForm:

TreeForm@parSen

enter image description here

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This is a neat approach. Your rules could be written more concisely by naming the pattern sequence, e.g. {a___, x : PatternSequence[_d, _n], b___} :> {a, np[x], b} $\endgroup$ Commented Dec 13, 2015 at 14:13
  • $\begingroup$ @SimonWoods. Yes absolutely! That is certainly neater. I will add it to the post. $\endgroup$ Commented Dec 13, 2015 at 17:48

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.