Язык Си в примерах/Простая грамматика

Грамматики (подмножества множества слов в некотором алфавите ) можно описывать с помощью правил. Каждое правило состоит из левой и правой части, между которыми стоит стрелка ( -> ).

Данную стрелку можно интерпретировать как «представляет собой» или «состоит из». Например, правило

A -> B C D

можно прочитать как

«Слово типа A представляет собой слияние слова типа B, слова типа C и слова типа D.»

Но в теории формальных грамматик принята другая терминология:

«Из символа A можно вывести последовательность символов B, C и D.»

Расcмотрим три правила, в которых присутствует только один символ S (один нетерминальный символ), и три терминальных (то есть нераскладываемых, таких символов, из которых ничего нельзя вывести кроме их самих) символов '0', '1', '2', '3':

 S -> '0'
 S -> '1' S
 S -> '2' S S
 S -> '3' S S S 

Правило S -> '3' S S S , к примеру, означает, что если a, b и c являются корректными словами (словами, выводимыми из символа S), то и слово 3abc тоже является корректным.

• Примеры корректных слов: 0, 10, 110, 200, 2100, 2010, 1111111110.
• Примеры некорректных слов: 01, 00, 300, 3333, 11120.

Приведённая ниже программа на Си определяет корректность введённого слова.

 #include <stdio.h>
 #include <limits.h>
 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++) {
        if(Read()) {
            return 1;
        }
     }
     return 0;
 }
 int main()
 {
   if(!Read()) {  
      int n;
      if(scanf("%d", &n) != 0)
         printf("incorect\n");
      else
         printf("correct\n");
   } else {
      printf("incorrect\n");
   }
   return 0;   
 }

Здесь представлен классический рекурсивный способ лексографического разбора.

Программный код можно максимально приблизить к самим правилам:

  ReadS() {
      if( scanf("%d", &n) != 1 ) return 0;
      switch(c) {
        '0': return 1;
        '1': return ReadS();
        '2': return (ReadS() && ReadS() );
        '3': return (ReadS() && ReadS() && ReadS());
         default: return 0;
      }
  }

Задание

Задача 1. Напишите программу, определяющую корректность слова, не используя идеи рекурсии и стека. Для этого обявите переменную n, равную количеству объектов S, которые осталось считать. Изначально n = 1.

Задача 2. Напишите программу, которая определяет, является ли введённое слово выводимым из символа S.

 S ->  A | B
 A -> '(' B* ')'
 B -> '[' A* ']'

Вертикальная черта «|» означает соединительный союз «или».

Здесь используется специальный символ «*». Это указатель количества. Запись B* означает любое количество слов типа B (слов, выводимых из символа B), либо пустое слово. Другими словами, символ «*» означает 0, 1, 2,... $\mathrm{\infty }$ раз. Есть также специальные символы + и ?:

• * -- 0,1, ..., $\mathrm{\infty }$ раз.
• + -- 1,2, ..., $\mathrm{\infty }$ раз (то есть, любое число раз, но по крайней мере один раз).
• ? -- 0 или 1 раз (то есть либо есть, либо нет).

Примеры слов, выводимых из A:

  (), ([]), ([][()()]), ([][][][])  

Примеры слов, выводимых из B:

  [], [()], [([])([])()], [([][][][])]  

Подсказка: определите две функции ReadA и ReadB которые рекурсивно вызывают друг друга.

Код примерно должен быть таким:

 ReadChar(char x) {
    int c;
    if((c=getchar()) != x) {
        ungetc(c);
        return 0;
    } else {
        return 1;
    }
 }
 ReadA() {
     int c;
     if ( !ReadChar( '(' ) ) return 0;  // читаем открывающую скобку
     while(ReadB()) {};                 // читаем B*
     if ( !ReadChar( ')' ) ) return 0;  // читаем закрывающую скобку
     return 1;
 }
 ReadB() {
     ... // по аналогии с ReadA
 }
 ReadS() {
     ReadA || ReadB;
     if(getchar() != EOF) 
         printf ("Incorrect\n");
     else
         printf ("Correct\n");           
 }

Разбор языков (parsing), которые задаются простыми рекурсивными грамматиками, реализуют с помощью рекурсивных функций, которые возвращают 1 (успешно считано) или 0 (не считано).

Задача 4. Прочитайте учебный текст про формальные грамматики. Напишите грамматики следующих языков:

• язык записи действительных чисел в языке Си.
• язык записи email адресов.
• язык записи арифметических выражений над целыми числами со скобками и операциями + * - / .

Задача 5. Просмотрите формальное описание грамматики языка Си. Является ли условие выводимости из символа program необходимым для компиляции программы? Является ли это условие достаточным? Ответ обоснуйте.

Задача 6. Изучите задачу вычисления сопротивления по описанию параллельно-последовательной электрической схемы из сопротивлений — Язык Си в примерах/Задача «Расчёт сопротивления схемы»