Как разобрать контекстно-зависимую грамматику?

Question

CSG похож на CFG, но символ сокращения кратен.

Итак, могу ли я просто использовать анализатор CFG для анализа CSG с сокращением производства на несколько терминалов или нетерминалов?

подобно

1. S → a bc
2. S → a S B c
3. c B → W B
4. W B → W X
5. W X → B X
6. B X → B c
7. b B → b b

Когда мы встретимся W Xмы можем просто уменьшить W X в W B?

Когда мы встретимся W Bмы можем просто уменьшить W B в c B?

Так что, если парсер CSG основан на парсере CFG, написать несложно, правда?

Но когда я проверил вики, он сказал, что для разбора CSG, мы должны использовать linear bounded automaton,

Что такое linear bounded automaton?

Answer 1

Контекстно-зависимые грамматики недетерминированы. Таким образом, вы не можете предполагать, что сокращение будет иметь место, просто потому, что RHS оказывается видимым в какой-то момент деривации.

LBA (линейно-ограниченные автоматы) также недетерминированы, поэтому они не являются практическим алгоритмом. (Вы можете смоделировать одно с помощью обратного отслеживания, но нет удобного ограничения на количество времени, которое может потребоваться для выполнения анализа.) Тот факт, что они являются акцепторами для CSG, интересен для теории парсинга, но не для практики парсинга.

Как и в случае с CFG, существуют разные классы CSG. Некоторые ограниченные подклассы CSG легче анализировать (например, CFG - это один подкласс), но я не думаю, что было проведено много исследований практического использования; на практике CSG сложно написать, и нет очевидного аналога дерева разбора, которое можно построить из деривации.

Для получения дополнительной информации вы можете начать с записи в Википедии о LBA и продолжить, следуя ее ссылкам. Удачи.

Answer 2

Nearley генератор синтаксический анализатор способен разобрать несколько простых контекстных моделей с помощью постпроцессоров.

Можно написать контекстно-зависимое правило, которое соответствует to be or not to be или to do or not to do, но нет to be or not to do:

# "_" is whitespace, "word" is a single word
example_rule -> "to" _ word _ "or" _ "not" _ "to" _ word {%
    function(d,l, reject) {
        if (d[2] !== d[10]) {
            return reject;
        } else {
            return {d.join(" ")};
        }
    }
%}