Язык Си в примерах/Простая грамматика: различия между версиями
Содержимое удалено Содержимое добавлено
Greck (обсуждение | вклад) мНет описания правки |
Greck (обсуждение | вклад) Нет описания правки |
||
Строка 2:
Грамматики (подмножества множества слов в некотором алфавите ) можно
описывать с помощью правил. Каждое правило состоит из левой и правой части, между которыми стоит
стрелка (<tt> -> </tt>).
Правило <tt>
* Примеры корректных слов: 0, 10, 110, 200, 2100, 2010, 1111111110.
Строка 20 ⟶ 21 :
int Read()
{
int head, i;
scanf("%d", &head); // Читаем первое число.
if(head < 0 || head > 3) { // Возвращаем код ошибки, если оно не из
return 1; // множества {0, 1, 2, 3}
}
for(i = 0; i < head ; i++) {
Строка 35 ⟶ 36 :
{
if(!Read()) {
int
if(
printf("
else
printf("correct\n"); } else {
printf("incorrect\n");
}
return 0;
}
Здесь представлен классический рекурсивный способ лексографического разбора.
Программный код можно максимально приблизить к самим правилам:
ReadS() {
scanf("%d", &n);
switch(c) {
'0': return 1;
'1': return ReadS();
'2': return (ReadS() && ReadS() );
'3': return (ReadS() && ReadS() && ReadS());
default: return 0;
}
}
== Задание ==
:'''Задача 1.''' Напишите программу, определяющую корректность слова, не используя идеи рекурсии и стека. Для этого обявите переменную <tt>n</tt>, равную количеству объектов <tt>S</tt>, которые осталось считать. Изначально <tt>n = 1</tt>.
:'''Задача 2.''' Напишите программу, которая определяет, является ли введённое слово выводимым из символа S.
S -> A | B
A -> '(' B* ')'
B -> '[' A* ']'
Вертикальная черта означает соединительный союз или
Здесь используется специальный символ '*'. Это указатель количества.
Запись <tt>B*</tt> означает любое количество слов типа <tt>B</tt> (слов, выводимых из символа <tt>B</tt>), либо пустое слово. Другими словами, * означает 0, 1, 2,... <math>\infty</math> раз.
Есть также специальные символы + и ?:
* <b>*</b> -- 0,1, ..., <math>\infty</math> раз.
* '''+''' -- 1,2, ..., <math>\infty</math> раз (то есть, любое число раз, но по крайней мере один раз).
* '''?''' -- 0 или 1 <math>\infty</math> раз (то есть либо есть, либо нет).
Примеры слов, выводимых из <tt>A</tt>:
(), ([]), ([][()()]), ([][][][])
Примеры слов, выводимых из <tt>B</tt>:
[], [()], [([])([])()], [([][][][])]
Подсказка: определите две функции ReadA и ReadB которые рекурсивно вызывают друг друга.
Код примерно должен быть таким:
ReadA() {
while(ReadA()) {};
return 1;
}
ReadB() {
while(ReadB()) {};
return 1;
}
ReadS() {
ReadA || ReadB;
if(getchar() != EOF)
printf ("Incorrect\n");
else
printf ("Correct\n");
}
| |||