Примеры неконтролируемого языка на языке C?

Каковы примеры неконтекстно-свободных языков в языке Си? Как существует следующий не-CFL язык C?

а) L1 = {wcw | w is {a, b} *}

б) L2 = {a ^ n b ^ m c ^ n d ^ m | н, м>= 1}

 Roy Dictus22 окт. 2012 г., 15:57
Isn»т C CFG ??
 akshaykumar622 окт. 2012 г., 16:05
C составляет 99% CFG, но я хочу пример из этого 1%, который не является CFG.

Ответы на вопрос(2)

Эти вещи неt не зависит от контекста в C:

foo * bar; // foo multiplied by bar or declaration of bar pointing to foo?
foo(*bar); // foo called with *bar as param or declaration of bar pointing to foo?
foo bar[2] // is bar an array of foo or a pointer to foo?
foo (bar baz) // is foo a function or a pointer to a function?
 akshaykumar622 окт. 2012 г., 16:18
Я имею в виду примеры, которые относятся к не-CFL L1 или L2 в C?
 akshaykumar622 окт. 2012 г., 16:15
Хорошо! Благодарю. Любой пример для данных языков? ?
 rici23 окт. 2012 г., 16:49
@AlexeyFrunze: грамматика не зависит от контекста, даже если она неоднозначна, а язык не зависит от контекста, если существует грамматика без контекста, которая выводит в точности набор всех строк в языке. Чувствительность контекста C демонстрируется не двусмысленностями, а непринятыми строками. Я пытаюсь объяснить это в своем ответе.
 Andy Hayden22 окт. 2012 г., 16:18
Арен»t эти примеры двусмысленностей, а не демонстрация языка не свободны от контекста?
 Alexey Frunze22 окт. 2012 г., 16:22
@hayden Это не такнеоднозначны в контексте в C. Они неоднозначны вне контекста. Итак, похоже, это демонстрирует, что C не является контекстно-свободным.
 Alexey Frunze22 окт. 2012 г., 16:20
@developer Можете ли вы привести более четкий пример того, что выищете?
 Alexey Frunze22 окт. 2012 г., 16:17
Каковы данные языки? Я думаю, что, возможно, неправильно понял вопрос. Вы можете это уточнить? И какое это имеет отношение к C?
 akshaykumar622 окт. 2012 г., 16:28
Я хочу выражения, которые принадлежат этим не-CFL языкам (L1 и L2). Один из примеров, который я думаю о языке L1: "а + = а» но я не уверен в этом. Нет идеи о L2.

поэтому яЯ читаю между строк, здесь. Тем не менее, этоОбычный домашний / учебный вопрос.

Различные неоднозначности [1] в грамматике C, как обычно представлены, не делаютязык без контекстно-свободной. (Действительно, они неt даже делает грамматику неконтекстно-свободной.) Общее правило "если это выглядит как декларация, этоs объявление независимо от других возможных разборов " может быть кодифицировано в очень сложной контекстно-свободной грамматике (хотяне на 100% очевидно, что это правда, так как CFG не закрыты на пересечении или разнице), но это 'Проще разобрать с более простым CFG и затем устранить неоднозначность в соответствии с правилом объявления.

Важным моментом в отношении C (и большинства языков программирования) является то, что синтаксис языка немного сложнее, чем BNF, используемый для пояснительных целей. Например, программа на C не является правильно сформированной, если переменная используется без определения. Тот'Синтаксическая ошибка, но этоне обнаружен парсером CFG. Грамматические произведения, необходимые для определения этих случаев, довольно сложны из-за сложного синтаксиса языка, но онимы сводимся к требованию, чтобы идентификаторы дважды появлялись в действующей программе. следовательноL1 = {wcw|w is {a,b}+} (Вотw это идентификатор, иc слишком сложно разобрать) На практике проверка этого требования обычно выполняется с помощью таблицы символов, и правила формального языка, хотя и точные, не записаны в логическом формализме. посколькуL1не является контекстно-свободным языком, формализм не может быть контекстно-свободным, но контекстно-зависимая грамматика может распознаватьL1, так что'не совсем невозможно. (См., Например,Алгол 68.)

Таблица символов также используется, чтобы решить, является ли конкретныйidentifier должен быть сокращен доtypedef-name [2]. Это необходимо для устранения ряда неясностей в грамматике. (Это также дополнительно ограничивает набор строк в языке, потому что в некоторых случаяхidentifier должен быть решен какtypedef-name для того, чтобы программа была действительной.)

Для другого типа чувствительности к контексту вызовы функций должны соответствовать объявлениям функций вчисло аргументов; такого рода требования моделируютсяL2 = {a^n b^m c^n d^m| n,m >=1} гдеa а такжеc представляют определение и использование некоторой функции, иb а такжеd представляют определение и использование другой функции. (Опять же, в очень упрощенной форме.)

Это второе требование, возможно, менее ясно синтаксическое требование. Другие языки (например, Python) допускают вызовы функций с любым количеством аргументов и обнаруживают совпадение количества аргументов / параметров как семантическую ошибку, обнаруженную только во время выполнения. Однако в случае C несоответствие явно является синтаксической ошибкой.

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

Примечание 1: Большинство из них на самом деле не являются двусмысленностями, потому что они зависят от того, какidentifier разрешается (typedef name, идентификатор функции, объявленная переменная, ...).

Примечание 2: дело не в том, чтоidentifier должен быть решен какtypedef-name если это случится один; это происходит только в тех местах, где сокращение возможно. Не является синтаксической ошибкой использование одного и того же идентификатора как для типа, так и для переменной, даже в одной и той же области видимости. (Это'не очень хорошая идея, но этоs действителен.) Следующий пример, адаптированный из примера в разделе 6.7.8 стандарта, показывает использованиеt как имя поля и определение типа:

typedef signed int t;
struct tag {
    unsigned t:4;  // field named 't' of type unsigned int
    const t:5;     // unnamed field of type 't' (signed int)
};
 rici23 окт. 2012 г., 16:46
@SteveJessop: яЯ бы пошел с этим. Не все ограничения вограничения» секции; например, 6.5.1 (2): "Идентификатор является первичным выражением, при условии, что он был объявлен как обозначающий объект (в этом случае это lvalue) или функцию (в этом случае это обозначение функции) " находится всемантика" раздел, хотя в сопроводительной записке 91 четко говорится, что "необъявленный идентификатор является нарушениемсинтаксис." Препроцессор вводит некоторые дополнительные сложности.
 Steve Jessop23 окт. 2012 г., 11:32
Поэтому было бы правильно сказать, что так называемая C-грамматика, формально представленная в стандарте, является CFG (поскольку все производства являются BNF без контекста), хотя и неоднозначной. Затем это'с "ограничения» разделы (возможно, плюс другие правила), которые используют английский для определения подмножества без CFG, которое является фактическим языком C?

Ваш ответ на вопрос