Как реализовать алгоритм синтаксического анализа CYK в Ruby? - PullRequest
Новая
       55

Как реализовать алгоритм синтаксического анализа CYK в Ruby?

0 голосов
/ 16 марта 2019

Я пытаюсь реализовать алгоритм CYK в Ruby в соответствии с псевдокодом из Википедии .Моя реализация не может создать правильную таблицу разбора.В приведенном ниже методе grammar является членом моего собственного класса грамматики.Вот код: 

# checks whether a grammar accepts given string
# assumes input grammar to be in CNF

def self.parse(grammar, string)
    n = string.length
    r = grammar.nonterminals.size
    # create n x n x r matrix
    tbl = Array.new(n) { |_| Array.new(n) { |_| Array.new(r, false) } }
    (0...n).each { |s| 
        grammar.rules.each { |rule| 
            # check if rule is unit production: A -> b
            next unless rule.rhs.size == 1
            unit_terminal = rule.rhs[0]
            if unit_terminal.value == string[s]
                v = grammar.nonterminals.index(rule.lhs)
                tbl[0][s][v] = true
            end
        }
    }
    (1...n).each { |l| 
        (0...n - l + 1).each { |s| 
            (0..l - 1).each { |p| 
                # enumerate over A -> B C rules, where A, B and C are
                # indices in array of NTs
                grammar.rules.each { |rule| 
                    next unless rule.rhs.size == 2
                    a = grammar.nonterminals.index(rule.lhs)
                    b = grammar.nonterminals.index(rule.rhs[0])
                    c = grammar.nonterminals.index(rule.rhs[1])
                    if tbl[p][s][b] and tbl[l - p][s + p][c]
                        tbl[l][s][a] = true
                    end
                }
            }
        }
    }
    v = grammar.nonterminals.index(grammar.start_sym)
    return tbl[n - 1][0][v]
end

Я проверил это на этом простом примере: 

grammar:
A -> B C
B -> 'x'
C -> 'y'

string: 'xy'

Таблица разбора tbl была следующей: 

[[[false, true, false], [false, false, true]],
[[false, false, false], [false, false, false]]]

Проблема определенно заключается во второй части алгоритма - подстроки длиной больше 1. Первый слой (tbl[0]) содержит правильные значения.

Помощь очень ценится.

1 Ответ

1 голос
/ 18 марта 2019

Проблема заключается в переводе массивов на основе 1 в псевдокоде в массивы на основе 0 в вашем коде. Это становится очевидным, когда вы смотрите на первые индексы в условии tbl[p][s][b] and tbl[l-p][s+p][c] в самом первом запуске цикла. Псевдокод проверяет tbl[1] and tbl[1], а ваш код проверяет tbl[0] and tbl[1].

Я думаю, что вы должны сделать коррекцию на основе 0, когда вы обращаетесь к массиву, а не в диапазонах для l и p. В противном случае расчеты с индексами неверны. Это должно работать: 

 (2..n).each do |l|
    (0...n - l + 1).each do |s|
      (1..l - 1).each do |p|
        grammar.rules.each do |rule|
          next unless rule.rhs.size == 2
          a = grammar.nonterminals.index(rule.lhs)
          b = grammar.nonterminals.index(rule.rhs[0])
          c = grammar.nonterminals.index(rule.rhs[1])
          if tbl[p - 1][s][b] and tbl[l - p - 1][s + p][c]
            tbl[l - 1][s][a] = true
          end
        end
      end
    end
  end
...