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.

  • $\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$ – march Dec 13 '15 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$ – march Dec 13 '15 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$ – march Dec 13 '15 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$ – R.Teek Dec 13 '15 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$ – Daniel Lichtblau Dec 13 '15 at 21:27

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"]};


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


(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:


enter image description here

  • 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$ – Simon Woods Dec 13 '15 at 14:13
  • $\begingroup$ @SimonWoods. Yes absolutely! That is certainly neater. I will add it to the post. $\endgroup$ – march Dec 13 '15 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.