anchor.diff: -﻿#light
  -(*
  +﻿(*
   Курсовая работа Лебедковой Татьяны, 361гр
   на тему "Реализация алгоритма CYK для разбора языков, порожденных
   контекстно-свободными грамматиками в нормальной форме Хомского"
  
positive.code:            
     let recTable = Microsoft.FSharp.Collections.Array2D.create s.Length s.Length ([],(0,0),(0,0),[]) 
     //recTable(i,l), для l > 0
     let elem i l = for rule in rules do
                       for k in 0..(l-1) do
                          match rule with
                          |ToBranch(a,b,c) -> let nonTerminals1,_,_,_ = recTable.[i,k]
                                              let nonTerminals2,_,_,_ = recTable.[k+i+1,l-k-1]
                                              let nonTerminals,_,_,rules = recTable.[i,l]
                                              if(List.exists ((=)b) nonTerminals1) && (List.exists ((=)c) nonTerminals2)then
                                                 recTable.[i,l] <- ((a::nonTerminals),(i,k),(k+i+1,l-k-1),(rule::rules))
                          |_               -> ()                  
     //Заполнение RecognitionTable                                            
     let rec fillTable i l = if l = s.Length-1 then
                                elem i l//последний элемент таблицы
                             else if(i+l) <= (s.Length-1)then
                                     elem i l
                                     fillTable (i+1) l//продолжаем заполнять столбец
                                  else
                                     fillTable 0 (l+1)//переход на новый столбец
     //первый столбец таблицы для правил, выводящих терминал
     for rule in rules do
        for k in 0..(s.Length-1) do
  
negative.code:       match (i,l) with 
        |(_,0) -> [ToLeaf(top,leftNT.[0])]
        |_     -> currentRule::(subRecognize leftI leftL leftNT)@(subRecognize rightI rightL rightNT)
     let resultRules = if List.exists ((=)start) ((fun (a,_,_,_) -> a) recTable.[0,s.Length-1])
                       then subRecognize 0 (s.Length-1) start//если цепочка принадлежит языку L(g)
                       else []
  
     System.Console.WriteLine(s)
     System.Console.WriteLine("Rules:")
     printRules resultRules
     //printOutput resultRules start    
  
  
  
  //грамматика, допускающая операции +, * и позволяющая группировать их с помощью скобок, преобразованная в НФХ
  let testGrammar1 = (Array.ofList <| (List.map ToBranch [("E","T","N1");("N1","N2","E");("E","F","N3");("N3","N4","T");("E","N5","N6");("N6","E","N7");("E1","N2","E");("T","F","N3");("T","N5","N6");("T1","N4","T");("F","N5","N6")]) @ (List.map ToLeaf [("N2",'+');("N4",'*');("E",'a');("N5",'(');("N7",')');("T",'a');("F",'a')]),"E")
  let testGrammar2 = ((List.map ToBranch [("S","A","B");("B","N1","N2");("N1","D1","D2")])@(List.map ToLeaf [("A",'a');("D2",'c');("B",'a');("D1",'b');("N2",'d')]),"S")
  //System.Console.WriteLine("Test1:")
  //recognize testGrammar1 "a*a+a"
  
  
  let str = List.init 40 (fun i -> "(a+a)*a") |> String.concat "+"
  System.Console.WriteLine("Test2:")
  let start = System.DateTime.Now
  recognize testGrammar1 str
  printfn "Time = %A" (System.DateTime.Now - start)
  
  //System.Console.WriteLine("Test3:")
  //recognize testGrammar2 "abcd"
  System.Console.ReadLine()   
  