Может кто-нибудь привести простой, но не игрушечный пример контекстно-зависимой грамматики?

Question

Может кто-нибудь привести простой, но не игрушечный пример контекстно-зависимой грамматики?

Я пытаюсь понять контекстно-зависимые грамматики, и я понимаю, почему такие языки, как

{ww | w это строка}
{aⁿ bⁿ cⁿ | a, b, c являются символами}

не являются контекстно-свободными, но я хотел бы знать, является ли язык, подобный нетипизированному лямбда-исчислению, контекстно-зависимым. Я хотел бы видеть пример простой, но не игрушечной (я рассматриваю выше игрушечные примеры), пример контекстно-зависимой грамматики, которая может, для некоторого производственного правила, например, сказать, есть ли некоторая строка символов в настоящее время находится в области видимости (например, при создании тела функции). Являются ли контекстно-зависимые грамматики достаточно мощными, чтобы сделать неопределенные / необъявленные / несвязанные переменные синтаксической (а не семантической) ошибкой?

6

grammar automata computation-theory language-theory context-sensitive-grammar

Источник

user1335290 31 дек '12 в 00:39

1 ответ

Решение

Другие вопросы по тегам grammar automata computation-theory language-theory context-sensitive-grammar

user1673391 31 дек '12 в 08:39 2012-12-31 08:39 · Accepted Answer · 2012-12-31 08:39

Да, контекстно-зависимые грамматики (CSG) достаточно мощны, чтобы проверять неопределенные / необъявленные / несвязанные переменные, но, к сожалению, мы не знаем какого-либо эффективного алгоритма для анализа строк CSG.

Настоящим примером контекстно-зависимого языка является язык программирования C. Такая функция, как объявление переменных сначала, а затем их использование, делает язык C контекстно-зависимым языком (CSL). (Я не знаю о нетипизированном лямбда-исчислении).

И потому что мы не знаем ни одного линейного алгоритма синтаксического анализа для CSL (или CSG). По этой причине при разработке компилятора мы используем CFG (и только его алгоритм синтаксического анализа) для проверки синтаксиса, поскольку мы знаем эффективные алгоритмы для синтаксического анализа CFG (если он находится в ограниченной форме). Компиляторы сначала анализируют контекстно-независимую функцию, а затем обрабатывают контекстно-зависимые функции проблемным способом (например, проверяют любую использованную переменную в таблице символов, если она определена. В противном случае она генерирует ошибку).

Также контекстно-зависимая грамматика используется в обработке естественного языка (NLP). И большинство естественных языков являются примерами контекстно-зависимых языков. (Я не уверен в санскрите).

Я попытаюсь объяснить это глупым, но простым примером (это просто идея, вы можете уточнить это):

NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>

Теперь, используя эту грамматику, мы можем генерировать некоторые правильные утверждения, но некоторые также ошибочны. Например,

SENTENCE --> <NOUN>   <TENSE>   <VERB>
             Grijesh    is       working       [Correct statement]

Но

             Grijesh    am       working       [wrong statement]

Причина: значение зависит от значения (например, I <TENSE> --> I am) и, следовательно, грамматика не дает правильных утверждений на английском языке.

На самом деле мы не можем написать контекстную грамматику для полного английского!

_{Вы могли заметить, что любой переводчик естественного языка или средство проверки грамматики работает неправильно (попробуйте использовать длинные операторы).} _{Потому что эта проблема подпадает под алгоритм контекстного анализа.}

СПРАВКА: Вы можете посмотреть лекции доктора Аруна Кумара. _{В какой-то лекции он объясняет, что именно вас интересует.}