In order to process natural language more effectively, a semantic relevancy calculating model of natural language was proposed, and the k-pruning algorithm for solving the model was researched. In the model, the best parsing process for a sentence could be determined by the value of semantic relevancy of the sentence; the two-level semantic structure of a sentence were analyzed, and two grammar rules were used to describe the two-level semantic structure; In the process of solving the model, a state tree would be generated; the k-pruning algorithm could be used to delete the states with less semantic relevancy when searching the state tree, and the computational complexity could be effectively reduced and the approximate solution could be acquired. Finally experiments were finished to verify the effectiveness of the algorithm.